N A large safe prime (N = 2q+1 where q is prime). All arithmetic is done modulo N. g A primitive root of GF(N). Also known as a "generator". s User's salt u Username P Cleartext Password H() One-way hash function ^ (Modular) Exponentiation Ws,Ys Secret values Wp,Yp Public values Xs Salted and hashed password Xp Password verifierThe host stores passwords using the following formula:

Xs = s * H(P) (s is chosen randomly) Xp = g ^ Xs (computes password verifier)The host then keeps {u, s, Xp} in its password database. The authentication protocol itself goes as follows:

User -> Host: u, Wp = g ^ Ws (identifies self, Ws = random number) Host: Yp = g ^ Ys (Ys = random number) Host -> User: s, Z = Xp + Yp (sends salt, adds verifier to residue) User: Xs = s * H(P) (user enters password) User: Xp = g ^ Xs (computes verifier) User: Yp = Z - Xp (recovers Yp from message) User: S = Yp ^ (Ws + Xs) (computes session key) User: K = H(S) Host: S = (Wp * Xp) ^ Ys (computes session key) Host: K = H(S)Now the two parties have a shared, strong session key K. To complete authentication, they need to prove to each other that their keys match. One possible way:

User -> Host: H(Z, K) (hash with host's value) Host -> User: H(Wp, K) (hash with user's value)The two parties also employ the following safeguards:

- The user will abort if he receives Z == 0 (mod N).
- The host will abort if it detects that Wp * Xp == {-g, -1, 0, 1, g} (mod N).
- The user must show his proof of K first. If the server detects that the user's proof is incorrect, it must abort without showing its own proof of K.

Back