K. Matsuura, H. Imai INTERNET-DRAFT University of Tokyo draft-matsuura-sign-mode-00.txt March 31, 1999 Expires October 1999 A revised signature mode for the Internet Key Exchange Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 1. Abstract The Internet Key Exchange (IKE) [HC98] uses the Oakley Key Exchange Protocol in conjunction with ISAKMP to obtain authenticated and secret keying materials. Phase 1 of the IKE has several modes with different number of message passes. For those who are vulnerable to Denial-of-Service (DoS) attacks and want to save their resource, three-pass Aggressive Mode is a good choice since it has minimal number of message passes in Phase 1. The public-key primitive method in Aggressive Mode provides significant security advantages over the other alternatives and should be the method of choice in many implementations. In the public-key primitive method, unfortunately, the responder must pay computational cost as expensive as modular exponentiation BEFORE he becomes sure that the protocol initiator is really a correct entity. This can be abused by malicious initiators for a DoS attack; they may launch quite a large number of bogus requests to exhaust the computational resource of the responders who verify each request honestly. The purpose of this document is to solve this problem in digital-signature method by using a DoS-protection strategy called falling-together (FT) mechanism [MI98], [MI99]; in the resolution, malicious initiators or DoS attackers fear their own resource exhaustion when they want to exhaust the resource of the responder. Expires October 1999 [Page 1] INTERNET DRAFT March 31, 1999 Remark: This document is NOT self-contained, it is intended as an addendum to the authentication methods defined in [HC98]. In particular, it uses notation and definitions of [HC98]. Thus, it is best read in conjunction with [HC98]. 2. Introduction The IKE protocol [HC98] defines three alternative methods of carrying out Phase 1 of the key exchange in Aggressive Mode. Three of these methods are usable by parties that have not shared a secret key yet: the Signature Method (Section 5.1 in [HC98]), the Encryption Method (Section 5.2 in [HC98]), and the Revised Encryption Method (Section 5.3 in [HC98]). These methods are vulnerable to a DoS attack. In the Signature Method, the protocol requires the responder to generate a digital signature with heavy computation BEFORE identifying the initiator. For example, RSA public-key primitives are recommended to be supported in IKE implementations, and generation of RSA signatures costs much more than their verification due to the deployment of a relatively larger exponent in signature generation. This motivates a DoS attacker to launch tremendous number of arbitrary requests. Even if the signature generation is inexpensive, the responder must verify the signature for a fake acknowledgment message. It is sufficient that the attacker has the possibility to send fake messages, nothing else is required; the fake requests must follow the format specified in the protocol but do not have to really generate/verify any signatures. In the Encryption Method, the protocol requires the responder to decrypt two public-key encrypted payloads BEFORE identifying the initiator. Unfortunately, this decryption is also computationally expensive and therefore can be abused by an attacker. For instance, RSA decryption costs much more than RSA encryption due to the deployment of a larger exponent. Although the required number of decryption is reduced to be one in the Revised Encryption Method, honest responders can be attacked in the same scenario. This document describes a simple modification of the IKE Signature Method. The resulting Revised Signature Method provides a deterrent to the DoS attack. The change from the IKE Signature Method is basically as follows. There, a random fresh mateial reconstructed by the protocol initiator is used as an additional input into the pseudo-random function to produce hash payload in the acknowledgement message. This is verified by the responder not with heavy computation but with inexpensive one such as keyed hashing. The rest of this document is organized as follows. In Section 3, the Revised Signature Method is described. The description is written in a way so that Section 3 can be read as a replacement to Section 5.2 in [HC98]. Section 4 specifies example algorithms. Matsuura, Imai Revised signature mode for IKE [Page 2] INTERNET DRAFT March 31, 1999 3. The new method: Revised Signature Method of IKE Phase 1 First, we describe a DoS-resistant resolution of Aggressive Mode, which is a three-pass protocol. The first message, a request from the initiator, is the same as that in the Signature Mode; the initiator sends ISAKMP header HDR followed by SA, keying material KE, the initiator's nonce Ni, and his ISAKMP ID IDii. The second message, a reply from the responder, is also the same as that in the Signature Method but there is one restriction. To generate SIG_R, the responder must use a signature scheme with the following properties: + Expensive computation in signature generation can be completed in advance independent of the initiator, i.e., as a precomputation before receiving the request. + The verification procedure includes reconstruction of a random and fresh material, which is denoted by RF in the following. The default RSA signature is thus not a good choice. In the computation of digitally-signed hash payloads, SKEYID is replaced with a one-way hashed value SKEYID' = hash(Ni | Nr) The resultant authenticated keying materials SKEYID_d, SKEYID_a, and SKEYID_e are derived not from this SKEYID' but from conventional SKEYID as in the Signature Method. In the computation of the initiator's digitally-signed hash payload, the hash payload is replaced with a modified hash payload. The modified hash is defined as HASH_I* = prf(SKEYID', g^xi | g^xr | CKY-I | CKY-R | RF | SAi_b | IDii_b). The acknowledgment message explicitly includes this HASH_I*; in the third message from the initiator, ISAKMP header is followed by the modified hash payload and the initiator's signature on it. A certificate payload CERT is optional. On receiving the acknowledgment message, the responder first checks whether the modified hash really uses the correct RF or not. Then, if successful, he goes on to the signature verification procedure. The signature scheme for SIG_I (on HASH_I*) does not necessarily the same as that for SIG_R. Finally, Phase 1 (Aggressive Mode) is defined as follows. Matsuura, Imai Revised signature mode for IKE [Page 3] INTERNET DRAFT March 31, 1999 Initiator Responder ----------- ----------- HDR, SA, KE, Ni, IDii --> <-- HDR, SA, KE, Nr, IDir, [ CERT, ] SIG_R HDR, [ CERT, ] HASH_I*, SIG_I --> 4. Algorithms In the following, we show two example algorithms of the Revised Signature Method. Secret key of an entity x is denoted by SK_x where x is i (initiator) or r (responder). Likewise, public key of an entity x is denoted by PK_x. The first one is based on a shortened Digital Signature Standard (SDSS) [Z97]. As well as the original DSA (Digital Signature Algorithm) [K93] in DSS (Digital Signature Standard) [FIPS94], the shortened DSS is unforgeable by adaptive attackers under the assumptions that discrete logarithm is hard and that the one-way hash function behaves like a random function [Z97], [PS96]. + Precomputation by the responder Pick an integer u randomly from [1, 2, ..., q-2], and modular exponentiate to obtain RF = g^u mod p where p is a large prime and q is a large prime factor of p-1. + Generation of the responder's signature Let g be a public integer with order q modulo p. Compute SIG_R as (s1, s2) = ( u / (hash(RF,HASH_R) + SK_r) mod q, hash(RF,HASH_R) ) + Verification of the responder's signature Reconstruct RF as RF = (g^s2 PK_r)^s1 mod p. where PK_r=g^{SK_r} mod p. The initiator accepts the signature if and only if s2 is equal to hash(RF,HASH_R). + Computation of the modified hash Compute SKEYID' = hash(Ni | Nr) and then generate the modified hash as HASH_I* = prf(SKEYID', g^xi | g^xr | CKY-I | CKY-R | RF | SAi_b | IDii_b). Matsuura, Imai Revised signature mode for IKE [Page 4] INTERNET DRAFT March 31, 1999 + Verification of the modified hash The responder accepts the modified hash if and only if it is equal to prf(SKEYID', g^xi | g^xr | CKY-I | CKY-R | RF | SAi_b | IDii_b). The second example is based on Schnorr's signature scheme [S91]. + Precomputation by the responder Pick an integer u randomly from [1, 2, ..., q-2], and modular exponentiate to obtain RF = g^u mod p where p is a large prime and q is a large prime factor of p-1. + Generation of the responder's signature Let g be a public integer with order q modulo p. Compute SIG_R as (s1, s2) = ( SK_r hash(HASH_R | RF) + u mod q, hash(HASH_R | RF) ) + Verification of the responder's signature Reconstruct RF as RF = g^s1 PK_r^{-s2} mod p. where PK_r=g^{SK_r} mod p. The initiator accepts the signature if and only if s2 is equal to hash(HASH_R | RF). + Computation of the modified hash Compute SKEYID' = hash(Ni | Nr) and then generate the modified hash as HASH_I* = prf(SKEYID', g^xi | g^xr | CKY-I | CKY-R | RF | SAi_b | IDii_b). + Verification of the modified hash The responder accepts the modified hash if and only if it is equal to prf(SKEYID', g^xi | g^xr | CKY-I | CKY-R | RF | SAi_b | IDii_b). 5. Security Considerations First let us consider the difference between SKEYID and SKEYID'. Different from SKEYID, SKEYID' does not include the Diffie-Hellman key g^xy. In order to obtain the negotiated keying materials (SKEYID_d, SKEYID_a, and SKEYID_e), however, an attacker must anyway solve the Diffie-Hellman problem. This problem is assumed to be hard in the IKE since it is based on the Diffie-Hellman key agreement. Matsuura, Imai Revised signature mode for IKE [Page 5] INTERNET DRAFT March 31, 1999 In the following, we evaluate the Revised Signaure Method in terms of DoS resistance. DoS attackers can be classified into to types. One launches completely fake requests while the other pays computational cost necessary for imposing modular exponentiation on the responder. Attackers of the first type do not carry out any heavy computation comparable to modular exponentiation. In the conventional Signature Method, the responder attacked by them must pay the following computational cost as heavy as modular exponentiation: + 0.375|n| (if implemented with RSA signature) + 1.5|p| (if implemented with ElGamal signature) + 3|q| (if implemented with DSA) + 3|q| (if implemented with Schnorr's signature). These costs are represented by the equivalent number of modular multiplications. On the other hand, in the proposed Revised Signature Method, the responder does not have to pay those costs. This is because bogus requests can be detected by the output of inexpensive pseudo-random function. Attackers of the second type do not carry out any heavy computation comparable to modular exponentiation in the conventional Signature Method while the responder must pay the following computational cost as heavy as modular exponentiation: + 0.375|n| (if implemented with RSA signature) + 4.5|p| (if implemented with ElGamal signature) + 3|q| (if implemented with DSA) + 3|q| (if implemented with Schnorr's signature). On the other hand, in the proposed Revised Signature Method (implemented with SDSS or with Schnorr's signature), the attackers also must pay the computational cost of 1.75|q|, which is comparable to the cost on the responder's side, 3|q|. Thus the proposed method discourages DoS attackers by ``falling- together'' nightmare; if the attacker and the target have similar level of computational power, the attacker must exhaust his/her resource in order to exhaust that of the target. Matsuura, Imai Revised signature mode for IKE [Page 6] INTERNET DRAFT March 31, 1999 6. References [HC97] D. Harkins and D. Carrel, "The Internet Key Exchange", RFC 2409, November 1998. [MI98] K. Matsuura and H. Imai, "Protection of Authenticated Key- Agreement Protocol against a Denial-of-Service Attack", In Proc. of 1998 International Symposium on Information Theory and Its Applications (ISITA'98), pp.466-470, October 1998. [MI99] K. Matsuura and H. Imai, "Resolution of ISAKMP/Oakley Key-Agreement Protocol Resistant against Denial-of-Service Attack", In Pre-proc. of Internet Workshop'99, pp.17-24, February 1999. [Z97] Y. Zheng, "Digital Signcryption or How to Achieve Cost(Signature & Encryption) << Cost(Signature) + Cost(Encryption)", Lecture Notes in Computer Science 1294, pp.165-179. Springer-Verlag. August 1997. [K93] D. W. Kravitz, "Digital signature algorithm", U. S. Patent #5,231,668, July 1993. [FIPS94] FIPS 186, "Digital Signature Standard", Federal Information Processing Standards Publication FIPS PUB 186, U. S. Department of Commerce/N.I.S.T., 1994. [PS96] D. Pointcheval and J. Stern, "Security Proofs for Signature Schemes", Lecture Notes in Computer Science 1070, pp.387-398. Springer-Verlag. 1996. [S91] C. P. Schnorr, "Efficient Signature Generation by Smart Cards", Journal of Cryptology, vol.4, pp.161-174, 1991. Authors' Addresses: ==================== Kanta Matsuura Institute of Industrial Science, University of Tokyo Roppongi 7-22-1, Minato-ku Tokyo 106-8558, JAPAN Tel. +81-3-3402-6231 (ext. 2325) kanta@iis.u-tokyo.ac.jp Hideki Imai Institute of Industrial Science, University of Tokyo Roppongi 7-22-1, Minato-ku Tokyo 106-8558, JAPAN Tel. +81-3-3402-6231 (ext. 2313) imai@iis.u-tokyo.ac.jp Expires October 1999 [Page 7]