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

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 last name …

All the symmetrical watch faces (and code to generate them)

If you ever look at pictures of clocks and watches in advertising they are set to roughly 10:10 which is meant to be the most attractive (smiling!) position for the hands. They are actually set to 10:09.14 if the hands are truly symmetrical. CC BY 2.0image by Shinji
I wanted to know what all the possible symmetrical watch faces are and so I wrote some code using Processing. Here's the output (there's one watch face missing, 00:00 or 12:00, because it's very boring):

The key to writing this is to figure out the relationship between the hour and minute hands when the watch face is symmetrical. In an hour the minute hand moves through 360° and the hour hand moves through 30° (12 hours are shown on the watch face and 360/12 = 30).
The core loop inside the program is this:   for (int h = 0; h <= 12; h++) {
    float m = (360-30*float(h))*2/13;
    int s = round(60*(m-floor(m)));
    int col = h%6;
    int row = floor(h/6);
    draw_clock((r+f)*(2*col+1), (r+f)*(row*2+1), r, h, floor(m…

Importing an existing SSL key/certificate pair into a Java keystore

I'm writing this blog post in case anyone else has to Google that. In Java 6 keytool has been improved so that it now becomes possible to import an existing key and certificate (say one you generated outside of the Java world) into a keystore.

You need: Java 6 and openssl.

1. Suppose you have a certificate and key in PEM format. The key is named host.key and the certificate host.crt.

2. The first step is to convert them into a single PKCS12 file using the command: openssl pkcs12 -export -in host.crt -inkey host.key > host.p12. You will be asked for various passwords (the password to access the key (if set) and then the password for the PKCS12 file being created).

3. Then import the PKCS12 file into a keystore using the command: keytool -importkeystore -srckeystore host.p12 -destkeystore host.jks -srcstoretype pkcs12. You now have a keystore named host.jks containing the certificate/key you need.

For the sake of completeness here's the output of a full session I performe…