Request for Comments: 3766 Purple Streak Dev.
BCP: 86 P. Hoffman
Category: Best Current Practice VPN Consortium
April 2004
Determining Strengths For Public Keys Used
For Exchanging Symmetric Keys
Status of this Memo
This document specifies an Internet Best Current Practices for the
Internet Community, and requests discussion and suggestions for
improvements. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
Implementors of systems that use public key cryptography to exchange
symmetric keys need to make the public keys resistant to some
predetermined level of attack. That level of attack resistance is
the strength of the system, and the symmetric keys that are exchanged
must be at least as strong as the system strength requirements. The
three quantities, system strength, symmetric key strength, and public
key strength, must be consistently matched for any network protocol
usage.
While it is fairly easy to express the system strength requirements
in terms of a symmetric key length and to choose a cipher that has a
key length equal to or exceeding that requirement, it is harder to
choose a public key that has a cryptographic strength meeting a
symmetric key strength requirement. This document explains how to
determine the length of an asymmetric key as a function of a
symmetric key strength requirement. Some rules of thumb for
estimating equivalent resistance to large-scale attacks on various
algorithms are given. The document also addresses how changing the
sizes of the underlying large integers (moduli, group sizes,
exponents, and so on) changes the time to use the algorithms for key
exchange.
Table of Contents
1. Model of Protecting Symmetric Keys with Public Keys. . . . . . 2
1.1. The key exchange algorithms . . . . . . . . . . . . . . . 4
2. Determining the Effort to Factor . . . . . . . . . . . . . . . 5
2.1. Choosing parameters for the equation. . . . . . . . . . . 6
2.2. Choosing k from empirical reports . . . . . . . . . . . . 7
2.3. Pollard’s rho method. . . . . . . . . . . . . . . . . . . 7
2.4. Limits of large memory and many machines. . . . . . . . . 8
2.5. Special purpose machines. . . . . . . . . . . . . . . . . 9
3. Compute Time for the Algorithms. . . . . . . . . . . . . . . . 10
3.1. Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . 10
3.1.1. Diffie-Hellman with elliptic curve groups. . . . . 11
3.2. RSA encryption and decryption . . . . . . . . . . . . . . 11
3.3. Real-world examples . . . . . . . . . . . . . . . . . . . 12
4. Equivalences of Key Sizes. . . . . . . . . . . . . . . . . . . 13
4.1. Key equivalence against special purpose brute force
hardware. . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2. Key equivalence against conventional CPU brute force
attack. . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3. A One Year Attack: 80 bits of strength. . . . . . . . . . 16
4.4. Key equivalence for other ciphers . . . . . . . . . . . . 16
4.5. Hash functions for deriving symmetric keys from public
key algorithms. . . . . . . . . . . . . . . . . . . . . . 17
4.6. Importance of randomness. . . . . . . . . . . . . . . . . 19
5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1. TWIRL Correction. . . . . . . . . . . . . . . . . . . . . 20
6. Security Considerations. . . . . . . . . . . . . . . . . . . . 20
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.1. Informational References. . . . . . . . . . . . . . . . . 20
8. Authors’ Addresses . . . . . . . . . . . . . . . . . . . . . . 22
9. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 23
1. Model of Protecting Symmetric Keys with Public Keys
Many books on cryptography and security explain the need to exchange
symmetric keys in public as well as the many algorithms that are used
for this purpose. However, few of these discussions explain how the
strengths of the public keys and the symmetric keys are related.
To understand this, picture a house with a strong lock on the front
door. Next to the front door is a small lockbox that contains the
key to the front door. A would-be burglar who wants to break into
the house through the front door has two options: attack the lock on
the front door, or attack the lock on the lockbox in order to
retrieve the key. Clearly, the burglar is better off attacking the
weaker of the two locks. The homeowner in this situation must make
sure that adding the second entry option (the lockbox containing the
front door key) is at least as strong as the lock on the front door,
in order not to make the burglar’s job easier.
An implementor designing a system for exchanging symmetric keys using
public key cryptography must make a similar decision. Assume that an
attacker wants to learn the contents of a message that is encrypted
with a symmetric key, and that the symmetric key was exchanged
between the sender and recipient using public key cryptography. The
attacker has two options to recover the message: a brute-force
attempt to determine the symmetric key by repeated guessing, or
mathematical determination of the private key used as the key
exchange key. A smart attacker will work on the easier of these two
problems.
A simple-minded answer to the implementor’s problem is to be sure
that the key exchange system is always significantly stronger than
the symmetric key; this can be done by choosing a very long public
key. Such a design is usually not a good idea because the key
exchanges become much more expensive in terms of processing time as
the length of the public keys go up. Thus, the implementor is faced
with the task of trying to match the difficulty of an attack on the
symmetric key with the difficulty of an attack on the public key
encryption. This analysis is not necessary if the key exchange can
be performed with extreme security for almost no cost in terms of
elapsed time or CPU effort; unfortunately, this is not the case for
public key methods today.
A third consideration is the minimum security requirement of the
user. Assume the user is encrypting with CAST-128 and requires a
symmetric key with a resistance time against brute-force attack of 20
years. He might start off by choosing a key with 86 random bits, and
then use a one-way function such as SHA-1 to "boost" that to a block
of 160 bits, and then take 128 of those bits as the key for CAST-128.
In such a case, the key exchange algorithm need only match the
difficulty of 86 bits, not 128 bits.
The selection procedure is:
1. Determine the attack resistance necessary to satisfy the security
requirements of the application. Do this by estimating the
minimum number of computer operations that the attacker will be
forced to do in order to compromise the security of the system and
then take the logarithm base two of that number. Call that
logarithm value "n".
A 1996 report recommended 90 bits as a good all-around choice for
system security. The 90 bit number should be increased by about
2/3 bit/year, or about 96 bits in 2005.
2. Choose a symmetric cipher that has a key with at least n bits and
at least that much cryptanalytic strength.
3. Choose a key exchange algorithm with a resistance to attack of at
least n bits.
A fourth consideration might be the public key authentication method
used to establish the identity of a user. This might be an RSA
digital signature or a DSA digital signature. If the modulus for the
authentication method isn’t large enough, then the entire basis for
trusting the communication might fall apart. The following step is
thus added:
4. Choose an authentication algorithm with a resistance to attack of
at least n bits. This ensures that a similar key exchanged cannot
be forged between the two parties during the secrecy lifetime of
the encrypted material. This may not be strictly necessary if the
authentication keys are changed frequently and they have a well-
understood usage lifetime, but in lieu of this, the n bit guidance
is sound.
1.1. The key exchange algorithms
The Diffie-Hellman method uses a group, a generator, and exponents.
In today’s Internet standards, the group operation is based on
modular multiplication. Here, the group is defined by the
multiplicative group of an integer, typically a prime p = 2q + 1,
where q is a prime, and the arithmetic is done modulo p; the
generator (which is often simply 2) is denoted by g.
In Diffie-Hellman, Alice and Bob first agree (in public or in
private) on the values for g and p. Alice chooses a secret large
random integer (a), and Bob chooses a secret random large integer
(b). Alice sends Bob A, which is g^a mod p; Bob sends Alice B, which
is g^b mod p. Next, Alice computes B^a mod p, and Bob computes A^b
mod p. These two numbers are equal, and the participants use a
simple function of this number as the symmetric key k.
Note that Diffie-Hellman key exchange can be done over different
kinds of group representations. For instance, elliptic curves
defined over finite fields are a particularly efficient way to
compute the key exchange [SCH95].
For RSA key exchange, assume that Bob has a public key (m) which is
equal to p*q, where p and q are two secret prime numbers, and an
encryption exponent e, and a decryption exponent d. For the key
exchange, Alice sends Bob E = k^e mod m, where k is the secret
symmetric key being exchanged. Bob recovers k by computing E^d mod
m, and the two parties use k as their symmetric key. While Bob’s
encryption exponent e can be quite small (e.g., 17 bits), his
decryption exponent d will have as many bits in it as m does.
2. Determining the Effort to Factor
The RSA public key encryption method is immune to brute force
guessing attacks because the modulus (and thus, the secret exponent
d) will have at least 512 bits, and that is too many possibilities to
guess. The Diffie-Hellman exchange is also secure against guessing
because the exponents will have at least twice as many bits as the
symmetric keys that will be derived from them. However, both methods
are susceptible to mathematical attacks that determine the structure
of the public keys.
Factoring an RSA modulus will result in complete compromise of the
security of the private key. Solving the discrete logarithm problem
for a Diffie-Hellman modular exponentiation system will similarly
destroy the security of all key exchanges using the particular
modulus. This document assumes that the difficulty of solving the
discrete logarithm problem is equivalent to the difficulty of
factoring numbers that are the same size as the modulus. In fact, it
is slightly harder because it requires more operations; based on
empirical evidence so far, the ratio of difficulty is at least 20,
possibly as high as 64. Solving either problem requires a great deal
of memory for the last stage of the algorithm, the matrix reduction
step. Whether or not this memory requirement will continue to be the
limiting factor in solving larger integer problems remains to be
seen. At the current time it is not, and there is active research
into parallel matrix algorithms that might mitigate the memory
requirements for this problem.
The number field sieve (NFS) [GOR93] [LEN93] is the best method today
for solving the discrete logarithm problem. The formula for
estimating the number of simple arithmetic operations needed to
factor an integer, n, using the NFS method is:
L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2))
Many people prefer to discuss the number of MIPS years (MYs) that are
needed for large operations such as the number field sieve. For such
an estimation, an operation in the L(n) formula is one computer
instruction. Empirical evidence indicates that 4 or 5 instructions
might be a closer match, but this is a minor factor and this document
sticks with one operation/one instruction for this discussion.
2.1. Choosing parameters for the equation
The expression above has two parameters that can be estimated by
empirical means: k and o(1). For the range of numbers we are
interested in, there is little distinction between them.
One could assume that k is 1 and o(1) is 0. This is reasonably valid
if the expression is only used for estimating relative effort
(instead of actual effort) and one assumes that the o(1) term is very
small over the range of the numbers that are to be factored.
Or, one could assume that o(1) is small and roughly constant and thus
its value can be folded into k; then estimate k from reported amounts
of effort spent factoring large integers in tests.
This document uses the second approach in order to get an estimate of
the significance of the factor. It appears to be minor, based on the
following calculations.
Sample values from recent work with the number field sieve include:
Test name Number of Number of MYs of effort
decimal bits
digits
RSA130 130 430 500
RSA140 140 460 2000
RSA155 155 512 8000
RSA160 160 528 3000
There are few precise measurements of the amount of time used for
these factorizations. In most factorization tests, hundreds or
thousands of computers are used over a period of several months, but
the number of their cycles were used for the factoring project, the
precise distribution of processor types, speeds, and so on are not
usually reported. However, in all the above cases, the amount of
effort used was far less than the L(n) formula would predict if k was
1 and o(1) was 0.
A similar estimate of effort, done in 1995, is in [ODL95].
Results indicating that for the Number Field Sieve factoring method,
the actual number of operations is less than expected, are found in
[DL].
2.2. Choosing k from empirical reports
By solving for k from the empirical reports, it appears that k is
approximately 0.02. This means that the "effective key strength" of
the RSA algorithm is about 5 or 6 bits less than is implied by the
naive application of equation L(n) (that is, setting k to 1 and o(1)
to 0). These estimates of k are fairly stable over the numbers
reported in the table. The estimate is limited to a single
significant digit of k because it expresses real uncertainties;
however, the effect of additional digits would have make only tiny
changes to the recommended key sizes.
The factorers of RSA130 used about 1700 MYs, but they felt that this
was unrealistically high for prediction purposes; by using more
memory on their machines, they could have easily reduced the time to
500 MYs. Thus, the value used in preparing the table above was 500.
This story does, however, underscore the difficulty in getting an
accurate measure of effort. This document takes the reported effort
for factoring RSA155 as being the most accurate measure.
As a result of examining the empirical data, it appears that the L(n)
formula can be used with the o(1) term set to 0 and with k set to
0.02 when talking about factoring numbers in the range of 100 to 200
decimal digits. The equation becomes:
L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
To convert L(n) from simple math instructions to MYs, divide by
3*10^13. The equation for the number of MYs needed to factor an
integer n then reduces to:
MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2))
With what confidence can this formula be used for predicting the
difficulty of factoring slightly larger numbers? The answer is that
it should be a close upper bound, but each factorization effort is
usually marked by some improvement in the algorithms or their
implementations that makes the running time somewhat shorter than the
formula would indicate.
2.3. Pollard’s rho method
In Diffie-Hellman exchanges, there is a second attack, Pollard’s rho
method [POL78]. The algorithm relies on finding collisions between
values computed in a large number space; its success rate is
proportional to the square root of the size of the space. Because of
Pollard’s rho method, the search space in a DH key exchange for the
key (the exponent in a g^a term), must be twice as large as the
symmetric key. Therefore, to securely derive a key of K bits, an
implementation must use an exponent with at least 2*K bits. See
[ODL99] for more detail.
When the Diffie-Hellman key exchange is done using an elliptic curve
method, the NFS methods are of no avail. However, the collision
method is still effective, and the need for an exponent (called a
multiplier in EC’s) with 2*K bits remains. The modulus used for the
computation can also be 2*K bits, and this will be substantially
smaller than the modulus needed for modular exponentiation methods as
the desired security level increases past 64 bits of brute-force
attack resistance.
One might ask, how can you compare the number of computer
instructions really needed for a discrete logarithm attack to the
number needed to search the keyspace of a cipher? In comparing the
efforts, one should consider what a "basic operation" is. For brute
force search of the keyspace of a symmetric encryption algorithm like
DES, the basic operation is the time to do a key setup and the time
to do one encryption. For discrete logs, the basic operation is a
modular squaring. The log of the ratio of these two operations can
be used as a "normalizing factor" between the two kinds of
computations. However, even for very large moduli (16K bits), this
factor amounts to only a few bits of extra effort.
2.4. Limits of large memory and many machines
Robert Silverman has examined the question of when it will be
practical to factor RSA moduli larger than 512 bits. His analysis is
based not only on the theoretical number of operations, but it also
includes expectations about the availability of actual machines for
performing the work (this document is based only on theoretical
number of operations). He examines the question of whether or not we
can expect there be enough machines, memory, and communication to
factor a very large number.
The best factoring methods need a lot of random access memory for
collecting data relations (sieving) and a critical final step that
does a row reduction on a large matrix. The memory requirements are
related to the size of the number being factored (or subjected to
discrete logarithm solution). Silverman [SILIEEE99] [SIL00] has
argued that there is a practical limit to the number of machines and
the amount of RAM that can be brought to bear on a single problem in
the foreseeable future. He sees two problems in attacking a 1024-bit
RSA modulus: the machines doing the sieving will need 64-bit address
spaces and the matrix row reduction machine will need several
terabytes of memory. Silverman notes that very few 64-bit machines
that have the 170 gigabytes of memory needed for sieving have been
sold. Nearly a billion such machines are necessary for the sieving
in a reasonable amount of time (a year or two).
Silverman’s conclusion, based on the history of factoring efforts and
Moore’s Law, is that 1024-bit RSA moduli will not be factored until
about 2037. This implies a much longer lifetime to RSA keys than the
theoretical analysis indicates. He argues that predictions about how
many machines and memory modules will be available can be with great
confidence, based on Moore’s Law extrapolations and the recent
history of factoring efforts.
One should give the practical considerations a great deal of weight,
but in a risk analysis, the physical world is less predictable than
trend graphs would indicate. In considering how much trust to put
into the inability of the computer industry to satisfy the voracious
needs of factorers, one must have some insight into economic
considerations that are more complicated than the mathematics of
factoring. The demand for computer memory is hard to predict because
it is based on applications: a "killer app" might come along any day
and send the memory industry into a frenzy of sales. The number of
processors available on desktops may be limited by the number of
desks, but very capable embedded systems account for more processor
sales than desktops. As embedded systems absorb networking
functions, it is not unimaginable that millions of 64-bit processors
with at least gigabytes of memory will pervade our environment.
The bottom line on this is that the key length recommendations
predicted by theory may be overly conservative, but they are what we
have used for this document. This question of machine availability
is one that should be reconsidered in light of current technology on
a regular basis.
2.5. Special purpose machines
In August of 2003, a design for a special-purpose "sieving machine"
(TWIRL) surfaced [Shamir2003], and it substantially changed the cost
estimates for factoring numbers up to 1024 bits in size. By applying
many high-speed VLSI components in parallel, such a machine might be
able to carry out the sieving of 512-bit numbers in 10 minutes at a
cost of $10K for the hardware. A larger version could sieve a 1024-
bit number in one year for a cost of $10M. The work cites some
advances in approaches to the row reduction step in concluding that
the security of 1024-bit RSA moduli is doubtful.
The estimates for the time and cost for factoring 512-bit and 1024-
bit numbers correspond to a speed-up factor of about 2 million over
what can be achieved with commodity processors of a few years ago.
3. Compute Time for the Algorithms
This section describes how long it takes to use the algorithms to
perform key exchanges. Again, it is important to consider the