Hacker News Reader

Comment by Someone | Hacker News Reader

Given 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.

View on HN

I'm not claiming that my dictionary function has all the attributes of a good one way function, it's illustrative.

Even 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.

Knuth'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).

It 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.

You 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.

Makes 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.

Here'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."

I 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: any of a family (Elephantidae, the elephant family) of...

http://www.merriam-webster.com/dictionary/rhinoceros: any of a family (Rhinocerotidae) of...

http://www.merriam-webster.com/dictionary/crocodile: any of several large...

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.

Good 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.

That 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.)

Reply on news.ycombinator.com