5.5. Entity Authentication

Entity authentication (also called identification) is a process by means of which an entity Alice, called the claimant, proves her identity to another entity Bob, called the prover or the verifier. Alice is assumed to possess some secret piece(s) of information that no intruder is expected to know. During the execution of the identification protocol, an interaction takes place between Alice and Bob. If the interaction allows Bob to conclude (deterministically or with high probability) that the claimer possesses the secret knowledge, he accepts the claimer as Alice. An intruder Carol lacking the secret information is expected (with high probability) to fail to convince Bob of her identity as Alice. This is how entity authentication schemes tend to prevent impersonation attacks by intruders. Typically, identification schemes are used to protect access to some sensitive piece(s) of data, like a user’s (or a group’s) private files in a computer or an account in a bank. Both secret-key and public-key techniques are used for the realization of entity authentication protocols.

5.5.1. Passwords

A password is a small string to be remembered by an entity and produced verbatim to the verifier at the time of identification. The most common example is a computer password used to protect access to a user’s private working area in a file system. In this case, an alphanumeric string (or a string that can be input using a computer keyboard) of length between 4 and 20 characters is normally used as the secret information associated with an entity. Passwords are also used to prevent misuse of certain physical objects (like an ATM card for withdrawing cash from one’s bank account, a prepaid telephone card) by anybody other than the legitimate owners of the objects. In this case, a password usually consists of a sequence of four to ten digits and is also called a personal identification number or a PIN.

In order that Bob can recognize an entity from her password, a possibility for Bob is to store the (entity, password) pairs corresponding to all the entities that are expected to participate in identification interactions with Bob. When Alice enters her password, Bob checks if Alice’s input is the same as what he stores in the pair for Alice. The file(s) storing these private records should be preserved with high secrecy, and neither read nor write access should be granted to any user. But a privileged user (the superuser) is usually given the capability to inspect any file (even read-protected ones) and, therefore, can make misuse of the passwords.

This problem can be avoided by storing, instead of the passwords themselves, a one-way transform of the passwords.^[3] When Alice enters a password P, Bob computes the transform f(P) and compares f(P) with the record stored for Alice. The identity of Alice is accepted if and only if a match occurs. The password file now need not be read-protected, since any intruder (even the superuser) knowing the value f(P) cannot easily compute P.

^[3] Informally speaking, a one-way function is one which is computationally infeasible to invert.

Passwords should be chosen from a space large enough to preclude exhaustive search by an intruder in feasible time. Unfortunately, however, it is a common tendency for human users to choose passwords from limited subsets of the allowed space. For example, use of lower case characters, dictionary words, popular names, birth dates and so on in passwords makes attacks on passwords much easier. A strategy to foil such dictionary-based attacks is to use a pseudorandom bit sequence S known as the salt and apply the one-way function f to a combination of the password P and the salt S. That is, a function f(P, S) is now stored against an entity Alice having a password P. The combination (P, S) is often referred to as a key for the password scheme. Since a password now corresponds to many possible keys, the search space for an intruder increases dramatically. For instance, if S is a pseudorandomly chosen bit string of length 64, the intruder has to compute f(P, S) for a total of 2⁶⁴ times in order to guess the correct candidates for S for each P under trial. It is also necessary that the same key is not chosen for two different entities. If the salt S is a 64-bit string, then by the birthday paradox a collision between two keys is expected to occur only after (at least) 2³² keys are generated.

A second strategy to strengthen the protection of passwords is to increase the so-called iteration count n, that is, instead of storing f(P, S) for each password P, Bob now stores fⁿ(P, S). An n-fold application of the function f increases by a factor of n both the time for password verification and for exhaustive search by an intruder. For a legitimate user, this is not really a nuisance, since computation of fⁿ(P, S) only once during identification is tolerable (and may even be unnoticeable), whereas to an intruder breaking a password simply becomes n times as difficult. In typical applications, values of n ≥ 1000 are recommended.

In some situations, it is advisable to lock access to a password-protected area after a predetermined number of (say, three) wrong passwords have been input in succession. This is typically the case with PINs for which the search space is rather small. For unlocking the access (to the legitimate user Alice), a second longer key (again known only to Alice) is used or human intervention is called for.

