Why?

One question that may arise is:

Why do we bother with this special protocol?

Can’t we just use existing stuff that we already know? Let’s take an example.

You know hash functions. An intuitive definition is that they allow to “hash” data. Give it the same data, it will always give you the same fixed-size number. And hopefully one cannot reverse a hash.

You probably know SHA-256, it’s a hash function, and you heard that it’s “safe to use”¹.

So, consider our problem at hand: Alice and Bob want to know if they share information without revealing information they don’t share. Intuitively, you may want to use the “un-revertible” SHA-256 building block to create a hopefully working protocol:

1. Alice found a clue in room \(a_0\), she computes \(x_{a_0} = SHA256(a_0)\).
2. Bob found a clue in room \(b_0\), he computes \(x_{b_0} = SHA256(b_0)\).
3. Bob sends \(x_{b_0}\) to Alice.
4. Alice then compares \(x_{a_0}\) with \(x_{b_0}\). Consequently, she knows whether \(a_0 = b_0\) or not. She can’t compute \(b_0\) because she can’t reverse SHA-256. Right?

Again, don’t hesitate to draw this protocol as a diagram. Cryptographs love these diagrams. They help to see the whole picture.

Does it work? Is it safe? What do you think?

Adapt the security definition from the previous exercise (because we don’t have a server anymore) and try to break it. We suppose Alice cannot reverse SHA-256, making it part of our threat model (it’s a sensible assumption indeed).

Tip

Click to get a hint.

Alice can’t reverse SHA-256, but she can still compute it of course.

Tip

Click to see the answer.

Alice knows the existing rooms. Otherwise, she would not be able to communicate with Bob. Taking the Faculty’s rooms as an example, we can even assume it’s public information (add this to your threat model).

Consequently, she can just compute every possible SHA-256 beforehand (that’s only 12 values in our case). So in this sense, yes, Alice can “reverse” SHA-256; not the \(2^{256} = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936\) existing hashes, but the set of \(12\) hashes she cares about. If we use SHA-256 this way, it’s not secure.

Maybe you could try to add the Server back in the broken protocol from this exercise. Let it compare the hashes and then tell the result to Alice (and/or Bob). Alice, not knowing Bob’s hash, is now in the dark. The Server is not, though. Why? Our updated threat model indicates that room numbers are public information, and our security definition requires the Server not being able to deduce information. Not secure. If we don’t care about the Server knowing information, then it would be secure (according to that new weaker definition).

If you look back at the secure protocol from previous exercise, you’ll see that, even with rooms as public information, even with an adversary knowing every details about the protocol, it stays secure. Let me reformulate: even with our updated threat model, the security properties hold.

We need secret keys for the protocol to work. Its security must rely on an adversary not knowing the keys, not on any other secret. Oh wait, well, isn’t that Kerckhoff’s Principle lurking behind all of this?

1. You now know that security always needs a definition! Saying that something is “safe to use” without context doesn’t make sense. ↩