One-Way Functions
Silvio Micali taught me cryptography. To explain one-way functions, he gave the following example of encryption. Alice and Bob procure the same edition of the white pages book for a particular town, say Cambridge. For each letter Alice wants to encrypt, she finds a person in the book whose last name starts with this letter and uses his/her phone number as the encryption of that letter.
To decrypt the message Bob has to read through the whole book to find all the numbers. The decryption will take a lot more time than the encryption. If the book increases in size the time it takes Alice to do the encryption almost doesn’t increase, but the decryption process becomes more and more draining.
This example is very good for teaching one-way functions to non-mathematicians. Unfortunately, the technology changes and the example that Micali taught me fifteen years ago isn’t so cute anymore. Indeed you can do a reverse look-up online of every phone number in the white pages.
I still use this example, with an assumption that there is no reverse look-up. I recently taught it to my AMSA students. And one of my 8th graders said, “If I were Bob, I would just call all the phone numbers and ask their last names.”
In the fifteen years since I’ve been using this example, this idea never occurred to me. I am very shy so it would never enter my mind to call a stranger and ask for their last name. My student made me realize that my own personality affected my mathematical inventiveness.
Since modern technology is murdering my 15-year-old example, I would like to ask my readers to suggest other simple examples of one-way functions or ways to resurrect the white pages example.
Share:
Leo:
“I would just call all the phone numbers and ask their last names” – this is the same as reverse lookup, only using social engineering instead of computer engineering.
3 November 2010, 2:44 pmpossiblywrong:
This is a great example, thanks! I have been fortunate to have given talks about cryptography to groups of advanced middle school students, and am always amazed at how many cool directions the Q&A takes us. Describing one-way functions and what sort of functions might have inverses that are “hard” to compute can be tough; I plan to add this example to my toolbox :).
3 November 2010, 4:24 pmMaria Droujkova:
I am using a method akin to what students suggested. I asked Google for:
“one-way function” “elementary example.”
Polynomials of high degree are easy to evaluate, but hard to solve. There is apparently a whole cryptography theory about which ones are good. I don’t know how “non-mathematician” you are meaning – adult poets, five-year-olds? Most people who have heard of algebra will be able to appreciate the polynomial as a one-way function, with some prep possibly. I rather like this example.
There was also an example from graph theory, something about disguising an easy graph with extraneous elements, which I did not get due to the lack of knowledge. Michael Fellows taught it to elementary students, apparently.
4 November 2010, 5:12 pmNatasha:
Not quite the same, but I hope still relevant: I use the tale of Rumpelstiltskin to explain the difference between solving a problem generally (hard) and evaluating the correctness of a particular solution (easy). The queen, trying to guess Rumpelstiltskin’s name, can evaluate the truth of a single guess easily (he answers yes or no). However, it is much harder to work backward to find his name from the set of all possible names.
4 November 2010, 7:04 pmBrian Slesinsky:
Perhaps the example could be fixed by saying it’s a book of incorrect phone numbers? Or perhaps a very old phone book from before reverse lookups were common?
8 November 2010, 12:16 amMike Buchanan:
Another example is at the grocery store. If you have like 13 aisles you can have a left and a right side for all the letters. Then you can go to an aisle, pick a grocery item and read off some ingredient. Of course the ingredients are not a one-to-one function but at least it brings to mind how much trouble it is to walk back and forth in the grocery store.
9 November 2010, 8:32 pmMike Watson:
It seems to me that we are setting up a relationship between each letter and a pool of many candidates, where each candidate has a one to one relationship with the resultant piece of ciphertext, and we are looking for something that can’t be queried directly (as in asking a person his last name) nor looked up in a database (such as doing a reverse lookup). Increasingly, the problem is that we love to store information in databases, so what you are looking for is a one way function that reaches toward infinity, thus is difficult if not impossible to database.
My first response was to think of characteristics that animals may have. Let’s say we are to cipher “And”. What unique quality does an Aardvark have or an Antelope or an Alpaca? This may be hard to decode because it may use phrases as part of the ciphertext. The problem may be normalising the phrases (i.e. for length and uniqueness) Next, I thought about using snippets of genetic code for each animal, which would seem to solve the uniqueness problem, but these will be increasingly catalogued. Even genetic code is finite, though large. The stars seem infinite. Alas, our catalogue of them is also finite, and their names are not very useful.
So we are brought back to math, which is exquisitely (and infinitely) suited to ciphers. Perhaps, we may assign the numbers 1-26 to letters of the alphabet, randomly if one wishes. Given “And” to cipher, we may assign the number “1” to the letter “A”. Now, we find a prime number that begins with “1”. We lop off the “1” at the beginning of the prime and use the rest of the digits as the ciphertext. The trick here is finding unique trailing sequences of digits after the “1” that can only be paired to the “1”. So the question becomes, are there primes that begin with a certain number that are unique when the beginning number is taken out. Consulting the first thousand primes shows us that “77” could be paired with 21 different numbers beginning with up to two digits (5, 6, 8, 9, 12, 18, 23, 24, 26, 36, 38, 41, 48, 50, 54, 62, 65, 69, 71, 74, 75), so we will need to reach for larger primes (more digits) to look for those with unique sequences after their leading numbers. This might be in interesting exercise.
Perhaps, I am rambling as I reach for another cipher. For that, I apologise. I am, after all, a rank amateur.
11 November 2010, 9:36 amChrist Schlacta:
we write the text we wish to encipher onto a sheet of paper, then we feed the paper into a cross-cut shredder which feeds into a ziplock baggie. the user at the other end must then reassemble the paper to restore the original text, which would take hours of work for a computer or days of work by hand, but can be done.
Example 2: the pieces of a puzzle. it took the puzzle maker only minutes to cut the puzzle into 500 pieces and dump them into a box and shake, but can take a family of four days to complete.
Example 3: Smashed statues. gotta piece them back together carefully, but it only took one quick swing with a hammer to smash them.
Example 4: SHA512 Hashed Passwords. Only using an exhaustive search can a password be recovered. (without the use of a lookup table, who’s creation is computationally intensive)
8 January 2011, 4:36 pmBarry A.:
Death and taxes seem the only constants.
Since taxes put most people to sleep, that kind of thins the herd a bit.
9 April 2013, 4:52 pmNice Security Mindset Example:
[…] real-world one-way function: Alice and Bob procure the same edition of the white pages book for a particular town, say […]
9 April 2013, 5:36 pmMuntz:
Perhaps the example would work if they omit the area code of the phone number, assuming that the phone book only contains a single area code for all phone numbers. Then the 8th grader’s method becomes very hard to implement as they would need to call many different area codes (out of hundreds) and multiple phone numbers to determine whether any particular string results in an intelligible string of letters.
10 April 2013, 8:16 amHow cognitive blind-spots compromise security systems - Heavenarticles:
[…] One-Way Functions […]
10 April 2013, 12:23 pmtwobits:
Hmm.. I know I and a number of my friends would either refuse to answer a caller that asked that, or just give them a false name. Don’t think this would be an effective attack myself, unless most people would not act like my circle of friends.
10 April 2013, 12:24 pmtwobits:
Not to also mention, that you can often have different last names in the same household, so even an honest answer would depends on who answered the phone. Unless you then ask under who’s name is the phone billed/listed, which seems all the more likely to get people to clam up.
10 April 2013, 12:27 pmHow cognitive blind-spots compromise security systems » Nerd In A Box Online:
[…] One-Way Functions (via Schneier) […]
10 April 2013, 12:44 pmSean HM:
I wouldn’t change the example at all, but would most certainly follow on with the discussion of reverse look-up and calling the numbers. What a great teaching moment!
10 April 2013, 3:53 pmMarc B:
One good analogy for one-way hashes: It’s easy to turn a cow into hamburger; not quite as easy to take the hamburger and make a cow from it.
11 April 2013, 9:14 amiqvoice:
How about two copies of the same old encyclopedia. You could use the third letter of the third word of the third sentence from each entry.
11 April 2013, 2:30 pmIvan:
The point of one-way functions that *there should be no going back*. Meaning, best if information is *lost* in the process, like with hash functions.
My example function is modulo, explained with a clock.
In your example, why not only take the seventh digit of each phone number instead of the whole number?
11 April 2013, 2:46 pmTanya Khovanova:
Ivan, there should be a way to decode it.
11 April 2013, 2:49 pmTanya Khovanova:
In cryptography many one-way functions are used with a back door, a way to decode. In the example above, a prearranged reverse look up can be used to decode.
11 April 2013, 2:54 pmCRYPTO-GRAM April 15, 2013 | MasterAdrian2nd:
[…] A nice example of the security mindset from an eighth grader. https://blog.tanyakhovanova.com/?p=277 I’ve written about the security mindset in the past, and this is a great example of it. […]
15 April 2013, 8:05 amChris:
The example is terrible to begin with – it’s a “one way function”, no sentence after that point should be *able* to contain this phrase: “To decrypt the message…”.
15 April 2013, 8:33 amI visualize these things in binary, where individual incoming bits perturb the state of *multiple* output ones – can’t think of a real-world example, but maybe one exists. How many people might understand simple wiring circuits with lightbulbs, or redstone bricks in minecraft, or whatever – it might not be so easy to say it, but a diagram to show it would work really well (the incoming bits, and how they each in-turn mess-up multiple outgoing ones to produce a result)
George Michaelson:
There are two parts to this problem. One is that hashes are one way functions which produce something strong which relates to its specific input, but isn’t reversible in any way we currently understand (a qualification is that we know some hash functions collide, but thats a known weakness). I think linguistically you can say lots of analogous things like ‘the chances of two people having the same fingerprint is one in a million’ or ‘grains of sand on a beach’ type analogies, and you’re ok. Its a way to make something big into something a lot smaller, but the small thing still has enough variance you can have a lot of them, and they can’t be made easily (if you obey the rules) from two different things and be the same, and if you change the big thing, the small thing changes in unpredictable ways so you can “tell” the big thing has been changed. Thats hashes, as one-way functions.
The other is the one-way function aspect of public, private keying. This is NOT THE SAME. Its a different thing, because the p,q form a pair, and there is a third player, such that p and q relate, and using one you can perform operations which relate to the other, but you cannot ‘guess’ the one from the other. Neither P or Q are like hash functions because the whole point is that p and q relate, against third knowledge. By making one public and keeping one secret you create a world where knowledge of public can prove operations performed by private, and knowledge of private can be proved by operations of public ON THIRD THINGS. So verification is sign(private, data) and then prove via public(data) that only private(data) created that thing. Whereas private communications is use public(data) to make something only private(data) can decode.
This latter one is the hard one to explain. This is the one you are searching for analogies to. And, because its so frighteningly unusual, there are just no good analogies to this one. “only alice did it” is not the same as “only alice can read it” and yet bob can do both, if alice keeps her private key private, and publishes her public key to the world, including bob. SO we get two outcomes from one keypair! this is unusual. Are they corollories? well yes. because they depend on the properties of p,q and third knowledge, and public private status of p and q. Both depend on this. but they use different instances. one is an operation on p, one on q an the proof each time is an inverse operation on q and p respectively.
Most of the analogies here depend on different world models. “only alice did it” is the “you have the other part of the torn label” that the spies used, which ultimately lead to the rosenberg trial. Its best analogy as I see it is “proof of posession”. “only alice can read it” is the world where you whisper something to alice and then only alice knows it. Alas, this is a very poor fit for how public,private works to send something privately to the private keyholder, because instead of whispering it to alice, alice SHOUTS TO THE WORLD the magic which only she can decode. Bizarre!
16 April 2013, 1:40 amDaniel:
I would continue to use the example because it is good.
16 April 2013, 3:43 amYou can easily advert both the given attack and reverse lookup by either omitting digits or adding random ones (salt).
The Security Mindset | O nuit:
[…] This is cute. The obvious solution never occurred to me either. To find out more about the security mindset, go here […]
16 April 2013, 5:07 amStephan:
“Tanya Khovanova: Ivan, there should be a way to decode it.”
NO, one way encryption should NOT have a way to decode it!!
16 April 2013, 9:58 amTypical example:
Allice needs to verify her password on Bob’s system. Allice does not want to transmit the password in the clear and Bob does not want to store the password in the clear.
Allice uses a ONE-WAY encryption (‘hash’)to transform her password to a ‘hash’. Bob has a hash of Allice’s password stored on his system, created using the same ‘hashing’ algorithm as Alice. Bob can compare the 2 hashes to determine if the password is correct. No need to be able to DECODE the hash back to the password, that would be bad.
Tanya Khovanova:
Stephan,
Yes, you do not need to decode a one-way function. But I gave this example to build up to the discussion of public key encryption, so I wanted an example where you can decode. But you are right.
16 April 2013, 10:10 amInteresting attack on a one-way function « Nitemare Cafe:
[…] Bruce Schneier points us to an interesting attack on a one-way function. […]
19 April 2013, 6:56 amGary:
So for the one way hash, where the original sequence cannot be (should not be) recoverable, I have literally used hash. The food is a combination of ingredients is specific proportions that produce a unique flavor once combined. Without all sorts of chemical analysis (the weakness) the original recipe cannot be discovered. All the ingredients are put into a grinder which homogenizes them into a single consistent product. Unable to pick out the original pieces this is hash! Now for math purposes it can be more specific where original text is mutated into something else that is simpler to manage and does not require as much protection.
For example, if we do a simple hash algorithm which assigns all the letters of a password to a number and adds all those numbers together we get a number from which it is impossible to retrieve the original password (unless it was something simple or very repetitive). While that protect the original password, it has a weakness because many other passwords could produce the same number (collisions); “password” and “drowssap” would produce the same number as would “ssawprod” and many others.
So the true objective of the math for a one way has is to generate a unique value and reduce (or eliminate) the potential of collisions.
With encryption, imagine that you have to have a way to reverse that algorithm to recover the original password. A good hash algorithm resists this recovery, this is where encryption comes in. There is a conversion (like password to number), but there is also a reverse (like recover the password from the number).
4 May 2013, 1:26 pmexample of Collision resistance and one-way function | One Ordinary Blog:
[…] https://blog.tanyakhovanova.com/?p=277 About these ads var wpcom_adclk_hovering = false; var wpcom_adclk_recorded = false; var […]
6 October 2013, 2:29 pmA Scribe:
One simple example can be done with a dictionary. I start with a word, then I look-up the word in the dictionary and take the first word of the definition that’s >3 letters long. That’s one round of the hash function. Do three rounds
If the password is: “Critical”
Critical: express criticism or disapproval
Express: convey a thought or feeling in words or by gestures and conduct
Convey: transport or carry to a place
So, assuming you and I have the same dictionary, I can prove that I know the password “Critical” by telling you the hash “Transport”.
10 April 2014, 11:05 amHashing Algorithms and Security. Computer Science. – Geektator:
[…] One-Way Functions […]
20 May 2021, 11:11 amAlborz:
You have a large stack of colored photos (no apparent patterns in the photos), and each photo maps to some letter. You make multiple copies of all these photos. For each letter, you cut out some small but distinguishable portion of the corresponding photo. Each cut-out represents an encrypted letter. To reverse the message (consisting of cut-outs) back to regular letters, the challenger needs to match each cut-out with a corresponding uncut photo.
20 September 2022, 7:40 pm