4.5. Public-key encryption

189

or m2. This is true even though the adversary is able to obtain the decryptions of any ciphertexts (different from the target ciphertext c) of its choosing.

This security definition is a very strong one—the adversary is unable to do better than guess whether c is the encryption of one of two plaintext messages m1 and m2 that the adversary itself chose even when it has access to a decryption oracle. Indistinguishability against adaptive chosen-ciphertext attacks has gained acceptance as the “right” notion of security for public-key encryption schemes.

Another desirable security property is that it should be infeasible for an adversary who is given a valid ciphertext c to produce a different valid ciphertext c such that the (unknown) plaintext messages m and m are related in some known way; this security property is called non-malleability. It has been proven that a public-key encryption scheme is indistinguishable against adaptive chosen-ciphertext attacks if and only if it is non-malleable against adaptive chosen-ciphertext attacks.

4.5.1ECIES

The Elliptic Curve Integrated Encryption Scheme (ECIES) was proposed by Bellare and Rogaway, and is a variant of the ElGamal public-key encryption scheme. It has been standardized in ANSI X9.63 and ISO/IEC 15946-3, and is in the IEEE P1363a draft standard.

In ECIES, a Diffie-Hellman shared secret is used to derive two symmetric keys k1 and k2. Key k1 is used to encrypt the plaintext using a symmetric-key cipher, while key k2 is used to authenticate the resulting ciphertext. Intuitively, the authentication guards against chosen-ciphertext attacks since the adversary cannot generate valid ciphertexts on her own. The following cryptographic primitives are used:

1.KDF is a key derivation function that is constructed from a hash function H . If a key of l bits is required then KDF(S) is defined to be the concatenation of the hash values H (S, i), where i is a counter that is incremented for each hash function evaluation until l bits of hash values have been generated.

2.ENC is the encryption function for a symmetric-key encryption scheme such as the AES, and DEC is the decryption function.

3.MAC is a message authentication code algorithm such as HMAC.

Algorithm 4.42 ECIES encryption

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), public key Q, plaintext m. OUTPUT: Ciphertext (R, C, t).

1. Select k R [1, n − 1].

2. Compute R = k P and Z = hk Q. If Z = ∞ then go to step 1.

3.(k1, k2) ← KDF(xZ , R), where xZ is the x-coordinate of Z.

4.Compute C = ENCk1 (m) and t = MACk2 (C).

5.Return(R, C, t).

190 4. Cryptographic Protocols

Algorithm 4.43 ECIES decryption

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), private key d, ciphertext

(R, C, t).

OUTPUT: Plaintext m or rejection of the ciphertext.

1.Perform an embedded public key validation of R (Algorithm 4.26). If the validation fails then return(“Reject the ciphertext”).

2.Compute Z = hd R. If Z = ∞ then return(“Reject the ciphertext”).

3.(k1, k2) ← KDF(xZ , R), where xZ is the x-coordinate of Z.

4.Compute t = MACk2 (C). If t = t then return(“Reject the ciphertext”).

5.Compute m = DECk1 (C).

6.Return(m).

Proof that decryption works If ciphertext (R, C, t) was indeed generated by the legitimate entity when encrypting m, then

hd R = hd(k P) = hk(d P) = hk Q.

Thus the decryptor computes the same keys (k1, k2) as the encryptor, accepts the ciphertext, and recovers m.

Security notes

Note 4.44 (security proofs for ECIES) ECIES has been proven secure (in the sense of Definition 4.41) under the assumptions that the symmetric-key encryption scheme and MAC algorithm are secure, and that certain non-standard (but reasonable) variants of the computational and decision Diffie-Hellman problems are intractable. These DiffieHellman problems involve the key derivation function KDF.

Note 4.45 (public key validation) The shared secret point Z = hd R is obtained by multiplying the Diffie-Hellman shared secret dk P by h. This ensures that Z is a point in the subgroup P . Checking that Z = ∞ in step 2 of the decryption procedure confirms that Z has order exactly n. This, together with embedded key validation performed in step 1, provides resistance to the small subgroup and invalid-curve attacks described in §4.3 whereby an attacker learns information about the receiver’s private key by sending invalid points R.