As a case study, let us briefly describe the password scheme used by the UNIX operating system. During the creation of a password a user supplies a string P of eight 7-bit ASCII characters as the password. (Longer strings are truncated to first 8 characters.) A 56 bit DES^[4] key K is constructed from P. A 12-bit random salt S is obtained from the system clock at the time of the creation of the password. The zero message (that is, a block of 64 zero bits) is then iteratively encrypted n = 25 times using K as the key. The encryption algorithm is a variant of the DES, that depends on the salt S. The output ciphertext and the salt (which account for a total of 64 + 12 = 76 bits) are then packed into eleven 7-bit ASCII characters and stored in the password file (usually /etc/passwd). When UNIX was designed (in 1970), this algorithm, often referred to as the UNIX crypt password algorithm, was considered to be reasonably safe under the assumption of the difficulty of finding a DES key from a plaintext–ciphertext pair. With today’s hardware and software speed, a motivated attacker can break UNIX passwords in very little time.

^[4] The data encryption standard (DES) is a well-known symmetric-key cipher (Section A.2.1).

Password-based authentication schemes suffer from the disadvantage that the user has to disclose her secret P to the verifier. The verifier may misuse the knowledge of P by storing it secretly and deploying it afterwards. During the process of computation of fⁿ(P, S) the string P resides in the machine’s memory. An eavesdropper capable of monitoring the temporary storage holding the string P easily gets its value. In view of these shortcomings, password schemes are referred to as weak authentication schemes.

5.5.2. Challenge–Response Algorithms

In a strong authentication scheme, the claimant proves the possession of a secret knowledge to a verifier without disclosing the secret to the verifier. One of the communicating entities generates a random bit string c known as the challenge and sends c (or a function of c) to the other. The latter then reacts to the challenge appropriately, for example, by sending a response string r to the former. Strong authentication schemes are, therefore, also called challenge–response authentication schemes. The communication between the entities depends both on the random challenge and on the secret knowledge of the claimant. An intruder lacking the secret knowledge of a valid claimant cannot take part properly in the interaction. Furthermore, since a random challenge is used during each invocation of the identification protocol, an eavesdropper cannot use the intercepted transcripts of a particular session for a future invocation of the protocol.

Public-key protocols can be used to realize challenge–response schemes. We assume that Alice is the claimant and Bob is the verifier. Without committing to specific algorithms, we denote the public and private keys of Alice by e and d, and the encryption and decryption transforms by f_e and f_d respectively. Alice proves her identity by demonstrating her knowledge of d (but without revealing d) to Bob. Bob uses the transform f_e and Alice the transform f_d under the respective keys e and d. If a key d′ other than d is used by Carol in conjunction with e, some step of the interaction detects this and the protocol rejects Carol’s claim to be Alice. We describe two challenge–response schemes that differ in the sequence of applying the transforms f_e and f_d.

A challenge–response scheme based on encryption–decryption

In this scheme, Bob (the verifier) first generates a random string r, encrypts the same by the public key of Alice (the claimant) and sends the ciphertext c (the challenge) to Alice. Alice uses her private key to decrypt c to the message r′ and sends r′ (the response) back to Bob. Identification of Alice succeeds if and only if r = r′. Algorithm 5.65 illustrates the details of this scheme. It employs a one-way function H (like a hash function) for a reason explained later. This scheme checks whether the claimant can recover the random string r correctly. A knowledge of the decryption key d is needed for that.

Algorithm 5.65. Challenge–response authentication based on encryption

The string H(r) = w is called the witness. By sending w to Alice, Bob convinces her of his knowledge about the secret r without disclosing r itself. If Bob (or a third party pretending to be Bob) tries to cheat, Alice has the option to abort the protocol prematurely. In other words, Alice does not have to decrypt an arbitrary ciphertext presented by Bob without confirming that Bob knows the corresponding plaintext.

A challenge–response scheme based on digital signatures

In the scheme explained in Algorithm 5.66, Alice (the claimant) first does the private key operation, that is, Alice sends her digital signature on a message to Bob (the prover). Bob then verifies the signature of Alice by employing the encryption transform with Alice’s public key.

Algorithm 5.66. Challenge–response authentication based on signature

