RFC 3766

Determining Strengths For Public Keys Used For Exchanging Symmetric Keys

📅 published April 2004, from ietf

RFC 3766 🎀

Okay bestie, let's get into RFC 3766! It's called Determining Strengths For Public Keys Used For Exchanging Symmetric Keys 🦋 It's a Best Current Practice (that's BCP 86) 💅 H. Orman from Purple Streak Dev. and P. Hoffman from the VPN Consortium wrote it, and it's dated April 2004 🌸 It doesn't list anything it obsoletes or updates, so it stands on its own ✨

This is part 1 of 5, so more is coming! 🫶

Status of this Memo ✨

So this doc is a Best Current Practice for the Internet Community 🌈 It's also asking people for discussion and suggestions on how to make it better. The memo can be distributed with no limits, so share it with everyone 💖

Copyright (C) The Internet Society (2004). All Rights Reserved.

Abstract 🌸

Okay so picture this: implementors building systems that use public key cryptography to exchange symmetric keys need to make those public keys hold up against some predetermined level of attack 🛡️ That level is the strength of the system, and the symmetric keys being exchanged have to be at least as strong as what the system requires. The three numbers (system strength, symmetric key strength, and public key strength) have to be consistently matched for any network protocol usage. No cap, all three need to line up 💅

Expressing the system requirement as a symmetric key length is pretty easy, and you just pick a cipher whose key length meets or beats it. Picking a public key that's strong enough to match the symmetric requirement is way harder 😭 This document explains how to work out the length of an asymmetric key from a symmetric key strength requirement. It also gives some rules of thumb for estimating how much resistance an algorithm has against large-scale attacks 🧚 Plus it covers how changing the sizes of the big integers (moduli, group sizes, exponents, and so on) changes how long the algorithms take to do 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 🔐

Okay so loads of books on cryptography and security explain why you need to swap symmetric keys in public, and they list all the algorithms people use for it. But honestly, not many of them explain how the strength of the public keys and the strength of the symmetric keys are connected 🙈

Let's make it make sense with a house 🏠 Picture a house with a strong lock on the front door. Right next to it is a tiny lockbox that holds the key to the front door 🗝️ A would-be burglar has two ways in: attack the lock on the front door, or attack the lock on the lockbox to grab the key. The burglar is obviously better off going after whichever lock is weaker 💀 So the homeowner has to make sure that adding that second way in (the lockbox with the front door key) is at least as strong as the front door lock. Otherwise they're making the burglar's life easier, and we don't do that here 🙅‍♀️

An implementor designing a system that swaps symmetric keys with public key cryptography has to make the same kind of call 🧠 Say an attacker wants to read a message encrypted with a symmetric key, and that symmetric key was exchanged between the sender and recipient using public key cryptography. The attacker has two options to recover the message: brute-force guessing at the symmetric key over and over, or doing the math to find the private key used as the key exchange key 🧮 A smart attacker picks whichever of those two problems is easier 🎯

Now, a simple-minded fix would be to make sure the key exchange is always way stronger than the symmetric key, and you can do that by using a super long public key 🐢 But that's usually not a good idea, because key exchanges get way more expensive in processing time as the public keys get longer 😩 So the implementor has to try to match how hard it is to attack the symmetric key with how hard it is to attack the public key encryption ⚖️ You can skip this whole analysis if the key exchange could be done with extreme security for basically zero cost in elapsed time or CPU effort. Sadly, that's not where public key methods are today 💔

A third thing to think about is the minimum security requirement of the user 👤 Let's say the user is encrypting with CAST-128 and needs a symmetric key that resists brute-force attack for 20 years 🕰️ They might start by picking a key with 86 random bits. Then they can use a one-way function like SHA-1 to "boost" that up to a block of 160 bits, and take 128 of those bits as the key for CAST-128. In that case, the key exchange algorithm only needs to match the difficulty of 86 bits, not 128 bits ✨ Bestie, that's a glow-up for the budget!

Here's the selection procedure 📝

  1. First, figure out the attack resistance the application's security requirements actually need 🎯 To do that, estimate the minimum number of computer operations the attacker will be forced to do in order to compromise the system, then take the base-two logarithm of that number. Call that logarithm value "n".

