“Where is Waldo?”, or “Security by Origami”

This is an interesting excersize in security:

A friend of mine gave me a riddle this morning regarding “Where’s Waldo?”. The riddle is as follows:

You and a friend play “Where’s Waldo?”. You solve the puzzle before your friend, and you want to prove to your friend you solved the puzzle, without giving him any hints. How do you do this?

Zero knowledge? Geographic descriptions? Riddles? Hashes?
How do you let your friend know that you solved it, without helping out? What is your solution to this problem? Be creative and leave comments.

Math not required (please) but allowed (if you must). :)

For solutions and cool ideas, visit this blog post. There’s some other cool stuff on that blog.

  • http://www.BeyondSecurity.com Aviram

    Similar to Dave Aitel’s “who found this vulnerability first” system.

    Write down the hash of the solution on a piece of paper. After your friend solves it (or gives up), show him the original message.
    He can verify the message matches the hash and he knows he received it in the early date/time so it proves you had that information when you said you did.

  • sunshine

    That’s what I also said, but some people can be so much more creative than us two, I suppose. :)

    My friend told me someone he knows came up with this cool zero-knowledge solution:
    “Describe to the other player the differences in what the Waldo’s on both sides of the one you spotted wear”

  • Jason DePriest

    Take a digital picture of it and crop out everything but Waldo.

    Give the resulting tiny photo to your friend.

    When he finally finds Waldo, he can verify the little Waldo’s are the same.

  • sunshine

    Originally, they was in Hebrew. Hmm..
    איפה אפי?
    מצא את אפי

  • http://www.BeyondSecurity.com Aviram

    Jason – the main problem with what you’re suggesting is that it gives additional information (a “hint”, basically) to the friend and thus changes the scenario.

    It’s obviously not a problem when playing “where’s Waldo”, but if you want to draw conclusions from this to other practical matters it’s not a “clean” solution.

  • pheh

    Buy two books.

  • http://securemanhattan.com Justin Polazzo

    Give the description of what the person 5 people away from waldo is wearing.

    If you think this will give away too much location to your friend, then give him the descriptions of four people in the crowd, each exactly 10 people away from waldo at different cardinal points.

    He will have a hard time finding these people, due to the nature of the game, and would have an easier time of it just looking for waldo. Once your friend finds waldo, he will be able to verify your markers.


  • http://www.argo-menti.com/prestito/ Prestito

    sunshine, what you mean when said in hebrew ?

  • Jason DePriest

    Alright then. Take two.

    The origami solution is forgetting that by deforming the paper, you change its effective dimensions when you unfold it.

    The creases you made can never be completely removed and each one shortens the paper along its perpendiculars.

    It won’t line up when you unfold it. Not exactly.

    My new suggestion is to take a ruler and measure the X / Y coordinates from some corner of the page. Do something simple to obfuscate them like XOR and give the other guy the numbers.

    As long as your friend spends the time looking for Waldo and not reversing your two numbers, this works fine.

    If you are worrying about your friend doing that, then SHA-256 them or whatever you want.

  • heh

    mapgas torch. works fast