Friday, April 12, 2013

Bob outsmarts Alice's 'one way function'

In a previous blog post I described a one way function using a dictionary. Read that post before reading this one.

That night Bob realizes he's found a way to outsmart Alice and not bother doing the crossword at all. The next day, he waits for Alice's gloating call and starts asking her about clues in the crossword. As before Alice replies with words that have passed through her one way function, but now Bob manages to fill in the complete crossword without any thinking, searching or delay.

Late the night before Bob had a brainwave: it's easy to go forward through Alice's one way function and hard to go backwards, but there only so many words in the dictionary. So, instead of waiting for Alice to give him a word and then be forced to undertake the nearly impossible task of working backwards through all the possible definitions containing that word, Bob realizes that he can just build his own reverse dictionary. A dictionary in which he can look up a word Alice gives him and find the word she must have started with.

With the Oxford dictionary and a stack of paper Bob starts working through the entire dictionary word by word working out the one way function of every single word. It's a long job, but it's feasible: since the one way function is easy to compute he can figure out for any dictionary word the corresponding word that Alice would give him.

His reverse dictionary consists of all the words that Alice could say (the result of the one way function) and the corresponding word that Alice must have started with.

And Bob realizes he only has to do this work once. Once he's built his reverse dictionary he can use it for any word and any time Alice calls. The effort of making the dictionary pays off in the long run. Critically, the one way function is fairly quick to work out in one direction, and there are a limited number of starting words (thousands and thousands, but limited). So, all the hard work is done in advance of needing to know which words go together.

So, when Alice says the one way function of the solution to 2D is CEASE, Bob quickly finds CEASE in his reverse dictionary and sees that the original word was ORNATE.

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.

PART 3: Alice strikes back against Bob's 'reverse dictionary'

PS In reality, the result of Alice's one way function is not unique. More than one starting word 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.

PPS A nice comment on Hacker News goes into detail about rainbow tables in the context of Alice's dictionary one way function.

This entire series of blog posts is available for purchase as an illustrated PDF or eBook for $1.99.


Abhishek Ghose said...

I am thoroughly enjoying this!

Unknown said...

I'm looking forward to the next, well-seasoned installment.

Anonymous said...

Great post. Please keep them coming!

asenski said...

Love it! Alice could also change the rules every day right at the start of the call, that way the reverse dictionary will be impossible to build in advance.

e.g. she can start the phone call with, "today the rules for verification are to use the 3rd word, then the 5th word, then the 1st, then the 2nd".