[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20070609011344.GA9838@openwall.com>
Date: Sat, 9 Jun 2007 05:13:44 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...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/john-1.7.0.2-netlm-netntlm-jmk-3.diff
This is now in contrib/
> http://www.foofus.net/jmk/tools/jtr/john-1.7.2-all-6-netlm-netntlm-jmk-1.diff
I've merged this one into -all-7, 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 56-bit key.
This means that there are at most 2**56 different LM hash half values,
even though they're 64-bit. If we take just first 7 of the 8 bytes of
LM hash first halves, the number of different values of such 7-byte
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 * (1-1/e)), which is a bit more than 2**55.
Then we use this not-exactly-perfect DES key to encrypt our fixed
challenge. The result is a 64-bit 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 (64-bit). Chances are that many values of
the first response block correspond to their unique 7-character halves
on input, whereas many others correspond to several input halves. On
average, I'd expect the number of different 7-character 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 (upper-casing, 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, 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.