This authentication scheme is based on the assumption that only a person knowing Alice’s private key d can generate a signature s that leads to the equalities and . Using only r_A and the signature s = f_d(r_A, d) would demonstrate to Bob that Alice possesses the requisite knowledge of d. The random string r_B is used to prevent the so-called replay attack. If r_B were not used, an eavesdropper Carol intercepting the transcripts of a session can later claim her identity as Alice by simply supplying r_A and Alice’s signature on r_A to Bob. Using a new r_B in every session (and incorporating it in the signature) guarantees that the signature varies in different sessions, even when r_A remains the same.

There is an alternative strategy by which the use of the random string r_B can be avoided. All we have to ensure is that a value of r_A used once cannot be reused in a subsequent session. This can be achieved by using a timestamp, which is a string reflecting the time when a certain event occurs (in our case, when Alice generates the signature). Thus, if Alice gets the local time t_A, computes the signature s := f_d(t_A, d) and sends (t_A, s) to Bob, it is sufficient for Bob to check that the timestamp t_A is valid. A possible criterion for the validity of Alice’s timestamp t_A is that the difference between t_A and the time when Bob is verifying the signature is within an allowed bound (predetermined, based on the approximate time for the communication). But it may be possible for an adversary to provide to Bob the timestamp t_A and Alice’s signature on t_A, before t_A expires. Therefore, Bob should additionally ensure that timestamps from Alice come in a strictly ascending order. Maintaining the timestamp for the last interaction with Alice takes care of this requirement. Algorithm 5.67 describes the modified version of Algorithm 5.66, based on timestamps. A problem with timestamps is that (local) clocks across a network have to be properly synchronized.

Algorithm 5.67. Using timestamp in challenge–response authentication

Mutual authentication

So far, we have described identification schemes that are unidirectional or unilateral in the sense that only Alice tries to prove her identity to Bob. For mutual authentication between Alice and Bob, the above schemes can be used a second time by reversing the roles of Alice and Bob. Algorithm 5.68 describes an alternative strategy that achieves mutual authentication with reduced communication overhead (compared to two invocations of the unidirectional scheme). Now, the key pairs (e_A, d_A) and (e_B, d_B) and the transforms f_{e, A}, f_{d, A} and f_{e, B}, f_{d, B} of both Alice and Bob should be used.

5.5.3. Zero-Knowledge Protocols

The challenge–response schemes described above ensure that the claimant’s secret is not made available to the verifier (or a listener to the communication between the verifier and the claimant). But the claimant uses her private key for generating the response and, therefore, it continues to remain possible that a verifier extracts some partial information on the secret by choosing challenges strategically.

Algorithm 5.68. Mutual authentication

Using a zero-knowledge (ZK) protocol overcomes this difficulty in the sense that (absolutely) no information on the claimant’s secret is leaked out during the conversation between the claimant and the verifier. The verifier (or a listener) continues to remain as much ignorant of the secret as he was before the invocation of the protocol. In other words, the verifier (or a listener) does not learn anything form the conversation, that he could not learn by himself in absence of the claimant. The only thing the verifier gains is the confidence whether the claimant actually knows the secret or not. This is intuitively the defining feature of a ZK protocol.

Similar to other public-key techniques, the security of the ZK protocols is based on the intractability of some difficult computational problems. A repeated use of a public-key scheme with a given set of parameters may degrade the security of the scheme under those parameters. For example, each encryption of a message (or each generation of a signature) makes available a plaintext–ciphertext pair which may eventually help a cryptanalyst. A ZK protocol, on the other hand, does not lead to such a degradation of the security of the protocol, irrespective of how many times it is invoked.

We stick to the usual scenario: Alice is the claimant, Bob is the verifier and Carol is an eavesdropper trying to impersonate Alice. In the jargon of ZK protocols, Alice (and not Bob) is called the prover. In order to avoid confusions, we continue to use the terms claimant and verifier. A ZK protocol is usually a three-pass interactive protocol. To start with, Alice chooses a random commitment and sends a witness of the commitment to Bob. A new commitment should be selected by Alice during each invocation of the protocol in order to guard against an adversarial verifier. Upon receiving the witness, Bob chooses and sends a random challenge to Alice. Finally, Alice replies by sending a response to the challenge. If Alice knows the secret (and performs the protocol steps correctly), her response can be easily proved by Bob to be valid. Carol, in an attempt to impersonate Alice without knowing the secret, can produce the valid response with a probability P bounded away from 1. If P happens not to be negligibly small, then the protocol can be repeated a sufficient number of times, so that Carol’s probability of giving the correct response on all occasions becomes extremely low.

