increased time it takes to exchange symmetric keys when increasing
the length of public keys. It is important to avoid choosing
unfeasibly long public keys.
3.1. Diffie-Hellman Key Exchange
A Diffie-Hellman key exchange is done with a finite cyclic group G
with a generator g and an exponent x. As noted in the Pollard’s rho
method section, the exponent has twice as many bits as are needed for
the final key. Let the size of the group G be p, let the number of
bits in the base 2 representation of p be j, and let the number of
bits in the exponent be K.
In doing the operations that result in a shared key, a generator is
raised to a power. The most efficient way to do this involves
squaring a number K times and multiplying it several times along the
way. Each of the numbers has j/w computer words in it, where w is
the number of bits in a computer word (today that will be 32 or 64
bits). A naive assumption is that you will need to do j squarings
and j/2 multiplies; fortunately, an efficient implementation will
need fewer (NB: for the remainder of this section, n represents j/w).
A squaring operation does not need to use quite as many operations as
a multiplication; a reasonable estimate is that squaring takes .6 the
number of machine instructions of a multiply. If one prepares a
table ahead of time with several values of small integer powers of
the generator g, then only about one fifth as many multiplies are
needed as the naive formula suggests. Therefore, one needs to do the
work of approximately .8*K multiplies of n-by-n word numbers.
Further, each multiply and squaring must be followed by a modular
reduction, and a good assumption is that it is as hard to do a
modular reduction as it is to do an n-by-n word multiply. Thus, it
takes K reductions for the squarings and .2*K reductions for the
multiplies. Summing this, the total effort for a Diffie-Hellman key
exchange with K bit exponents and a modulus of n words is
approximately 2*K n-by-n-word multiplies.
For 32-bit processors, integers that use less than about 30 computer
words in their representation require at least n^2 instructions for
an n-by-n-word multiply. Larger numbers will use less time, using
Karatsuba multiplications, and they will scale as about n^(1.58) for
larger n, but that is ignored for the current discussion. Note that
64-bit processors push the "Karatsuba cross-over" number out to even
more bits.
The basic result is: if you double the size of the Diffie-Hellman
modular exponentiation group, you quadruple the number of operations
needed for the computation.
3.1.1. Diffie-Hellman with elliptic curve groups
Note that the ratios for computation effort as a function of modulus
size hold even if you are using an elliptic curve (EC) group for
Diffie-Hellman. However, for equivalent security, one can use
smaller numbers in the case of elliptic curves. Assume that someone
has chosen an modular exponentiation group with an 2048 bit modulus
as being an appropriate security measure for a Diffie-Hellman
application and wants to determine what advantage there would be to
using an EC group instead. The calculation is relatively
straightforward, if you assume that on the average, it is about 20
times more effort to do a squaring or multiplication in an EC group
than in a modular exponentiation group. A rough estimate is that an
EC group with equivalent security has about 200 bits in its
representation. Then, assuming that the time is dominated by n-by-n-
word operations, the relative time is computed as:
((2048/200)^2)/20 ~= 5
showing that an elliptic curve implementation should be five times as
fast as a modular exponentiation implementation.
3.2. RSA encryption and decryption
Assume that an RSA public key uses a modulus with j bits; its factors
are two numbers of about j/2 bits each. The expected computation
time for encryption and decryption are different. As before, we
denote the number of words in the machine representation of the
modulus by the symbol n.
Most implementations of RSA use a small exponent for encryption. An
encryption may involve as few as 16 squarings and one multiplication,
using n-by-n-word operations. Each operation must be followed by a
modular reduction, and therefore the time complexity is about 16*(.6
+ 1) + 1 + 1 ~= 28 n-by-n-word multiplies.
RSA decryption must use an exponent that has as many bits as the
modulus, j. However, the Chinese Remainder Theorem applies, and all
the computations can be done with a modulus of only n/2 words and an
exponent of only j/2 bits. The computation must be done twice, once
for each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)-
word multiplies. Because multiplying numbers with n/2 words is only
1/4 as difficult as multiplying numbers with n words, the equivalent
effort for RSA decryption is j/4 n-by-n-word multiplies.
If you double the size of the modulus for RSA, the n-by-n multiplies
will take four times as long. Further, the decryption time doubles
because the exponent is larger. The overall scaling cost is a factor
of 4 for encryption, a factor of 8 for decryption.
3.3. Real-world examples
To make these numbers more real, here are a few examples of software
implementations run on hardware that was current as of a few years
before the publication of this document. The examples are included
to show rough estimates of reasonable implementations; they are not
benchmarks. As with all software, the performance will depend on the
exact details of specialization of the code to the problem and the
specific hardware.
The best time informally reported for a 1024-bit modular
exponentiation (the decryption side of 2048-bit RSA), is 0.9 ms
(about 450,000 CPU cycles) on a 500 MHz Itanium processor. This
shows that newer processors are not losing ground on big number
operations; the number of instructions is less than a 32-bit
processor uses for a 256-bit modular exponentiation.
For less advanced processors timing, the following two tables
(computed by Tero Monenen at SSH Communications) for modular
exponentiation, such as would be done in a Diffie-Hellman key
exchange.
Celeron 400 MHz; compiled with GNU C compiler, optimized, some
platform specific coding optimizations:
group modulus exponent time
type size size
mod 768 ~150 18 msec
mod 1024 ~160 32 msec
mod 1536 ~180 82 msec
ecn 155 ~150 35 msec
ecn 185 ~200 56 msec
The group type is from [RFC2409] and is either modular exponentiation
("mod") or elliptic curve ("ecn"). All sizes here and in subsequent
tables are in bits.
Alpha 500 MHz compiled with Digital’s C compiler, optimized, no
platform specific code:
group modulus exponent time
type size size
mod 768 ~150 12 msec
mod 1024 ~160 24 msec
mod 1536 ~180 59 msec
ecn 155 ~150 20 msec
ecn 185 ~200 27 msec
The following two tables (computed by Eric Young) were originally for
RSA signing operations, using the Chinese Remainder representation.
For ease of understanding, the parameters are presented here to show
the interior calculations, i.e., the size of the modulus and exponent
used by the software.
Dual Pentium II-350:
equiv equiv equiv
modulus exponent time
size size
256 256 1.5 ms
512 512 8.6 ms
1024 1024 55.4 ms
2048 2048 387 ms
Alpha 264 600mhz:
equiv equiv equiv
modulus exponent time
size size
512 512 1.4 ms
Recent chips that accelerate exponentiation can perform 1024-bit
exponentiations (1024 bit modulus, 1024 bit exponent) in about 3
milliseconds or less.
4. Equivalences of Key Sizes
In order to determine how strong a public key is needed to protect a
particular symmetric key, you first need to determine how much effort
is needed to break the symmetric key. Many Internet security
protocols require the use of TripleDES for strong symmetric
encryption, and it is expected that the Advanced Encryption Standard
(AES) will be adopted on the Internet in the coming years.
Therefore, these two algorithms are discussed here. In this section,
for illustrative purposes, we will implicitly assume that the system
security requirement is 112 bits; this doesn’t mean that 112 bits is
recommended. In fact, 112 bits is arguably too strong for any
practical purpose. It is used for illustration simply because that
is the upper bound on the strength of TripleDES.
If one could simply determine the number of MYs it takes to break
TripleDES, the task of computing the public key size of equivalent
strength would be easy. Unfortunately, that isn’t the case here
because there are many examples of DES-specific hardware that encrypt
faster than DES in software on a standard CPU. Instead, one must
determine the equivalent cost for a system to break TripleDES and a
system to break the public key protecting a TripleDES key.
In 1998, the Electronic Frontier Foundation (EFF) built a DES-
cracking machine [GIL98] for US$130,000 that could test about 1e11
DES keys per second (additional money was spent on the machine’s
design). The machine’s builders fully admit that the machine is not
well optimized, and it is estimated that ten times the amount of
money could probably create a machine about 50 times as fast.
Assuming more optimization by guessing that a system to test
TripleDES keys runs about as fast as a system to test DES keys, so
approximately US$1 million might test 5e12 TripleDES keys per second.
In case your adversaries are much richer than EFF, you may want to
assume that they have US$1 trillion, enough to test 5e18 keys per
second. An exhaustive search of the effective TripleDES space of
2^112 keys with this quite expensive system would take about 1e15
seconds or about 33 million years. (Note that such a system would
also need 2^60 bytes of RAM [MH81], which is considered free in this
calculation). This seems a needlessly conservative value. However,
if computer logic speeds continue to increase in accordance with
Moore’s Law (doubling in speed every 1.5 years), then one might
expect that in about 50 years, the computation could be completed in
only one year. For the purposes of illustration, this 50 year
resistance against a trillionaire is assumed to be the minimum
security requirement for a set of applications.
If 112 bits of attack resistance is the system security requirement,
then the key exchange system for TripleDES should have equivalent
difficulty; that is to say, if the attacker has US$1 trillion, you
want him to spend all his money to buy hardware today and to know
that he will "crack" the key exchange in not less than 33 million
years. (Obviously, a rational attacker would wait for about 45 years
before actually spending the money, because he could then get much
better hardware, but all attackers benefit from this sort of wait
equally.)
It is estimated that a typical PC CPU of just a few years ago can
generate over 500 MIPs and could be purchased for about US$100 in
quantity; thus you get more than 5 MIPs/US$. Again, this number
doubles about every 18 months. For one trillion US dollars, an
attacker can get 5e12 MIP years of computer instructions on that
recent-vintage hardware. This figure is used in the following
estimates of equivalent costs for breaking key exchange systems.
4.1. Key equivalence against special purpose brute force hardware
If the trillionaire attacker is to use conventional CPU’s to "crack"
a key exchange for a 112 bit key in the same time that the special
purpose machine is spending on brute force search for the symmetric
key, the key exchange system must use an appropriately large modulus.
Assume that the trillionaire performs 5e12 MIPs of instructions per
year. Use the following equation to estimate the modulus size to use
with RSA encryption or DH key exchange:
5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
n = 10^(625) = 2^(2077)
Thus, assuming similar logic speeds and the current efficiency of the
number field sieve, moduli with about 2100 bits will have about the
same resistance against attack as an 112-bit TripleDES key. This
indicates that RSA public key encryption should use a modulus with
around 2100 bits; for a Diffie-Hellman key exchange, one could use a
slightly smaller modulus, but it is not a significant difference.
4.2 Key equivalence against conventional CPU brute force attack
An alternative way of estimating this assumes that the attacker has a
less challenging requirement: he must only "crack" the key exchange
in less time than a brute force key search against the symmetric key
would take with general purpose computers. This is an "apples-to-
apples" comparison, because it assumes that the attacker needs only
to have computation donated to his effort, not built from a personal
or national fortune. The public key modulus will be larger than the
one in 4.1, because the symmetric key is going to be viable for a
longer period of time.
Assume that the number of CPU instructions to encrypt a block of
material using TripleDES is 300. The estimated number of computer
instructions to break 112 bit TripleDES key:
300 * 2^112
= 1.6 * 10^(36)
= .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving this approximately for n yields:
n = 10^(734) = 2^(2439)
Thus, for general purpose CPU attacks, you can assume that moduli
with about 2400 bits will have about the same strength against attack
as an 112-bit TripleDES key. This indicates that RSA public key
encryption should use a modulus with around 2400 bits; for a Diffie-
Hellman key exchange, one could use a slightly smaller modulus, but
it not a significant difference.
Note that some authors assume that the algorithms underlying the
number field sieve will continue to get better over time. These
authors recommend an even larger modulus, over 4000 bits, for
protecting a 112-bit symmetric key for 50 years. This points out the
difficulty of long-term cryptographic security: it is all but
impossible to predict progress in mathematics and physics over such a
long period of time.
4.3. A One Year Attack: 80 bits of strength
Assuming a trillionaire spends his money today to buy hardware, what
size key exchange numbers could he "crack" in one year? He can
perform 5*e12 MYs of instructions, or
3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))
Solving for an approximation of n yields
n = 10^(360) = 2^(1195)
This is about as many operations as it would take to crack an 80-bit
symmetric key by brute force.
Thus, for protecting data that has a secrecy requirement of one year
against an incredibly rich attacker, a key exchange modulus with
about 1200 bits protecting an 80-bit symmetric key is safe even
against a nation’s resources.
4.4. Key equivalence for other ciphers
Extending this logic to the AES is straightforward. For purposes of
estimation for key searching, one can think of the 128-bit AES as
being at least 16 bits stronger than TripleDES but about three times
as fast. The time and cost for a brute force attack is approximately
2^(16) more than for TripleDES, and thus, under the assumption that
128 bits of strength is the desired security goal, the recommended
key exchange modulus size is about 700 bits longer.
If it is possible to design hardware for AES cracking that is
considerably more efficient than hardware for DES cracking, then
(again under the assumption that the key exchange strength must match
the brute force effort) the moduli for protecting the key exchange
can be made smaller. However, the existence of such designs is only
a matter of speculation at this early moment in the AES lifetime.
The AES ciphers have key sizes of 128 bits up to 256 bits. Should a
prudent minimum security requirement, and thus the key exchange
moduli, have similar strengths? The answer to this depends on whether
or not one expect Moore’s Law to continue unabated. If it continues,
one would expect 128 bit keys to be safe for about 60 years, and 256
bit keys would be safe for another 400 years beyond that, far beyond
any imaginable security requirement. But such progress is difficult
to predict, as it exceeds the physical capabilities of today’s
devices and would imply the existence of logic technologies that are
unknown or infeasible today. Quantum computing is a candidate, but
too little is known today to make confident predictions about its
applicability to cryptography (which itself might change over the
next 100 years!).
If Moore’s Law does not continue to hold, if no new computational
paradigms emerge, then keys of over 100 bits in length might well be
safe "forever". Note, however that others have come up with
estimates based on assumptions of new computational paradigms
emerging. For example, Lenstra and Verheul’s web-based paper
"Selecting Cryptographic Key Sizes" chooses a more conservative
analysis than the one in this document.
4.5. Hash functions for deriving symmetric keys from public key
algorithms
The Diffie-Hellman algorithm results in a key that is hundreds or
thousands of bits long, but ciphers need far fewer bits than that.
How can one distill a long key down to a short one without losing
strength?
Cryptographic one-way hash functions are the building blocks for
this, and so long as they use all of the Diffie-Hellman key to derive
each block of the symmetric key, they produce keys with sufficient
strength.
The usual recommendation is to use a good one-way hash function
applied to he base material (the result of the key exchange) and to
use a subset of the hash function output for the key. However, if
the desired key length is greater than the output of the hash
function, one might wonder how to reconcile the two.
The step of deriving extra key bits must satisfy these requirements:
- The bits must not reveal any information about the key exchange
secret
- The bits must not be correlated with each other
- The bits must depend on all the bits of the key exchange secret
Any good cryptographic hash function satisfies these three
requirements. Note that the number of bits of output of the hash
function is not specified. That is because even a hash function with
a very short output can be iterated to produce more uncorrelated bits
with just a little bit of care.
For example, SHA-1 has 160 bits of output. For deriving a key of
attack resistance of 160 bits or less, SHA(DHkey) produces a good
symmetric key.
Suppose one wants a key with attack resistance of 160 bits, but it is
to be used with a cipher that uses 192 bit keys. One can iterate
SHA-1 as follows:
Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00)
(that is, concatenate a single octet of value 0x00 to
the right side of the DHkey, and then hash)
Bits 161-192 of the symmetric key = K2 =
select_32_bits(SHA(K1 | 0x01))
But what if one wants 192 bits of strength for the cipher? Then the
appropriate calculation is
Bits 1-160 of the symmetric key = SHA(0x00 | DHkey)
Bits 161-192 of the symmetric key =
select_32_bits(SHA(0x01 | DHkey))
(Note that in the description above, instead of concatenating a full
octet, concatenating a single bit would also be sufficient.)
The important distinction is that in the second case, the DH key is
used for each part of the symmetric key. This assures that entropy
of the DH key is not lost by iteration of the hash function over the
same bits.
From an efficiency point of view, if the symmetric key must have a
great deal of entropy, it is probably best to use a cryptographic
hash function with a large output block (192 bits or more), rather
than iterating a smaller one.
Newer hash algorithms with longer output (such as SHA-256, SHA-384,
and SHA-512) can be used with the same level of security as the
stretching algorithm described above.
4.6. Importance of randomness
Some of the calculations described in this document require random
inputs; for example, the secret Diffie-Hellman exponents must be
chosen based on n truly random bits (where n is the system security
requirement). The number of truly random bits is extremely important
to determining the strength of the output of the calculations. Using
truly random numbers is often overlooked, and many security
applications have been significantly weakened by using insufficient
random inputs. A much more complete description of the importance of
random numbers can be found in [ECS].
5. Conclusion
In this table it is assumed that attackers use general purpose
computers, that the hardware is purchased in the year 2000, and that
mathematical knowledge relevant to the problem remains the same as
today. This is an pure "apples-to-apples" comparison demonstrating
how the time for a key exchange scales with respect to the strength
requirement. The subgroup size for DSA is included, if that is being
used for supporting authentication as part of the protocol; the DSA
modulus must be as long as the DH modulus, but the size of the "q"
subgroup is also relevant.
+-------------+-----------+--------------+--------------+
| System | | | |
| requirement | Symmetric | RSA or DH | DSA subgroup |
| for attack | key size | modulus size | size |
| resistance | (bits) | (bits) | (bits) |
| (bits) | | | |
+-------------+-----------+--------------+--------------+
| 70 | 70 | 947 | 129 |
| 80 | 80 | 1228 | 148 |
| 90 | 90 | 1553 | 167 |
| 100 | 100 | 1926 | 186 |
| 150 | 150 | 4575 | 284 |
| 200 | 200 | 8719 | 383 |