Solution
Note
Clicking the button below automatically creates a blood oath with the course. It only works if you actually tried to do the exercise beforehand. Click at your own risk.
Reveal the solution.
In Theory
As the hints said, let’s only focus on two rounds between Alice and the adversary Server:
As we can see above, if Alice reuses the same key twice, the malicious server can “cancel” \(k1\) and thus compute \(\delta\) which is the difference between Alice’s first and second room numbers.
For instance, given: $$a_0 = I02 \quad a_1 = I22$$ the server then computes: $$\delta = +20$$ and knows that Alice found her second clue two floors above the first. This is information. The server should not be able to deduce any information.
Observe how additions and subtractions cancelling out, what make the protocol work in the first place, are also what break it when reusing keys!
We just showed that the malicious server can learn information about \(a_i\) \(\forall i \in [0,n[\). It is sufficient to conclude that reusing the same key makes the protocol not secure…
In Practice
… but this is a practical session! So, let’s break it for real.
Here is a simulation showing how one can leverage the theoretical attack we discovered. Take your time to clearly understand how it works. Please note that the server does not find the keys. It only relies on computing \(\delta\) at multiple points.
If you click on the replay button, you’ll notice that, sometimes, the malicious server is 100% sure and, other times, it’s not. It doesn’t mean the protocol is secure, far from it! If we can break it with a non-negligible probability, it’s not. Period.
On the contrary, changing keys at each step is provably secure. So let’s do that instead!
As a rule of thumb, remember that reusing keys is generally a red flag in cryptography.