Rainbow Table

Question

Post reply

Rainbow Table

Viewing 10 posts - 16 through 24 (of 24 total)

You must be logged in to reply to this topic. Login to reply

OzYbOi d(-_-)b SSCarpal Tunnel Points: 4054 More actions · Answer 1

OzYbOi d(-_-)b

SSCarpal Tunnel

Points: 4054

January 16, 2012 at 10:29 am

#1434180

good question - as with many others, a subject I was not familiar with.

TomThomson SSC Guru Points: 104773 More actions · Answer 2

cengland0 (1/16/2012)

L' Eomot Inversé (1/15/2012)

Well, I managed to get this one wrong, but only because I guessed wrongly as to which of the incorrect options would count as "correct". It's a good question except that (a) the correct answer isn't offered as an option and (b)the "correct" answer is so utterly wrong as to amaze me. The wikipedia article referenced in the explanation makes the wrongness of the answer absolutely clear, so we have an swer/explanation which are apparently based on material that directly contradicts them.

I used to do ethical hacking and I used to call these dictionary attacks. It was quite easy because you already had your table of passwords and hashes. Then, you'd get your Unix/Linux user file (mirroring makes that more difficult now) and process those hashed passwords through your "dictionary" table and once you find a match, you will have your unencrypted password.

Some of the duplicates are being produced by two different passwords having the same hash value. That didn't matter when you're trying to sign in as one of the users. If their password was "abcdefg" and that produced a hash of 1kl5 and you encrypted a password of "12345678" and it produced the same hash of 1kl5, you could still log in as that user with the wrong password.

So, in short, I believe the answer and explanation is very correct. Perhaps the Wikipedia article made it appear more confusing than it really is.

I don't know when you did your ethical hashing, but the idea of complete lists of hash values became old hat back when people started using sensible length hashes instead of old-fashioned 16 bit CRCs for password checking - that was at least a couple of decades ago (longer than that for most people) - because the size of the required dictionary file was just too big. Even if I assume that the characters allowed in the text version of a password number only 64 (which hasn't been true in Europe for a very long time indeed, and maybe isn't true in the US either now) there are more than 2**80 passwords consisting of 10 symbols, so even a 32 bit CRC as the hash function entails more than 2**35 bytes of storage for such a dictionary file. When you consider 32Gbytes of storage was rather large back in 1990 it becomes quite clear that although dictionaries that large could exist they would have been extremely rare and very expensive. Later on dictionaries big enough couldn't exist, because everyone was using 64 bit hashes (requiring more than 2**71 bytes of store for a complete dictionary, that's a couple of zettabytes) or 128 bits, or 160 bits (and more recently 256 bits and 512 bits) and the amounts of storage needed became unachievable, even given todays storage methods. If your dictionary attack was for a restricted dictionary with words like "Minnie", "Mickey", "Spock", "Blake", "Bilbo" and so on, it was feasible to do a dictionary - but you would have to be very lucky get a password for anyone who had a clue (many didn't, of course, as you probably observed in the course of your ethical hacking).

But noticing the non-feasibility of complete dictionaries was straightforward, so people who wanted to attack passwords noticed it: attack methods were developed that reduced the size of file required; first hash-chain files which stored beginning and end of chain; and, when that proved inadequate, similar files using modified hash-chains (separate reductions at each step). Maybe before then dictionaries had been called rainbow files; but since then the term has meant a file (used in a more modern, more efficient sort of attack) which stores only chain ends for varied reduction hash chains, and that's a very long time ago. Yes, there may still be people who still use the old meaning; but maybe there are still people who use Oracle Release 2 as well (that died a lot less than twice as long ago), and I see neither why I should conform with one outdated bunch when no-one expects me to conform with the other nor why you consider it sensible for QotD to use technical terms in archaic senses.

With hash chains the point you make about being able to use any password that hashes right is still valid; but if two length N chains with a single reduction collide they cover on average only 3N/2 hash values between them, instead of 2N if they don't collide. That's where the storage inefficiency comes from. With different reductions at each step, this is a lot smaller so it's possible to cover a bigger subset of the possible passwords with a given sized table; of course the computational complexity of building the table goes up (for a given table size) and so does the computational complexity of using it.

And that - the computational complexity of run-time use combined with the necessity to reduce storage space by covering only chain ends is where we finally killed rainbow tables stone dead for anything but finding the "Mickey Mouse" passwords even with massive supercomputer support (at least until someone gets quantum computers on the job); several of us worked on slow hashes with variable complexity in the early 90s, using cryptographically useful PRNGs to generate strings from password plus seed that could then be fed into hash functions, but that was not the right approach (I was still doing it that way - the wrong way - in 2000 because I hadn't kept in touch with research - changes of employment had led to less research-oriented responsibilities; but the wrong way was probably good enough then, as we allowed long pass phrases with no restriction on character set and generated a 160 bit hash); later someone came up with using hash chaining directly to increase complexity, initially using MD5; and later again someone else hit on the idea of using something a bit more inheritly complex than MD5 (initially one of Schneier's encryption protocols, which happens to have complex setup so is very appropriate here, later yet more enhancements/variants).

Tom

spaghettidba SSC Guru Points: 105712 More actions · Answer 3

spaghettidba

SSC Guru

Points: 105712

January 17, 2012 at 3:34 am

#1434478

cengland0 (1/16/2012)

Perhaps the Wikipedia article made it appear more confusing than it really is.

I agree. I got it wrong BTW...

-- Gianluca Sartori

cengland0 SSCertifiable Points: 6102 More actions · Answer 4

Gianluca Sartori (1/17/2012)

cengland0 (1/16/2012)

Perhaps the Wikipedia article made it appear more confusing than it really is.

I agree. I got it wrong BTW...

At the time, we didn't have a name for those tables but used them anyway -- now I know they are called Rainbow tables. Don't know why people are saying it took too much space when it didn't. This was a dictionary attack -- not a brute force attack. There is a huge difference.

First, an assumption was made that some people in an organization will use a very simple password. For example, their password might be "pyramid". In that case, this is a word in any standard dictionary. So, once you get the user list with the password hashes, you just process it with the small dictionary. You wouldn't catch any passwords that are like "H3ll0 W@rld" using a dictionary attack and it was never expected either.

At this early time, corporations didn't require their employees to use a minimum password strength of one uppercase letter, one number, one lower case letter, a symbol, and at least 8 characters long. It was more simple such as your password cannot be the same as your username and must be at least 6 characters. So people tended to use names of pets, spouses, girfriends, etc. Those were all in the dictionary of common password terms. I have even seen passwords as easy as 123456.

Since your password had to be at least 6 characters in most cases, you could reduce your dictionary size significantly by removing words such as a, an, if, or, and, we, because they are too small and you wouldn't be able to use them as passwords anyway.

Note that this method does not retrieve every user's password. You're scanning the entire user base for a match in your hashed column and the more people in the user base, the more likely you will find a match. I've done this scan many times and have found hundreds of matches.