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]