CIS 798. Secure login protocols.

• In this section, we demonstrate another useful application of hash functions in the domain of authentication. In particular, we describe a protocol that can realize one-time, or token-based, passwords for login procedures. Citibank already uses such tools to protect certain accounts and this approach is increasingly pursued by industry.

• Traditional logins: The old standard on Unix and Windows operating systems was to get access to the system by a simple password protocol:

  • you need to enter your login name;
  • if the network knows a user with that name, you are asked to provide a ``password'' associated with that name;
  • the system then compares this password to the actual password that is stored on the system.
  • If the entered and stored passwords match, then network access is granted.

• Provers and verifiers: A network user who wishes to login to a network is called a prover. The part of the system which runs the login protocol and decides whether to grant access to provers is called the verifier. More generally, any program or system resource which can be requested by a client (a user, some other program, etc.) is seen as a verifier; and all clients are called provers.

• We present a suite of protocols for login, or general server access, which meets the following set of criteria:

  • No secret information is transmitted across the network;
  • no secret has to be stored by the verifier;
  • ideally, the verifier should not know the user's secret to avoid impersonation;
  • upon demand, a server should have a means of proving that a client used that server;
  • mutual authentication should be possible;
  • the protocols should not put severe constraints on computational resources.

• Our draft scheme requires a trusted authority who initializes the system: it equips a prover with a pair (x₀,k), where x₀ is a secret value, and k specifies an implementation-specific number determining how often that prover can present the password to the verifier; the authority also provides the verifier with a pair (x_k,k), where
  x_k = h^k(x₀),
  

  as the identity information of the prover. Note that x_k is obtained by k many applications of h to x₀:
  

  x_n+1 = h(x_n)
  

• Verification of prover's identity: The (successful) verification of a prover's identity then consists of a successful run of the following protocol:

  • the prover sends the verifier her personal identity information x_k;
  • the verifier matches that with his stored value x_k; this corresponds to asking for a login name (and a mismatch results in a failed login attempt);
  • the verifier asks for a password, which is any value x' such that h(x') = x_k. Since the prover knows the secret x₀, she can use h to compute x_k-1 as such an x' and send this to the verifier;
  • the verifier can compute h(x_k-1) and match it with x_k;
  • after a successful match, the verifier grants access to the prover, stores x_k-1 as the current identity information of that user, and the next authentication round will be done with x_k-1 and x_k-2 instead of x_k and x_k-1.

• This scheme does not transmit secret information across the network, and the verifier does not store, nor know, the secret value x₀. The verifier also should not possess a trap door for the hash function; an efficient algorithm for solving h(x) =y for x, where y = h(x') for some x'. The authority provides all provers with their initial parameters (x₀,k) and all provers with the initial access pair (x_k,k). However, the authority ought to possess a trap door for the hash function, allowing it to function as an agency that can settle disputes between provers and verifiers. The short-comings of this scheme are that passwords can only be used once, that they have to be shown before the service, and that they may be used in a replay attack, e.g. if the verifying server crashes right after the prover provided x_k-1 along an insecure channel, another ``prover'' could, upon recovery of the verifier, replay x<sub>k</sub>, provided that the verifier would ``remember'' x_k as current password of the alleged user.

• Zero-knowledge proofs: Zero-knowledge proofs are protocols in which a prover can successfully demonstrate to the verifier that the prover knows a secret without revealing any information whatsoever about that secret to the verifier. This sounds like a paradox, but this paradox can be realized in number theory. Using such a protocol in combination with the previous scheme, we obtain a new login protocol which does not expose the current user identity information x_k, so it may be reused until, and if, the server requests it as a access ticket and proof of usage of the provided service. To state the protocol, we have to work with an explicit hash function h. Assume that n = pq, where p and q are two primes of about 512 bits in length such that p =2p'+1 and q = 2q' + 1 for prime numbers p' and q'. Fix any e with gcd(e,(p-1)(q-1)) = 1. Then the function
  

  h(x) = x^e mod n
  

  is essentially the RSA-based hash function discussed already in class. The authority is responsible for computing p and q and it keeps those parameters secret. The provers and verifiers will obtain n and e so that they are able to compute h. Since the authority knows the factorization of n, it can easily derive an efficient algorithm for computing inverses of h. That way, it can investigate and rule disputes between provers and verifiers.

• Guillou-Quisquater protocol:

  • the prover generates a random number r between 0 and n - 1 and sends the verifier her commitment c = h(r) and her current personal identity information x_k;
  • the verifier sends a challenge s between 0 and e to the prover;
  • the prover computes some b with bx_k-1 = 1 mod n using the algorithm Extended_Euclid, computes c' = rb^s mod n and sends c' to the verifier;
  • the verifier now computes x_k^s(c')^e mod n which should equal the prover's commitment c.
  To see that a prover, who knows x_k-1, will be granted access under this protocol, we compute ... (to be continued)

Feel free to consult me during my Office Hours: W 2:00--3:00 P.M., U 10:30--11:30 A.M.