The parameters and the secrets for a ZK protocol can be set privately by each claimant. Another alternative is that a trusted third party (TTP) generates a set of parameters and makes these parameters available for use by every claimant over a network. A second duty of the TTP is to register a secret against each entity. The secret may be generated either by the TTP or by the respective entity. The knowledge of this (registered) secret by an entity is equivalent to her identity in the network. Finally, the authenticity of the public key of an entity is ensured by the digital signature of the TTP on the public key. For simplicity, however, we will not bother about the existence of the TTP and the way in which the secret (the possession of which by Alice is to be proved) has been created and/or handed over to Alice. We will also assume that each entity’s public key is authentic.

The Feige–Fiat–Shamir (FFS) protocol

The FFS protocol (Algorithm 5.69) is based on the intractability of computing square roots modulo a composite integer n. We take n = pq with two distinct primes p and q each congruent to 3 modulo 4.

Algorithm 5.69. Feige–Fiat–Shamir zero-knowledge protocol

Selection of domain parameters: Select two large distinct primes p and q each congruent to 3 modulo 4. n := pq. Select a small integer t. /* The probability of a successful cheat is 2–t */ Selection of Alice’s secret: Alice selects t random integers . Alice selects t random bits . Alice computes for i = 1, . . . , t. Alice makes (y1, . . . , yt) public and keeps (x1, . . . , xt) secret. The protocol: Alice randomly chooses and . /* Commitment */ Alice computes and sends to Bob w := (–1)γc2 (mod n). /* Witness */ Bob randomly chooses and sends to Alice . /* Challenge */ Alice computes and sends to Bob . /* Response */ Bob computes (mod n). Bob accepts Alice’s identity if and only if w′ ≠ 0 and w′ ≡ ±w (mod n).

It is clear from Algorithm 5.69 that knowing the secret (x₁, . . . , x_t) allows Alice to let Bob accept her identity (as Alice). The check w′ ≠ 0 in the last line is necessary to preclude the commitment c = 0, that makes any claimant succeed irrespective of the availability of the knowledge of the secret.

Now, let us see how an opponent (Carol), without knowing the secret, can succeed in impersonating Alice by taking part in this protocol. To start with, we consider the simple case t = 1 (which corresponds to Fiat and Shamir’s original scheme). Carol can start the process by generating a random c and γ and computing w = (–1)^γc². Now, Carol should send the response c or cx₁ depending on whether Bob sends ∊₁ = 0 or 1. Her capability of sending both correctly is equivalent to her knowledge of x₁. If Bob sends ∊₁ = 0, then she can provide the correct response c. Otherwise, Carol can at best select a random response from , and the probability that this is correct is overwhelmingly low. On the other hand, let Carol choose a random c and and send the (improper) witness . In that case, Carol can answer the valid response r = c, if Bob’s challenge is ∊₁ = 1. Sending the correct response to the challenge ∊₁ = 0 now requires knowledge of x₁. Therefore, if ∊₁ is randomly chosen by Bob (without the prior knowledge of Carol), Carol can successfully respond with probability (very close to) 1/2. For t ≥ 1, this probability of a cheat by Carol can be easily shown to be (very close to) 1/2^t which is negligibly small for t ≥ 80.

In practice, however, t is chosen to be O(ln ln n). It is, therefore, necessary to repeat the protocol t′ times, so that the probability of a successful cheat becomes (nearly) 1/2^tt′. Taking t′ = Θ(ln n) is recommended. It can be shown that these choices for t and t′ offer the FFS protocol the desired ZK property. Without going into a proof of this assertion, let us informally explain the ZK property of the FFS protocol. Neither Bob nor a listener to the conversation between Alice and Bob can get any idea of the secret (x₁, . . . , x_t). Bob gets as a response the product of c and those x_i’s for which ∊_i = 1. Since c is randomly chosen by Alice and is not available to Bob, there is no way to choose a strategic challenge. However, if the square root of w (or –w) can be computed by Bob, then the interaction may give away partial information on the secret. For example, if Bob chooses the challenge (∊₁, ∊₂, . . . , ∊_t) = (1, 0, . . . , 0), then Alice’s response would be cx₁ from which x₁ can be computed by Bob, if he knows c. Thus, the security and the ZK property of the FFS protocol are based on the assumption that computing square roots modulo n is an infeasible computational problem.

