Skip to main content

A non-mathematical explanation of one way functions

Alice and Bob are crossword enthusiasts. Every morning they rush to complete the Daily Telegraph cryptic crossword. One morning Alice finishes the crossword and telephones Bob to gloat. Bob challenges her by asking for the solution to 21D as proof that she's completed the entire thing.

Alice knows the answer (FOLIO) but doesn't want to tell Bob because that would give away an answer that Bob might not yet have. And she knows that Bob may ask her for more solutions as further challenges, and she really doesn't want to help him complete the crossword.

So, she proposes to Bob that they both get out their Shorter Oxford English Dictionaries. Alice proceeds as follows:

1. She finds the word FOLIO and its definition: "an individual leaf of paper or parchment, either loose as one of a series or forming part of a bound volume, which is numbered on the recto or front side only."  She finds the first word (that's not an article) from the definition, in this case INDIVIDUAL.

2. She finds the word INDIVIDUAL and its definition: "a single human being as distinct from a group". From its definition she finds the second word, in this case HUMAN.

3. She finds the word HUMAN and its definition: "relating to or characteristic of humankind". From its definition she finds the third word, in this case OR.

4. She finds the word OR and its definition: "used to link alternatives". From its definition she finds the fourth word (if the definition were shorter than four words she would have just wrapped around to the beginning of the definition counting up to four). In this case the word is ALTERNATIVES.

5. Finally, she finds ALTERNATIVES and its definition: "(of one or more things) available as another possibility or choice". The fifth word is THINGS.

She tells Bob the word THINGS. If Bob has completed 21D then he can follow the same procedure as Alice, arrive at THINGS and know that Alice had the answer to 21D all along.

But if Bob didn't know the answer to 21D (FOLIO) he'll have a very hard time figuring it out from THINGS. To do that he'd need to work backwards and find every definition in the dictionary where the fifth word is THINGS, and for each of those find the definitions with that corresponding fourth word and so on. Not only is this procedure very slow (Bob would do better to solve the crossword) it will result in a number of possibilities for the solution to 21D as paths through the dictionary from different words will overlap.

So Alice's dictionary procedure is a 'one way function': it's easy to go from a word to another in one direction, but very hard to do so in the opposite.  Such one way functions are widespread in computer security.

For example, one class of one way functions is often used for password verification. A web site need not store your actual password, just a one way function of it. That way if the database of stored passwords is stolen it's hard for an attacker to retrieve the actual passwords (just as Bob would have a hard time going from THINGS to FOLIO), but in day to day use it's easy to verify a password by calculating a one way function of what you type in (just as how Bob can easily go from FOLIO to THINGS) and comparing the result with what's stored in the database.

Of course, computers are much too fast and capable to use actual dictionaries: they use mathematical functions that are easy for computers to calculate in one direction, but difficult for them to compute in the other. Nevertheless the principle is the same.

PS In the algorithm above Alice proceeds through the dictionary looking up five words. There's nothing magical about the number five. In fact, she could just look up the first word found in the definition of FOLIO and give that to Bob (INDIVIDUAL). But following a deeper chain of words makes any attempt by Bob to work backwards harder. I picked five 'rounds' of word look ups to illustrate the principle, but any other number could be chosen. And in the real world of mathematical one way functions it's not uncommon to use multiple 'rounds' to increase the difficulty of reversing the function.

PART 2: Bob outsmarts Alice's one way function

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

Comments

Unknown said…
Best explanation I've seen for a while.
Unknown said…
Nice
Unknown said…
Nice
diagonal said…
great explanation!
Dave O said…
That's a very clear way to explain it! Thanks!
Unknown said…
That's why Magic Johnson is better than Alice : he never give a word...
Unknown said…
That's why Magic Johnson is better than Alice : he never give a word...
Geoff Gariepy said…
Thank you. This and the follow-up explain a lot. I've never written a hashing routine and I've always wondered how it works.
Anonymous said…
very nice explanation
Anonymous said…
very nice explanation
Unknown said…
Is this why we give the name "dictionary" to a certain data type?

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…