Chess Grandmaster Problem and "Valid" Attacks on Zero-Knowledge Proofs of Identity

Question

A long question here, but I really want to motivate why I'm confused.

Consider the following attack on the Schnorr Identification Scheme.

1. Alice chooses a random $k$, computes $\gamma = \alpha^k \pmod p$, and sends a message to Bob, containing her certificate and $\gamma$, of her intent to authenticate.
2. Oscar hijacks this message, preventing it from reaching Bob. He then sends a message to Bob, containing Alice's certificate and $\gamma$, of his intent to authenticate.
3. Bob verifies Alice's certificate (and notes the public key $v$), randomly chooses a challenge $0 \leq r_B \leq 2^t$, and sends it to Oscar.
4. Oscar recieves $r_B$ and sends it to Alice as $r_O$.
5. Alice recieves $r_O$, computes $y_O = k + ar_O \pmod q$, and sends the response to Oscar.
6. Oscar recieves $y_O$, and sends it along to Bob as $y_B$.
7. Bob verifies that $\gamma \equiv \alpha^{y_B}v^{r_b} \pmod p$ and accepts.

And therefore Oscar has authenticated to as Alice to Bob. Note as well that as Oscar never has to alter any of the message in transmission, this attack is not dependent on the channel being insecure.

This form of attack, in which Oscar pretends to be Bob to Alice and Alice to Bob, is presented as the Chess Grandmaster Problem by Schneier (Applied Cryptography, pg. 109) as follows (I'm changing Karpov to Carlsen so that it reads easier).

Here's how Alice, who doesn't even know the rules to chess, can defeat a grandmaster. She challenges both Gary Kasparov and Magnus Carlsen to a game, at the same time and place, but in separate rooms. She plays white against Kasparaov and black against Carlsen. Neither Grandmaster knows about the other.

Carlsen, as white, makes his first move. Alice records the move and walks into the room with Kasparaov. Playing white, she makes the same move against Kasparov. Kasparov makes his first move as black. Alice records the move, walks into the room with Carlsen, and makes the same move. This continues, until she wins one game and loses the other, or both games end in a draw.

In reality, Kasparov is playing Carlsen and Alice is simply acting as the middleman, mimicking the moves of each grandmaster on the other's board. However, if neither Carlsen nor Kasparov knows about the other's presence, each will be impressed will Alice's play.

This kind of fraud can be used against zero-knowledge proofs of identity. While Alice is proving her identity to Mallory, Mallory can simultaneously prove to Bob that she is Alice.

Of course in this analogy Alice just tries to prove she is a good chess player, but as the last two sentences show, it can be used for more nefarious purposes. Schneier states that there are solutions, such as predetermining the timing of when messages are sent, not allowing Oscar the time to operate.

What initially caused me to be interested in the problem is that Stinson, in Cryptography: Theory in Practice, does not consider this intruder-in-the-middle to be a valid attack. He writes (Pgs. 361-362) :

However, we do not consider this to be a real attack, because the "union" of the two "sessions" is a single session in which Alice has successfully identified herself to Bob. The overall result is that Bob issued a challenge $r$ and Alice computed the correct response $y$ to the challenge. Oscar simply forwarded messages to their intended recipients without modifying the scheme. The session executed exactly as it would have if Oscar had not been present.

A clear formulation of the adversarial goal should allow us to demonstrate that this is not an attack. We adopt the following approach. We will define the adversary (Oscar) to be active in a particular session if one of the following conditions holds:

1. Oscar creates a new message and places it in the channel
2. Oscar changes a message in the channel, or
3. Oscar diverts a message in the channel so it is sent to someone other than the intended receiver.

The goal of the adversary is to have the initiator of the scheme (e.g., Bob, who is assumed to be honest) "accept" in some session in which the adversary is active. According to this definition, Oscar is not active in the intruder-in-the-middle scenario above, and therefore the adversarial goal is not realized.

This definition of an attacker's "adversarial goal" seems misguided to me, and I'll motivate it with one of Stinson's exercises (9.7, though I won't produce it word for word here).

Consider the following identification scheme, which is based on the Rabin Cryptosystem:

