# Challenge-response by public-key techniques

Public-key techniques may be used for challenge-response based identification, with a claimant demonstrating knowledge of its private key in one of two ways (cf. §12.5):

- 1. the claimant decrypts a challenge encrypted under its public key;
- 2. the claimant digitally signs a challenge.

Ideally, the public-key pair used in such mechanisms should not be used for other purposes, since combined usage may compromise security (Remark 10.40). A second caution is that the public-key system used should not be susceptible to chosen-ciphertext attacks,^{5}

“Both chosen-ciphertext and chosen-plaintext attacks are of concern for challenge-response techniques based on symmetric-key encryption.

as an adversary may attempt to extract information by impersonating a verifier and choosing strategic rather than random challenges. (See Notes 8.13 and 8.58 regarding the Ra- bin/Williams and Blum-Goldwasser schemes.)

Incorporating a self-generated random number or *confounder* (§ 10.5) into the data over which the response is computed may address both of these concerns. Such data may be made available to the verifier in cleartext to allow verification.

(i) Challenge-response based on public-key decryption

*Identification based on PK decryption and witness.* Consider the following protocol:

*В* chooses a random r, computes the *witness x* = *h(r)* *(x* demonstrates knowledge of *r *without disclosing it - cf. §10.4.1), and computes the challenge e = *P _{A}(r, В).* Here

*P*denotes the public-key encryption (e.g., RSA) algorithm of

_{A }*A,*and

*h*denotes a one-way hash function.

*В*sends (1) to

*A. A*decrypts e to recover

*r'*and

*B',*computes

*x' = h(r'),*and quits if

*x' ф x*(implying

*г' ф r*) or if

*B'*is not equal to its own identifier

*B.*Otherwise,

*A*sends

*r*=

*r'*to

*В. В*succeeds with (unilateral) entity authentication of

*A*upon verifying the received

*r*agrees with that sent earlier. The use of the witness precludes chosen-text attacks.

*Modified Needham-SchroederPK protocol for identification.* The modified Needham-Schr- oeder public-key protocol of Note 12.39 provides key transport of distinct keys *ki*, *к*2 from *A* to *В* and *В* to *A,* respectively, as well as mutual authentication. If the key establishment feature is not required, *ki* and may be omitted. With Pb denoting the public-key encryption algorithm for *В* (e.g., RSA), the messages in the modified protocol for identification are then as follows:

Verification actions are analogous to those of Note 12.39.

(ii) Challenge-response based on digital signatures

*X.509 mechanisms based on digital signatures.* The ITU-T (formerly CCITT) X.509 two- and three-way strong authentication protocols specify identification techniques based on digital signatures and, respectively, timestamps and random number challenges. These are described in §12.5.2, and optionally provide key establishment in addition to entity authentication.

*9798-3 mechanisms.* Three challenge-response identification mechanisms based on signatures are given below, analogous to those in §10.3.2(i) based on symmetric-key encryption, but, in this case, corresponding to techniques in ISO/IEC 9798-3. Regarding notation (cf. 9798-2 above): *r _{A}* and

*t*

_{A}, respectively, denote a random number and timestamp generated by

*A. S*denotes A’s signature mechanism; if this mechanism provides message recovery, some of the cleartext fields listed below are redundant and may be omitted.

_{A}*cert*denotes the public-key certificate containing A’s signature public key. (In these mechanisms, if the verifier has the authentic public key of the claimant a priori, certificates may be omitted; otherwise, it is assumed that the verifier has appropriate information to verify the validity of the public key contained in a received certificate - see Chapter 13.) Remark 10.17 also applies here.

_{A}1. *unilateral authentication with timestamps:*

Upon reception, *В* verifies that the timestamp is acceptable, the received identifier *В *is its own, and (using *A’s* public key extracted from *cert a* after verifying the latter) checks that the signature over these two fields is correct.

2. *unilateral authentication with random numbers:* Reliance on timestamps may be replaced by a random number, at the cost of an additional message:

*В* verifies that the cleartext identifier is its own, and using a valid signature public key for *A* (e.g., from *cert a),* verifies that A’s signature is valid over the cleartext random number *r*_{A}, the same number гд as sent in (1), and this identifier. The signed *г a *explicitly prevents chosen-text attacks.

3. *mutual authentication with random numbers:*

Processing of (1) and (2) is as above; (3) is processed analogously to (2).