[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20080127062428.GA1534@openwall.com>
Date: Sun, 27 Jan 2008 09:24:28 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: optimization - reusing intermediate results (was: wordlist mode improvement maybe)
On Sat, Jan 26, 2008 at 08:41:55PM +0000, helleye wrote:
> also saw that some encryptions use update function and final function
> where update add some string and final make the final hash
This is a programming interface convention, which I think originates
from RSA's reference implementations of MD* hashes. It does not always
reflect the way the work is actually split between the "update" and the
"final" functions. When the total amount of data being processed is
small, which is typically the case when computing password hashes,
"update" may merely buffer the data and "final" may do the actual work.
Thus, the obvious optimization is to eliminate this programming
interface altogether, despite of it being a nice abstraction layer.
This is why you won't see it used anywhere in the official JtR code
(currently). You probably saw it in the patches.
> does des use it also ?
No, the DES code in JtR does not use this programming interface,
although generic crypto libraries may include other abstraction layers
for block ciphers such as DES as well.
As I have already explained, this has little to do with what actually
happens "under the hood".
> if so , can we save a progress of it lets say
> when 7 of 8 chars are already there then just update it with the final char
> to save time ? (and if yes does jtr already does it ?)
It's not as simple as that. For example, MD5 processes data in 64-byte
blocks (the last block is limited to 56 bytes of input data, though).
Thus, if raw MD5 is being used to hash passwords (to give the simplest
example), almost all passwords will fit in just one block. This means
that there's no progress to be saved after doing an "update" on, say,
just 7 characters of input - those characters are merely buffered for
further processing. For "passwords" of 57 characters or more, you may
in fact save and reuse the MD5 context (although not always between the
"update" and "final" - sometimes you'd have to do that from inside the
code that is usually found in "final").
What JtR actually does is save on key setup costs with DES-based hashes
when the new candidate password differs from a previous one by just a
few characters (in any positions). When JtR uses its bitslice
implementation of DES, which it does most of the time, it's differences
between the new candidate password and one that was in the same "bit
layer" that matter. Thus, a further optimization would be to adjust
higher-level code to reduce the average number of character differences
between such passwords rather than between adjacent passwords - but only
when bitslice DES is being used.
Since this is only about key setup "overhead" rather than about actual
DES encryptions, the overall performance improvement from this sort of
optimizations is not as large as you might expect. For example, with
traditional DES-based crypt(3) hashes, which do 25 DES encryptions per
hash computation, key setup might be responsible for around 10% of
overall processing time, so making it twice faster will only save you 5%
overall - and that's assuming that you're attacking a single salt. With
multiple salts, key setup is of even less importance.
With LM hashes, which are neither iterated nor salted, key setup is very
important, though. This is why you can actually notice a lot of
difference in performance at LM hashes depending on what candidate
passwords you supply and how they are ordered.
--
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15 fp: B3FB 63F4 D7A3 BCCC 6F6E FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments
--
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.
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.
