K. Matsuura, H. Imai INTERNET-DRAFT University of Tokyo draft-matsuura-sign-mode-01.txt September 13, 1999 Expires March 13, 2000 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 Phase 1 of the Internet Key Exchange (IKE) [HC98] has several modes with different number of message passes. For those who want to save their bandwidth, 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 this method, however, the responder must pay computational cost as expensive as modular exponentiation BEFORE identifying the initiator. This feature can be abused by malicious initiators for a Denial-of-Service (DoS) attack. The purpose of this document is to solve this problem in digital-signature method by using falling- together (FT) mechanism [MI98], [MI99] in conjunction with stateless-connection technique [AN97] and an appropriate use of Cookies [KS99]. 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]. Expires March 13 2000 [Page 1] INTERNET DRAFT September 13, 1999 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. Although an anti-clogging token Cookie is used, the current IKE version of Cookies fails to meet the explicit requirements for DoS- protection [Si99]. Regarding DoS-protection, a new mode called Base Mode is currently discussed [DB99]. However, it also fails since the responder creates states after receiving the first message. This document describes a simple modification of the IKE Signature Method. The resulting Revised Signature Method provides a deterrent to the DoS attack in a stateless manner. The change from the IKE Signature Method is basically as follows. (2) and (3) are the changes from the previous version of this draft. (1) A random fresh mateial reconstructed by the initiator's heavy computation 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 with inexpensive computation such as keyed hashing. (2) Use of Cookies conforms to [KS99] regarding the statelessness. Matsuura, Imai Revised signature mode for IKE [Page 2] INTERNET DRAFT September 13, 1999 (3) As proposed in [AN97], local symmetric-key encryption is used to implement DH key agreement and FT mechanism in a stateless manner. 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. 3. The new method: Revised Signature Method of IKE Phase 1 Our revised version is described as follows. ===================================================================== Initiator Responder ----------- ----------- HDR, SA, KE, Ni, IDii --> (**1) <-- HDR, SA, KE, Nr, IDir, [ CERT, ] SIG_R, ENC(RF | xr) (**2) HDR, [ CERT, ] HASH_I*, --> SIG_I, ENC(RF | xr), Ni, IDii, SA, Nr (**3) ===================================================================== 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. HDR contains the initiator's Cookie CKY-I. (**1) In the second message (reply from the responder), the responder puts in the R-Cookie a hash of all the information which would otherwise create states. Some of the information is related with generation of the responder's Cookie CKY-R: a private secret, SA, IDii, Ni, Nr and CKY-I, for example (Note 1: the exact technique by which a negotiating party generates a Cookie is implementation dependent. Note 2: the current time and date are NOT included.). Another is related with FT mechanism and KE: RF and xr, as described in the following. When the responder generates SIG_R in the second message, he must use a signature scheme with the following properties: Matsuura, Imai Revised signature mode for IKE [Page 3] INTERNET DRAFT September 13, 1999 + Expensive computation in signature generation can be completed in advance independent of the initiator, i.e., as a pre- computation 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. Desirable algorithms will be described in Section 4. 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. RF is concatenated with a secret parameter xr (if DH public value is g^x) used for KE and then encrypted with a secret key. This key can be used for different requests (i.e., this symmetric encryption does not create a state). The encrypted result is sent to the initiator and then sent back to the responder in the next message. (**2) 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. IDii, Ni, and Nr are copies of what was exchanged in the first two messages. SA is what the responder sent in the reply message. (**3) On receiving the acknowledgment message, the responder first decrypts ENC(RF | xr) and checks the hash in CKY-R by regenerating it from the local secret, the materials contained in the acknowledgment message, and the decrypted materials. If succsessful, the responder checks whether the modified hash really uses the correct RF or not; he computes HASH_I* from the decrypted RF, and then compares it with what is contained in the acknowledgment message. Then, if this is also 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. Matsuura, Imai Revised signature mode for IKE [Page 4] INTERNET DRAFT September 13, 1999 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). + 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]. Matsuura, Imai Revised signature mode for IKE [Page 5] INTERNET DRAFT September 13, 1999 + 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^{xi*xr}. 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. In the following, we evaluate the Revised Signaure Method in terms of DoS resistance. DoS attackers can be classified into two types. One launches completely fake requests while the other pays computational cost necessary for imposing modular exponentiation on the responder. Matsuura, Imai Revised signature mode for IKE [Page 6] INTERNET DRAFT September 13, 1999 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. Another evaluation on a blocking probability of the responder is given in [MI99]. When we can assume an ingress filter or some bandwidth restrictions, the responder is usually alive; the blocking probability is lower than 10% if the number of bogus requests per attack is less than 256. Matsuura, Imai Revised signature mode for IKE [Page 7] INTERNET DRAFT September 13, 1999 6. References [HC98] 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. [AN97] T. Aura and P. Nikander, "Stateless Connections", Lecture Notes in Computer Science 1334, pp.87-97. Springer-Verlag. November 1997. [KS99] P. Karn and W. Simpson, "Photuris: Session-Key Management Protocol", RFC 2522, March 1999. [Si99] W. A. Simpson, "IKE/ISAKMP Considered Dangerous", draft-simpson-danger-isakmp-01.txt, Work In Progress, June 1999. [DB99] Y. Dayan and S. Bitan, "IKE Base Mode", draft-ietf-ipsec-ike- base-mode-00.txt, Work In Progress, June 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. Matsuura, Imai Revised signature mode for IKE [Page 8] INTERNET DRAFT September 13, 1999 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 March 13, 2000 [Page 9]