idnits 2.17.1 draft-orman-public-key-lengths-04.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. ** The document is more than 15 pages and seems to lack a Table of Contents. == 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 878 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 5 instances of too long lines in the document, the longest one being 3 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 484 has weird spacing: '... group modul...' == Line 485 has weird spacing: '... type siz...' == Line 499 has weird spacing: '... group modul...' == Line 500 has weird spacing: '... type siz...' == Line 516 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.) -- The document date (November 19, 2001) is 8188 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'SILIEEE99' is mentioned on line 320, but not defined == Unused Reference: 'DL' is defined on line 822, but no explicit reference was found in the text == Unused Reference: 'ODL95' is defined on line 843, but no explicit reference was found in the text == Unused Reference: 'ODL99' is defined on line 846, but no explicit reference was found in the text == Unused Reference: 'RFC2409' is defined on line 852, but no explicit reference was found in the text == Unused Reference: 'SIL99' is defined on line 860, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'DL' ** Obsolete normative reference: RFC 1750 (ref. 'ECS') (Obsoleted by RFC 4086) -- Possible downref: Non-RFC (?) normative reference: ref. 'GIL98' -- Possible downref: Non-RFC (?) normative reference: ref. 'GOR93' -- Possible downref: Non-RFC (?) normative reference: ref. 'LEN93' -- 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' ** Obsolete normative reference: RFC 2409 (Obsoleted by RFC 4306) -- Possible downref: Non-RFC (?) normative reference: ref. 'SCH95' -- Possible downref: Non-RFC (?) normative reference: ref. 'SIL99' -- Possible downref: Non-RFC (?) normative reference: ref. 'SIL00' Summary: 9 errors (**), 0 flaws (~~), 14 warnings (==), 13 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-04.txt Paul Hoffman 3 November 19, 2001 4 Expires in six months 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 72 a symmetric key, and that the symmetric key was exchanged between the 73 sender and recipient using public key cryptography. The attacker has two 74 options to recover the message: a brute-force attempt to determine the 75 symmetric key by repeated guessing, or mathematical determination of the 76 private key used as the key exchange key. A smart attacker will work on 77 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 necessary 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 not the case for public key methods 90 today. 92 A third consideration is the minimum security requirement of the user. 93 Assume the user is encrypting with CAST-128 and requires a symmetric 94 key with a resistance time against brute-force attack of 20 years. He 95 might start off by choosing a key with 86 random bits, and then use a 96 one-way function such as SHA-1 to "boost" that to a block of 160 bits, 97 and then take 128 of those bits as the key for CAST-128. In such a 98 case, the key exchange algorithm need only match the difficulty of 86 99 bits, not 128 bits. 101 The selection procedure is: 103 1. Determine the attack resistance necessary to satisfy the security 104 requirements of the application. Do this by estimating minimum number 105 of computer operations that the attacker will be forced to do in order 106 to compromise the security of the system and then take the logarithm 107 base two of that number. Call that logarithm value "n". 109 2. Choose a symmetric cipher that has a key with at least n bits and 110 at least that much cryptanalytic strength. 112 3. Choose a key exchange algorithm with a resistance to attack of at 113 least n bits. 115 A fourth consideration might be the public key authentication method 116 used to establish the identity of a user. This might be an RSA digital 117 signature or a DSA digital signature. If the modulus for the 118 authentication method isn't large enough, then the entire basis for 119 trusting the communication might fall apart. The following step 120 is thus added: 122 4. Choose an authentication algorithm with a resistance to attack of at 123 least n bits. 125 1.2 The key exchange algorithms 127 The Diffie-Hellman method uses a group, a generator, and exponents. In 128 today's Internet standards, the group operation is based on modular 129 multiplication. Here, the group is defined by the multiplicative group 130 of an integer, typically a prime p = 2q + 1, where q is a prime, and 131 the arithmetic is done modulo p; the generator (which is often simply 132 2) is denoted by g. 134 In Diffie-Hellman, Alice and Bob first agree (in public or in private) 135 on the values for g and p. Alice chooses a secret large random integer 136 (a), and Bob chooses a secret random large integer (b). Alice sends Bob 137 A, which is g^a mod p; Bob sends Alice B, which is g^b mod p. Next, 138 Alice computes B^a mod p, and Bob computes A^b mod p. These two numbers 139 are equal, and the participants use a simple function of this number as 140 the symmetric key k. 142 Note that Diffie-Hellman key exchange can be done over different kinds 143 of group representations. For instance, elliptic curves defined over 144 finite fields are a particularly efficient way to compute the key 145 exchange [SCH95]. 147 For RSA key exchange, assume that Bob has a public key (m) which is 148 equal to p*q, where p and q are two secret prime numbers, and an 149 encryption exponent e, and a decryption exponent d. For the key 150 exchange, Alice sends Bob E = k^e mod m, where k is the secret 151 symmetric key being exchanged. Bob recovers k by computing E^d mod m, 152 and the two parties use k as their symmetric key. While Bob's 153 encryption exponent e can be quite small (e.g., 17 bits), his 154 decryption exponent d will have as many bits in it as m does. 156 2. Determining the Effort to Factor 158 The RSA public key encryption method is immune to brute force guessing 159 attacks because the modulus will have at least 512 bits, and that is 160 too many possibilities to guess. The Diffie-Hellman exchange is also 161 secure against guessing because the exponents will have at least twice 162 as many bits as the symmetric keys that will be derived from 163 them. However, both methods are susceptible to mathematical attacks 164 that determine the structure of the public keys. 166 Factoring an RSA modulus will result in complete compromise of the 167 security of the private key. Solving the discrete logarithm problem for 168 a Diffie-Hellman modular exponentiation system will similarly destroy 169 the security of all key exchanges using the particular modulus. This 170 document assumes that the difficulty of solving the discrete logarithm 171 problem is equivalent to the difficulty of factoring numbers that are 172 the same size as the modulus. In fact, it is slightly harder because it 173 requires more operations; based on empirical evidence so far, the ratio 174 of difficulty is at least 20, possibly as high as 64. Solving either 175 problem requires a great deal of memory for the last stage of the 176 algorithm, the matrix reduction step. Whether or not this memory 177 requirement will continue to be the limiting factor in solving larger 178 integer problems remains to be seen. At the current time it is not, and 179 there is active research into parallel matrix algorithms that might 180 mitigate the memory requirements for this problem. 182 The number field sieve (NFS) [GOR93] [LEN93] is the best method today 183 for solving the discrete logarithm problem. The formula for estimating 184 the number of simple arithmetic operations needed to factor an integer, 185 n, using the NFS method is: 187 L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) 189 Many people prefer to discuss the number of MIPS years (MYs) that are 190 needed for large operations such as the number field sieve. For such an 191 estimation, an operation in the L(n) formula is one computer 192 instruction. Empirical evidence indicates that 4 or 5 instructions 193 might be a closer match, but this is a minor factor and this document 194 sticks with one operation/one instruction for this discussion. 196 2.1 Choosing parameters for the equation 198 The expression above has two parameters that can be estimated by 199 empirical means: k and o(1). For the range of numbers we are interested 200 in, there is little distinction between them. 202 One could assume that k is 1 and o(1) is 0. This is reasonably valid if 203 the expression is only used for estimating relative effort (instead of 204 actual effort) and one assumes that the o(1) term is very small over the 205 range of the numbers that are to be factored. 207 Or, one could assume that o(1) is small and roughly constant and thus 208 its value can be folded into k; then estimate k from reported amounts of 209 effort spent factoring large integers in tests. 211 This document uses the second approach in order to get an estimate of 212 the significance of the factor. It appears to be minor, based on the 213 following calculations. 215 Sample values from recent work with the number field sieve, 216 collected by RSA Labs, include: 218 Test name Number of Number of MYs of effort 219 decimal bits 220 digits 221 RSA130 130 430 500 222 RSA140 140 460 2000 223 RSA155 155 512 8000 225 There are no precise measurements of the amount of time used for these 226 factorizations. In most factorization tests, hundreds or thousands of 227 computers are used over a period of several months, but the number of 228 their cycles were used for the factoring project, the precise 229 distribution of processor types, speeds, and so on are not usually 230 reported. However, in all cases, the amount of effort used was far less 231 than the L(n) formula would predict if k was 1 and o(1) was 0. 233 2.2 Choosing k from empirical reports 235 By solving for k from the empirical reports, it appears that k is 236 approximately 0.02. This means that the "effective key strength" of the 237 RSA algorithm is about 5 or 6 bits less than is implied by the naive 238 application of equation L(n) (that is, setting k to 1 and o(1) to 0). 239 These estimates of k are fairly stable over the numbers reported in the 240 table. The estimate is limited to a single significant digit of k 241 because it expresses real uncertainties; however, the effect of 242 additional digits would have make only tiny changes to the recommended 243 key sizes. 245 The factorers of RSA130 used about 1700 MYs, but they felt that this 246 was unrealistically high for prediction purposes; by using more memory 247 on their machines, they could have easily reduced the time to 500 MYs. 248 Thus, the value used in preparing the table above was 500. This story 249 does, however, underscore the difficulty in getting an accurate measure 250 of effort. This document takes the reported effort for factoring RSA155 251 as being the most accurate measure. 253 As a result of examining the empirical data, it appears that the L(n) 254 formula can be used with the o(1) term set to 0 and with k set to 0.02 255 when talking about factoring numbers in the range of 100 to 200 decimal 256 digits. The equation becomes: 258 L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 260 To convert L(n) from simple math instructions to MYs, divide by 261 3*10^13. The equation for the number of MYs needed to factor an integer 262 n then reduces to: 264 MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 266 With what confidence can this formula be used for predicting the 267 difficulty of factoring slightly larger numbers? The answer is that it 268 should be a close upper bound, but each factorization effort is usually 269 marked by some improvement in the algorithms or their implementations 270 that makes the running time somewhat shorter than the formula would 271 indicate. 273 2.3 Pollard's rho method 275 In Diffie-Hellman exchanges, there is a second attack, Pollard's rho 276 method [POL78]. The algorithm relies on finding collisions between 277 values computed in a large number space; its success rate is 278 proportional to the square root of the size of the space. Because of 279 Pollard's rho method, the search space in a DH key exchange for the key 280 (the exponent in a g^a term), must be twice as large as the symmetric 281 key. Therefore, to securely derive a key of K bits, an implementation 282 must use an exponent with at least 2*K bits. 284 When the Diffie-Hellman key exchange is done using an elliptic curve 285 method, the NFS methods are of no avail. However, the collision method 286 is still effective, and the need for an exponent (called a multiplier 287 in EC's) with 2*K bits remains. The modulus used for the computation 288 can also be 2*K bits, and this will be substantially smaller than the 289 modulus needed for modular exponentiation methods as the desired 290 security level increases past 64 bits of brute-force attack 291 resistance. 293 One might ask, how can you compare the number of computer instructions 294 really needed for a discrete logarithm attack to the number needed to 295 search the keyspace of a cipher? In comparing the efforts, one should 296 consider what a "basic operation" is. For brute force search of the 297 keyspace of a symmetric encryption algorithm like DES, the basic 298 operation is the time to do a key setup and the time to do one 299 encryption. For discrete logs, the basic operation is a modular 300 squaring. The log of the ratio of these two operations can be used as a 301 "normalizing factor" between the two kinds of computations. However, 302 even for very large moduli (16K bits), this factor amounts to only a few 303 bits of extra effort. 305 2.4 Limits of large memory and many machines 307 Robert Silverman has examined the question of when it will be practical 308 to factor RSA moduli larger than 512 bits. His analysis is based not 309 only on the theoretical number of operations, but it also includes 310 expectations about the availability of actual machines for performing 311 the work (this document is based only on theoretical number of 312 operations). He examines the question of whether or not we can expect 313 there be enough machines, memory, and communication to factor a very 314 large number. 316 The best factoring methods need a lot of random access memory for 317 collecting data relations (sieving) and a critical final step that does 318 a row reduction on a large matrix. The memory requirements are related 319 to the size of the number being factored (or subjected to discrete 320 logarithm solution). Silverman [SILIEEE99] [SIL00] has argued that there 321 is a practical limit to the number of machines and the amount of RAM 322 that be brought to bear on a single problem in the foreseeable future. 323 He sees two problems in attacking a 1024-bit RSA modulus: the machines 324 doing the sieving will need 64-bit address spaces and the matrix row 325 reduction machine will need several terabytes of memory. Silverman notes 326 that very few 64-bit machines have been sold, and none of those machines 327 have the 170 gigabytes of memory needed for sieving. Nearly a billion 328 such machines are necessary for the sieving in a reasonable amount of 329 time (a year or two). 331 Silverman's conclusion, based on the history of factoring efforts and 332 Moore's Law, is that 1024-bit RSA moduli will not be factored until 333 about 2037. This implies a much longer lifetime to RSA keys than the 334 theoretical analysis indicates. He argues that predictions about how 335 many machines and memory modules will be available can be with great 336 confidence, based on Moore's Law extrapolations and the recent history 337 of factoring efforts. 339 One should give the practical considerations a great deal of weight, but 340 in a risk analysis, the physical world is less predictable than trend 341 graphs would indicate. In considering how much trust to put into the 342 inability of the computer industry to satisfy the voracious needs of 343 factorers, one must have some insight into economic considerations that 344 are more complicated than the mathematics of factoring. The demand for 345 computer memory is hard to predict because it is based on applications: 346 a "killer app" might come along any day and send the memory industry 347 into a frenzy of sales. The number of processors available on desktops 348 may be limited by the number of desks, but very capable embedded systems 349 account for more processor sales than desktops. As embedded systems 350 absorb networking functions, it is not unimaginable that millions of 351 64-bit processors with at least gigabytes of memory will pervade our 352 environment. 354 The bottom line on this is that the key length recommendations predicted 355 by theory may be overly conservative, but they are what we have used for 356 this document. This question of machine availability is one that should 357 be reconsidered in light of current technology on a regular basis. 359 3. Time to Use the Algorithms 361 This section describes how long it takes to use the algorithms to 362 perform key exchanges. Again, it is important to consider the increased 363 time it takes to exchange symmetric keys when increasing the length of 364 public keys. It is important to avoid choosing unfeasibly long public 365 keys. 367 3.1 Diffie-Hellman Key Exchange 369 A Diffie-Hellman key exchange is done with a group G with a generator g 370 and an exponent x. As noted in the Pollard's rho method section, the 371 exponent has twice as many bits as are needed for the final key. Let 372 the size of the group G be p, let the number of bits in the base 2 373 representation of p be j, and let the number of bits in the exponent be 374 K. 376 In doing the operations that result in a shared key, a generator is 377 raised to a power. The most efficient way to do this involves squaring 378 a number K times and multiplying it several times along the way. Each 379 of the numbers has j/w computer words in it, where w is the number of 380 bits in a computer word (today that will be 32 or 64 bits). A naive 381 assumption is that you will need to do j squarings and j/2 multiplies; 382 fortunately, an efficient implementation will need fewer (NB: for the 383 remainder of this section, n represents j/w). 385 A squaring operation does not need to use quite as many operations as a 386 multiplication; a reasonable estimate is that squaring takes .6 the 387 number of machine instructions of a multiply. If one prepares a table 388 ahead of time with several values of small integer powers of the 389 generator g, then only about one fifth as many multiplies are needed as 390 the naive formula suggests. Therefore, one needs to do the work of 391 approximately .8*K multiplies of n-by-n word numbers. Further, each 392 multiply and squaring must be followed by a modular reduction, and a 393 good assumption is that it is as hard to do a modular reduction as it 394 is to do an n-by-n word multiply. Thus, it takes K reductions for the 395 squarings and .2*K reductions for the multiplies. Summing this, the 396 total effort for a Diffie-Hellman key exchange with K bit exponents and 397 a modulus of n words is approximately 2*K n-by-n-word multiplies. 399 For 32-bit processors, integers that use less than about 30 computer 400 words in their representation require at least n^2 instructions for an 401 n-by-n-word multiply. Larger numbers will use less time, using 402 Karatsuba multiplications, and they will scale as about n^(1.58) for larger 403 n, but that is ignored for the current discussion. Note that 64- 404 bit processors push the "Karatsuba cross-over" number out to even more 405 bits. 407 The basic result is: if you double the size of the Diffie-Hellman 408 modular exponentiation group, you quadruple the number of operations 409 needed for the computation. 411 3.1.1 Diffie-Hellman with elliptic curve groups 413 Note that the ratios for computation effort as a function of 414 modulus size hold even if you are using an elliptic curve 415 (EC) group for Diffie-Hellman. However, for equivalent security, one 416 can use smaller numbers in the case of elliptic curves. Assume that 417 someone has chosen an modular exponentiation group with an 2048 bit 418 modulus as being an appropriate security measure for a Diffie-Hellman 419 application and wants to determine what advantage there would be to 420 using an EC group instead. The calculation is relatively 421 straightforward, if you assume that on the average, it is about 20 422 times more effort to do a squaring or multiplication in an EC group 423 than in a modular exponentiation group. A rough estimate is that an EC 424 group with equivalent security has about 200 bits in its 425 representation. Then, assuming that the time is dominated by n-by-n- 426 word operations, the relative time is computed as: 428 ((2048/200)^2)/20 ~= 5 430 showing that an elliptic curve implementation should be five times as 431 fast as a modular exponentiation implementation. 433 3.2 RSA encryption and decryption 435 Assume that an RSA public key uses a modulus with j bits; its factors 436 are two numbers of about j/2 bits each. The expected computation time 437 for encryption and decryption are different. As before, we denote the 438 number of words in the machine representation of the modulus by the 439 symbol n. 441 Most implementations of RSA use a small exponent for encryption. An 442 encryption may involve as few as 16 squarings and one multiplication, 443 using n-by-n-word operations. Each operation must be followed by a 444 modular reduction, and therefore the time complexity is about 445 16*(.6 + 1) + 1 + 1 ~= 28 n-by-n-word multiplies. 447 RSA decryption must use an exponent that has as many bits as the 448 modulus, j. However, the Chinese Remainder Theorem applies, and all the 449 computations can be done with a modulus of only n/2 words and an 450 exponent of only j/2 bits. The computation must be done twice, once for 451 each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)-word 452 multiplies. Because multiplying numbers with n/2 words is only 1/4 as 453 difficult as multiplying numbers with n words, the equivalent effort 454 for RSA decryption is j/4 n-by-n-word multiplies. 456 If you double the size of the modulus for RSA, the n-by-n multiplies 457 will take four times as long. Further, the decryption time doubles 458 because the exponent is larger. The overall scaling cost is a factor of 459 4 for encryption, a factor of 8 for decryption. 461 3.3 Real-world examples 463 To make these numbers more real, here are a few examples of software 464 implementations run on current hardware. The examples are included to 465 show rough estimates of reasonable implementations; they are not 466 benchmarks. As with all software, the performance will depend on the 467 exact details of specialization of the code to the problem and the 468 specific hardware. 470 The best time informally reported for a 1024-bit modular exponentiation 471 (the decryption side of 2048-bit RSA), is 0.9 ms (about 450,000 CPU 472 cycles) on a 500 MHz Itanium processor. This shows that newer 473 processors are not losing ground on big number operations; the number of 474 instructions is less than a 32-bit processor uses for a 256-bit modular 475 exponentiation. 477 For less advanced processors timing, the following two tables (computed 478 by Tero Monenen at SSH Communications) for modular exponentiation, such 479 as would be done in a Diffie-Hellman key exchange. 481 Celeron 400 MHz; compiled with GNU C compiler, optimized, some platform 482 specific coding optimizations: 484 group modulus exponent time 485 type size size 486 mod 768 ~150 18 msec 487 mod 1024 ~160 32 msec 488 mod 1536 ~180 82 msec 489 ecn 155 ~150 35 msec 490 ecn 185 ~200 56 msec 492 The group type is from RFC2409 and is either modular exponentiation 493 ("mod") or elliptic curve ("ecn"). All sizes here and in subsequent 494 tables are in bits. 496 Alpha 500 MHz compiled with Digital's C compiler, optimized, no 497 platform specific code: 499 group modulus exponent time 500 type size size 501 mod 768 ~150 12 msec 502 mod 1024 ~160 24 msec 503 mod 1536 ~180 59 msec 504 ecn 155 ~150 20 msec 505 ecn 185 ~200 27 msec 507 The following two tables (computed by Eric Young) were originally 508 for RSA signing operations, using the Chinese Remainder representation. 509 For ease of understanding, the parameters are presented here to show the 510 interior calculations, i.e., the size of the modulus and exponent used 511 by the software. 513 Dual Pentium II-350: 515 equiv equiv equiv 516 modulus exponent time 517 size size 518 256 256 1.5 ms 519 512 512 8.6 ms 520 1024 1024 55.4 ms 521 2048 2048 387 ms 523 Alpha 264 600mhz: 525 equiv equiv equiv 526 modulus exponent time 527 size size 528 512 512 1.4 ms 530 Current chips that accelerate exponentiation can perform 1024-bit 531 exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 532 milliseconds or less. 534 4. Equivalences of Key Sizes 536 In order to determine how strong a public key is needed to protect a 537 particular symmetric key, you first need to determine how much effort 538 is needed to break the symmetric key. Many Internet security protocols 539 require the use of TripleDES for strong symmetric encryption, and it is 540 expected that the Advanced Encryption Standard (AES) will be adopted on 541 the Internet in the coming years. Therefore, these two algorithms are 542 discussed here. 544 If one could simply determine the number of MYs it takes to break 545 TripleDES, the task of computing the public key size of equivalent 546 strength would be easy. Unfortunately, that isn't the case here because 547 there are many examples of DES-specific hardware that encrypt faster 548 than DES in software on a standard CPU. Instead, one must determine the 549 equivalent cost for a system to break TripleDES and a system to break 550 the public key protecting a TripleDES key. 552 In 1998, the Electronic Frontier Foundation (EFF) built a DES-cracking 553 machine [GIL98] for US$130,000 that could test about 1e11 DES keys per 554 second (additional money was spent on the machine's design). The 555 machine's builders fully admit that the machine is not well optimized, 556 and it is estimated that ten times the amount of money could probably 557 create a machine about 50 times as fast. Assuming more optimization by 558 guessing that a system to test TripleDES keys runs about as fast as a 559 system to test DES keys, so approximately US$1 million might test 5e12 560 TripleDES keys per second. 562 In case your adversaries are much richer than EFF, you may want to 563 assume that they have US$1 trillion, enough to test 5e18 keys per 564 second. An exhaustive search of the TripleDES space of 2^112 keys with 565 this quite expensive system would take about 1e15 seconds or about 33 566 million years. (Note that such a system would also need 2^60 bytes of 567 RAM [MH81], which is considered free in this calculation). This seems a 568 needlessly conservative value. However, if computer logic speeds 569 continue to increase in accordance with Moore's Law (doubling in speed 570 every 1.5 years), then one might expect that in about 50 years, the 571 computation could be completed in only one year. For the purposes of 572 illustration, this 50 year resistance against a trillionaire is assumed 573 to be the minimum security requirement for a set of applications. 575 If 112 bits of attack resistance is the system security requirement, 576 then the key exchange system for TripleDES should have equivalent 577 difficulty; that is to say, if the attacker has US$1 trillion, you want 578 him to spend all his money to buy hardware today and to know that he 579 will "crack" the key exchange in not less than 33 million years. 580 (Obviously, a rational attacker would wait for about 45 years before 581 actually spending the money, because he could then get much better 582 hardware, but all attackers benefit from this sort of wait equally.) 584 It is estimated that a typical PC CPU today can generate over 500 MIPs 585 and can be purchased for about US$100 in quantity; thus you get more 586 than 5 MIPs/US$. For one trillion US dollars, an attacker can get 5e12 587 MIP years of computer instructions. This figure is used in the following 588 estimates of equivalent costs for breaking key exchange systems. 590 4.1 Key equivalence against special purpose brute force hardware 592 If the trillionaire attacker is to use conventional CPU's to "crack" a 593 key exchange for a 112 bit key in the same time that the special 594 purpose machine is spending on brute force search for the symmetric 595 key, the key exchange system must use an appropriately large modulus. 596 Assume that the trillionaire performs 5e12 MIPs of instructions per 597 year. Use the following equation to estimate the modulus size to use 598 with RSA encryption or DH key exchange: 600 5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 602 Solving this approximately for n yields: 604 n = 10^(625) = 2^(2077) 606 Thus, assuming similar logic speeds and the current efficiency of the 607 number field sieve, moduli with about 2100 bits will have about the 608 same resistance against attack as an 112-bit TripleDES key. This 609 indicates that RSA public key encryption should use a modulus with 610 around 2100 bits; for a Diffie-Hellman key exchange, one could use a 611 slightly smaller modulus, but it not a significant difference. 613 4.2 Key equivalence against conventional CPU brute force attack 615 An alternative way of estimating this assumes that the attacker has a 616 less challenging requirement: he must only "crack" the key exchange in 617 less time than a brute force key search against the symmetric key would 618 take with general purpose computers. This is an "apples-to-apples" 619 comparison, because it assumes that the attacker needs only to have 620 computation donated to his effort, not built from a personal or 621 national fortune. The public key modulus will be larger than the one 622 in 4.1, because the symmetric key is going to be viable for a longer 623 period of time. 625 Assume that the number of CPU instructions to encrypt a block of 626 material using TripleDES is 300. The estimated number of computer 627 instructions to break 112 bit TripleDES key: 629 300 * 2^112 630 = 1.6 * 10^(36) 631 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 633 Solving this approximately for n yields: 635 n = 10^(734) = 2^(2439) 637 Thus, for general purpose CPU attacks, you can assume that moduli with 638 about 2400 bits will have about the same strength against attack as an 639 112-bit TripleDES key. This indicates that RSA public key encryption 640 should use a modulus with around 2400 bits; for a Diffie-Hellman key 641 exchange, one could use a slightly smaller modulus, but it not a 642 significant difference. 644 Note that some authors assume that the algorithms underlying the number 645 field sieve will continue to get better over time. These authors 646 recommend an even larger modulus, over 4000 bits, for protecting a 112- 647 bit symmetric key for 50 years. This points out the difficulty of 648 long-term cryptographic security: it is all but impossible to predict 649 progress in mathematics and physics over such a long period of time. 651 4.3 A One Year Attack 653 Assuming a trillionaire spends his money today to buy hardware, what 654 size key exchange numbers could he "crack" in one year? He can perform 655 5*e12 MYs of instructions, or 657 3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 659 Solving for an approximation of n yields 661 n = 10^(360) = 2^(1195) 663 This is about as many operations as it would take to crack an 80-bit 664 symmetric key by brute force. 666 Thus, for protecting data that has a secrecy requirement of one year 667 against an incredibly rich attacker, a key exchange modulus with about 668 1200 bits protecting an 80-bit symmetric key is safe even against a 669 nation's resources. 671 4.4 Key equivalence for other ciphers 673 Extending this logic to the AES is straightforward. For purposes of 674 estimation for key searching, one can think of the 128-bit AES as being 675 at least 16 bits stronger than TripleDES but about three times as fast. 676 The time and cost for a brute force attack is approximately 2^(16) more 677 than for TripleDES, and thus, under the assumption that 128 bits of 678 strength is the desired security goal, the recommended key exchange 679 modulus size is about 700 bits longer. 681 If it is possible to design hardware for AES cracking that is 682 considerably more efficient than hardware for DES cracking, then (again 683 under the assumption that the key exchange strength must match the brute 684 force effort) the moduli for protecting the key exchange can be made 685 smaller. However, the existence of such designs is only a matter of 686 speculation at this early moment in the AES lifetime. 688 The AES ciphers have key sizes of 128 bits up to 256 bits. Should a 689 prudent minimum security requirement, and thus the key exchange moduli, 690 have similar strengths? The answer to this depends on whether or not 691 one expect Moore's Law to continue unabated. If it continues, one would 692 expect 128 bit keys to be safe for about 60 years, and 256 bit keys 693 would be safe for another 400 years beyond that, far beyond any 694 imaginable security requirement. But such progress is difficult to 695 predict, as it exceeds the physical capabilities of today's devices and 696 would imply the existence of logic technologies that are unknown or 697 infeasible today. Quantum computing is a candidate, but too little is 698 known today to make confident predictions about its applicability to 699 cryptography (which itself might change over the next 100 years!). 701 If Moore's Law does not continue to hold, if no new computational 702 paradigms emerge, then keys of over 100 bits in length might well be 703 safe "forever". Note, however that others have come up with estimates 704 based on assumptions of new computational paradigms emerging. For 705 example, Lenstra and Verheul's web-based paper "Selecting Cryptographic 706 Key Sizes" chooses a more conservative analysis than the one in this 707 document. 709 4.5 Hash functions for deriving symmetric keys from public key 710 algorithms 712 The Diffie-Hellman algorithm results in a key that is hundreds or 713 thousands of bits long, but ciphers need far fewer bits than that. How 714 can one distill a long key down to a short one without losing strength? 716 Cryptographic one-way hash functions are the building blocks for this, 717 and so long as they use all of the Diffie-Hellman key to derive each 718 block of the symmetric key, they produce keys with sufficient strength. 720 The usual recommendation is to use a good one-way hash function 721 applied to he base material (the result of the key exchange) and to 722 use a subset of the hash function output for the key. However, if the 723 desired key length is greater than the output of the hash function, 724 one might wonder how to reconcile the two. 726 The step of deriving extra key bits must satisfy these requirements: 728 - The bits must not reveal any information about the key exchange secret 730 - The bits must not be correlated with each other 732 - The bits must depend on all the bits of the key exchange secret 734 Any good cryptographic hash function satisfies these three 735 requirements. Note that the number of bits of output of the hash 736 function is not specified. That is because even a hash function with 737 a very short output can be iterated to produce more uncorrelated bits 738 with just a little bit of care. 740 For example, SHA-1 has 160 bits of output. For deriving a key of attack 741 resistance of 160 bits or less, SHA(DHkey) produces a good symmetric 742 key. 744 Suppose one wants a key with attack resistance of 160 bits, but it is to 745 be used with a cipher that uses 192 bit keys. One can iterate SHA-1 as 746 follows: 748 Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00) 749 (that is, concatenate a single octet of value 0x00 to 750 the right side of the DHkey, and then hash) 751 Bits 161-192 of the symmetric key = K2 = 752 select_32_bits(SHA(K1 | 0x01)) 754 But what if one wants 192 bits of strength for the cipher? Then the 755 appropriate calculation is 757 Bits 1-160 of the symmetric key = SHA(0x00 | DHkey) 758 Bits 161-192 of the symmetric key = 759 select_32_bits(SHA(0x01 | DHkey)) 761 (Note that in the description above, instead of concatenating a full 762 octet, concatenating a single bit would also be sufficient.) 764 The important distinction is that in the second case, the DH key is used 765 for each part of the symmetric key. This assures that entropy of the DH 766 key is not lost by iteration of the hash function over the same bits. 768 From an efficiency point of view, if the symmetric key must have a great 769 deal of entropy, it is probably best to use a cryptographic hash 770 function with a large output block (192 bits or more), rather than 771 iterating a smaller one. 773 4.6 Importance of ramdomness 775 Some of the calculations described in this document require random inputs. 776 The number of truly random bits is extremely important to determining 777 the strength of the output of the calculations. Using truly random 778 numbers is often overlooked, and many security applications have been 779 significantly weakened by using insufficient random inputs. A much 780 more complete description of the importance of random numbers can be 781 found in [ECS]. 783 5. Conclusion 785 In this table it is assumed that attackers use general purpose 786 computers, that the hardware is purchased in the year 2000, and that 787 mathematical knowledge relevant to the problem remains the same as 788 today. This is an pure "apples-to-apples" comparison demonstrating how 789 the time for a key exchange scales with respect to the strength 790 requirement. The subgroup size for DSA is included, if that is being 791 used for supporting authentication as part of the protocol; the DSA 792 modulus must be as long as the DH modulus, but the size of the "q" 793 subgroup is also relevant. 795 Symm. key RSA or DH DSA subgroup 796 size modulus size size 797 (bits) (bits) (bits) 799 70 947 128 800 80 1228 145 801 90 1553 153 802 100 1926 184 803 150 4575 279 804 200 8719 373 805 250 14596 475 807 5. Security Considerations 809 The equations and values given in this document are meant to be as 810 accurate as possible, based on the state of the art in general purpose 811 computers at the time that this document is being written. No 812 predictions can be completely accurate, and the formulas given here are 813 not meant to be definitive statements of fact about cryptographic 814 strengths. For example, some of the empirical results used in 815 calibrating the formulas in this document are probably not completely 816 accurate, and this inaccuracy affects the estimates. It is the authors' 817 hope that the numbers presented here vary from real world experience as 818 little as possible. 820 6. References 822 [DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an explosive 823 experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, 824 (1995) 372-385. 826 [ECS] D. Eastlake, S. Crocker. J. Schiller, "Randomness Recommendations 827 for Security", RFC 1750. 829 [GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics 830 & Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 831 pages, May 1998, O'Reilly & Associates; ISBN: 1565925203 833 [GOR93] D. Gordon, "Discrete logarithms in GF(p) using the number field 834 sieve", SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. 836 [LEN93] A. K. Lenstra, H. W. Lenstra, Jr. (eds), The development of the 837 number field sieve, Lecture Notes in Math, 1554, Springer Verlag, 838 Berlin, 1993. 840 [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple 841 Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467. 843 [ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future 844 of Integer Factorization, A. M. Odlyzko 846 [ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, 847 Designs, Codes, and Cryptography (1999). 849 [POL78] J. Pollard, "Monte Carlo methods for index computation mod p", 850 Mathematics of Computation, 32 (1978), 918-924. 852 [RFC2409] D. Harkens and D. Carrel, "Internet Key Exchange (IKE)", 853 RFC 2409. 855 [SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve 856 Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 857 '95, volume 963 of Lecture Notes in Computer Science, pages 43-56, 27- 858 31 August 1995. Springer-Verlag 860 [SIL99] R. D. Silverman, RSA Laboratories Bulletin, Number 12 - May 3, 861 1999; An Analysis of Shamir's Factoring Device 863 [SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 - April 2000, 864 A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths 866 A. Authors' Addresses 868 Hilarie Orman 869 hilarie@xmission.com 871 Paul Hoffman 872 Internet Mail Consortium and VPN Consortium 873 127 Segre Place 874 Santa Cruz, CA 95060 USA 875 paul.hoffman@imc.org and paul.hoffman@vpnc.org