The Schnorr identification scheme is being used to remotely log into a home computer which has stored $p$, $α$ and $β(\equiv α^a(mod p))$ - with $a$ the password. This works thusly:

1) The user chooses $k$, forming $γ \equiv α^k(mod p)$ and sends $γ$ to the remote computer.

2) Computer then sends random $r$ to the user.

3) The user computes $y \equiv k − ar (mod (p − 1))$, sends y to Computer.

4) Computer checks if $γ \equiv α^yβ^r(mod p)$ and if so allows login.

$k$ should be random, but the user figures it's fine to use the same 100 digit number instead each time. If another person has been intercepting all the traffic for several logins, can the fact that $k$ isn't changing be exploited?

Here is what I've thought through so far, but I haven't quite figured it out.

Assume it is known that Schnorr scheme is being used. $p, α, β,$ and $k$ are fixed, but unknown. As a result, so is $γ$. $r$ is random and changes with each iteration of the scheme. By monitoring all traffic, $γ, r,$ and $y$ are known. Is it possible to solve for the unknown values if several equations are known and the only value that changes is known? Or is this not feasible because of the nature of the equations?

  • $\begingroup$ Please note $p$, $\alpha$ and $\beta$ are generally considered known for this scheme. Adversary is solving equations for $a$. Please try again with two different challenges $r_1, r_2$, responses $y_1, y_2$ and some unknown fixed $k_1 = k_2 = k$. $\endgroup$ – Vadym Fedyukovych Nov 12 '17 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.