
Date: Sat, 9 Jun 2007 05:13:44 +0400 From: Solar Designer <solar@...nwall.com> To: johnusers@...ts.openwall.com Subject: Re: LM/NTLMv1 challenge/response cracking On Fri, Jun 08, 2007 at 11:25:44AM 0500, jmk wrote: > I've made the BENCHMARK_LENGTH and mdfour() modifications to the 1.7.0.2 > version of the patch. I've also added a few notes regarding the > challenge/response file format and the gathering of such pairs. Let me > know if you had something else in mind. What you did is perfect. Thank you! > http://www.foofus.net/jmk/tools/jtr/john1.7.0.2netlmnetntlmjmk3.diff This is now in contrib/ > http://www.foofus.net/jmk/tools/jtr/john1.7.2all6netlmnetntlmjmk1.diff I've merged this one into all7, which is now also in contrib/ > With respect to the Rainbow Tables, I'm not really sure how much benefit > there is to using this "half" method rather than just computing the full > response tables. I think that the benefit is huge for long passwords. The time to compute the tables and their size are reduced a lot  or the number of recognized passwords is increased a lot (considering that you do not stop at just the half, but figure out the rest of characters). > IIRC, the half method only generates 8 bytes of the 24 > byte LM response. This reduces the number of DES encryptions necessary > during table computation and maybe the final table size. More importantly, it lets first halves to be cracked separately, just like JtR does for regular LM hashes. This reduces the total keyspace for long passwords by many orders of magnitude. > However, the > DES encryption to generate the first 8 bytes of the response uses only 7 > of the 8 bytes of the first half of the LM hash. Correct. > I would think that if > we ignore that final byte that it would leave (2^8) possible passwords > which could match those first 7 bytes. That's flawed logic. The following analysis is based on your netlm_crypt_all(), assuming that it does indeed represent LM response computation correctly: First, recall that each LM hash half is a function of just a 56bit key. This means that there are at most 2**56 different LM hash half values, even though they're 64bit. If we take just first 7 of the 8 bytes of LM hash first halves, the number of different values of such 7byte sequences will be a bit less, but likely still quite close to 2**56. Assuming that DES is perfect, that number should be close to (2**56 * (11/e)), which is a bit more than 2**55. Then we use this notexactlyperfect DES key to encrypt our fixed challenge. The result is a 64bit block that once again can take fewer different values than the number of different keys passed to DES is. Once again, assuming that DES is perfect and that I did my math correctly, this further reduction is around 0.2%. This leaves us with a number that is still above 2**55. Now it makes sense to compare this number against two things: 1. The number of possible input passwords for the first half, which is almost exactly 2**56 (I wrote "almost" because of potential issues with NUL termination of C strings and other such restrictions). Yes, it means that there have to be some colliding input passwords, despite of the hash space being wider (64bit). Chances are that many values of the first response block correspond to their unique 7character halves on input, whereas many others correspond to several input halves. On average, I'd expect the number of different 7character halves on input per response block value to be slightly higher than 1.585 (under assumptions already mentioned). 2. The number of candidate passwords actually tried, possibly during generation of rainbow tables. This number is 69**7, which is almost 10,000 times smaller than 2**56. This gives us chances for hitting a collision at roughly 0.0052% for any given first response block value (under assumptions already mentioned). In other words, you may expect one first block collision per roughly 19,300 responses. Over 99% of those collisions are likely to be "erroneous", to be rejected later (by making use of the second response block). One in roughly 256 collisions found in this way should be real (two different passwords work). Does this agree with your practical results? > Maybe because of the other LM > limitations (uppercasing, character space, etc.) this number is > drastically smaller... Correct, but it's more like a reduction from 1.585 to 1.000051.  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, email johnusersunsubscribe@...ts.openwall.com and reply to the automated confirmation request that will be sent to you.
Powered by blists  more mailing lists