[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
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.
