Bob outsmarts Alice's one way function

http://blog.jgc.org/2013/04/bob-outsmarts-alices-one-way-function.html

by jgrahamc • 13 years ago

81 34 13 years ago

blog.jgc.org

rlpb• 13 years ago

"In the real, mathematical world of one way functions Bob's reverse dictionary is called a 'rainbow table'..."

No; it's just a reverse lookup table. A "rainbow table" is a specific space optimization on top of a reverse lookup table. See the Wikipedia article you linked to:

"To address this issue of scale, reverse lookup tables were generated that stored only a smaller selection of hashes that when reversed could generate long chains of passwords. Although the reverse lookup of a hash in a chained table takes more computational time, the lookup table itself can be much smaller, so hashes of longer passwords can be stored. Rainbow tables are a refinement of this chaining technique and provide a solution to a problem called chain collisions."

jgrahamc5• 13 years ago

Yes, that was sloppy of me. I will correct.

withoutthis• 13 years ago

Link before edit: http://archive.is/3i48g

lucb1e2• 13 years ago

I'm not sure if I'd call this brute force attack "outsmarting", but I see the point. Good way to explain how reverse lookup tables work.

dkwak• 13 years ago

I think a more salient point than "Bob only has to do the work once" is "Bob has done the work ahead of time", no? In fact, even in the long run, Bob is doing a lot more work than necessary (computing inverse one-way functions for all/most possible inputs). It's just that he's preemptively computing them.

Retric• 13 years ago

The point is he wants to look-up more than one example because the crossword contains several words. Going though the full dictionary N times is harder even if on average he only needed to try half of it than doing it once.

drostie3• 13 years ago

In fact I think this would be more informative as a description of rainbow tables, so here goes:

Okay, so Bob in principle can write down a lookup table, but there's a problem -- that lookup table is going to be as long as the dictionary! What if he has to take it somewhere, or if he wants to make a copy for someone? That's serious work each time. We'd like to take the 100,000 words in the dictionary and convert them to only, say, 1,000 words.

Fortunately for Bob, and unfortunately for Alice, one-way functions come with a really simple compression method, where you can reduce the look up table as much as you want. This will make extracting the actual word slower, but you don't have to store a huge book anywhere.

Here is how it works. We work with 'chains' of one-way computations. See, our one-way function maps ORNATE → CEASE. Now we 'chain' the function by looking up CEASE and we find that it maps CEASE → SNIDE. We can "chain" it again to find SNIDE → JOYRIDE.

After a hundred of these chained together, we find that ORNATE ⇒ HOMOPHONE. In our lookup table we store the entry 'homophone: chain starts with ornate.' And I claim that now the lookup table can be about a hundred times smaller. Why? Because CEASE and SNIDE now do not need to start chains of their own! They are covered by the chain which starts with ORNATE. These chain tables are called "rainbow tables."

It might help to see how we use the rainbow table to look up some word near the end of this chain. Let's say that Alice has the word VEGAN and calculates that VEGAN → ORATION, so she sends us ORATION. Bob can't easily reverse this, but he can do the one-way function to ORATION and find some other word, ORATION → PERSECUTOR. But Bob can't find that in our rainbow table! So he does the one-way function again, PERSECUTOR → PAY. He can't find that either! So he does the one-way function again, PAY → CREATIVE. Nope, still no help! But then, CREATIVE → HOMOPHONE, and we find in our rainbow table that yes, we know how to make HOMOPHONE, because the rainbow table, remember, stored the fact that HOMOPHONE ⇐ ORNATE.

Now we use the one-way function again, starting with ORNATE → CEASE → SNIDE → ... → VEGAN → ORATION. Hey look, we found ourself back at ORATION, but now we know a word (VEGAN) which maps to ORATION! It's a long process of about 100 queries of the one-way function, but it's not so long -- because remember, the one-way function was fast.

There is a one-way function called SHA1 sometimes used to protect passwords. Today you can download a big file -- 86 GB -- which is just a rainbow table for passwords hashed with it. This rainbow table covers all passwords from 1 to 7 characters -- any combination of upper- or lower-case letters, numbers, spaces, special symbols, anything. That's about 95^7 = 70 trillion passwords! But it doesn't take ~70 trillion bytes, it only takes ~70 billion bytes, because it's been compressed by a factor of 1000 this way.

There's also a lookup table for 1-10 character passwords which are made of lowercase letters and numbers only, so about 36^10 = 3.6 quadrillion passwords. The file size is 588 GB, it's been compressed by a factor of 5,000 to make it possible to store on a modern hard drive. So if your password is all lower-case letters and numbers, it had better be a very long password, at least 12 characters long.

jgrahamc5• 13 years ago

A very enjoyable explanation. That was a little outside the scope of what I was trying to explain, but would make a good follow up. I'll post a link to your comment.

jonahx• 13 years ago

This is the best explanation of rainbow tables I've read. Thanks!

cs702• 13 years ago

drostie: this is the most accessible plain-English explanation of rainbow tables I've ever seen, and it's short to boot. From now on, whenever anyone asks me how stolen lists of hashed passwords get hacked, I will point them to your comment. Thank you.

aidenn0• 13 years ago

Of course a lot of hashed passwords have been hacked not because of rainbow tables, but by brute force because the site used a single round of a fast hash function.

They think they are good with a 4-byte salt and one round of sha-1, since that is effectively immune to rainbow-table attacks, but its' not immune to "I have a massively powerful processor in my computer called a 'video card'"

danielweber• 13 years ago

It's good. I wrote my own rainbow table code several years ago, and I had to read and re-read white papers and wikipedia articles for several days until it finally clicked. This would have helped a lot.

digger250• 13 years ago

