Re: Rainbow Tables and Authentication Alternatives

[Alan Amesbury <amesbury () OITSEC UMN EDU>]

Anthony Maszeroski wrote:

> There are online rainbow tables/crackers for several other hashes,
> including PIX, MD2, MD4, MD5, NTLM, MySQL, RIPEMD160, SHA1, etc. Many of
> them support greater than 8 character passwords. Check out these sites
> for more information :
>
> http://md5.rednoize.com/
> http://gdataonline.com/
> http://www.milw0rm.com/md5/
> http://passcracking.ru/
> http://passcrack.spb.ru/
> http://www.rainbowcrack-online.com/
> http://www.antsight.com/zsl/rainbowcrack/
> http://rainbowcrack.com/
> http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/
> http://www.md5lookup.com/?category=main&page=search
> http://md5.crysm.net/

This is where hashing algorithms that use salts come in very handy.  The
ones used with WinDOS (to the best of my knowledge) do NOT, i.e., for
every possible password there is (assuming a hashing algorithm with no
collisions) exactly one possible hash.  However, for algorithms that use
a salt (a random value used to perturb the hashing algorithm), the same
input value can have multiple output values.  So, using the traditional
Unix crypt() function, the input "password" can yield the hash values
"OEkufURo0wtpk" and "DJaFvL4Hpt6P2" as outputs.

When attacking an unsalted algorithm (like those used with WinDOS),
Rainbow tables work pretty well.  An attacker only has to precompute the
hash value.  For a salted algorithm, the attacker has to precompute the
hash value *FOR EACH* possible salt.  crypt() has something like 4K
possible salts, so in that respect it's somewhat weak... but it still
takes 4K times more possible computations.  Newer hashing algorithms
(like the salted MD5 hashing algorithm used for the past several years
in some Unix and Unix-like OSes) use salts around eight characters in
length.  Assuming they use the same sized character set for salts as
traditional crypt(), that gives them something like 2E14 possible salts,
which somewhat increases the amount of space needed to store precomputed
tables.

There's other concerns, though, when talking about password hashes.  In
WinDOS, I think the hash can actually be used as a password equivalent,
or so I've heard from some Samba types.  Of course, if the Bad Guy[tm]
has gotten to the point where they can actually read your password
hashes in the first place, the game's mostly over anyway.


--
Alan Amesbury
University of Minnesota