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

["Jérôme" ATHIAS <jerome.athias@xxxxxxxxxxxx>]

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