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

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