Mar 05, 2020
by Paul de Lange

Secure verification pt. 1 (Or: How Buzz Lightyear saves the day, again)

In this third article in Paul Moonshine’s series, the concept of proving things is explored.

In the last two episodes of this blog, where we are learning about Zero Knowledge protocols, we had some fun setting up a tree-house club. Being a bunch of nerds, we introduced a little mathematical riddle for our password, and we were happy because the riddle was uncrackable enough to keep out unwanted folk. To keep them out, we agreed that at the door we ask for the solution to a Discrete Logarithm. If the person on the other end whispers the correct solution, we open the door.

Eavesdropping sister alert

But apparently, being nerdy runs in the family, and our super annoying sister is learning how to lip read AND has a telescope to gaze at the stars (she says); AND for some reason she has crafted a super sensitive DIY microphone.

So we’re in trouble. The last thing we want is for our sister to eavesdrop on us and figure out our super-secret password and make her way into our tree-house. And with all her new hobbies, simply whispering the solution through the tree-house door doesn’t feel so safe anymore. What do we do?

Buzz Lightyear to the rescue!

One of the toys lying around in the tree-house is a very old, rusty Buzz Lightyear toy. Its battery is leaking nasty fluids, and it’s acting weird. It’s still talking, but it’s talking all this gibberish nonsense. Since we’re kind of bored up there anyway, we’ve been playing around with this toy enough to have noticed the following behavior of this slightly creepy Buzz toy:

  1. It replies to whatever you say to it
  2. The reply it gives, is always consistent, given the question you ask: on Monday you can ask Buzz:
    “Hey Buzz, what’s up?”,
    and it it’ll reply:
    “Oranges”.
    Then, coming back in the tree-house on Friday, if you ask it the exact same question, it is guaranteed to reply, again, with “Oranges”.
  3. The slightest alteration of the question dramatically alter the answer: asking, instead,
    “Hey Buzz, what’s up, doc?”
    will yield:
    “It’s raining in Nevada”
  4. The answers are always absolutely nonsensical.

We’re playing with this weird toy, amazed at the insane answers Buzz gives us. “Hey, Buzz, what’s 1+1?” gives “Cowboys and Outlaws”. And just “Waffles” yields “A pig is a pal, who’ll boost your morale”. But we need to fix the problem that our sister poses, and playing with Buzz we get an idea:

Let’s tell Buzz our password. Buzz will give back some insane reply, and then we can use his reply at the door. This way someone can eavesdrop, but they will not know our password!

Pass the hash

We’re close, but not yet quite there. In cryptographic terms, Buzz is what we call a Hash function, a very central topic in cryptography. The answer that buzz gives to an input “X” is called the “hash” of X, sometimes abbreviated with hash(X), or just H(X). The fault in just using the hash of our password is that our sister can still eavesdrop, and learn the hash, and then just go to the door and use the hash! This type of breach is sometimes called “Pass the hash”. The doorman will recognize the hash, open the door, and we’re hacked again. But we’re very close! All we need, is a set of dice.

Rolling our way to victory (or security at least)

OK, so that didn’t work, because of the Pass the Hash breach. But in a moment of clarity, we come up with this wonderful solution that uses a set of dice. We can exploit Buzz and his weird feature, where questions that are close give radically different solutions, by setting up the following protocol:

  1. A visitor comes at the door of our tree-house and knocks on the door. We open the cat flip and hand over Buzz and a pair of dice.
  2. The Buzz and dice are accepted. The dice are rolled. The visitor takes the outcome of the roll, and now makes a new password by pasting this outcome after the dice. If the password was “37” (like in our previous blog post), and the outcome of the roll was 11, then the new password will be “3711”.
  3. We give this new number, “3711” as input to Buzz. It replies with something insane like “1964 Chevrolet Malibu”.
  4. The visitor knocks on the door and whispers the dice roll and Buzz’s reply:
    “1964 Chevrolet Malibu”. “11”. We pass Buzz back through the cat flip.
  5. The guard in the tree-house now also pastes the password and the dice roll, “3711”, and tells this to Buzz. If Buzz’s reply matches the visitor’s phrase, the door opens.

This way, out sister can eavesdrop, but will not learn the password. She also does not learn the hash of the password. There’s still one weakness, however: she could eavesdrop on many entries, thus assembling a database that has, for every dice roll, the matching Buzz reply that would be accepted. This weakness we can eliminate by taking not two dice, but ten, making out protocol a little more cumbersome in the process.

Zero knowledge authorization

We have learned how to protect our tree-house against unwanted intruders with the help of Buzz. We managed to verify identity, in a way that prevents eavesdroppers learning our password.

At Veil, we’d like to verify not just identities, but also transactions, without revealing information about either. We also want to make sure we leak absolutely no information. We will also be able to use this protocol instead of the Buzz-dice combination, but for all this, we need some more powerful tools like homomorphic encryption. We’ll discuss this and more in our next installment on Zero Knowledge Protocols.

Share