10 ms·
A non-mathematical explanation of one way functions
- Someone 14y agoGiven http://en.wikipedia.org/wiki/Wikipedia:Getting_to_Philosophy http://en.wikipedia.org/wiki/Wikipedia:Getting_to_Philosophy, I am not sure I would accept THINGS as proof that Alice knew the answer. I know dictionaries probably are structured differently. But they might suffer from the same problem.
- jonahx 14y agoGood point, although "eventually reaching philosophy" is a lot easier than reaching it after exactly five steps. Also that requires clicking the first link. Still you are right it's a phenomenon that should be ruled out.
- jgrahamc 14y agoI'm not claiming that my dictionary function has all the attributes of a good one way function, it's illustrative.
- michael_nielsen 14y agoYou could easily turn a bug into a feature: add a couple of paragraphs to your post pointing out exactly this potential problem, and how you you could test to see whether or not it really is a problem. Your post (which is already terrific) then becomes a great explanation of why not all functions work as one-way functions, and what it means for something to be a good one-way function.
- jgrahamc 14y agoMakes sense. I was aiming for a single 'a ha!' moment for the reader. What I actually want to do is so how well this mapping works with a real dictionary by writing some code to follow this algorithm with real words.
- michael_nielsen 14y agoHere's a rough draft that would, I think, only reinforce the 'aha' moment. It could be inserted as the third last paragraph: "There's a potential problem with this procedure. What if Alice had started with some other word - say 'FILES' - and following this procedure also led to the word 'THINGS'. In fact, it might be that many, many English words all lead to the word 'THINGS'. If that were so then Bob would be justified in feeling skeptical that Alice had solved the crossword. She'd be using a "bad" one-way function. Both Alice and Bob need to be confident that this procedure doesn't lead to too many collision between English words. This is a challenge that needs to be addressed if you want to prove that a function is truly a good one-way function."
- Someone 14y agoI think it is highly likely that many words clash that way. Worse, I expect many clashes between words that fit the crossword description. Consider, for example, a description of 'animal'. Now, look up a few animal: http://www.merriam-webster.com/dictionary/elephant http://www.merriam-webster.com/dictionary/elephant: any of a family (Elephantidae, the elephant family) of... http://www.merriam-webster.com/dictionary/rhinoceros http://www.merriam-webster.com/dictionary/rhinoceros: any of a family (Rhinocerotidae) of... http://www.merriam-webster.com/dictionary/crocodile http://www.merriam-webster.com/dictionary/crocodile: any of several large... http://www.merriam-webster.com/dictionary/buffalo http://www.merriam-webster.com/dictionary/buffalo: any of several wild bovids... So, there is some variation, but it isn't hard to find immediate collisions, especially for related words. That makes sense; a dictionary should not attempt to vary the way it describes similar words.
- Someone 14y agoEven if it is illustrative, you should aim to give a good example. Now, you could make this a good example by continuing, in lesson 2, to show weaknesses with this approach. For an analogous case, read Knuth. In 'the art of computer programming', chapter ?2? on random numbers, he gives a convoluted random number generator that, in an abstract sense, is not unlike your one-way function, then shows how bad it is, and makes the case that you shouldn't let ordinary programmers design (or even tweak) these algorithms for you.
- jgrahamc 14y agoKnuth's point is that the random number generator that he came up with isn't good and so people shouldn't write such functions themselves. This is different from my blog post which is trying to explain to people what a one way function is without resorting to mathematics. I do agree that a follow up could be written (e.g. Bob could compute a 'rainbow table' of the dictionary for the next time Alice uses the same trick; and the Alice could introduce some salt; Alice could introduce multiple rounds as well with a 'work factor' to make Bob's life harder).
- doorhammer 14y agoIt was pretty much the perfect explanation for me. If you're trying to non-mathematically explain a mathematical process, I think, more often than not, you're going to end up with an incomplete example. If you try, I'd wager that you'd probably end up with something fairly long and possibly convoluted. Which isn't to say that more blog posts about the topic would be wasted. I think the posts so far are great ideas for expansion. I just think it accomplished what it wanted to accomplish. Hopefully the blog post won't spur too many novice developers into writing home-grown password hashing functions based on the outlined technique.
- stan_rogers 14y agoThat would just be a hash collision. They all have 'em. You not only need to be able to get to THINGS, you need to get to THINGS in an arithmetic sequence of non-article words (first from the first, second from the second, third from the third, and so on). Given that even in an exhaustive dictionary, the definitions are finite in length (and that the hash space is only three words short of the message space), the collision frequency is probably pretty low. In much the same way, I don't need to know your password, I just need to stumble across something that hashes to the same value. (It would likely be useless elsewhere even if you use the same password everywhere, unless the same salt, peppper and hash algo are being used there as well, but it'll still work on that one account.)
- rustc 14y agoSlightly off-topic, but I've been intrigued by one way functions for quite a while now. How does someone go about making a one way function like MD5 and SHA1? How do you know it can't be reversed easily?
- masklinn 14y agohttp://en.wikipedia.org/wiki/Cryptographic_hash http://en.wikipedia.org/wiki/Cryptographic_hash should be an OK start, with further links to more precise explanations of the crypto concepts. > How do you know it can't be reversed easily? Some you prove: http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function http://en.wikipedia.org/wiki/Provably_secure_cryptographic_h... But more commonly (because provably secure crypto functions are extremely hard to design) you think hard about them, then unleash fellow and opposing crypto specialists to try and break them[0], as was done by NIST[1] [0] http://en.wikipedia.org/wiki/Cryptanalysis http://en.wikipedia.org/wiki/Cryptanalysis [1] http://en.wikipedia.org/wiki/NIST_hash_function_competition http://en.wikipedia.org/wiki/NIST_hash_function_competition
- martinced 14y ago> How do you know it can't be reversed easily? It is impossible to reverse because information is lost. There's an infinite number of "plain text" leading to a same hash. If you could reverse, say, SHA-1, then you'd just have invented the best compression scheme ever and the world as we know it would be no more: the implication would be huger than anything we can imagine. You could compress a full movie in a SHA-1 hash. Not. Gonna. Happen. It is impossible. The problem is not reversing information: reversing is simply impossible. The problem is finding collisions and hence being able to create plain texts that shall lead to the same hash.
- bo1024 14y agoIt should be noted that we still don't "know": even "provably" secure functions depend on an assumption that may or may not be true, such as that factoring integers is much harder than multiplying them. Of course, almost everyone thinks these problems are in fact hard (at least for classical computers), but there's no proof (such a proof would imply P != NP).
- andyhmltn 14y agoThis is a great explanation. I wish I would've had something like this when I started out haha. Another good one is the mixing colour analogy.
- jamessun 14y agoThis talk, http://pyvideo.org/video/1778/crypto-101 http://pyvideo.org/video/1778/crypto-101, given by Laurens Van Houtven at PyCon US 2013, is a fantastic intro to crpytography and he uses the mixing color analogy as one of his examples.
- andyhmltn 14y agoThanks I'll watch that when I get home :-)
- mseebach 14y agoIt's a very good explanation, but I think it could benefit from a simpler base case, and then the explicit addition of "rounds". So, the base case is "FOLIO is on page 655(?)" and Alice gives Bob the number 655. Now, there are only 12 five-letter words on page 655, so she's actually giving a pretty good hint away. Instead, she picks the second word of the first line, and give the page of that. Depending on how secure she wants the verification to be, she can repeat this process, with each round making the one-way-function 1000(?) times harder to reverse.
- deleted 14y ago[deleted]
- jgrahamc 14y agoI've added a PS. Thanks for the suggestion.
- 205guy 14y agoWhile you're taking editing suggestions, there are 2 points that are missing in the narrative: - Alice and Bob must have identical copies of the dictionary. Different editions could have slightly different definitions. The risk is not large, but it throws off all confidence. - Alice tells Bob her procedure. Either they do it in real-time together or she tells him the procedure along with the encrypted word. But nowhere in the text as written does Alice communicate the "algorithm" to Bob. Also, Bob does not know if Alice completed the puzzle until he completes the puzzle (or the solution is published) [actually that one clue, but Alice could've chosen any clue, possibly the last one that Bob finds]. The story made me believe Bob would know if Alice completed the puzzle immediately, so by definition of the problem, before he completed it. Is there a protocol that would allow this? [I think that's where we need 3rd party trusted sources]
- dhimes 14y agoshe picks the second word of the first line, and give the page of that You've lost me. I think OP does it in a way that people don't have to guess at what he's talking about, which is important (very important) when introducing an idea). There are certain tweaks we can argue about to be sure, but I think this serves as an intro that everybody can "get." She's not securing a $100,000 account. If someone were to get interested in this and pursue more knowledge she would quickly realize that she couldn't use this algorithm to secure important accounts. Note: I assume you mean that she picks the second word of the first line, looks that word up in the dictionary and gives the page number of that word.
- spacemanaki 14y agoA similar example was highlighted on BB the other day, with an interesting twist about cognitive bind-spots leading to security holes: http://blog.tanyakhovanova.com/?p=277 http://blog.tanyakhovanova.com/?p=277 http://www.schneier.com/blog/archives/2013/04/nice_security_m.html http://www.schneier.com/blog/archives/2013/04/nice_security_...
- S4M 14y agoIt's a nice example, but I think it's flawed. The steps are: folio -> individual -> human -> or -> alternatives -> things. So, is "folio" the only (five letters) word in the dictionnary that has "individual" as the second word of its definition? Is "individual" the only word in the dictionnary that has "human" as the third word of its definition? I doubt it, so their way or identifying words is by no mean bijective, hence it's not a valid one.
- mistercow 14y agoI think it's actually a good analogy because of that. When an astute listener asks that question, you have the perfect segue into discussing collisions and why designing cryptographic hash functions is difficult and should be left to experts.
- bockris 14y agoIt doesn't matter. The exact point of a one-way function is to go forward from a known answer. It should be very hard (impossible) to go backwards. As the article mentioned, he could have stopped at 1 round but did 5 just to show the concept.
- S4M 14y agoIt matters (in the case of the example), because if I tell you "things", you have no way to know if I got it by starting from folio, or from another word X that gave me the steps (for example): X -> Y -> Z -> or -> alternatives -> things EDIT: grammatical correction.
- bockris 14y agoI don't want to tell you 'folio'. I want to prove to you that I know the answer is 'folio' without telling you the word 'folio'. If you thought the answer was 'bored' and you followed the steps (which are not a secret) and you didn't come up with the same end confirmation word as I did. (i.e. me = 'things' you = 'hamster') one of us is wrong and neither of us had to provide our starting word to the other. We don't know who is right yet, we just know we don't agree. One round leaves some room for error because we could both accidentally choose a word that resolves to the same word in the target position. But since we are doing 5 rounds and moving the target word (1st, 2nd, 3rd etc) for each successive round the odds become much better that we won't have an accidental collision. (edit: grammar)
- edanm 14y agoI just go with "some things are easy to do but hard to undo - like breaking a glass of water. Easy to do, hard to undo." At least as a first explanation of what we're trying to achieve in the first place. Also, I love the "Waldo" example of zero-knowledge proofs: I want to prove to someone that I found Waldo in a "Where's Waldo" puzzle. How do I do this without showing them where Waldo is? . . I can simply cut a "Waldo-sized" hole in a big blanket, then position the "Where's Waldo" puzzle under the blanket with Waldo showing through the cut. Easy to do since I know where Waldo is, but impossible to get information from. (At least, theoretically).
- Evbn 14y agoBreaking a glass is non-repeatable, which loses a key aspect of hashing.
- learc83 14y agoOk how about the classic mixing two colors together.
- Evbn 14y agoIf you are only thinking of physical processes and non-expert technicians,and mathematically simulating the inverse is not accepted, yes. It is a good example for lay people not in the paint/color/physics industry.
- kaoD 14y agoThen just cutting a paper in half will do.
- kibibu 14y agoMy first eye-opener about 1-way functions is this algorithm: Take a word. Remove every second letter. This is a one-way function, because it's basically impossible to recover the original, even for two letter words. It's not a very good as a one way hash, because you can trivially construct collisions. It does, however, nicely capture the idea that you are pretty much always going to be discarding information to get a hash (if the hash is shorter than the input), without really resorting to the pigeonhole principle.
- bradford 14y agoFor non-mathematical explanations I liked this video, which uses a paint mixing analogy to explain the one way functions: http://www.youtube.com/watch?v=3QnD2c4Xovk http://www.youtube.com/watch?v=3QnD2c4Xovk
- btilly 14y agoNice example. Of course the challenge is to verify that the one-way function actually yields information about the starting word. As an example, a conceptually similar procedure with Wikipedia usually winds up at philosophy. See http://www.geekosystem.com/xkcd-philosophy/ http://www.geekosystem.com/xkcd-philosophy/ for more.
- michael_nielsen 14y agoSee the discussion of this point at https://news.ycombinator.com/item?id=5530988 https://news.ycombinator.com/item?id=5530988 (and child comments)
- wdaher 14y agoI really like this analogy - very clear, and it gets at the essence of what's going on here. Reminds me of this similar abstract explanation of zero-knowledge proofs: http://en.wikipedia.org/wiki/Zero-knowledge_proof#Abstract_example http://en.wikipedia.org/wiki/Zero-knowledge_proof#Abstract_e...
- tgflynn 14y agoThis particular function is easy to reverse though. Using appropriate data structures you can start with the end result and find all possible candidates for the word in polynomial time.
- brianpan 14y agoAnd exactly what data structure do you suppose is appropriate for Bob?
- tgflynn 14y agoProbably a hash map from words to definitions along with a list of positions within each definition record. I may post an implementation later if nobody beats me to it but I don't have time right now.
- jgrahamc 14y agoWhat's the point? This is an example to show people what a one way function looks like. I even say at the bottom of the blog post that you wouldn't do this on a computer. This specific one way function is hard for a human to reverse. Writing a computer program to automate Bob's work is completely missing the point.
- eyeface 14y agoAn algorithm that takes polynomial time would not be feasible given the size of a dictionary, assuming you're running it on poor old Bob (who is not a computer).
- ctdonath 14y agoAll security can be broken/beaten. The trick is making the evasion process more costly than "proper" acquisition of the contents. In this case, it's easier to just look up all the 5-letter words matching known letters (or otherwise corresponding to other fixed-length overlapping words), to wit just write a crossword solver. Bob can always just fall back on rubber hose cryptography.
- pash 14y agoIf you want to take a closer (and, yes, mathematical) look at this idea, check out the lecture notes [0] from the MIT course Great Ideas in Theoretical Computer Science. Sections 4 and 5 of the introductory notes [1] give the classic example of using prime factorization to verify bets in a game of "flipping a coin over the telephone". Much of the rest of the course develops the major ideas underlying this example (computational complexity, cryptography) and shows you other things you can do with them (machine learning). 0. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-080-great-ideas-in-theoretical-computer-science-spring-2008/lecture-notes/ http://ocw.mit.edu/courses/electrical-engineering-and-comput... 1. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-080-great-ideas-in-theoretical-computer-science-spring-2008/lecture-notes/lec1.pdf http://ocw.mit.edu/courses/electrical-engineering-and-comput... [PDF]
- anologwintermut 14y agoAlthough this does give an interesting intuition for a one way function, the application is wrong. Per the article, Alice doesn't want to leak any information about the solution. Simply using a one way function allows Bob to check if one of a possible set of solutions is valid. ( He can just evaluate f on the finite set of answers). It also can leak a bunch of other information, provided it doesn't give the solution in its entirety. For example, f(x) =x^2 mod N is a one way function if factoring is hard. However, it's only hard to learn some log(log(N)) bits of X, the rest is believed to be easy ( and know to be for certain bits). What Alice wants is a commitment scheme[0] which has some secret randomized input. She would commit to her solution, send it to Bob, wait until Bob has solved the puzzle or gives up, and then prove that she had the solution first by providing both the solution and the randomness. Now you can construct a commitment scheme from a one way function, but a one way function is not a commitment scheme. Now if they both just want to check if they have the same solution, you have to do far more complex than either of these involving Secure Multi Party Computation. [0] http://en.wikipedia.org/wiki/Commitment_scheme http://en.wikipedia.org/wiki/Commitment_scheme
- csl 14y agoIf you liked this, you should really read the Wikipedia article on one-way functions, https://en.wikipedia.org/wiki/One_way_function https://en.wikipedia.org/wiki/One_way_function Some tidbits: * "The existence of such one-way functions is still an open conjecture. In fact, their existence would prove that the complexity classes P and NP are not equal" * "It is not sufficient to make a function 'lossy' (not one-to-one) to have a one-way function." * "The existence of a one-way function implies the existence of many other useful concepts, including: [PRNGs, MACs, etc.]"
- utopkara 14y agoThe following papers created one-way functions on words for resilient information hiding in text, first one through synonym substitutions, second one through typos: "The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions", U. Topkara et. al. MMSec'06 https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2006-61.pdf https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2006... "Information hiding through errors: A confusing approach", M.Topkara et. al. SPIE'07 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1426 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1...
- thewisedude 14y agoI think I can come up with a simpler explanation of one way function to start with. Lets say the word I want to apply one way function is 'america'. Lets say I assign a number to each character in the password and the number that I assign is equal to the position of that character in English alphabet. For eg: 'a' would get the value 1, 'b' would get 2, 'c' would get '3' and so on. My one way function adds the values of each character, in case I apply it to 'america', it would be 1+13+5+18+9+3+1 => 50. So, if somebody had to find the word from only from resultant sum or value, it would take time to come up with all the possible words. Some of the possible candidates also include aameric, cmeriaa etc. Clearly in this case there are many possible words that map to a particular value or sum, in the good one way function there are not going to be as many words that map to one value, also a good one way function is more complicated(for a computer too or computer takes non polynomial time) than the one I chose!
- Oculus 14y agoThe question of "Why does it change things if you hash a passwd in the DB?" always lingered in my mind and now it totally makes sense! Awesome and incredibly simple explanation, thanks!
- tekniiq 14y agoterrible explanation imo since the algorithm is still not clear to me. how about: 3+7 is 10 and 2+8 is also 10. Given the expression you can find the sum, but given the sum it's very hard to find the expression. This becomes harder for bigger number of course.
- noonespecial 14y agoNot 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. When used in the context of password encryption though, all of these "overlapping" words are also the password.
- oneway 14y agoCached copy: http://www.jottit.com/fp693 http://www.jottit.com/fp693
- ilitirit 14y agoI think the easiest mathematical example would probably be something along the lines of: "I've managed to solve for X, Y and Z!" "So did I, but I don't believe you. Prove it to me." "The sum of all the digits in X, Y and Z is 143"
- elchief 14y agoI like to think of a very precise meat grinder. You can turn a cow into hamburger but not hamburger into a cow. Want to store a password (cow)? Meat grind it. Store the hamburger. How does someone login? Grind their attempted password (cow) exactly as you did their stored password and compare hamburgers. If same, they can log This of course assumes hackers are hindus and value cows but not hamburger.