Note 4.46 (inputs to the key derivation function) The symmetric keys k1 and k2 are derived from the x-coordinate xZ of the Diffie-Hellman shared secret Z as well as the one-time public key R of the sender. Inclusion of R as input to KDF is necessary because otherwise the scheme is malleable and hence also not indistinguishable. An adversary could simply replace R in the ciphertext (R, C, t) by −R thus obtaining another valid ciphertext with the same plaintext as the original ciphertext.

4.5. Public-key encryption

191

4.5.2PSEC

Provably Secure Encryption Curve scheme (PSEC) is due to Fujisaki and Okamoto. The version we present here is derived by combining PSEC-KEM, a key encapsulation mechanism, and DEM1, a data encapsulation mechanism, that are described in the ISO 18033-2 draft standard. PSEC-KEM has also been evaluated by NESSIE and CRYPTREC.

The following cryptographic primitives are used in PSEC:

1.KDF is a key derivation function that is constructed from a hash function.

2.ENC is the encryption function for a symmetric-key encryption scheme such as the AES, and DEC is the decryption function.

3.MAC is a message authentication code algorithm such as HMAC.

Algorithm 4.47 PSEC encryption

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), public key Q, plaintext m. OUTPUT: Ciphertext (R, C, s, t).

1.Select r R {0, 1}l , where l is the bitlength of n.

2.(k , k1, k2) ← KDF(r ), where k has bitlength l + 128.

3.Compute k = k mod n.

4.Compute R = k P and Z = k Q.

5.Compute s = r KDF(R, Z).

6.Compute C = ENCk1 (m) and t = MACk2 (C).

7.Return(R, C, s, t).

Algorithm 4.48 PSEC decryption

INPUT: Domain parameters D = (q, FR, S, a, b, P, n, h), private key d, ciphertext

(R, C, s, t).

OUTPUT: Plaintext m or rejection of the ciphertext.

1.Compute Z = d R.

2.Compute r = s KDF(R, Z).

3.(k , k1, k2) ← KDF(r ), where k has bitlength l + 128.

4.Compute k = k mod n.

5.Compute R = k P.

6.If R = R then return(“Reject the ciphertext”).

7.Compute t = MACk2 (C). If t = t then return(“Reject the ciphertext”).

8.Compute m = DECk1 (C).

9.Return(m).

192 4. Cryptographic Protocols

Proof that decryption works If ciphertext (R, C, s, t) was indeed generated by the legitimate entity when encrypting m, then d R = d(k P) = k(d P) = k Q. Thus the decryptor computes the same keys (k , k1, k2) as the encryptor, accepts the ciphertext, and recovers m.

Note 4.49 (security proofs for PSEC) PSEC has been proven secure (in the sense of Definition 4.41) under the assumptions that the symmetric-key encryption and MAC algorithms are secure, the computational Diffie-Helman problem is intractable, and the key derivation function is a random function.

4.6Key establishment

The purpose of a key establishment protocol is to provide two or more entities communicating over an open network with a shared secret key. The key may then be used in a symmetric-key protocol to achieve some cryptographic goal such as confidentiality or data integrity.

A key transport protocol is a key establishment protocol where one entity creates the secret key and securely transfers it to the others. ECIES (see §4.5.1) can be considered to be a two-party key transport protocol when the plaintext message consists of the secret key. A key agreement protocol is a key establishment protocol where all participating entities contribute information which is used to derive the shared secret key. In this section, we will consider two-party key agreement protocols derived from the basic Diffie-Hellman protocol.

Security definition A key establishment protocol should ideally result in the sharing of secret keys that have the same attributes as keys that were established by people who know each other and meet in a secure location to select a key by repeatedly tossing a fair coin. In particular, subsequent use of the secret keys in a cryptographic protocol should not in any way reduce the security of that protocol. This notion of security has proved very difficult to formalize. Instead of a formal definition, we present an informal list of desirable security properties of a key establishment protocol.

Attack model A secure protocol should be able to withstand both passive attacks where an adversary attempts to prevent a protocol from achieving its goals by merely observing honest entities carrying out the protocol, and active attacks where an adversary additionally subverts the communications by injecting, deleting, altering or replaying messages. In order to limit the amount of data available for cryptanalytic attack (e.g., ciphertext generated using a fixed session key in an encryption application), each run of a key establishment protocol between two entities A and B should produce a unique secret key called a session key. The protocol should still achieve its goal in the face of an adversary who has learned some other session keys.