A 1996 report recommended 90 bits as a good all-around choice for system security 💜 That 90 bit number should go up by about 2/3 bit per year, which works out to about 96 bits in 2005 📈

  1. Next, choose a symmetric cipher with a key of at least n bits, and at least that much cryptanalytic strength 🔑
  2. Then choose a key exchange algorithm with a resistance to attack of at least n bits 🤝

A fourth thing might be the public key authentication method used to establish a user's identity 🪪 That could be an RSA digital signature or a DSA digital signature. If the modulus for the authentication method isn't big enough, the whole basis for trusting the communication might fall apart 😱 So we add one more step:

  1. Choose an authentication algorithm with a resistance to attack of at least n bits. This makes sure a similar key exchanged can't be forged between the two parties during the secrecy lifetime of the encrypted material 🔒 This may not be strictly necessary if the authentication keys get changed frequently and have a well-understood usage lifetime. But if you're not doing that, the n bit guidance is still sound 🫶

1.1. The key exchange algorithms 🧚

Okay so the Diffie-Hellman method uses a group, a generator, and exponents 🌸 In today's Internet standards, the group operation is based on modular multiplication. The group is defined by the multiplicative group of an integer, usually a prime p = 2q + 1, where q is also a prime, and all the arithmetic is done modulo p. The generator, which is often just 2, is written as g ✨

With Diffie-Hellman, Alice and Bob first agree on the values of g and p (either in public or in private) 🤍 Alice picks a secret large random integer a, and Bob picks a secret random large integer b. Then:

Alice sends Bob:  A = g^a mod p
Bob sends Alice:  B = g^b mod p

Next, Alice computes B^a mod p, and Bob computes A^b mod p. These two numbers come out equal 🥹 The participants then use a simple function of that number as the symmetric key k 🗝️

Note that Diffie-Hellman key exchange can be done over different kinds of group representations 🦋 For example, elliptic curves defined over finite fields are a particularly efficient way to compute the key exchange [SCH95].

For RSA key exchange, assume Bob has a public key m, which is equal to p*q, where p and q are two secret prime numbers. He also has 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 then the two parties use k as their symmetric key 🎉 Bob's encryption exponent e can be pretty small (like 17 bits), but his decryption exponent d will have as many bits in it as m does 🧠

2. Determining the Effort to Factor ✨

Okay so bestie, 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 way 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. Actually, 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 ✨

Okay so in August of 2003, a design for a special-purpose "sieving machine" called (TWIRL) dropped [Shamir2003] 😭, and it totally changed the cost estimates for factoring numbers up to 1024 bits. By stacking tons of high-speed VLSI components in parallel, a machine like this might sieve 512-bit numbers in 10 minutes for about $10K of hardware. A bigger version could sieve a 1024-bit number in one year for $10M. The work also cites some advances in how the row reduction step is done, and it concludes that the security of 1024-bit RSA moduli is doubtful 💀

The time and cost estimates for factoring 512-bit and 1024-bit numbers line up with a speed-up factor of about 2 million over what commodity processors could do a few years earlier 🔥

3. Compute Time for the Algorithms ⏱️

This section is all about how long the algorithms take to do key exchanges. Bestie, remember that when you make public keys longer, exchanging symmetric keys takes longer too, so it's important not to pick unfeasibly long public keys 🙅

3.1. Diffie-Hellman Key Exchange 💖

A Diffie-Hellman key exchange is done with a finite cyclic group G, 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.

