a companion discussion area for blog.codinghorror.com

Rainbow Hash Cracking


#121

Noted security researcher MC Frontalot claims that one simply can’t hide secrets from the future with math, although you can try. Maybe he’s right.

One trick for making up long, complicated, but easy-to-remember passwords is to use a (fake) email address. This gives a long password a familiar mnemonic structure which can lend itself very naturally to a larger mnemonic scheme. The password even includes a few non-alphanumerics (@ and .) pretty much for free, as far as human memory consumption goes.

"WinstonSmith@Room101.com," for example, gets top scores on the GeekWisdom and Microsoft password testers. It’s much too long for currently-practical rainbow tables to work on. But its pretty easy to remember, and its a lot easier to type than the line-noise a random password generator puts out.


#122

Am I the only poster wondering why you have a Hello Kitty Rainbow background?


#123

@sysadminwithquestion the opcrack are not for brute forcing password on-site, it would obviously take a long time like you said. it is given if you can obtain the password hash from somewhere else, say database or a file on OS, copy them and run opcrack over the password hash.


#124

Salting the hash serves two purposes. First two people on the same machine shouldn’t have the same has as the other even if they have the same password. Even though in Unix the hashed password was public, even though, in Unix or NT it no longer is, this argument better still hold.

Secondly, these table attacks become much harder. The factor by which you make things harder is determined by the effective number of bits you add. The salt needs to be recoverable at the time of password verification. So you can just as well store it with the password hash. Use a random number. Those seventies Unix-designers weren’t all that stupid.

It’s just that the number of bits required against an attack is now slightly larger. On the other hand, about 10 or 12 bits, making a hash table attack about 1000 times more memoryconsuming, will STILL work in the examples in the article. Who has 1G RAM? Most of you do. Who has 8G RAM? Some of you do. Who has 1T RAM? None. 8T? nobody.


#125

So what I’ve gotten out of this is always salt your hash with base64 encoded hello kitty jpgs.

And lolcats will do in a pinch.


#126

I tend to be very paranoid, and use an extremely long server salt (which also includes the hash of the password, and the hash of the reverse of the password) AND a per-user salt which is also added into the mix (probably forwards and backwards at some point as well) - you end up with a very long string (200+ characters) which you then hash. The server salt is kept secret, as is the hashing algorithm and how the salt and password are combined (and the password is usually introduced multiple times, forwards, backwards, any other property of it that doesn’t change such as length), and the user salts are randomly generated upon registration, stored in the user table, and also used in this mix.

Hopefully… it’s pretty damn secure against this kind of attack!


#127

What about creating collisions! Rainbow tables can’t work in a system with lots of collisions (not a good hash algorithm).


#128

There are a lot of great ideas here, I typically take the unique identifier for the row and the username for the salt and use bit shifting for keep a hacker from guessing my steps, this gives you a pretty decent dynamic hash that you can recreate easily.


#129

As a previous engineer for Myspace.com I can tell you that even that large companies store passwords in clear-text. I was shocked when I walked in the door to find 200 million records with email addresses and clear text passwords. My words then made no difference to the ass-clowns that make the decisions there, maybe my words here will get the no-talent architects and managers to change the policy to something a little more secure.


#130

Another cheap way (in addition to using a salt) to prevent this is hash twice i.e. hash the hash - so long as the operation is reproducible, no problem.


#131

Bruce Schneier’s book ‘Practical Cryptography’ goes into a lot of this, and it should be standard reading for anyone dealing with passwords. It’s fascinating, quite apart from anything else, and goes into most of these issues - I mean, they’ve been known for a while. Still, it would make my top 5 computer books.

As a rule, though, Thomas Ptacek’s advice is right on - use the standard method that some guys who’re smarter than you designed, and other guys who’re smarter than you checked. Don’t invent your own.

http://www.amazon.co.uk/Practical-Cryptography-Niels-Ferguson/dp/0471223573/ref=pd_bbs_sr_4/202-7708932-4694202?ie=UTF8s=booksqid=1190040157sr=8-4


#132

This was interesting in the 90’s.


#133

The comments here are interesting, but only in the following way: They demonstrate how difficult it is to get people to understand security technology and application, even supposedly “smart” computer users responsible for developing software that implements security policy.


#134

Well, 160seconds? My free (as in free beer) program did it in about one second.

Video Download:
http://timtux.net/9-jkain-the-md5-cracker

Video:
http://www.youtube.com/watch?v=jg3cu-l8Hv4


#135

An example of one decent way to do it:

$hashed_password = sha1( sha1($userid . $salt) . sha1($password) );

Substitute your favorite hash function(s) for sha1.

For those who don’t get this, . is the concatenation operator in Perl.

And of course as others have pointed out, you never store the salt anywhere near the database.

Another way to do it:

$timestamp = time;
$hashed_password = sha1( sha1($userid . $salt) . sha1($password) . sha1($timestamp) );

Then store the value of $timestamp in the database along with $hashed_password. No need to update it; it’s just used as one more semi-random salt. This prevents anyone from being able to build a custom rainbow table that covers your entire user base, not that they would be likely to do that.


#136

Why isn’t there a website that contains a couple terabytes of rainbow tables to which you can just submit a hash to for either NT-style passwords or *nix-style passwords? If you could charge an access fee, you could probably make a bundle.


#137

Actually, salt is trivial to circumvent anyway, although it is true that it makes rainbow tables bigger (you’d have to produce every combination for a given salt… not a big deal with a 12 bit salt, though, as that’s only about 4096 as a multiplicative). From an algorithms standpoint, as well, salt is ineffective as it is a constant (the 2^bits_in_salt) and so can be removed, yielding the same O for the time and space. From a real world sense, too, though it is useless against Rainbow tables unless you start making it 32-bits.
Salt is mostly used for two reasons: the *NIX PRNG is not very random and favors lower-order bits; so that two users with the same password have less of a likelihood (not a guarantee) of having the same hash. Anyway… enjoy your salt, but remember, too much of it in your diet can be bad for you :wink:


#138

Ok, what if you have an sha1 hash and you know the salt is “1234”, how would you go about cracking it?

Do you just use rainbow tables to crack the hash and then pick out the “1” “2” “3” and “4”?

That seems silly because most people will make a password that is a word or concept, like “purpletoy”

It would be very simple to recognize “purpletoy” in “pur2plet43oy1”.

Can someone explain this to me? Do I have it wrong?


#139

An interesting tool has come out to address the salted SHA hash techniques used in LDAP. It addresses some of the issues discussed here and those of you truly interested in this subject should check it out. It’s on sourceforge - http://sourceforge.net/projects/ssha-attack


#140

i like ophcrack because it doesnt do anything noticable on the computer, such as save something on it or something. but i also like Windows Key because it easily can reset ANY windows password, alphanumeric or anything, instantly! you put it onto boot up disk, put it in, wait for it to load (usually 30 seconds to 60 seconds) and you can select an account to erase the password to instantly.

there are many torrents for this program if you dont want to pay the 300$