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
Let’s only focus on the interaction between Alice and the malicious 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.
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 unsecure…
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.