idnits 2.17.1 draft-orman-public-key-lengths-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 729 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 2 instances of too long lines in the document, the longest one being 3 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 399 has weird spacing: '... group modul...' == Line 400 has weird spacing: '... type size...' == Line 414 has weird spacing: '... group modul...' == Line 415 has weird spacing: '... type size...' == Line 430 has weird spacing: '...modulus exp...' == (2 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'DL' is defined on line 661, but no explicit reference was found in the text == Unused Reference: 'ODL95' is defined on line 684, but no explicit reference was found in the text == Unused Reference: 'ODL99' is defined on line 687, but no explicit reference was found in the text == Unused Reference: 'SIL99' is defined on line 707, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'DL' -- Possible downref: Non-RFC (?) normative reference: ref. 'GIL98' -- Possible downref: Non-RFC (?) normative reference: ref. 'GOR93' -- Possible downref: Non-RFC (?) normative reference: ref. 'HIFN' -- Possible downref: Non-RFC (?) normative reference: ref. 'LEN93' -- Possible downref: Non-RFC (?) normative reference: ref. 'LEN99' -- Possible downref: Non-RFC (?) normative reference: ref. 'MH81' -- Possible downref: Non-RFC (?) normative reference: ref. 'ODL95' -- Possible downref: Non-RFC (?) normative reference: ref. 'ODL99' -- Possible downref: Non-RFC (?) normative reference: ref. 'POL78' -- Possible downref: Non-RFC (?) normative reference: ref. 'RSA96' -- Possible downref: Non-RFC (?) normative reference: ref. 'RSA99' -- Possible downref: Non-RFC (?) normative reference: ref. 'RSAc99' -- Possible downref: Non-RFC (?) normative reference: ref. 'SCH95' -- Possible downref: Non-RFC (?) normative reference: ref. 'SIL99' -- Possible downref: Non-RFC (?) normative reference: ref. 'TER00' -- Possible downref: Non-RFC (?) normative reference: ref. 'YOU00' Summary: 6 errors (**), 0 flaws (~~), 12 warnings (==), 19 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Hilarie Orman 2 draft-orman-public-key-lengths-01.txt Novell, Inc. 3 August 8, 2000 Paul Hoffman 4 Expires in six months IMC & VPNC 6 Determining Strengths For Public Keys Used 7 For Exchanging Symmetric Keys 9 Status of this memo 11 This document is an Internet-Draft and is in full conformance with all 12 provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering Task 15 Force (IETF), its areas, and its working groups. Note that other 16 groups may also distribute working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet-Drafts as reference 21 material or to cite them other than as "work in progress." 23 The list of current Internet-Drafts can be accessed at 24 http://www.ietf.org/ietf/1id-abstracts.txt 26 The list of Internet-Draft Shadow Directories can be accessed at 27 http://www.ietf.org/shadow.html. 29 Abstract 31 Implementors of systems that use public key cryptography to exchange 32 symmetric keys need to make the public keys resistant to some 33 predetermined level of attack. That level of attack resistance is the 34 strength of the system, and the symmetric keys that are exchanged must 35 be at least as strong as the system strength requirements. The three 36 quantities, system strength, symmetric key strength, and public key 37 strength, must be consistently matched for any network protocol usage. 39 While it is fairly easy to express the system strength requirements in 40 terms of a symmetric key length and to choose a cipher that has a key 41 length equal to or exceeding that requirement, it is harder to choose a 42 public key that has a cryptographic strength meeting a symmetric key 43 strength requirement. This document explains how to determine the 44 length of an asymmetric key as a function of the length of a symmetric 45 key. Some rules of thumb for estimating equivalent resistance to 46 large-scale attacks on various algorithms are given. The document also 47 addresses how changing the sizes of the underlying large integers 48 (moduli, group sizes, exponents, and so on) changes the time to use the 49 algorithms for key exchange. 51 1. Model of Protecting Symmetric Keys with Public Keys 53 Many books on cryptography and security explain the need to exchange 54 symmetric keys in public as well as the many algorithms that are used 55 for this purpose. However, few of these discussions explain how the 56 strengths of the public keys and the symmetric keys are related. 58 To understand this, picture a house with a strong lock on the front 59 door. Next to the front door is a small lockbox that contains the key 60 to the front door. A would-be burglar who wants to break into the house 61 through the front door has two options: attack the lock on the front 62 door, or attack the lock on the lockbox in order to retrieve the key. 63 Clearly, the burglar is better off attacking the weaker of the two 64 locks. The homeowner in this situation must make sure that adding the 65 second entry option (the lockbox containing the front door key) is at 66 least as strong as the lock on the front door in order not to make the 67 burglar's job easier. 69 An implementor designing a system for exchanging symmetric keys using 70 public key cryptography must make a similar decision. Assume that an 71 attacker wants to learn the contents of a message that is encrypted with a 72 symmetric key, and that the symmetric key was exchanged between the 73 sender and recipient using public key cryptography. The attacker has 74 two options to recover the message: a brute-force attempt to determine 75 the symmetric key by repeated guessing, or mathematical determination 76 of the private key used as the key exchange key. A smart attacker will 77 work on the easier of these two problems. 79 A simple-minded answer to the implementor's problem is to be sure that 80 the key exchange system is always significantly stronger than the 81 symmetric key; this can be done by choosing a very long public key. 82 Such a design is usually not a good idea because the key exchanges 83 become much more expensive in terms of processing time as the length of 84 the public keys go up. Thus, the implementor is faced with the task 85 of trying to match the difficulty of an attack on the symmetric key 86 with the difficulty of an attack on the public key encryption. This 87 analysis is not unnecessary if the key exchange can be performed with 88 extreme security for almost no cost in terms of elapsed time or CPU 89 effort; unfortunately, this is no the case for public key methods today. 91 A third consideration is the minimum security requirement of the user. 92 Assume the user is encrypting with CAST-128 and requires a symmetric 93 key with a resistance time against brute-force attack of 20 years. He 94 might start off by choosing a key with 86 random bits, and then use a 95 one-way function such as SHA-1 to "boost" that to a block of 160 bits, 96 and then take 128 of those bits as the key for CAST-128. In such a 97 case, the key exchange algorithm need only match the difficulty of 86 98 bits, not 128 bits. The selection rule is: 100 1. Determine the number of symmetric key bits matching the security 101 requirement of the application (n). 103 2. Choose a symmetric cipher that has a key with at least n bits, and a 104 cryptanalytic strength of at least that much. 106 3. Choose a key exchange algorithm with a resistance to attack of at 107 least n bits. 109 A fourth consideration might be the public key authentication method 110 used to establish the identity of a user. This might be an RSA digital 111 signature or a DSA digital signature. If the modulus for the 112 authentication method isn't large enough, then the entire basis for 113 trusting the communication might fall apart. The following step 114 is thus added: 116 4. Choose an authentication algorithm with a resistance to attack of at 117 least n bits. 119 1.2 The key exchange algorithms 121 The Diffie-Hellman method uses a group, a generator, and exponents. In 122 today's Internet standards, the group operation is based on modular 123 multiplication. Here, the group is defined by the multiplicative group 124 of an integer, typically a prime p = 2q + 1, where q is a prime, and 125 the arithmetic is done modulo p; the generator (which is often simply 126 2) is denoted by g. 128 In Diffie-Hellman, Alice and Bob first agree (in public or in private) 129 on the values for g and p. Alice chooses a secret large random integer 130 (a), and Bob chooses a secret random large integer (b). Alice sends Bob 131 A, which is g^a mod p; Bob sends Alice B, which is g^b mod p. Next, 132 Alice computes B^a mod p, and Bob computes A^b mod p. These two numbers 133 are equal, and the participants use a simple function of this number as 134 the symmetric key k. 136 Note that Diffie-Hellman key exchange can be done over different kinds 137 of group representations. For instance, elliptic curves defined over 138 finite fields are a particularly efficient way to compute the key 139 exchange [SCH95]. 141 For RSA key exchange, assume that Bob has a public key (m) which is 142 equal to p*q, where p and q are two secret prime numbers, and an 143 encryption exponent e, and a decryption exponent d. For the key 144 exchange, Alice sends Bob E = k^e mod m, where k is the secret 145 symmetric key being exchanged. Bob recovers k by computing E^d mod m, 146 and the two parties use k as their symmetric key. While Bob's 147 encryption exponent e can be quite small (e.g., 17 bits), his 148 decryption exponent d will have as many bits in it as m does. 150 2. Determining the Effort to Factor 152 The RSA public key encryption method is immune to brute force guessing 153 attacks because the modulus will have at least 512 bits. The Diffie- 154 Hellman exchange is also secure against guessing because the exponents 155 will have at least twice as many bits as the symmetric keys that will 156 be derived from them. However, both methods are susceptible to 157 mathematical attacks that determine the structure of the public keys. 159 Factoring an RSA modulus will result in complete compromise of the 160 security of the private key. Solving the discrete logarithm problem for 161 a Diffie-Hellman modular exponentiation system will similarly destroy 162 the security of all key exchanges using the particular modulus. This 163 document assumes that the difficulty of solving the discrete logarithm 164 problem is equivalent to the difficulty of factoring numbers that are 165 the same size as the modulus. In fact, it is slightly harder because it 166 requires more memory; based on empirical evidence so far, the ratio of 167 difficulty is at least 20, possibly as high as 64. Solving either 168 problem requires a great deal of memory for the last stage of the 169 algorithm, the matrix reduction step. Whether or not this memory 170 requirement will be the limiting factor in solving larger integer 171 problems remains to be seen. At the current time it is not, and advances 172 in parallel matrix algorithms are expected to mitigate the memory 173 requirements in the near future. 175 Nearly all cryptographers consider the number field sieve (NFS) [GOR93] 176 [LEN93] the best method today for solving the discrete logarithm 177 problem. The formula for estimating the number of simple arithmetic 178 operations needed to factor an integer, n, using the NFS method is: 180 L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) 182 Many people prefer to discuss the number of MIPS years (MYs) that are 183 needed for large operations such as the number field sieve. For such an 184 estimation, an operation in the L(n) formula is one computer 185 instruction. Empirical evidence indicates that 4 or 5 instructions 186 might be a closer match, but this is a minor factor and this document 187 sticks with one operation/one instruction for this discussion. 189 2.1 Choosing parameters for the equation 191 The expression above has two parameters that must be estimated by 192 empirical means: k and o(1). Different authors take different 193 approaches to choosing the parameters: 195 - Some authors assume that k is 1 and o(1) is 0. This is reasonably 196 valid if the expression is only used for estimating relative effort 197 (instead of actual effort) and one assumes that the o(1) term is very 198 small over the range of the numbers that are to be factored. 200 - Other authors implicitly assume that o(1) is small and roughly 201 constant and thus its value can be folded into k; they then estimate k 202 from reported amounts of effort spent factoring large integers in 203 tests. 205 This document uses the second approach. 207 Sample values from recent work with the number field sieve are: 209 Test name Number of Number of MYs of effort Reference 210 decimal bits 211 digits 212 RSA130 130 430 500 [RSA96] 213 RSA140 140 460 2000 [RSA99] 214 RSA155 155 512 8000 [RSAc99] 216 There are no precise measurements of the amount of time used for these 217 factorizations. In most factorization tests, hundreds or thousands of 218 computers are used over a period of several months, but the number of 219 their cycles were used for the factoring project, the precise 220 distribution of processor types, speeds, and so on are not usually 221 reported. However, in all cases, the amount of effort used was far less 222 than the L(n) formula would predict if k was 1 and o(1) was 0. 224 2.2 Choosing k from empirical reports 226 By solving for k from the empirical reports, it appears that k is 227 approximately 0.02. This means that the "effective key strength" of the 228 RSA algorithm is about 5.5 bits less than is implied by the naive 229 application of equation L(n) (that is, setting k to 1 and o(1) to 0). 230 These estimates of k are fairly stable over the numbers reported in the 231 table. The estimate is limited to a single significant digit of k 232 because it expresses real uncertainties; however, the effect of 233 additional digits would have make only tiny changes to the recommended 234 key sizes. 236 The factorers of RSA130 used about 1700 MYs, but they felt that this 237 was unrealistically high for prediction purposes; by using more memory 238 on their machines, they could have easily reduced the time to 500 MYs. 239 Thus, the value used in preparing the table above was 500. This story 240 does, however, underscore the difficulty in getting an accurate measure 241 of effort. This document takes the reported effort for factoring RSA155 242 as being the most accurate measure. 244 As a result of examining the empirical data, it appears that the L(n) 245 formula can be used with the o(1) term set to 0 and with k set to 0.02 246 when talking about factoring numbers in the range of 100 to 200 decimal 247 digits. The equation becomes: 249 L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 251 To convert L(n) from simple math instructions to MYs, divide by 252 3*10^13. The equation for the number of MYs needed to factor an integer 253 n then reduces to: 255 MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 257 With what confidence can this formula be used for predicting the 258 difficulty of factoring slightly larger numbers? The answer is that it 259 should be a close upper bound, but each factorization effort is usually 260 marked by some improvement in the algorithms or their implementations 261 that makes the running time somewhat shorter than the formula would 262 indicate. 264 2.3 Pollard's rho method 266 In Diffie-Hellman exchanges, there is a second attack, Pollard's rho 267 method [POL78]. The algorithm relies on finding collisions between 268 values computed in a large number space; its success rate is 269 proportional to the square root of the size of the space. Because of 270 Pollard's rho method, the search space in a DH key exchange for the key 271 (the exponent in a g^a term), must be twice as large as the symmetric 272 key. Therefore, to securely derive a key of K bits, an implementation 273 must use an exponent with at least 2*K bits. 275 When the Diffie-Hellman key exchange is done using an elliptic curve 276 method, the NFS methods are of no avail. However, the collision 277 method is still effective, and the need for an exponent (called a 278 multiplier in EC's) with 2*K bits remains. 280 Implementors should note that the modulus for the key exchange must be 281 longer than 2*K bits. 283 3. Time to Use the Algorithms 285 This section describes how long it takes to use the algorithms to 286 perform key exchanges. Again, it is important to consider the increased 287 time it takes to exchange symmetric keys when increasing the length of 288 public keys in order to not choose unfeasibly long public keys. 290 3.1 Diffie-Hellman Key Exchange 292 A Diffie-Hellman key exchange is done with a group G with a generator g 293 and an exponent x. As noted in the Pollard's rho method section, the 294 exponent has twice as many bits as are needed for the final key. Let 295 the size of the group G be p, let the number of bits in the base 2 296 representation of p be j, and let the number of bits in the exponent be 297 K. 299 In doing the operations that result in a shared key, a generator is 300 raised to a power. The most efficient way to do this involves squaring 301 a number K times and multiplying it several times along the way. Each 302 of the numbers has j/w computer words in it, where w is the number of 303 bits in a computer word (today that will be 32 or 64 bits). 304 A naive assumption is that you will need 305 to do j squarings and j/2 multiplies; fortunately, an efficient 306 implementation will need fewer. For the remainder of this section, 307 n represents j/w. 309 A squaring operation does not need to use quite as many operations as a 310 multiplication; a reasonable estimate is that squaring takes .6 the 311 number of machine instructions of a multiply. If one prepares a table 312 ahead of time with several values of small integer powers of the 313 generator g, then only about one fifth as many multiplies are needed as 314 the naive formula suggests. Therefore, one needs to do the work of 315 approximately .8*K multiplies of n-by-n word numbers. Further, each 316 multiply and squaring must be followed by a modular reduction, and a 317 good assumption is that it is as hard to do a modular reduction as it 318 is to do an n-by-n word multiply. Thus, it takes K reductions for the 319 squarings and .2*K reductions for the multiplies. Summing this, the 320 total effort for a Diffie-Hellman key exchange with K bit exponents and 321 a modulus of n words is approximately 2*K n-by-n-word multiplies. 323 For 32-bit processors, integers that use less than about 30 computer 324 words in their representation require at least n^2 instructions for an 325 n-by-n-word multiply. Larger numbers will use less time, using 326 Karatsuba multiplications, and they will scale as about n^(1.58) for larger 327 n, but that is ignored for the current discussion. Note that 64- 328 bit processors push the "Karatsuba cross-over" number out to even more 329 bits. 331 The basic result is: if you double the size of the Diffie-Hellman 332 modular exponentiation group, you quadruple the number of operations 333 needed for the computation. 335 3.1.1 Diffie-Hellman with elliptic curve groups 337 Note that the ratios for computation effort as a function of 338 modulus size hold even if you are using an elliptic curve 339 (EC) group for Diffie-Hellman. However, for equivalent security, one 340 can use smaller numbers in the case of elliptic curves. Assume that 341 someone has chosen an modular exponentiation group with an 2048 bit 342 modulus as being an appropriate security measure for a Diffie-Hellman 343 application and wants to determine what advantage there would be to 344 using an EC group instead. The calculation is relatively 345 straightforward, if you assume that on the average, it is about 20 346 times more effort to do a squaring or multiplication in an EC group 347 than in a modular exponentiation group. A rough estimate is that an EC 348 group with equivalent security has about 200 bits in its 349 representation. Then, assuming that the time is dominated by n-by-n- 350 word operations, the relative time is computed as: 352 ((2048/200)^2)/20 ~= 5 354 showing that an elliptic curve implementation should be five times as 355 fast as a modular exponentiation implementation. 357 3.2 RSA encryption and decryption 359 Assume that an RSA public key uses a modulus with j bits; its factors 360 are two numbers of about j/2 bits each. The expected computation time 361 for encryption and decryption are different. Denote the number of words 362 in the machine representation of the modulus by the symbol n. 364 Most implementations of RSA use a small exponent for encryption. An 365 encryption may involve as few as 16 squarings and one multiplication, 366 using n-by-n-word operations. Each operation must be followed by a 367 modular reduction, and therefore the time complexity is about 368 16*(.6 + 1) + 1 + 1 ~= 28 n-by-n-word multiplies. 370 RSA decryption must use an exponent that has as many bits as the 371 modulus, j. However, the Chinese Remainder Theorem applies, and all the 372 computations can be done with a modulus of only n/2 words and an 373 exponent of only j/2 bits. The computation must be done twice, once for 374 each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)-word 375 multiplies. Because multiplying numbers with n/2 words is only 1/4 as 376 difficult as multiplying numbers with n words, the equivalent effort 377 for RSA decryption is j/4 n-by-n-word multiplies. 379 If you double the size of the modulus for RSA, the n-by-n multiplies 380 will take four times as long. Further, the decryption time doubles 381 because the exponent is larger. The overall scaling cost is a factor of 382 4 for encryption, a factor of 8 for decryption. 384 3.3 Real-world examples 386 To make these numbers more real, here are a few examples of software 387 implementations run on current hardware. The examples are included to 388 show rough estimates of reasonable implementations; they are not 389 benchmarks. As with all software, the performance will depend on the 390 exact details of specialization of the code to the problem and the 391 specific hardware. 393 The following two tables are from [TER00] and are for modular 394 exponentiation, such as would be done in a Diffie-Hellman key exchange. 396 Celeron 400 MHz; compiled with GNU C compiler, optimized, some platform 397 specific coding optimizations: 399 group modulus exponent time 400 type size size 401 mod 768 ~150 18 msec 402 mod 1024 ~160 32 msec 403 mod 1536 ~180 82 msec 404 ecn 155 ~150 35 msec 405 ecn 185 ~200 56 msec 407 The group type is from RFC2409 and is either modular exponentiation 408 ("mod") or elliptic curve ("ecn"). All sizes here and in subsequent 409 tables are in bits. 411 Alpha 500 MHz compiled with Digital's C compiler, optimized, no 412 platform specific code: 414 group modulus exponent time 415 type size size 416 mod 768 ~150 12 msec 417 mod 1024 ~160 24 msec 418 mod 1536 ~180 59 msec 419 ecn 155 ~150 20 msec 420 ecn 185 ~200 27 msec 422 The following numbers were originally for RSA signing operations, using 423 the Chinese Remainder representation. For ease of understanding, the 424 parameters are presented here to show the interior calculations, i.e., 425 the size of the modulus and exponent used by the software. 427 Dual Pentium II-350 from [YOU00]: 429 equiv equiv equiv 430 modulus exponent time 431 size size 432 256 256 1.5 ms 433 512 512 8.6 ms 434 1024 1024 55.4 ms 435 2048 2048 387 ms 437 Alpha 264 600mhz from [YOU00]: 439 equiv equiv equiv 440 modulus exponent time 441 size size 442 512 512 1.4 ms 444 Chips that accelerate exponentiation can perform 1024-bit 445 exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 446 milliseconds [HIFN]. 448 4. Equivalences of Key Sizes 450 In order to determine how strong a public key is needed to protect a 451 particular symmetric key, you first need to determine how much effort 452 is needed to break the symmetric key. Most Internet security protocols 453 require the use of TripleDES for strong symmetric encryption, and it is 454 expected that the Advanced Encryption Standard (AES) will be adopted on 455 the Internet after it has been selected. Therefore, these two 456 algorithms are discussed here. 458 If one could simply determine the number of MYs it takes to break 459 TripleDES, the task of computing the public key size of equivalent 460 strength would be easy. Unfortunately, that isn't the case here because 461 there are many examples of DES-specific hardware that encrypt faster 462 than DES in software on a standard CPU. Instead, one must determine the 463 equivalent cost for a system to break TripleDES and a system to break 464 the public key protecting a TripleDES key. 466 In 1998, the Electronic Frontier Foundation (EFF) built a DES-cracking 467 machine [GIL98] for US$130,000 that could test about 1e11 DES keys per 468 second (additional money was spent on the machine's design). The 469 machine's builders fully admit that the machine is not well optimized, 470 and it is estimated that ten times the amount of money could probably 471 create a machine about 50 times as fast. Assuming more optimization by 472 guessing that a system to test TripleDES keys runs about as fast as a 473 system to test DES keys, so approximately US$1 million might test 5e12 474 TripleDES keys per second. 476 In case your adversaries are much richer than EFF, you may want to 477 assume that they have US$1 trillion, enough to test 5e18 keys per 478 second. An exhaustive search of the TripleDES space of 2^112 keys with 479 this quite expensive system would take about 1e15 seconds or about 33 480 million years. (Note that such a system would also need 2^60 bytes of 481 RAM [MH81], which is considered free in this calculation). This seems a 482 needlessly conservative value. However, if computer logic speeds 483 continue to increase in accordance with Moore's Law (doubling in speed 484 every 1.5 years), then one might expect that in about 50 years, the 485 computation could be completed in only one year. For the purposes of 486 illustration, this 50 year resistance against a trillionaire is assumed 487 to be the minimum security requirement for a set of applications. 489 If 112 bits of attack resistance is the system security requirement, 490 then the key exchange system for TripleDES should have equivalent 491 difficulty; that is to say, if the attacker has US$1 trillion, you want 492 him to spend all his money to buy hardware today and to know that he 493 will "crack" the key exchange in not less than 33 million years. 494 (Obviously, a rational attacker would wait for about 45 years before 495 actually spending the money, because he could then get much better 496 hardware, but all attackers benefit from this sort of wait equally.) 498 It is estimated that a typical PC CPU today can generate about 500 MIPs 499 and can be purchased for about US$100 in quantity; thus you get about 5 500 MIPs/US$. For one trillion US dollars, an attacker can get 5e12 MIP 501 years of computer instructions. This figure is used in the following 502 estimates of equivalent costs for breaking key exchange systems. 504 4.1 Key equivalence against special purpose brute force hardware 506 If the trillionaire attacker is to use conventional CPU's to "crack" a 507 key exchange for a 112 bit key in the same time that the special 508 purpose machine is spending on brute force search for the symmetric 509 key, the key exchange system must use an appropriately large modulus. 510 Assume that the trillionaire performs 5e12 MIPs of instructions per 511 year. Use the following equation to estimate the modulus size to use 512 with RSA encryption or DH key exchange: 514 5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 516 Solving this approximately for n yields: 518 n = 10^(625) = 2^(2077) 520 Thus, assuming similar logic speeds and the current efficiency of the 521 number field sieve, moduli with about 2100 bits will have about the 522 same resistance against attack as an 112-bit TripleDES key. This 523 indicates that RSA public key encryption should use a modulus with 524 around 2100 bits; for a Diffie-Hellman key exchange, one could use a 525 slightly smaller modulus, but it not a significant difference. 527 4.2 Key equivalence against conventional CPU brute force attack 529 An alternative way of estimating this assumes that the attacker has a 530 less challenging requirement: he must only "crack" the key exchange in 531 less time than a brute force key search against the symmetric key would 532 take with general purpose computers. This is an "apples-to-apples" 533 comparison, because it assumes that the attacker needs only to have 534 computation donated to his effort, not built from a personal or 535 national fortune. The public key modulus will be larger than the one 536 in 4.1, because the symmetric key is going to be viable for a longer 537 period of time. 539 Assume that the number of congenial CPU instructions to encrypt a 540 block of material using TripleDES is 300. The estimated number of 541 computer instructions to break 112 bit TripleDES key: 543 300 * 2^112 544 = 1.6 * 10^(36) 545 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 547 Solving this approximately for n yields: 549 n = 10^(734) = 2^(2439) 551 Thus, for general purpose CPU attacks, you can assume that moduli with 552 about 2400 bits will have about the same strength against attack as an 553 112-bit TripleDES key. This indicates that RSA public key encryption 554 should use a modulus with around 2400 bits; for a Diffie-Hellman key 555 exchange, one could use a slightly smaller modulus, but it not a 556 significant difference. 558 Note that some authors assume that the algorithms underlying the number 559 field sieve will continue to get better over time. These authors 560 recommend an even larger modulus, over 4000 bits, for protecting a 112- 561 bit symmetric key for 50 years. This points out the difficulty of 562 long-term cryptographic security: it is all but impossible to predict 563 progress in mathematics and physics over such a long period of time. 565 4.3 A One Year Attack 567 Assuming a trillionaire spends his money today to buy hardware, what 568 size key exchange numbers could he "crack" in one year? He can perform 569 5*e12 MYs of instructions, or 571 3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 573 Solving for an approximation of n yields 575 n = 10^(360) = 2^(1195) 577 This is about as many operations as it would take to crack an 80-bit 578 symmetric key by brute force. 580 Thus, for protecting data that has a secrecy requirement of one year 581 against an incredibly rich attacker, a key exchange modulus with about 582 1200 bits protecting an 80-bit symmetric key is safe even against a 583 nation's resources. 585 4.4 Key equivalence for other ciphers 587 Extending this logic to the AES can be done with limited accuracy at 588 this point; the final algorithms have not been selected, but there are 589 software implementations and timings available. For purposes of 590 estimation, one can assume that the time for an encryption is about the 591 same as DES; one can think of the AES ciphers as being somewhat stronger 592 than TripleDES but three times as fast. The time and cost for a brute 593 force attack is approximately 2^16 more than for TripleDES, and thus the 594 recommended key exchange modulus size are about 700 bits longer. 596 If it is possible to design hardware for AES cracking that is 597 considerably more efficient than hardware for DES cracking, then the 598 moduli for protecting the key exchange can be made smaller. However, 599 the existence of such designs is only a matter of guessing at this 600 time. 602 The AES ciphers have key sizes of 128 bits up to 256 bits. Should a 603 prudent minimum security requirement, and thus the key exchange moduli, 604 have similar strengths? The answer to this depends on whether or not 605 one expect Moore's Law to continue unabated. If it continues, one would 606 expect 128 bit keys to be safe for about 60 years, and 256 bit keys 607 would be safe for another 400 years beyond that, far beyond any 608 imaginable security requirement. But such progress is difficult to 609 predict, as it exceeds the physical capabilities of today's devices and 610 would imply the existence of logic technologies that are unknown or 611 infeasible today. Quantum computing is a candidate, but too little is 612 known today to make confident predictions about its applicability to 613 cryptography (which itself might change over the next 100 years!). 615 If Moore's Law does not continue to hold, if no new computational 616 paradigms emerge, then keys of over 100 bits in length might well be 617 safe "forever". Note, however that others have come up with estimates 618 based on assumptions of new computational paradigms emerging. For 619 example, [LEN99] shows a more conservative analysis than the 620 one in this document. 622 4.5 Table of effort comparisons 624 In this table it is assumed that attackers use general purpose 625 computers, that the hardware is purchased in the year 2000, and that 626 mathematical knowledge relevant to the problem remains the same as 627 today. This is an pure "apples-to-apples" comparison demonstrating how 628 the time for a key exchange scales with respect to the strength 629 requirement. The subgroup size for DSA is included, if that is being 630 used for supporting authentication as part of the protocol; the DSA 631 modulus must be as long as the DH modulus, but the size of the "q" 632 subgroup is also relevant. 634 Symm. key RSA or DH DSA subgroup 635 size modulus size size 636 (bits) (bits) (bits) 638 70 947 128 639 80 1228 145 640 90 1553 153 641 100 1926 184 642 150 4575 279 643 200 8719 373 644 250 14596 475 646 5. Security Considerations 648 The equations and values given in this document are meant to be as 649 accurate as possible, based on the state of the art in general purpose 650 computers at the time that this document is being written. No 651 predictions can be completely accurate, and the formulas given here are 652 not meant to be definitive statements of fact about cryptographic 653 strengths. For example, some of the empirical results used in 654 calibrating the formulas in this document are probably not completely 655 accurate, and this inaccuracy affects the estimates. It is the authors' 656 hope that the numbers presented here vary from real world experience as 657 little as possible. 659 6. References 661 [DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an explosive 662 experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, 663 (1995) 372-385. 665 [GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics 666 & Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 667 pages, May 1998, O'Reilly & Associates; ISBN: 1565925203 669 [GOR93] D. Gordon, "Discrete logarithms in GF(p) using the number field 670 sieve", SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. 672 [HIFN] Hi/fn Inc., product literature, January 2000. 674 [LEN93] A. K. Lenstra, H. W. Lenstra, Jr. (eds), The development of the 675 number field sieve, Lecture Notes in Math, 1554, Springer Verlag, 676 Berlin, 1993. 678 [LEN99] A. K. Lenstra, E. Verheul, Selecting Cryptographic 679 Key Sizes, papers and tables available at http://www.cryptosavvy.com/. 681 [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple 682 Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467. 684 [ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future 685 of Integer Factorization, A. M. Odlyzko 687 [ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, 688 Designs, Codes, and Cryptography (1999). To appear. 690 [POL78] J. Pollard, "Monte Carlo methods for index computation mod p", 691 Mathematics of Computation, 32 (1978), 918-924. 693 [RSA96] RSA Labs Cryptobytes, Volume 2, No. 2 - Summer 1996; RSA-130 694 Factored 696 [RSA99] RSA Labs Bulletin Number 10 - March 8, 1999; The Factorization 697 of RSA-140 699 [RSAc99] Factorization of RSA-155, 700 http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html 702 [SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve 703 Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 704 '95, volume 963 of Lecture Notes in Computer Science, pages 43-56, 27- 705 31 August 1995. Springer-Verlag 707 [SIL99] R. D. Silverman, RSA Laboratories Bulletin, Number 12 - May 3, 708 1999; An Analysis of Shamir's Factoring Device 710 [TER00] Personal communication from Tero Monenen, January 2000. 712 [YOU00] Personal communication from XXXXXXXXXX Young, January 2000. 714 A. Authors' Addresses 716 Hilarie Orman 717 Novell, Inc. 718 122 East 1700 South 719 Provo, UT 84606 720 horman@novell.com 722 Paul Hoffman 723 Internet Mail Consortium and VPN Consortium 724 127 Segre Place 725 Santa Cruz, CA 95060 USA 726 paul.hoffman@imc.org and paul.hoffman@vpnc.org