Salting the password should defeat the rainbow table, right?

AnthonyMouse3• 13 years ago

Using a salt would require the attacker to include an entry for each possible salt for each password candidate. If the salt is only one bit, this makes the attack take twice as long (or, requires tables twice as large). If the salt sufficiently long it makes the attack infeasible.

drostie3• 13 years ago

Thanks for this question! The answer is complicated. :D

Let me tell you first why it does not help! In order to build a rainbow table, we must be able to build a lookup table (since they're just compressed lookup tables). But a lookup table is basically a brute force attack on a certain category of passwords! So, if your password would fall to a modern rainbow table, it can be brute-forced by modern computational clusters. Salting does not change that. Intrinsically the password is no more secure than it was before. (To make it more secure, use bcrypt, scrypt, or pbkdf2. Seriously, even PHP has pbkdf2 nowadays, you have no excuse[1].)

Now let me mitigate that naysaying a bit. If you salt every password with a random 12-character base64 string, you do indeed prevent building a lookup table for the database. And that's actually not bad. Security is best measured not in bits or in operations, but in dollars. If the value of the information is much smaller than the cost to crack it, you'll defeat a rational attacker.

Rainbow tables can be built in a highly parallel way, with attackers pooling their resources and attacking multiple systems. So it will generally cost more to brute-force a password than it will to break it with a rainbow table: the rainbow table lookup can be done with one CPU; but brute forcing may require a botnet or lots of GPUs.

[1] Okay, there is one excuse: you might want to be able to do password administration from phpMyAdmin using only built-in MySQL functions. If you are stuck in this particular case the REPEAT() and SHA1 commands can have a similar effect:

    create function pw(salt char(12), password varchar(255)) returns char(40) 
        return sha1(repeat(concat(salt, sha1(password)), 100000));

but if you're not in this case, use something better.

MattSayar• 13 years ago

This is a very good explanation. I have a couple questions though:

Is the chain-length of 100 arbitrary, or is there an optimal length of these chains?

How many times would you run ORATION through the one-way function and compare it to your rainbow table before you decide it's not in the table?

AnthonyMouse3• 13 years ago

>Is the chain-length of 100 arbitrary, or is there an optimal length of these chains?

100 is the compression ratio. If you make chains of length 100 then you can compress the dictionary 100:1. If you make the chains of length 1000 then you can compress 1000:1 but you have to do 1000 operations for each lookup instead of 100. It's a trade off.

> How many times would you run ORATION through the one-way function and compare it to your rainbow table before you decide it's not in the table?

You presumably know the length of the chains your table used, so if you go through the entire length without finding it then you'll know it really isn't in the table (e.g. Alice just provided a random word instead of one which was the output of the hash function and it turns out no dictionary word leads to the one she provided).

danbruc• 13 years ago

»[...] that lookup table is going to be as long as the dictionary! What if he has to take it somewhere [..]« ... now he has to carry around the rainbow table and the dictionary. This didn't work out as expected. ^^

ryan-c• 13 years ago

Technically, in your example you do still need the full dictionary - a one way function mapping to words requires it for operation.

jere• 13 years ago

Good explanation. I always thought this was a good one too: http://kestas.kuliukas.com/RainbowTables/

JoeOfTex• 13 years ago

Is cracking passwords even worth anyone's time anymore?

Most password salting is extremely unique from one website to the next. And as long as the salting increases the length of the string that will be encrypted passed 16 characters, it will be uncrackable.

It would be much quicker to social engineer your way into a system and just plant a script that honeypots unencrypted passwords.

marcin_kw• 13 years ago

The author did not realize that the "repetitive dictionary lookup" function is not a 1-to-1 mapping. There could be, for example, multiple words whose definition starts with "a type". All these words map to the same ciphertext, eventually.

The "repetitive dictionary lookup" function is very useful for validating Alice's claims of solving parts of the puzzle, but imperfect for deriving the solution from a ciphertext.

jgrahamc5• 13 years ago

I didn't? Or perhaps you didn't read my blog post where at the end I say...

"PS In reality, Alice's one way function is not 'bijective'. That means that some starting words will end up at the same word. For example, when FOLIO, PIECE and WORLD are passed through Alice's one way function they all end up at THINGS. In a follow up post I'll take about this and its implications."

peteretep• 13 years ago

That property is that it's not injective. It is also ("implies") not bijective, but that's a different thing.

petsos• 13 years ago

> In the real, mathematical world of one way functions something similar to Bob's reverse dictionary can be created (they are called 'rainbow tables') and they are part of the reason passwords get broken easily when companies' password databases get stolen.

In real life I don't think rainbow tables play any part at all.

B-Con• 13 years ago

They very likely come into play whenever a password hash database is leaked and the hashes were not salted/iterated properly.

sophacles2• 13 years ago

jgrahamc - I think you should introduce the concept of collision here. In the last article when you got to "things", my thought was: there have to be a few words that get to "things". In your reverse lookup table of the dictionary algorithm, there will be a lot of words for, e.g. "the", "or", "and" and so on. This is actually nice - because you start getting to other security concerns from here. For the crossword, you can talk about search spaces: instantly eliminate all words not of length N. For passwords, of course keys with lots of collisions reduce the search space, so that passwords with a high collision probability are less secure. And so on.

I'm not exactly sure what direction you're planning on taking this series, but astute readers, even without a solid grounding in crypto concepts, will notice.

jgrahamc5• 13 years ago

Yes. I mention this in the first PS. I plan to address this in a separate blog post but have been trying to keep these bite-sized.

sophacles2• 13 years ago

Oh right on. I either missed the PS on my first reading, or read it before you added it. Either way, cool :)

Bob outsmarts Alice's one way function

Related Stories