# Schnorr identification protocol security proof

I read about security proof of Schnorr identification protocol against impersonation attack. For the sake of comprehensibility let me sum up the protocol: Given group $G$ with generator $g$. Verifier is initialized by prover's public key $g^a$, where the knowledge of secret counterpart is to be proven by prover. The protocol runs as following:

1. Prover generates random $a_t\in G$ and sends $g^{a_t}$ to verifier
2. Verifier responds by sending random $c$ to the prover.
3. Prover responds by sending $a_z = a_t + c\,a$
4. Verifier checks whether $g^{a_z}\overset{?}{=}g^{a_t}\,(g^a)^c$

Now, the idea of the security proof was: Given adversary $\mathcal{A}$ being able to issue valid $a_z'$ against arbitrary public key $g^{a'}$, we can turn $\mathcal{A}$ into an efficient $\mathrm{DLog}\,_g(g^{a'})$ oracle.

The proof assumed we can "rewind" the adversary so that it issues 2 different $a_z$'s with respect to a single $a_t$. I didn't understand this assumption. It seems somehow incomplete to me. What if I have non-cooperative adversary? This can't be turned into DLog oracle, since such adversary were indistinguishable from honest prover who knows secret key, thus breaking zero-knowledge protocol property. So is this a complete proof, which I merely didn't get or is the fact that malicious adversary might break the protocol without breaking DLog on $G$ essentially unprovable?

A very clear analysis of the security of the id-scheme of Schnorr was given by Damgard in his cource material here : http://www.daimi.au.dk/∼ivan/Sigma.pdf . The first analysis of the security was given by Schnorr in his paper : https://link.springer.com/chapter/10.1007/0-387-34805-0_22 [proposition 2.1] (both of them explain why you can always get a passing pair $(a_z,a_z').$)
The "rewind" is needed for the security proof. Remark that, the attack is probabilistic (and not determenistic) and the the whole security proof is the computation of the success probability $\mathcal{P}$ (in fact a lower bound is enough) to get a passing pair. So, in the final argument of the security proof, you get that, after $1/{\mathcal{P}}$ calls of the adversary ${\mathcal{A}}$ (which is a probabilistic polynomial algorithm) you can have a passing pair $(a_z,a_z'),$ with $a_z\not=a_z'$ and then you can easily find the discrete log.