idnits 2.17.1 draft-orman-public-key-lengths-08.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 page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 974 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.) ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 535 has weird spacing: '... group modul...' == Line 536 has weird spacing: '... type siz...' == Line 550 has weird spacing: '... group modul...' == Line 551 has weird spacing: '... type siz...' == Line 567 has weird spacing: '...modulus exp...' == (1 more instance...) -- 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: Informational ---------------------------------------------------------------------------- == Missing Reference: 'Shamir2003' is mentioned on line 398, but not defined == Unused Reference: 'DL' is defined on line 899, but no explicit reference was found in the text == Unused Reference: 'ODL95' is defined on line 920, but no explicit reference was found in the text == Unused Reference: 'ODL99' is defined on line 923, but no explicit reference was found in the text == Unused Reference: 'RFC2409' is defined on line 929, but no explicit reference was found in the text == Unused Reference: 'SHAMIR03' is defined on line 937, but no explicit reference was found in the text == Unused Reference: 'SIL99' is defined on line 941, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 1750 (ref. 'ECS') (Obsoleted by RFC 4086) -- Obsolete informational reference (is this intentional?): RFC 2409 (Obsoleted by RFC 4306) Summary: 5 errors (**), 0 flaws (~~), 14 warnings (==), 4 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-08.txt Purple Streak Dev. 3 January 26, 2004 Paul Hoffman 4 Expires in six months VPN Consortium 5 Intended status: Informational 7 Determining Strengths For Public Keys Used 8 For Exchanging Symmetric Keys 10 Status of this memo 12 This document is an Internet-Draft and is in full conformance with all 13 provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering Task 16 Force (IETF), its areas, and its working groups. Note that other 17 groups may also distribute working documents as Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet-Drafts as reference 22 material or to cite them other than as "work in progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft 26 Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 28 Abstract 30 Implementors of systems that use public key cryptography to exchange 31 symmetric keys need to make the public keys resistant to some 32 predetermined level of attack. That level of attack resistance is the 33 strength of the system, and the symmetric keys that are exchanged must 34 be at least as strong as the system strength requirements. The three 35 quantities, system strength, symmetric key strength, and public key 36 strength, must be consistently matched for any network protocol usage. 38 While it is fairly easy to express the system strength requirements in 39 terms of a symmetric key length and to choose a cipher that has a key 40 length equal to or exceeding that requirement, it is harder to choose a 41 public key that has a cryptographic strength meeting a symmetric key 42 strength requirement. This document explains how to determine the length 43 of an asymmetric key as a function of a symmetric key strength 44 requirement. Some rules of thumb for estimating equivalent resistance to 45 large-scale attacks on various algorithms are given. The document also 46 addresses how changing the sizes of the underlying large integers 47 (moduli, group sizes, exponents, and so on) changes the time to use the 48 algorithms for key exchange. 50 Table of Contents 52 1. Model of Protecting Symmetric Keys with Public Keys 53 1.1 The key exchange algorithms 54 2. Determining the Effort to Factor 55 2.1 Choosing parameters for the equation 56 2.2 Choosing k from empirical reports 57 2.3 Pollard's rho method 58 2.4 Limits of large memory and many machines 59 2.5 Special purpose machines 60 3. Compute Time for the Algorithms 61 3.1 Diffie-Hellman Key Exchange 62 3.1.1 Diffie-Hellman with elliptic curve groups 63 3.2 RSA encryption and decryption 64 3.3 Real-world examples 65 4. Equivalences of Key Sizes 66 4.1 Key equivalence against special purpose brute force hardware 67 4.2 Key equivalence against conventional CPU brute force attack 68 4.3 A One Year Attack: 80 bits of strength 69 4.4 Key equivalence for other ciphers 70 4.5 Hash functions for deriving symmetric keys from public key 71 algorithms 72 4.6 Importance of randomness 73 5. Conclusion 74 5.1 TWIRL Correction 75 6. Security Considerations 76 7. References 77 7.1 Informational References 78 8. Authors' Addresses 80 1. Model of Protecting Symmetric Keys with Public Keys 82 Many books on cryptography and security explain the need to exchange 83 symmetric keys in public as well as the many algorithms that are used 84 for this purpose. However, few of these discussions explain how the 85 strengths of the public keys and the symmetric keys are related. 87 To understand this, picture a house with a strong lock on the front 88 door. Next to the front door is a small lockbox that contains the key to 89 the front door. A would-be burglar who wants to break into the house 90 through the front door has two options: attack the lock on the front 91 door, or attack the lock on the lockbox in order to retrieve the key. 92 Clearly, the burglar is better off attacking the weaker of the two 93 locks. The homeowner in this situation must make sure that adding the 94 second entry option (the lockbox containing the front door key) is at 95 least as strong as the lock on the front door, in order not to make the 96 burglar's job easier. 98 An implementor designing a system for exchanging symmetric keys using 99 public key cryptography must make a similar decision. Assume that an 100 attacker wants to learn the contents of a message that is encrypted with 101 a symmetric key, and that the symmetric key was exchanged between the 102 sender and recipient using public key cryptography. The attacker has two 103 options to recover the message: a brute-force attempt to determine the 104 symmetric key by repeated guessing, or mathematical determination of the 105 private key used as the key exchange key. A smart attacker will work on 106 the easier of these two problems. 108 A simple-minded answer to the implementor's problem is to be sure that 109 the key exchange system is always significantly stronger than the 110 symmetric key; this can be done by choosing a very long public key. Such 111 a design is usually not a good idea because the key exchanges become 112 much more expensive in terms of processing time as the length of the 113 public keys go up. Thus, the implementor is faced with the task of 114 trying to match the difficulty of an attack on the symmetric key with 115 the difficulty of an attack on the public key encryption. This analysis 116 is not necessary if the key exchange can be performed with extreme 117 security for almost no cost in terms of elapsed time or CPU effort; 118 unfortunately, this is not the case for public key methods today. 120 A third consideration is the minimum security requirement of the user. 121 Assume the user is encrypting with CAST-128 and requires a symmetric key 122 with a resistance time against brute-force attack of 20 years. He might 123 start off by choosing a key with 86 random bits, and then use a one-way 124 function such as SHA-1 to "boost" that to a block of 160 bits, and then 125 take 128 of those bits as the key for CAST-128. In such a case, the key 126 exchange algorithm need only match the difficulty of 86 bits, not 128 127 bits. 129 The selection procedure is: 131 1. Determine the attack resistance necessary to satisfy the security 132 requirements of the application. Do this by estimating the minimum 133 number of computer operations that the attacker will be forced to do 134 in order to compromise the security of the system and then take the 135 logarithm base two of that number. Call that logarithm value "n". 137 A 1996 report recommended 90 bits as a good all-around choice for 138 system security. The 90 bit number should be increased by about 2/3 139 bit/year, or about 96 bits in 2005. 141 2. Choose a symmetric cipher that has a key with at least n bits and at 142 least that much cryptanalytic strength. 144 3. Choose a key exchange algorithm with a resistance to attack of at 145 least n bits. 147 A fourth consideration might be the public key authentication method 148 used to establish the identity of a user. This might be an RSA digital 149 signature or a DSA digital signature. If the modulus for the 150 authentication method isn't large enough, then the entire basis for 151 trusting the communication might fall apart. The following step is thus 152 added: 154 4. Choose an authentication algorithm with a resistance to attack of at 155 least n bits. This ensures that a similar key exchanged cannot be 156 forged between the two parties during the secrecy lifetime of the 157 encrypted material. This may not be strictly necessary if the 158 authentication keys are changed frequently and they have a 159 well-understood usage lifetime, but in lieu of this, the n bit 160 guidance is sound. 162 1.1 The key exchange algorithms 164 The Diffie-Hellman method uses a group, a generator, and exponents. In 165 today's Internet standards, the group operation is based on modular 166 multiplication. Here, the group is defined by the multiplicative group 167 of an integer, typically a prime p = 2q + 1, where q is a prime, and the 168 arithmetic is done modulo p; the generator (which is often simply 2) is 169 denoted by g. 171 In Diffie-Hellman, Alice and Bob first agree (in public or in private) 172 on the values for g and p. Alice chooses a secret large random integer 173 (a), and Bob chooses a secret random large integer (b). Alice sends Bob 174 A, which is g^a mod p; Bob sends Alice B, which is g^b mod p. Next, 175 Alice computes B^a mod p, and Bob computes A^b mod p. These two numbers 176 are equal, and the participants use a simple function of this number as 177 the symmetric key k. 179 Note that Diffie-Hellman key exchange can be done over different kinds 180 of group representations. For instance, elliptic curves defined over 181 finite fields are a particularly efficient way to compute the key 182 exchange [SCH95]. 184 For RSA key exchange, assume that Bob has a public key (m) which is 185 equal to p*q, where p and q are two secret prime numbers, and an 186 encryption exponent e, and a decryption exponent d. For the key 187 exchange, Alice sends Bob E = k^e mod m, where k is the secret symmetric 188 key being exchanged. Bob recovers k by computing E^d mod m, and the two 189 parties use k as their symmetric key. While Bob's encryption exponent e 190 can be quite small (e.g., 17 bits), his decryption exponent d will have 191 as many bits in it as m does. 193 2. Determining the Effort to Factor 195 The RSA public key encryption method is immune to brute force guessing 196 attacks because the modulus (and thus, the secret exponent d) will have 197 at least 512 bits, and that is too many possibilities to guess. The 198 Diffie-Hellman exchange is also secure against guessing because the 199 exponents will have at least twice as many bits as the symmetric keys 200 that will be derived from them. However, both methods are susceptible to 201 mathematical attacks that determine the structure of the public keys. 203 Factoring an RSA modulus will result in complete compromise of the 204 security of the private key. Solving the discrete logarithm problem for 205 a Diffie-Hellman modular exponentiation system will similarly destroy 206 the security of all key exchanges using the particular modulus. This 207 document assumes that the difficulty of solving the discrete logarithm 208 problem is equivalent to the difficulty of factoring numbers that are 209 the same size as the modulus. In fact, it is slightly harder because it 210 requires more operations; based on empirical evidence so far, the ratio 211 of difficulty is at least 20, possibly as high as 64. Solving either 212 problem requires a great deal of memory for the last stage of the 213 algorithm, the matrix reduction step. Whether or not this memory 214 requirement will continue to be the limiting factor in solving larger 215 integer problems remains to be seen. At the current time it is not, and 216 there is active research into parallel matrix algorithms that might 217 mitigate the memory requirements for this problem. 219 The number field sieve (NFS) [GOR93] [LEN93] is the best method today 220 for solving the discrete logarithm problem. The formula for estimating 221 the number of simple arithmetic operations needed to factor an integer, 222 n, using the NFS method is: 224 L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) 226 Many people prefer to discuss the number of MIPS years (MYs) that are 227 needed for large operations such as the number field sieve. For such an 228 estimation, an operation in the L(n) formula is one computer 229 instruction. Empirical evidence indicates that 4 or 5 instructions might 230 be a closer match, but this is a minor factor and this document sticks 231 with one operation/one instruction for this discussion. 233 2.1 Choosing parameters for the equation 235 The expression above has two parameters that can be estimated by 236 empirical means: k and o(1). For the range of numbers we are interested 237 in, there is little distinction between them. 239 One could assume that k is 1 and o(1) is 0. This is reasonably valid if 240 the expression is only used for estimating relative effort (instead of 241 actual effort) and one assumes that the o(1) term is very small over the 242 range of the numbers that are to be factored. 244 Or, one could assume that o(1) is small and roughly constant and thus 245 its value can be folded into k; then estimate k from reported amounts of 246 effort spent factoring large integers in tests. 248 This document uses the second approach in order to get an estimate of 249 the significance of the factor. It appears to be minor, based on the 250 following calculations. 252 Sample values from recent work with the number field sieve, collected by 253 RSA Labs, include: 255 Test name Number of Number of MYs of effort 256 decimal bits 257 digits 258 RSA130 130 430 500 259 RSA140 140 460 2000 260 RSA155 155 512 8000 262 There are no precise measurements of the amount of time used for these 263 factorizations. In most factorization tests, hundreds or thousands of 264 computers are used over a period of several months, but the number of 265 their cycles were used for the factoring project, the precise 266 distribution of processor types, speeds, and so on are not usually 267 reported. However, in all cases, the amount of effort used was far less 268 than the L(n) formula would predict if k was 1 and o(1) was 0. 270 2.2 Choosing k from empirical reports 272 By solving for k from the empirical reports, it appears that k is 273 approximately 0.02. This means that the "effective key strength" of the 274 RSA algorithm is about 5 or 6 bits less than is implied by the naive 275 application of equation L(n) (that is, setting k to 1 and o(1) to 0). 276 These estimates of k are fairly stable over the numbers reported in the 277 table. The estimate is limited to a single significant digit of k 278 because it expresses real uncertainties; however, the effect of 279 additional digits would have make only tiny changes to the recommended 280 key sizes. 282 The factorers of RSA130 used about 1700 MYs, but they felt that this was 283 unrealistically high for prediction purposes; by using more memory on 284 their machines, they could have easily reduced the time to 500 MYs. 285 Thus, the value used in preparing the table above was 500. This story 286 does, however, underscore the difficulty in getting an accurate measure 287 of effort. This document takes the reported effort for factoring RSA155 288 as being the most accurate measure. 290 As a result of examining the empirical data, it appears that the L(n) 291 formula can be used with the o(1) term set to 0 and with k set to 0.02 292 when talking about factoring numbers in the range of 100 to 200 decimal 293 digits. The equation becomes: 295 L(n) = 0.02 * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 297 To convert L(n) from simple math instructions to MYs, divide by 3*10^13. 298 The equation for the number of MYs needed to factor an integer n then 299 reduces to: 301 MYs = 6 * 10^(-16) * e^(1.92 * cubrt(ln(n) * (ln(ln(n)))^2)) 303 With what confidence can this formula be used for predicting the 304 difficulty of factoring slightly larger numbers? The answer is that it 305 should be a close upper bound, but each factorization effort is usually 306 marked by some improvement in the algorithms or their implementations 307 that makes the running time somewhat shorter than the formula would 308 indicate. 310 2.3 Pollard's rho method 312 In Diffie-Hellman exchanges, there is a second attack, Pollard's rho 313 method [POL78]. The algorithm relies on finding collisions between 314 values computed in a large number space; its success rate is 315 proportional to the square root of the size of the space. Because of 316 Pollard's rho method, the search space in a DH key exchange for the key 317 (the exponent in a g^a term), must be twice as large as the symmetric 318 key. Therefore, to securely derive a key of K bits, an implementation 319 must use an exponent with at least 2*K bits. 321 When the Diffie-Hellman key exchange is done using an elliptic curve 322 method, the NFS methods are of no avail. However, the collision method 323 is still effective, and the need for an exponent (called a multiplier in 324 EC's) with 2*K bits remains. The modulus used for the computation can 325 also be 2*K bits, and this will be substantially smaller than the 326 modulus needed for modular exponentiation methods as the desired 327 security level increases past 64 bits of brute-force attack resistance. 329 One might ask, how can you compare the number of computer instructions 330 really needed for a discrete logarithm attack to the number needed to 331 search the keyspace of a cipher? In comparing the efforts, one should 332 consider what a "basic operation" is. For brute force search of the 333 keyspace of a symmetric encryption algorithm like DES, the basic 334 operation is the time to do a key setup and the time to do one 335 encryption. For discrete logs, the basic operation is a modular 336 squaring. The log of the ratio of these two operations can be used as a 337 "normalizing factor" between the two kinds of computations. However, 338 even for very large moduli (16K bits), this factor amounts to only a few 339 bits of extra effort. 341 2.4 Limits of large memory and many machines 343 Robert Silverman has examined the question of when it will be practical 344 to factor RSA moduli larger than 512 bits. His analysis is based not 345 only on the theoretical number of operations, but it also includes 346 expectations about the availability of actual machines for performing 347 the work (this document is based only on theoretical number of 348 operations). He examines the question of whether or not we can expect 349 there be enough machines, memory, and communication to factor a very 350 large number. 352 The best factoring methods need a lot of random access memory for 353 collecting data relations (sieving) and a critical final step that does 354 a row reduction on a large matrix. The memory requirements are related 355 to the size of the number being factored (or subjected to discrete 356 logarithm solution). Silverman [SILIEEE99] [SIL00] has argued that there 357 is a practical limit to the number of machines and the amount of RAM 358 that can be brought to bear on a single problem in the foreseeable 359 future. He sees two problems in attacking a 1024-bit RSA modulus: the 360 machines doing the sieving will need 64-bit address spaces and the 361 matrix row reduction machine will need several terabytes of memory. 362 Silverman notes that very few 64-bit machines that have the 170 363 gigabytes of memory needed for sieving have been sold. Nearly a billion 364 such machines are necessary for the sieving in a reasonable amount of 365 time (a year or two). 367 Silverman's conclusion, based on the history of factoring efforts and 368 Moore's Law, is that 1024-bit RSA moduli will not be factored until 369 about 2037. This implies a much longer lifetime to RSA keys than the 370 theoretical analysis indicates. He argues that predictions about how 371 many machines and memory modules will be available can be with great 372 confidence, based on Moore's Law extrapolations and the recent history 373 of factoring efforts. 375 One should give the practical considerations a great deal of weight, but 376 in a risk analysis, the physical world is less predictable than trend 377 graphs would indicate. In considering how much trust to put into the 378 inability of the computer industry to satisfy the voracious needs of 379 factorers, one must have some insight into economic considerations that 380 are more complicated than the mathematics of factoring. The demand for 381 computer memory is hard to predict because it is based on applications: 382 a "killer app" might come along any day and send the memory industry 383 into a frenzy of sales. The number of processors available on desktops 384 may be limited by the number of desks, but very capable embedded systems 385 account for more processor sales than desktops. As embedded systems 386 absorb networking functions, it is not unimaginable that millions of 387 64-bit processors with at least gigabytes of memory will pervade our 388 environment. 390 The bottom line on this is that the key length recommendations predicted 391 by theory may be overly conservative, but they are what we have used for 392 this document. This question of machine availability is one that should 393 be reconsidered in light of current technology on a regular basis. 395 2.5 Special purpose machines 397 In August of 2003, a design for a special-purpose "sieving machine" 398 (TWIRL) surfaced [Shamir2003], and it substantially changed the cost 399 estimates for factoring numbers up to 1024 bits in size. By applying 400 many high-speed VLSI components in parallel, such a machine might be 401 able to carry out the sieving of 512-bit numbers in 10 minutes at a cost 402 of $10K for the hardware. A larger version could sieve a 1024-bit 403 number in one year for a cost of $10M. The work cites some advances in 404 approaches to the row reduction step in concluding that the security of 405 1024-bit RSA moduli is doubtful. 407 The estimates for the time and cost for factoring 512-bit and 1024-bit 408 numbers correspond to a speed-up factor of about 2 million over 409 what can be achieved with commodity processors today. 411 3. Compute Time for the Algorithms 413 This section describes how long it takes to use the algorithms to 414 perform key exchanges. Again, it is important to consider the increased 415 time it takes to exchange symmetric keys when increasing the length of 416 public keys. It is important to avoid choosing unfeasibly long public 417 keys. 419 3.1 Diffie-Hellman Key Exchange 421 A Diffie-Hellman key exchange is done with a finite cyclic group G with 422 a generator g and an exponent x. As noted in the Pollard's rho method 423 section, the exponent has twice as many bits as are needed for the final 424 key. Let the size of the group G be p, let the number of bits in the 425 base 2 representation of p be j, and let the number of bits in the 426 exponent be K. 428 In doing the operations that result in a shared key, a generator is 429 raised to a power. The most efficient way to do this involves squaring a 430 number K times and multiplying it several times along the way. Each of 431 the numbers has j/w computer words in it, where w is the number of bits 432 in a computer word (today that will be 32 or 64 bits). A naive 433 assumption is that you will need to do j squarings and j/2 multiplies; 434 fortunately, an efficient implementation will need fewer (NB: for the 435 remainder of this section, n represents j/w). 437 A squaring operation does not need to use quite as many operations as a 438 multiplication; a reasonable estimate is that squaring takes .6 the 439 number of machine instructions of a multiply. If one prepares a table 440 ahead of time with several values of small integer powers of the 441 generator g, then only about one fifth as many multiplies are needed as 442 the naive formula suggests. Therefore, one needs to do the work of 443 approximately .8*K multiplies of n-by-n word numbers. Further, each 444 multiply and squaring must be followed by a modular reduction, and a 445 good assumption is that it is as hard to do a modular reduction as it is 446 to do an n-by-n word multiply. Thus, it takes K reductions for the 447 squarings and .2*K reductions for the multiplies. Summing this, the 448 total effort for a Diffie-Hellman key exchange with K bit exponents and 449 a modulus of n words is approximately 2*K n-by-n-word multiplies. 451 For 32-bit processors, integers that use less than about 30 computer 452 words in their representation require at least n^2 instructions for an 453 n-by-n-word multiply. Larger numbers will use less time, using Karatsuba 454 multiplications, and they will scale as about n^(1.58) for larger n, but 455 that is ignored for the current discussion. Note that 64- bit processors 456 push the "Karatsuba cross-over" number out to even more bits. 458 The basic result is: if you double the size of the Diffie-Hellman 459 modular exponentiation group, you quadruple the number of operations 460 needed for the computation. 462 3.1.1 Diffie-Hellman with elliptic curve groups 464 Note that the ratios for computation effort as a function of modulus 465 size hold even if you are using an elliptic curve (EC) group for 466 Diffie-Hellman. However, for equivalent security, one can use smaller 467 numbers in the case of elliptic curves. Assume that someone has chosen 468 an modular exponentiation group with an 2048 bit modulus as being an 469 appropriate security measure for a Diffie-Hellman application and wants 470 to determine what advantage there would be to using an EC group instead. 471 The calculation is relatively straightforward, if you assume that on the 472 average, it is about 20 times more effort to do a squaring or 473 multiplication in an EC group than in a modular exponentiation group. A 474 rough estimate is that an EC group with equivalent security has about 475 200 bits in its representation. Then, assuming that the time is 476 dominated by n-by-n- word operations, the relative time is computed as: 478 ((2048/200)^2)/20 ~= 5 480 showing that an elliptic curve implementation should be five times as 481 fast as a modular exponentiation implementation. 483 3.2 RSA encryption and decryption 485 Assume that an RSA public key uses a modulus with j bits; its factors 486 are two numbers of about j/2 bits each. The expected computation time 487 for encryption and decryption are different. As before, we denote the 488 number of words in the machine representation of the modulus by the 489 symbol n. 491 Most implementations of RSA use a small exponent for encryption. An 492 encryption may involve as few as 16 squarings and one multiplication, 493 using n-by-n-word operations. Each operation must be followed by a 494 modular reduction, and therefore the time complexity is about 16*(.6 + 495 1) + 1 + 1 ~= 28 n-by-n-word multiplies. 497 RSA decryption must use an exponent that has as many bits as the 498 modulus, j. However, the Chinese Remainder Theorem applies, and all the 499 computations can be done with a modulus of only n/2 words and an 500 exponent of only j/2 bits. The computation must be done twice, once for 501 each factor. The effort is equivalent to 2*(j/2) (n/2 by n/2)-word 502 multiplies. Because multiplying numbers with n/2 words is only 1/4 as 503 difficult as multiplying numbers with n words, the equivalent effort for 504 RSA decryption is j/4 n-by-n-word multiplies. 506 If you double the size of the modulus for RSA, the n-by-n multiplies 507 will take four times as long. Further, the decryption time doubles 508 because the exponent is larger. The overall scaling cost is a factor of 509 4 for encryption, a factor of 8 for decryption. 511 3.3 Real-world examples 513 To make these numbers more real, here are a few examples of software 514 implementations run on hardware that was current as of a few years 515 before the publication of this document. The examples are included to 516 show rough estimates of reasonable implementations; they are not 517 benchmarks. As with all software, the performance will depend on the 518 exact details of specialization of the code to the problem and the 519 specific hardware. 521 The best time informally reported for a 1024-bit modular exponentiation 522 (the decryption side of 2048-bit RSA), is 0.9 ms (about 450,000 CPU 523 cycles) on a 500 MHz Itanium processor. This shows that newer processors 524 are not losing ground on big number operations; the number of 525 instructions is less than a 32-bit processor uses for a 256-bit modular 526 exponentiation. 528 For less advanced processors timing, the following two tables (computed 529 by Tero Monenen at SSH Communications) for modular exponentiation, such 530 as would be done in a Diffie-Hellman key exchange. 532 Celeron 400 MHz; compiled with GNU C compiler, optimized, some platform 533 specific coding optimizations: 535 group modulus exponent time 536 type size size 537 mod 768 ~150 18 msec 538 mod 1024 ~160 32 msec 539 mod 1536 ~180 82 msec 540 ecn 155 ~150 35 msec 541 ecn 185 ~200 56 msec 543 The group type is from RFC2409 and is either modular exponentiation 544 ("mod") or elliptic curve ("ecn"). All sizes here and in subsequent 545 tables are in bits. 547 Alpha 500 MHz compiled with Digital's C compiler, optimized, no platform 548 specific code: 550 group modulus exponent time 551 type size size 552 mod 768 ~150 12 msec 553 mod 1024 ~160 24 msec 554 mod 1536 ~180 59 msec 555 ecn 155 ~150 20 msec 556 ecn 185 ~200 27 msec 558 The following two tables (computed by Eric Young) were originally for 559 RSA signing operations, using the Chinese Remainder representation. For 560 ease of understanding, the parameters are presented here to show the 561 interior calculations, i.e., the size of the modulus and exponent used 562 by the software. 564 Dual Pentium II-350: 566 equiv equiv equiv 567 modulus exponent time 568 size size 569 256 256 1.5 ms 570 512 512 8.6 ms 571 1024 1024 55.4 ms 572 2048 2048 387 ms 574 Alpha 264 600mhz: 576 equiv equiv equiv 577 modulus exponent time 578 size size 579 512 512 1.4 ms 581 Current chips that accelerate exponentiation can perform 1024-bit 582 exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 583 milliseconds or less. 585 4. Equivalences of Key Sizes 587 In order to determine how strong a public key is needed to protect a 588 particular symmetric key, you first need to determine how much effort is 589 needed to break the symmetric key. Many Internet security protocols 590 require the use of TripleDES for strong symmetric encryption, and it is 591 expected that the Advanced Encryption Standard (AES) will be adopted on 592 the Internet in the coming years. Therefore, these two algorithms are 593 discussed here. In this section, for illustrative purposes, we will 594 implicitly assume that the system security requirement is 112 bits; this 595 doesn't mean that 112 bits is recommended. In fact, 112 bits is arguably 596 too strong for any practical purpose. It is used for illustration simply 597 because that is the upper bound on the strength of TripleDES. 599 If one could simply determine the number of MYs it takes to break 600 TripleDES, the task of computing the public key size of equivalent 601 strength would be easy. Unfortunately, that isn't the case here because 602 there are many examples of DES-specific hardware that encrypt faster 603 than DES in software on a standard CPU. Instead, one must determine the 604 equivalent cost for a system to break TripleDES and a system to break 605 the public key protecting a TripleDES key. 607 In 1998, the Electronic Frontier Foundation (EFF) built a DES-cracking 608 machine [GIL98] for US$130,000 that could test about 1e11 DES keys per 609 second (additional money was spent on the machine's design). The 610 machine's builders fully admit that the machine is not well optimized, 611 and it is estimated that ten times the amount of money could probably 612 create a machine about 50 times as fast. Assuming more optimization by 613 guessing that a system to test TripleDES keys runs about as fast as a 614 system to test DES keys, so approximately US$1 million might test 5e12 615 TripleDES keys per second. 617 In case your adversaries are much richer than EFF, you may want to 618 assume that they have US$1 trillion, enough to test 5e18 keys per 619 second. An exhaustive search of the effective TripleDES space of 2^112 620 keys with this quite expensive system would take about 1e15 seconds or 621 about 33 million years. (Note that such a system would also need 2^60 622 bytes of RAM [MH81], which is considered free in this calculation). This 623 seems a needlessly conservative value. However, if computer logic speeds 624 continue to increase in accordance with Moore's Law (doubling in speed 625 every 1.5 years), then one might expect that in about 50 years, the 626 computation could be completed in only one year. For the purposes of 627 illustration, this 50 year resistance against a trillionaire is assumed 628 to be the minimum security requirement for a set of applications. 630 If 112 bits of attack resistance is the system security requirement, 631 then the key exchange system for TripleDES should have equivalent 632 difficulty; that is to say, if the attacker has US$1 trillion, you want 633 him to spend all his money to buy hardware today and to know that he 634 will "crack" the key exchange in not less than 33 million years. 635 (Obviously, a rational attacker would wait for about 45 years before 636 actually spending the money, because he could then get much better 637 hardware, but all attackers benefit from this sort of wait equally.) 639 It is estimated that a typical PC CPU of just a few years ago can 640 generate over 500 MIPs and could be purchased for about US$100 in 641 quantity; thus you get more than 5 MIPs/US$. Again, this number doubles 642 about every 18 months. For one trillion US dollars, an attacker can get 643 5e12 MIP years of computer instructions on that recent-vintage hardware. 644 This figure is used in the following estimates of equivalent costs for 645 breaking key exchange systems. 647 4.1 Key equivalence against special purpose brute force hardware 649 If the trillionaire attacker is to use conventional CPU's to "crack" a 650 key exchange for a 112 bit key in the same time that the special purpose 651 machine is spending on brute force search for the symmetric key, the key 652 exchange system must use an appropriately large modulus. Assume that the 653 trillionaire performs 5e12 MIPs of instructions per year. Use the 654 following equation to estimate the modulus size to use with RSA 655 encryption or DH key exchange: 657 5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 659 Solving this approximately for n yields: 661 n = 10^(625) = 2^(2077) 663 Thus, assuming similar logic speeds and the current efficiency of the 664 number field sieve, moduli with about 2100 bits will have about the same 665 resistance against attack as an 112-bit TripleDES key. This indicates 666 that RSA public key encryption should use a modulus with around 2100 667 bits; for a Diffie-Hellman key exchange, one could use a slightly 668 smaller modulus, but it is not a significant difference. 670 4.2 Key equivalence against conventional CPU brute force attack 672 An alternative way of estimating this assumes that the attacker has a 673 less challenging requirement: he must only "crack" the key exchange in 674 less time than a brute force key search against the symmetric key would 675 take with general purpose computers. This is an "apples-to-apples" 676 comparison, because it assumes that the attacker needs only to have 677 computation donated to his effort, not built from a personal or national 678 fortune. The public key modulus will be larger than the one in 4.1, 679 because the symmetric key is going to be viable for a longer period of 680 time. 682 Assume that the number of CPU instructions to encrypt a block of 683 material using TripleDES is 300. The estimated number of computer 684 instructions to break 112 bit TripleDES key: 686 300 * 2^112 687 = 1.6 * 10^(36) 688 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 690 Solving this approximately for n yields: 692 n = 10^(734) = 2^(2439) 694 Thus, for general purpose CPU attacks, you can assume that moduli with 695 about 2400 bits will have about the same strength against attack as an 696 112-bit TripleDES key. This indicates that RSA public key encryption 697 should use a modulus with around 2400 bits; for a Diffie-Hellman key 698 exchange, one could use a slightly smaller modulus, but it not a 699 significant difference. 701 Note that some authors assume that the algorithms underlying the number 702 field sieve will continue to get better over time. These authors 703 recommend an even larger modulus, over 4000 bits, for protecting a 112- 704 bit symmetric key for 50 years. This points out the difficulty of 705 long-term cryptographic security: it is all but impossible to predict 706 progress in mathematics and physics over such a long period of time. 708 4.3 A One Year Attack: 80 bits of strength 710 Assuming a trillionaire spends his money today to buy hardware, what 711 size key exchange numbers could he "crack" in one year? He can perform 712 5*e12 MYs of instructions, or 714 3*10^13 * 5*10^12 = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) 716 Solving for an approximation of n yields 718 n = 10^(360) = 2^(1195) 720 This is about as many operations as it would take to crack an 80-bit 721 symmetric key by brute force. 723 Thus, for protecting data that has a secrecy requirement of one year 724 against an incredibly rich attacker, a key exchange modulus with about 725 1200 bits protecting an 80-bit symmetric key is safe even against a 726 nation's resources. 728 4.4 Key equivalence for other ciphers 730 Extending this logic to the AES is straightforward. For purposes of 731 estimation for key searching, one can think of the 128-bit AES as being 732 at least 16 bits stronger than TripleDES but about three times as fast. 733 The time and cost for a brute force attack is approximately 2^(16) more 734 than for TripleDES, and thus, under the assumption that 128 bits of 735 strength is the desired security goal, the recommended key exchange 736 modulus size is about 700 bits longer. 738 If it is possible to design hardware for AES cracking that is 739 considerably more efficient than hardware for DES cracking, then (again 740 under the assumption that the key exchange strength must match the brute 741 force effort) the moduli for protecting the key exchange can be made 742 smaller. However, the existence of such designs is only a matter of 743 speculation at this early moment in the AES lifetime. 745 The AES ciphers have key sizes of 128 bits up to 256 bits. Should a 746 prudent minimum security requirement, and thus the key exchange moduli, 747 have similar strengths? The answer to this depends on whether or not one 748 expect Moore's Law to continue unabated. If it continues, one would 749 expect 128 bit keys to be safe for about 60 years, and 256 bit keys 750 would be safe for another 400 years beyond that, far beyond any 751 imaginable security requirement. But such progress is difficult to 752 predict, as it exceeds the physical capabilities of today's devices and 753 would imply the existence of logic technologies that are unknown or 754 infeasible today. Quantum computing is a candidate, but too little is 755 known today to make confident predictions about its applicability to 756 cryptography (which itself might change over the next 100 years!). 758 If Moore's Law does not continue to hold, if no new computational 759 paradigms emerge, then keys of over 100 bits in length might well be 760 safe "forever". Note, however that others have come up with estimates 761 based on assumptions of new computational paradigms emerging. For 762 example, Lenstra and Verheul's web-based paper "Selecting Cryptographic 763 Key Sizes" chooses a more conservative analysis than the one in this 764 document. 766 4.5 Hash functions for deriving symmetric keys from public key 767 algorithms 769 The Diffie-Hellman algorithm results in a key that is hundreds or 770 thousands of bits long, but ciphers need far fewer bits than that. How 771 can one distill a long key down to a short one without losing strength? 773 Cryptographic one-way hash functions are the building blocks for this, 774 and so long as they use all of the Diffie-Hellman key to derive each 775 block of the symmetric key, they produce keys with sufficient strength. 777 The usual recommendation is to use a good one-way hash function applied 778 to he base material (the result of the key exchange) and to use a subset 779 of the hash function output for the key. However, if the desired key 780 length is greater than the output of the hash function, one might wonder 781 how to reconcile the two. 783 The step of deriving extra key bits must satisfy these requirements: 785 - The bits must not reveal any information about the key exchange secret 787 - The bits must not be correlated with each other 789 - The bits must depend on all the bits of the key exchange secret 791 Any good cryptographic hash function satisfies these three requirements. 792 Note that the number of bits of output of the hash function is not 793 specified. That is because even a hash function with a very short output 794 can be iterated to produce more uncorrelated bits with just a little bit 795 of care. 797 For example, SHA-1 has 160 bits of output. For deriving a key of attack 798 resistance of 160 bits or less, SHA(DHkey) produces a good symmetric 799 key. 801 Suppose one wants a key with attack resistance of 160 bits, but it is to 802 be used with a cipher that uses 192 bit keys. One can iterate SHA-1 as 803 follows: 805 Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00) 806 (that is, concatenate a single octet of value 0x00 to 807 the right side of the DHkey, and then hash) 808 Bits 161-192 of the symmetric key = K2 = 809 select_32_bits(SHA(K1 | 0x01)) 811 But what if one wants 192 bits of strength for the cipher? Then the 812 appropriate calculation is 814 Bits 1-160 of the symmetric key = SHA(0x00 | DHkey) 815 Bits 161-192 of the symmetric key = 816 select_32_bits(SHA(0x01 | DHkey)) 818 (Note that in the description above, instead of concatenating a full 819 octet, concatenating a single bit would also be sufficient.) 821 The important distinction is that in the second case, the DH key is used 822 for each part of the symmetric key. This assures that entropy of the DH 823 key is not lost by iteration of the hash function over the same bits. 825 >From an efficiency point of view, if the symmetric key must have a great 826 deal of entropy, it is probably best to use a cryptographic hash 827 function with a large output block (192 bits or more), rather than 828 iterating a smaller one. 830 Newer hash algorithms with longer output (such as SHA-256, SHA-384, and 831 SHA-512) can be used with the same level of security as the stretching 832 algorithm described above. 834 4.6 Importance of randomness 836 Some of the calculations described in this document require random 837 inputs; for example, the secret Diffie-Hellman exponents must be chosen 838 based on n truly random bits (where n is the system security 839 requirement). The number of truly random bits is extremely important to 840 determining the strength of the output of the calculations. Using truly 841 random numbers is often overlooked, and many security applications have 842 been significantly weakened by using insufficient random inputs. A much 843 more complete description of the importance of random numbers can be 844 found in [ECS]. 846 5. Conclusion 848 In this table it is assumed that attackers use general purpose 849 computers, that the hardware is purchased in the year 2000, and that 850 mathematical knowledge relevant to the problem remains the same as 851 today. This is an pure "apples-to-apples" comparison demonstrating how 852 the time for a key exchange scales with respect to the strength 853 requirement. The subgroup size for DSA is included, if that is being 854 used for supporting authentication as part of the protocol; the DSA 855 modulus must be as long as the DH modulus, but the size of the "q" 856 subgroup is also relevant. 858 +-------------+-----------+--------------+--------------+ 859 | System | | | | 860 | requirement | Symmetric | RSA or DH | DSA subgroup | 861 | for attack | key size | modulus size | size | 862 | resistance | (bits) | (bits) | (bits) | 863 | (bits) | | | | 864 +-------------+-----------+--------------+--------------+ 865 | 70 | 70 | 947 | 129 | 866 | 80 | 80 | 1228 | 148 | 867 | 90 | 90 | 1553 | 167 | 868 | 100 | 100 | 1926 | 186 | 869 | 150 | 150 | 4575 | 284 | 870 | 200 | 200 | 8719 | 383 | 871 | 250 | 250 | 14596 | 482 | 872 +-------------+-----------+--------------+--------------+ 874 5.1 TWIRL Correction 876 If the TWIRL machine becomes a reality, and if there are advances in 877 parallelism for row reduction in factoring, then conservative 878 estimates would subtract about 11 bits from the system security column 879 of the table. Thus, in order to get 89 bits of security, one would 880 need an RSA modulus of about 1900 bits. 882 6. Security Considerations 884 The equations and values given in this document are meant to be as 885 accurate as possible, based on the state of the art in general purpose 886 computers at the time that this document is being written. No 887 predictions can be completely accurate, and the formulas given here are 888 not meant to be definitive statements of fact about cryptographic 889 strengths. For example, some of the empirical results used in 890 calibrating the formulas in this document are probably not completely 891 accurate, and this inaccuracy affects the estimates. It is the authors' 892 hope that the numbers presented here vary from real world experience as 893 little as possible. 895 7. References 897 7.1 Informational References 899 [DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an explosive 900 experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, 901 (1995) 372-385. 903 [ECS] D. Eastlake, S. Crocker. J. Schiller, "Randomness Recommendations 904 for Security", RFC 1750. 906 [GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics & 907 Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 908 pages, May 1998, O'Reilly & Associates; ISBN: 1565925203 910 [GOR93] D. Gordon, "Discrete logarithms in GF(p) using the number field 911 sieve", SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. 913 [LEN93] A. K. Lenstra, H. W. Lenstra, Jr. (eds), The development of the 914 number field sieve, Lecture Notes in Math, 1554, Springer Verlag, 915 Berlin, 1993. 917 [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple 918 Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467. 920 [ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future 921 of Integer Factorization, A. M. Odlyzko 923 [ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, 924 Designs, Codes, and Cryptography (1999). 926 [POL78] J. Pollard, "Monte Carlo methods for index computation mod p", 927 Mathematics of Computation, 32 (1978), 918-924. 929 [RFC2409] D. Harkens and D. Carrel, "Internet Key Exchange (IKE)", RFC 930 2409. 932 [SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve 933 Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 934 '95, volume 963 of Lecture Notes in Computer Science, pages 43-56, 27- 935 31 August 1995. Springer-Verlag 937 [SHAMIR03] Shamir, Adi and Eran Tromer, "Factoring Large Numbers 938 with the TWIRL Device", Advances in Cryptology - CRYPTO 2003, 939 Springer, Lecture Notes in Computer Science 2729. 941 [SIL99] R. D. Silverman, RSA Laboratories Bulletin, Number 12 - May 3, 942 1999; An Analysis of Shamir's Factoring Device 944 [SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 - April 945 2000, A Cost-Based Security Analysis of Symmetric and Asymmetric Key 946 Lengths 948 [SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer, 949 August 1999. 951 8. Authors' Addresses 953 Hilarie Orman 954 Purple Streak Development 955 500 S. Maple Dr. 956 Salem, UT 84653 957 hilarie@purplestreak.com and ho@alum.mit.edu 959 Paul Hoffman 960 VPN Consortium 961 127 Segre Place 962 Santa Cruz, CA 95060 USA 963 paul.hoffman@vpnc.org