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