Message-ID: <20040817081130.4202.qmail@www.securityfocus.com>
Date: 17 Aug 2004 08:11:30 -0000
From: "Jérôme" ATHIAS <jerome.athias@...amail.com>
To: bugtraq@...urityfocus.com
Subject: Breaking windows LM hashes using the Time-Memory Trade-Off :
    Optimization & new tool




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

Powered by blists - more mailing lists