Internet DRAFT - draft-matsuura-sign-mode
draft-matsuura-sign-mode
K. Matsuura, H. Imai
INTERNET-DRAFT University of Tokyo
draft-matsuura-sign-mode-02.txt March 2, 2000
Expires September 2, 2000
A revised signature mode for the Internet Key Exchange
<draft-matsuura-sign-mode-02.txt>
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 September 2, 2000 [Page 1]
INTERNET DRAFT March 2, 2000
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 March 2, 2000
(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 in 4.1
and mentions other possibilities in 4.2. Subsection 4.2 is appended
to the previous version of this draft.
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 March 2, 2000
+ 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 March 2, 2000
4. Algorithm
4.1 Examples
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).
Matsuura, Imai Revised signature mode for IKE [Page 5]
INTERNET DRAFT March 2, 2000
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).
4.2 Other Possibilities
In both the examples in 4.1, our design strategy against CPU-
exhaustion is as follows.
+ Find a signature algorithm whose computationally-heavy parts in
verification are performed with the sender's public key while
those in generation does not require the sender's secret key
(i.e., in the signature generation, the sender's secret key is
used in computationally-inexpensive parts while computationally-
heavy parts are independent of entities and therefore pre-
computable).
+ See if the resultant material from the "computationally-heavy
parts in verification" is a random and fresh number or not.
Matsuura, Imai Revised signature mode for IKE [Page 6]
INTERNET DRAFT March 2, 2000
+ If so, include the material as an additional input to the ac-
knowledgment hash.
Other possibilities could be found in the same way. It should be
noted that we do not have to use any plug-ins. Re-define the ac-
knowledgment hash, that's all.
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.
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:
Matsuura, Imai Revised signature mode for IKE [Page 7]
INTERNET DRAFT March 2, 2000
+ 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.
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 Proc. of Internet Workshop'99, IEEE Press, 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.
Matsuura, Imai Revised signature mode for IKE [Page 8]
INTERNET DRAFT March 2, 2000
[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 September 2, 2000 [Page 9]