The Guillou–Quisquater (GQ) protocol

The GQ identification protocol is based on the intractability of the RSA problem. The correctness of Algorithm 5.70 (for a legitimate claimant) is easy to establish. The check w′ ≠ 0 is necessary to avoid the commitment c = 0, which makes a claimant succeed always.

A TTP typically selects the domain parameters p, q, n, e and d. It also selects m and gives s to Alice without revealing d. The execution of the protocol does not require the use of the decryption exponent d. In fact, d is a global secret, whereas s is Alice’s personal secret. Alice tries to prove the knowledge of s (and not of d).

In the GQ algorithm, the power s^∊ is blinded by multiplying it with the random commitment c. As a witness for c, Alice presents its encrypted version w. With the assumption that RSA decryption without the knowledge of the decryption exponent d is infeasible, Bob (or an eavesdropper) cannot compute c and hence cannot separate out the value of s^∊. Thus, no partial information on s is provided. Furthermore, each invocation requires a random ∊. In order to compute a strategic witness, Carol can at best have a guess of ∊. The guess is correct with a probability of 1/e. If e is reasonably large, the probability of a successful cheat is low. However, larger values of e lead to more expensive generation of the witness from the commitment (and also of the response). So small values of e (say, 2¹⁶ + 1 = 65,537) are usually recommended. In that case, repeating the protocol a suitable number of times makes Carol’s chance of cheating as small as one desires. Taking t′e (where t′ is the number of iterations of the protocol) of the order of (log n)^α for some constant α gives the GQ protocol the desired zero-knowledge property.

Algorithm 5.70. Guillou–Quisquater zero-knowledge protocol

Selection of domain parameters: Select two distinct large primes p and q and set the modulus n := pq. Select an exponent and compute d := e–1 (mod φ(n)). The pair (n, e) is made public and d is kept secret. Selection of Alice’s secret: Alice selects a random and computes s := m–d (mod n). Alice makes m public and keeps s secret. The protocol: Alice selects a random . /* Commitment */ Alice computes and sends to Bob w := ce (mod n). /* Witness */ Bob selects and sends to Alice a random . /* Challenge */ Alice computes and sends to Bob r := cs∊ (mod n). /* Response */ Bob computes w′ := m∊re (mod n). Bob accepts Alice’s identity if and only if w′ ≠ 0 and w′ = w.

The Schnorr protocol

The Schnorr protocol is based on the intractability of computing discrete logarithms in a large prime field . We assume that a suitably large prime divisor q of p – 1 and an element of multiplicative order q are known. The algorithm works in the subgroup of , generated by g. In order to make the known algorithms for solving the DLP infeasible for the field , one should have q > 2¹⁶⁰.

Algorithm 5.71. Schnorr zero-knowledge protocol

Selection of domain parameters: Select a large prime p such that p – 1 has a large prime divisor q. Select an element having multiplicative order q modulo p. Publish (p, q, g). Select a small integer t < lg q.           /* The probability of a successful cheat is 2–t */ Selection of Alice’s secret: Alice chooses a random secret integer . Alice computes and makes public the integer y := g–d (mod p). The protocol: Alice chooses a random . /* Commitment */ Alice computes and sends to Bob w := gc (mod p). /* Witness */ Bob selects and sends to Alice a random . /* Challenge */ Alice computes and sends to Bob r := d∊ + c (mod q). /* Response */ Bob computes w′ := gry∊ (mod p). Bob accepts Alice’s identity if and only if w′ = w.

We leave the analysis of correctness and security of this protocol to the reader. The secret s is masked from Bob and other eavesdroppers by introducing the random additive bias c modulo q. The probability of a successful cheat by an adversary is 2^–t, since ∊ is chosen randomly from a set of cardinality 2^t. Usually the Schnorr protocol is not used iteratively. Therefore, t ≥ 40 is recommended for making the probability of cheating negligible. On the other hand, if t is too large, then the protocol can be shown to lose the ZK property. For the generation of the witness from the commitment, Alice computes a modular exponentiation to an exponent which is O(q). Generating the response, on the other hand, involves a single multiplication (and a single addition) modulo q and hence is very fast.

Exercise Set 5.5