|
Message-ID: <20110816170100.GA26144@openwall.com> Date: Tue, 16 Aug 2011 21:01:00 +0400 From: Solar Designer <solar@...nwall.com> To: john-users@...ts.openwall.com Subject: Re: Tripcodes, take 2 On Fri, Aug 12, 2011 at 05:26:36PM -0700, Corbin Simpson wrote: > As a trip, the plaintext looks like "corbin#simpson" and encrypts to > "corbin!Rk7VUsDT2U". I felt that it'd be easier for me to respond with code, so I just uploaded john-1.7.8-trip-1.diff to the wiki: http://openwall.info/wiki/john/patches This is a working, albeit slow tripcode cracker. As currently implemented, it uses the non-bitslice DES implementation, and moreover it does not group candidate passwords by crypt(3) salts. So it is roughly 10 times slower than it could be. The password file should contain lines like: corbin:Rk7VUsDT2U name:3GqYIJ3Obs > thought was to grab the salt from the inputted plaintext, and use that, This is what my PoC implementation does. > for each round. But then I got very confused, and after reading > some papers, I think I missed something fundamental: John runs > multiple DES rounds in parallel, doesn't it? You must be referring to multiple DES encryptions, and even to multiple DES-based crypt(3) hash computations. If so, yes - this is what it does with the bitslice implementation of DES (not used in my PoC patch). DES "rounds" are a different things - they're part of DES. > Single key, multiple plaintexts? It depends on what you mean by "key" and "plaintext" here. Perhaps you're confused as to how crypt(3) works. Anyway, with the bitslice DES implementation in JtR, the crypt(3) salt is shared for all candidate passwords being tested in parallel, but the candidate passwords themselves are different. > If that's the case, then the salt is set once and then never touched. It is set for each group of candidate passwords to test. The size of such groups should be at least the same as the machine's SIMD vector width in bits - e.g., 128 for x86 with SSE2. To apply this to tripcodes, yet not impose restrictions on candidate passwords being tried, you'd need to buffer large numbers of candidate passwords (perhaps thousands) and identify sufficiently large groups among those that share the same salt. Process those. For non-full groups, you may incur some performance penalty either by using the bitslice implementation anyway or by falling back to non-bitslice if the number is very small compared to the machine's SIMD vector width (e.g., fewer than 12 on a 128-bit machine like above). > I can't find any papers on it; how exactly does DES salting work? This is explained, for example, in the Menezes et al. book: http://www.cacr.math.uwaterloo.ca/hac/ > Does it alter anything besides key schedule? It doesn't alter the key schedule. It alters the expansion permutation. > Is it expensive enough to > warrant a specialized plaintext traversal instead of swapping the salt > for each key? Maybe. The cost of salt setup may be on the order of 10% of the total cost of computing a DES-based crypt(3) hash, although this varies greatly between different kinds of implementations. What's more important, for a typical bitslice implementation you can't "swap the salt for each key" even if you wanted to. > Maybe this is a guess out in left field, but is it possible to > sidestep the format subsystem? What for? Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.