How to forge Schnorr signatures if you can guess the challenge

Question

Underlying the Schnorr signature is an identification protocol: let $G$ be a cyclic group where discrete log is "hard" and choose $g$ as a generator of $G$. Now have Alice pick a random (secret) exponent $s$ and publish $v=g^s$.

To identify herself to Bob, it goes like this:

1. Alice chooses a random exponent $r$ and sends $g^r$ (commits $r$)
2. Bob sends random exponent $e$ (challenge $e$)
3. Alice sends $r + se$
4. Bob makes sure $g^r = g^{r + se}v^{-e}$

That's all well and good, but what if a cheating prover can guess $e$? Then how does he fool Bob?

Answer 1

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece.

Notation

• In step 1, Alice sends $g^r$. Call this value $a=g^r$.
• In step 3, Alice sends $r+se$. Call this value $b=r+se$.
• In step 1-3, one value is sent in each step: {$a,e,b$}. We'll call these three values a transcript for public key $v$.
• In step 4, with the new notation, Bob checks: $a=g^bv^{-e}$.

Basic question

With this notation, it may be easier to see how knowing $e$ can help. Generate a random $b$ and then compute $a$ so that the equation holds and {$a,e,b$} will accept.

Another thing to note

Other answers noted that since you choose $a$ directly, you do not really know an $r$ such that $a=g^r$ (by the discrete log problem). This is one thing that distinguishes a true proof from a simulated one.

A second thing to note, which is very important, is that to simulate a proof, you start by computing (choosing) $b$ and then you compute $a$ using $b$ and $e$. In a real execution, you compute everything in order.

The only way to forge?

The other answers have shown a way to simulate the proof. Is it the only way?

For example, is it possible to choose an $a$ value knowing $e$ and then compute the right $b$ to make {$a,e,b$} accept (short of knowing $s$)? The answer is no.

Pretend you have a black box that could do this: it takes {$a,e$} as input and returns the proper $b$ without knowing $s$. If such as box existed, you could query {$a,e_1$) and get $b_1$, and then query {$a,e_2$} with the same $a$ and different $e$, and get $b_2$. However one can verify that this is sufficient to compute $s$: in fact, $s=\frac{b_1-b_2}{e_1-e_2}$. So there is a contradiction: the box doesn't know $s$ by definition and yet it does "know" $s$ (in the sense that it can compute it). Therefore, by contradiction, such a box cannot exist, and neither can a forgery {$a,e,b$} where $a$ and $e$ are chosen.

Enforcing only true transcripts

If we put all of the above together, it basically says that if {$a,e,b$} accepts, it must have either been computed by someone who truly knows $s$, or it was computed backward by choosing/knowing $b$ and $e$ before computing $a$.

Can we eliminate the second case? One way is to be Bob. Another might be to be there in person to see that $a$ is sent before $e$: however do you really know that Alice doesn't know $e$? Can you really be sure?

The answer is yes.

If you can ensure $a$ is computed before $e$, then we are done. A simple technique (called Fiat-Shamir) is to set $e=\mathcal{H}(a)$, where $\mathcal{H}$ is a hash function (technically a random oracle). If you choose/know $e$ first, you cannot find an $a$ that will hash to it (by preimage-resistance).

Answer 2

If Alice guesses $e$ then she chooses a random value $x$ and computes $h = g^x v^{-e}$, a value which she sends to Bob at step 1. At step 3, Alice sends $x$. When Bob does step 4, he recomputes $g^x v^{-e}$ and finds $h$, and he is happy. However, Alice does not know $s$.

The "commitment" at step 1 is a way for Alice to say: "I know a $r$ corresponding to this $g^r$, which allows me to do the computation for any challenge $e$". But if Alice can guess the challenge in advance, she needs not really know $r$. Here, Alice sends a value $h$ which is part of the group and thus is equal to $g^r$ for some value $r$, but Alice does not know that $r$.

Answer 3

Suppose that we have Eve, that knows what $e$ is going to be, and does not need to know the prover's private key $s$, just the public one $v$.

She then sends $g^k \cdot v^{-e}$ as her first "move", where she can choose her own $k$ (you can modify the $k$ in different plays to make it all look nice and random...). The verifier sends $e$ as expected, of course, and finally Eve sends $k$ as her final move.

The verifier only checks that her last move raised to $g$ and then times $v^{-e}$ equals her first move (see step 4.) and this is true by construction.

Note that the verifier has no way of seeing that the first move wasn't of the form $g^r$ for some $r$ known to the sender, or that $r + se$ is sent, etc. He only sees 2 numbers by the prover, that have to satisfy a (known in advance) relation....

Answer 4

Well, if fake-Alice guesses the challenge exponent $e$ in step 1, then she can guess the value of $v^{-e}$. That means she can pick an arbitrary value to stand in for $r+se$, compute $g^{r+se}v^{-e}$, and send that as her commitment in step 1.

Then, assuming Bob sends the guessed exponent in step 1, fake-Alice sends the value $r+se$ that she picked above. That means that, in step 4, Bob will validate that $g^r = g^{r+se}v^{-e}$, because he is actually validating ${step1} = g^{step3}v^{-e}$, and fake-Alice picked the $step1$ and $step3$ values to make this equation work.