|
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.