To get a shared key, a generator gets 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 number has j/w computer words in it, where w is the number of bits in a computer word (today that's 32 or 64 bits). A naive assumption is that you'll need to do j squarings and j/2 multiplies, but fortunately an efficient implementation needs fewer of them. (NB: for the rest of this section, n represents j/w.)

Squaring doesn't need quite as many operations as a multiplication. A reasonable estimate is that squaring takes .6 the number of machine instructions of a multiply. If you prepare a table ahead of time with several values of small integer powers of the generator g, then you only need about one fifth as many multiplies as the naive formula suggests. So you need to do the work of approximately .8*K multiplies of n-by-n word numbers. Also, every multiply and squaring has to be followed by a modular reduction, and a good assumption is that a modular reduction is as hard as an n-by-n word multiply. That means K reductions for the squarings and .2*K reductions for the multiplies. Adding it all up, 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 need at least n^2 instructions for an n-by-n-word multiply. Larger numbers take less time thanks to Karatsuba multiplications, and they scale as about n^(1.58) for larger n, but that's ignored for this discussion. Also, 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 🦋

The ratios for computation effort as a function of modulus size still hold even if you're using an elliptic curve (EC) group for Diffie-Hellman. However, for equivalent security, you can use smaller numbers with elliptic curves. Say someone has picked a modular exponentiation group with a 2048 bit modulus as an appropriate security measure for a Diffie-Hellman application, and they want to know what advantage they'd get from using an EC group instead. The calculation is pretty straightforward if you assume that, on average, a squaring or multiplication in an EC group takes about 20 times more effort 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 the time is dominated by n-by-n-word operations, the relative time is computed as:

((2048/200)^2)/20 ~= 5

which shows that an elliptic curve implementation should be five times as fast as a modular exponentiation implementation ✨

3.2. RSA encryption and decryption 🔐

Assume an RSA public key uses a modulus with j bits. Its factors are two numbers of about j/2 bits each. The expected computation times 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 has to be followed by a modular reduction, so the time complexity is about 16*(.6 + 1) + 1 + 1 ~= 28 n-by-n-word multiplies.

RSA decryption has to use an exponent with as many bits as the modulus, j. However, the Chinese Remainder Theorem applies, so all the computations can be done with a modulus of only n/2 words and an exponent of only j/2 bits. The computation has to 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 take four times as long. The decryption time also doubles because the exponent is larger. So the overall scaling cost is a factor of 4 for encryption and a factor of 8 for decryption 🍓

3.3. Real-world examples 🌸

To make these numbers feel more real, here are a few examples of software implementations run on hardware that was current a few years before this document was published. The examples show rough estimates of reasonable implementations. They are not benchmarks! As with all software, the performance depends on the exact details of how the code is specialized to the problem and on 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 aren't 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, the following two tables were computed by Tero Monenen at SSH Communications for modular exponentiation, the kind you'd do 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 were computed by Eric Young and 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 do 1024-bit exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 milliseconds or less. Honestly, that's giving speed 🚀

4. Equivalences of Key Sizes ✨

okay so before we can pick a public key size, we need to know how much work it takes to break the symmetric key it protects 🔐 Lots of Internet security protocols use TripleDES for strong symmetric encryption, and AES is expected to get adopted on the Internet in the coming years 🎀 So those are the two we're looking at. In this section we're just assuming the system security requirement is 112 bits, for illustration 🌸 That does NOT mean 112 bits is recommended! ngl 112 bits is arguably way too strong for any practical purpose 💅 We only use it because it's the upper bound on how strong TripleDES can get.

If we could just work out how many MYs it takes to break TripleDES, figuring out the size of an equivalent-strength public key would be super easy 😌 But it's not that simple, because there are tons of DES-specific hardware examples that encrypt faster than DES does in software on a standard CPU 🤯 So instead we have to figure out the equivalent cost for one system to break TripleDES and another system to break the public key that protects a TripleDES key. Two different battles, bestie ⚔️

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 (extra money was spent on the machine's design too 💸). The builders fully admit the machine isn't well optimized 🙈 It's estimated that ten times the money could probably make a machine about 50 times as fast. So if we assume more optimization, by guessing that a system testing TripleDES keys runs about as fast as one testing DES keys, then approximately US$1 million might test 5e12 TripleDES keys per second 🔥

In case your adversaries are way richer than EFF, you might want to assume 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 😭 (Also, a system like that would need 2^60 bytes of RAM [MH81], which is considered free in this calculation 🧚.) This seems needlessly conservative, honestly. BUT, if computer logic speeds keep increasing in line with Moore's Law (doubling in speed every 1.5 years), then one might expect that in about 50 years, the computation could be finished 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's to say, if the attacker has US$1 trillion, you want him to spend all his money on 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 about 45 years before actually spending the money, because by then he could get much better hardware. But all attackers benefit from this sort of wait equally 🙃)

It's estimated that a typical PC CPU from just a few years ago can generate over 500 MIPs and could be purchased for about US$100 in quantity. So 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 gets used in the following estimates of equivalent costs for breaking key exchange systems 🫶

4.1. Key equivalence against special purpose brute force hardware

okay, so if the trillionaire attacker wants to use conventional CPUs to "crack" a key exchange for a 112 bit key in the same time the special purpose machine spends brute-forcing the symmetric key, the key exchange system has to use an appropriately large modulus 🧠 Assume the trillionaire performs 5e12 MIPs of instructions per year. Then use this 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 gives:

n = 10^(625) = 2^(2077)

So, 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 shows that RSA public key encryption should use a modulus with around 2100 bits. For a Diffie-Hellman key exchange, you could use a slightly smaller modulus, but it's not a significant difference 🌈

4.2 Key equivalence against conventional CPU brute force attack

okay this one is giving "apples-to-apples" energy 🍎 It assumes the attacker has an easier job: they only have to "crack" the key exchange in less time than a brute force key search against the symmetric key would take with general purpose computers. That's a fair comparison, because the attacker only needs computation donated to their effort, not a personal or national fortune 🫧 The public key modulus will be bigger than the one in 4.1, because the symmetric key is going to stay viable for a longer period of time ⏳

Assume the number of CPU instructions to encrypt a block of material using TripleDES is 300. The estimated number of computer instructions to break a 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 gives:

n = 10^(734) = 2^(2439)

So, for general purpose CPU attacks, you can assume that moduli with about 2400 bits will have about the same strength against attack as a 112-bit TripleDES key 💜 This shows RSA public key encryption should use a modulus with around 2400 bits. For a Diffie-Hellman key exchange, you could use a slightly smaller modulus, but it's not a significant difference ✨

Note that some authors assume the algorithms underlying the number field sieve will keep getting 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's 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

okay, pause and imagine it: a trillionaire spends their money today on hardware. What size key exchange numbers could they "crack" in one year? 🤔 They 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 gives:

n = 10^(360) = 2^(1195)

That's about as many operations as it would take to crack an 80-bit symmetric key by brute force 😌

So, for protecting data with a secrecy requirement of one year against an incredibly rich attacker, a key exchange modulus of about 1200 bits protecting an 80-bit symmetric key is safe, even against a nation's resources 🛡️🇺🇳 main character energy ✨

4.4. Key equivalence for other ciphers

okay so extending this logic to AES is pretty straightforward 🎀 For estimating key searching, you can think of 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 are approximately 2^(16) more than for TripleDES. So, 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's possible to design hardware for AES cracking that's considerably more efficient than hardware for DES cracking, then (again assuming the key exchange strength has to match the brute force effort) the moduli 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 from 128 bits up to 256 bits. Should a prudent minimum security requirement, and thus the key exchange moduli, have similar strengths? 🤷‍♀️ The answer depends on whether or not you 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 to be safe for another 400 years beyond that, which is far beyond any imaginable security requirement 🚀 But such progress is hard to predict, because it exceeds the physical capabilities of today's devices and would imply 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, and no new computational paradigms emerge, then keys 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" takes a more conservative analysis than the one in this document 🧐💅

4.5. Hash functions for deriving symmetric keys from public key algorithms 🔐

okay so Diffie-Hellman spits out a key that's hundreds or thousands of bits long, but ciphers only want a fraction of that 🥹 so how do you shrink it without losing strength?? 🤔 the answer is cryptographic one-way hash functions 💅 as long as they use ALL of the Diffie-Hellman key to derive each block of the symmetric key, the result is strong enough to slay ✨

the usual move is to run a good one-way hash function over the base material (the result of the key exchange) and then just grab a subset of the hash output for your key. but if you need MORE bits than the hash can output, you're like, wait, how do I reconcile that?? 😭

the step where you derive the extra bits has to hit three 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 meets all three 🫶 also, the hash's output size isn't specified here, because even a hash with a super short output can be iterated to make more uncorrelated bits, as long as you're a little careful about it 🦋

for example, SHA-1 gives you 160 bits of output. if you want a key with attack resistance of 160 bits or less, SHA(DHkey) gives you a good symmetric key 💖

now say you want 160 bits of attack resistance, but the cipher you're using takes 192 bit keys. you can iterate SHA-1 like this 👇

   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 you want 192 bits of strength for the cipher?? 👑 then the right calculation is this one 💅

   Bits 1-160   of the symmetric key = SHA(0x00 | DHkey)
   Bits 161-192 of the symmetric key =
                select_32_bits(SHA(0x01 | DHkey))

(fun fact, the description above says you could concatenate a single bit instead of a full octet, and that would be enough too 🧚)

the big difference is that in the second version, the DH key gets used for EACH part of the symmetric key. that way the entropy of the DH key doesn't get lost by iterating the hash over the same bits 🌈 this is the main thing to get right, bestie 🙈

from an efficiency point of view, if the symmetric key needs a lot of entropy, it's probably best to use a cryptographic hash with a big output block (192 bits or more) instead of iterating a smaller one ✨ newer hash algorithms with longer output, like SHA-256, SHA-384, and SHA-512, can give you the same level of security as the stretching algorithm we just went over 🍓

4.6. Importance of randomness 🎲

some of the calculations in this document need 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 matters SO much for how strong the output of the calculations is. using truly random numbers gets overlooked all the time, and tons of security applications have been seriously weakened by using insufficient random inputs 💀 if you want the full tea on why randomness matters, check out [ECS] 🫶

5. Conclusion 🏁

okay so in this table, we're assuming attackers use general purpose computers, the hardware was bought in the year 2000, and the math knowledge relevant to the problem is the same as it is today 🧠 this is a pure "apples-to-apples" comparison, showing how the time for a key exchange scales with the strength requirement 📈 the DSA subgroup size is included too, in case you're using DSA to support authentication as part of the protocol. the DSA modulus must be as long as the DH modulus, but the size of the "q" subgroup also matters 🔥

   +-------------+-----------+--------------+--------------+
   | 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      |
   |    250      |    250    |    14596     |     482      |
   +-------------+-----------+--------------+--------------+

5.1. TWIRL Correction 🤖

if the TWIRL machine becomes a reality, AND there are advances in parallelism for row reduction in factoring, then conservative estimates would subtract about 11 bits from the system security column of the table 😬 so, to get 89 bits of security, you'd need an RSA modulus of about 1900 bits. it's giving plot twist 🫣

6. Security Considerations 🚨

the equations and values in this document are meant to be as accurate as possible, based on the state of the art in general purpose computers at the time this document was written. no predictions can be completely accurate, and the formulas here are NOT meant to be definitive statements of fact about cryptographic strengths 💀

some of the empirical results used to calibrate the formulas in this document are probably not completely accurate, and that inaccuracy affects the estimates 😩 the authors really hope the numbers here vary from real world experience as little as possible 🙏✨

7. References 📚

7.1. Informational References 🔖

  • [DL] Dodson, B. and A. K. Lenstra, NFS with four large primes: an explosive experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, (1995) 372-385.
  • [ECS] Eastlake, D., Crocker, S. and J. Schiller, "Randomness Recommendations for Security", RFC 1750, December 1994.
  • [GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 pages, May 1998, O'Reilly & Associates; ISBN: 1565925203
  • [GOR93] Gordon, D., "Discrete logarithms in GF(p) using the number field sieve", SIAM Journal on Discrete Mathematics, 6 (1993), 124-138.
  • [LEN93] Lenstra, A. K. and H. W. Lenstra, Jr. (eds), The development of the number field sieve, Lecture Notes in Math, 1554, Springer Verlag, Berlin, 1993.
  • [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467.
  • [ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future of Integer Factorization, A. M. Odlyzko
  • [ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography (1999).
  • [POL78] J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, 32 (1978), 918-924.
  • [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998.
  • [SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 31 August 1995. Springer-Verlag
  • [SHAMIR03] Shamir, Adi and Eran Tromer, "Factoring Large Numbers with the TWIRL Device", Advances in Cryptology - CRYPTO 2003, Springer, Lecture Notes in Computer Science 2729.
  • [SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 - April 2000, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths
  • [SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer, August 1999.

8. Authors' Addresses ✉️

   Hilarie Orman
   Purple Streak Development
   500 S. Maple Dr.
   Salem, UT 84653

   EMail: hilarie@purplestreak.com and ho@alum.mit.edu


   Paul Hoffman
   VPN Consortium
   127 Segre Place
   Santa Cruz, CA  95060 USA

   EMail: paul.hoffman@vpnc.org

Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 🫠

Intellectual Property 🎀

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. 📬

Acknowledgement 🫶

Funding for the RFC Editor function is currently provided by the Internet Society. 💜🌸

📦 where this page comes from