Skip to main content

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".

Popular posts from this blog

Making an old USB printer support Apple AirPrint using a Raspberry Pi

There are longer tutorials on how to connect a USB printer to a Raspberry Pi and make it accessible via AirPrint but here's the minimal one that's just a list of commands and simple instructions. 1. Install Raspbian on a SD card 2. Mount SD card on some machine and navigate to / . Add a file called ssh and set up wpa_supplicant.conf for WiFi access. Now you have headless and don't need a keyboard or monitor. 3. Boot. Login. sudo raspi-config . Change password. 4. Connect printer via USB cable 5. Then execute the following sequence of commands to set up CUPS and make it accessible on the network. sudo apt-get update sudo apt-get full-upgrade sudo apt-get install cups sudo usermod -a -G lpadmin pi sudo cupsctl --remote-any sudo systemctl restart cups 6. Visit http://raspberrypi:631/admin and add the local printer. Make sure "sharing" is enabled on the printer. 7. Then make sure AirPrint is set up sudo apt-get install avahi-daemon sudo reboot Printer should work

How to write a successful blog post

First, a quick clarification of 'successful'. In this instance, I mean a blog post that receives a large number of page views. For my, little blog the most successful post ever got almost 57,000 page views. Not a lot by some other standards, but I was pretty happy about it. Looking at the top 10 blog posts (by page views) on my site, I've tried to distill some wisdom about what made them successful. Your blog posting mileage may vary. 1. Avoid using the passive voice The Microsoft Word grammar checker has probably been telling you this for years, but the passive voice excludes the people involved in your blog post. And that includes you, the author, and the reader. By using personal pronouns like I, you and we, you will include the reader in your blog post. When I first started this blog I avoid using "I" because I thought I was being narcissistic. But we all like to read about other people, people help anchor a story in reality. Without people your bl

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it: Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name. There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly. What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message: Our system is unable to process last names that contain non-letters, please replace them with spaces. Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your