Breaking windows LM hashes using the Time-Memory Trade-Off : Optimization & new tool

["Jérôme" ATHIAS <jerome.athias () caramail com>]

Hi,

some of guys here may have seen multiple articles and links about the "new" way to break windows' LM hashes using the 
Time-Memory Trade-Off technique described by Philippe Oechslin. Remember the RainbowCrack tool 
(http://www.antsight.com/zsl/rainbowcrack/)...

I've seen many sites which propose to break Window$ LM hashes online (for free or by buying rainbow tables).

P. Oechslin publish now his own tool (ophcrack) which is very more optimized.

As the new vector of optimization is described in a French paper, this is my fast translation in english.

Find the original references (papers & tool) here : 
http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/


--START OF TRANSLATION--
The Time-Memory Trade-Off technique and its use to break WindowsÂ’ passwords


Optimizations

The real performances of a cracker based on a time-memory trade-off finally depend of the speed of the hashing 
operations and of the number of chains that we are able to write in the available memory.

DES efficacity: For the hash calculation, we just have to find a good implementation of DES, for example the one which 
is present in the libssl library. Our use of DES has the particularity that the chiffer key change with all new chiffer 
operation. By using a bitslice implementation of DES, we probably could improve the performances. This type of 
implementation runs by example 32 DES in parallel using the 32 bits words of the processor to stock a bit of 32 
different DES. The DES operations which are made on bites could so be applicated to 32 calculs in one single operation 
of 32 bits. This method can also be extended to 64 bits with a 64 bitsÂ’ processors or 64 bitsÂ’ operations of 32 bits 
processors (I.E. MMX on Pentium processor). A bitslice implementation is by example used by the brute force passwords 
cracker John the Ripper[2].

Efficacity of the storage: The optimisation of the storage is more important than the DES optimisation due to the fact 
that the cracking time decrease with the square of stocked chains number. An ingenuous method is to store, for every 
chain, the 7 first bytes corresponding to the password of the start of the chain, and the 7 bytes corresponding to the 
end. ItÂ’s that it was done in the rainbowcrack tool. Note that, to facilitate the chains alignment, this tool use 16 
bytes by chain.

Binarization: The first point to note that we have to do is that there are only 236.23 alphanumeric passwords from 1 to 
7 characters. So, we did not have to use more than 37 bits to save a password. We just have to define a representation 
that we call binary representation, which assigns to every password a number between 0 and 236.23. A simple method is 
to consider the alphanumerical passwords as numbers in 37 base made of the 36 alphanumerical characters and an empty 
character for the short passwords. In binary representation, a chain can be saved with 74 bits, which is 1.5 times 
lesser than the 14 bytes proposed before. The cracking time are so reduce by a factor of 2.3 (1.52). Note that the 
start of chains that we have to save are passwords that we have arbitrary chosen during the creation of the tables. If 
we need m0 starts of chains to generate the tables, we will so choose the passwords which have the binary 
representation from 0 to m0-1. We so need only log2(m0) bits 
 to save the starts of chains. This way easily permits to save a start of alphanumerical chain in a 32 bits word.

Indexing the end of chains: The end of chains could take any value in the 236.23 possibilities. However these values 
will be sorted in croissant order. The following values have so common prefixes. At this point we could donÂ’t save 
these prefixes, and create an index table which indicates from which position we find a given prefix. A simple example 
is to create 36 files each corresponding to the first character of the ends of chains and to save the chains in the 
corresponding files. ItÂ’s so now unnecessary to save the first character of the end of the chains because itÂ’s the same 
for all chains saved in a file. It appears that passwords of 6 alphanumerical characters can be represented in binary 
style with 32 bits, which so permit to save the ends of chains in an integer of 32 bits. With what we said before about 
the starts of chains, we can so save a chain in 8 bytes, which reduce the cracking time by a factor of 3 in regard of 
14 bytes chains, or even a factor of 4 in regar
 d of 16 bytes chains like in rainbowcrack. This is the solution that we have implemented in the demonstration that we 
had made online during the 2003 summer [4]. In less of 1 Go, we had so could save 115 millions of chains (5 tables with 
23.8 millions of chains).
        The use of longer prefixes permits to grow up again the gain resulting of the indexation. For every 
supplementary bit that we consider in the prefix, thereÂ’s one bit less to save for every chain, but two more indexes to 
generate. In the first case interested us, the optimal solution is around 20 bits of prefix and 16 bits saved by chain. 
The storage of the index itself use less than 10% of the memory needed to save one table. We finally can save a chain 
of 6 bytes, which allows, with the same quantity of memory, to break the passwords 5.4 times faster than with a 
representation on 14 bytes.

Conclusions

The Time-Memory Trade-Offs permits to obtain exceptional results to break Windows passwords. ItÂ’s due to different 
reasons. First, the hashes of Windows systems (LM hash and NT hash) could be calculated in advance. For what we know, 
Windows is the only actual operating system where itÂ’s possible. In all variants of Unix, by example, an aleatory value 
(the sel) is added during the hashÂ’s computation. The second reason which makes ideal the use of time-memory trade-off 
to break passwords is that itÂ’s a problem with limited complexity. Effectively, the passwords which are potentially 
chosen by users represent only 256 possible keys for DES. If we have to break a system which uses DES with arbitrary 
keys, we maybe could break a key in some hours, but it would need years to precompute the tables!
        Other than the windows passwords, we could not find any system which donÂ’t use an aleatory value (sel, 
initialisation vector) and which are of a reasonable small complexity. We have successfully apply our method to break 
the LM hash of alphanumerical passwords (N = 236) and passwords made of numbers, characters and 16 special characters 
(N = 240). The only parade proposed by Microsoft against these type of attacks is to deactivate the LM hash generation. 
This could be only a momentary solution. By optimising quite again more the implementation and by taking part of more 
recent machinesÂ’ performance, it become possible to break directly NT hashes because they donÂ’t contain sel no more. 
There is by example less than 246 alphanumerical passwords with mixed lower/upper case. As the Time-Memory Trade-Offs 
benefit both of the MooreÂ’s law (by the growing of the available memory and of the processorsÂ’ speed), we could hope 
that Microsoft donÂ’t take too much time to propose a new typ
 e of hashes to preserve the security of the operating systemsÂ’ passwords.

--END OF TRANSLATION--

Note that according to both P. Oechslin & Zhu Shuanglei , the actual tables you could buy online are NOT OPTIMIZED in 
any way.

PS: i'm precomputing tables able to break a very large amount of passwords using a large charset since 6-7 months, 
using quite more optimized parameters, these represent about 10Go of data that i could actually not offer online. 
Please contact me if you could provide fast mirrors. Thanks.

Best regards,
Jérôme ATHIAS


(Poor english... i know, but think about the poor french reading english...)