1. Alice sends her certificate, containing a public key $n$, where $n=pq$, to Bob. The primes $p$ and $q$ are private, and $p \equiv q \equiv 3 \pmod 4$.
2. Bob chooses a random number $t$, and computes $x \equiv t^2 \pmod n$. He sends it to Alice.
3. Alice computes $y \equiv \sqrt{x} \pmod n$, and sends $y$ back to Bob.
4. Bob computes $y^2 \equiv z \pmod n$. If $z \equiv t \pmod n$, he accepts, else he rejects.

My initial construction for an attack was as follows:

1. Alice sends a message to Bob, containing her certificate, of her intent to authenticate.
2. Oscar hijacks this message, preventing it from reaching Bob. He then sends a message to Bob, containing Alice's certificate, of his intent to authenticate.
3. Bob verifies Alice's certificate, randomly chooses number $t$, and computes $x_B \equiv t^2 \pmod n$. He then sends $x_B$ to Oscar.
4. Oscar receives $x_B$ from Bob, and then sends it to Alice as $x_O$.
5. Alice receives $x_O$ from Oscar, computes $y_O \equiv \sqrt{x} \pmod n$, and sends $y_O$ back to Oscar.
6. Oscar receives $y_O$ and sends it along to Bob as $y_B$. Bob confirms that $y_B^2 \equiv x_B \pmod n$, and accepts.

Until I noticed that I could use this approach to create the attack on Schorr's scheme above, and then confused went back with my professor and he noticed that my attack isn't valid under Stinson's definition. Instead, we created the following:

1. Alice sends a message to Bob, containing her certificate, of her intent to authenticate.
2. Bob verifies Alice's certificate, randomly chooses number $t$, and computes $x \equiv t^2 \pmod n$. He then sends $x$ to Alice.
3. Alice receives $x$ from Bob, computes $y \equiv \sqrt{x} \pmod n$, and sends $y$ back to Bob.
4. Oscar hijacks the message, and sends $-y$ to Bob. Bob confirms that $-y^2 \equiv x \pmod n$, and accepts.

By Stinson's definition, this is a valid attack whereas mine isn't, despite the fact that the latter can be stopped by communication over a secure channel (Oscar can't compute $-y$), and therefore seems weaker.

So after all that, I end up with two questions. 1) What is the motivation for intruder-in-the-middle attacks not being considered a "real" attack? 2) How are they dealt with in practice, i.e. if I want to implement Schnorr's algorithm, what is the current practice for protecting against them?

Answer 1

The motivation, to me, is that in reality you can consider any router on the internet to be successfully executing an "intruder-in-the-middle" attack just by forwarding messages unchanged. After a successful execution of the identification scheme, Bob knows that someone on the channel is Alice, which is all the protocol was hoping to achieve. It was originally designed for smart cards, where the channel was guaranteed to be secure, but the person on the other end was unknown. When using it in a situation with potential man-in-the-middle attackers, you don't know that the channel is secure without additional safeguards.

In reality, you need to combine the identification scheme with a secure channel. You can do this by executing a key exchange (Diffie-Hellman for instance), and then using something from that exchange to "bind" the secure channel and your authentication scheme together. The value that you use and how you bind it will depend on your implementations.

For example, with DH you could start by executing a key exchange such that Bob and another entity $X$ share a secret $s$. At this point, you hope that $X$ is Alice, but you can't know for sure, so you want to execute the identification protocol. You can't just execute it naively over that channel, however, because Eve could be $X$ and she could just have created a second secure channel with Alice using secret $s'$ to forward all the messages between them (standard Diffie-Hellman man-in-the-middle)

We can note at this point though, that by creating the shared secret $s$, Bob has already had input into the protocol. Instead of him sending a challenge $y$, Alice can simply use $s$ as the challenge for the identification scheme. This has the effect of binding the secure channel and the identification scheme. A successful execution of that scheme will then guarantee that Alice is actually on the other end of the channel (since Alice's identification was tied to $s$, which itself constructs the channel).

The only way Eve can defeat this is if she can create two channels such that $s=s'$. This would allow her to "splice" the channels together, and the identification would work effectively with both channels. However, if the key exchange is contributive ($s$ is not determined unilaterally by one party), there is no way that Eve can create two channels where $s = s'$.

There is something like this in pretty much every secure internet protocol, including TLS. I believe the binding value is a hash of the transcript of the protocol execution or something, but the principle is the same.