News for hackers. Stuff that matters.
Re:A non-mathematical explanation of one way functions by tgflynn on Thursday April 11, 2013 @12:39PM (#5533052)
This 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.
Re:A non-mathematical explanation of one way functions by ctdonath on Thursday April 11, 2013 @01:28PM (#5533402)
All 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.

Re:A non-mathematical explanation of one way functions by tgflynn on Thursday April 11, 2013 @01:44PM (#5533502)
Yes but real cryptographic functions, like SHA256, are extremely hard to reverse.

I doubt writing a crossword solver is an easier solution since that would need to deal with word definitions and is hence a natural language problem.

Re:A non-mathematical explanation of one way functions by ctdonath on Thursday April 11, 2013 @02:13PM (#5533678)
The point of the article was to explain the concept of one-way functions. The objection was to how easy it would be to crack that example. My objection to the objection was that the example is still harder than finding the secret thru "legitimate" means.

I see crosswords as a data problem: given a dictionary of valid words, generate all possible solutions for the given grid. As the number of overlapping words is quite limited, shouldn't take long to run. The only natural-language factor is deciding which solution matches the clues provided. Dang, now I'm gonna have to go write one...

Re:A non-mathematical explanation of one way functions by brianpan on Thursday April 11, 2013 @01:17PM (#5533330)
And exactly what data structure do you suppose is appropriate for Bob?
Re:A non-mathematical explanation of one way functions by tgflynn on Thursday April 11, 2013 @01:41PM (#5533483)
Probably 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.
Re:A non-mathematical explanation of one way functions by jgrahamc on Thursday April 11, 2013 @01:43PM (#5533492)
What'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.

Re:A non-mathematical explanation of one way functions by eyeface on Thursday April 11, 2013 @01:45PM (#5533510)
An 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).