Network Working Group H. Orman Request for Comments: 3766 Purple Streak Dev. BCP: 86 P. Hoffman Category: Best Current Practice VPN Consortium April 2004 Determining Strengths For Public Keys Used For Exchanging Symmetric Keys Status of this Memo This document specifies an Internet Best Current Practices for the Internet Community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2004). All Rights Reserved.
AbstractImplementors of systems that use public key cryptography to exchange symmetric keys need to make the public keys resistant to some predetermined level of attack. That level of attack resistance is the strength of the system, and the symmetric keys that are exchanged must be at least as strong as the system strength requirements. The three quantities, system strength, symmetric key strength, and public key strength, must be consistently matched for any network protocol usage. While it is fairly easy to express the system strength requirements in terms of a symmetric key length and to choose a cipher that has a key length equal to or exceeding that requirement, it is harder to choose a public key that has a cryptographic strength meeting a symmetric key strength requirement. This document explains how to determine the length of an asymmetric key as a function of a symmetric key strength requirement. Some rules of thumb for estimating equivalent resistance to large-scale attacks on various algorithms are given. The document also addresses how changing the sizes of the underlying large integers (moduli, group sizes, exponents, and so on) changes the time to use the algorithms for key exchange.
1. Model of Protecting Symmetric Keys with Public Keys. . . . . . 2 1.1. The key exchange algorithms . . . . . . . . . . . . . . . 4 2. Determining the Effort to Factor . . . . . . . . . . . . . . . 5 2.1. Choosing parameters for the equation. . . . . . . . . . . 6 2.2. Choosing k from empirical reports . . . . . . . . . . . . 7 2.3. Pollard's rho method. . . . . . . . . . . . . . . . . . . 7 2.4. Limits of large memory and many machines. . . . . . . . . 8 2.5. Special purpose machines. . . . . . . . . . . . . . . . . 9 3. Compute Time for the Algorithms. . . . . . . . . . . . . . . . 10 3.1. Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . 10 3.1.1. Diffie-Hellman with elliptic curve groups. . . . . 11 3.2. RSA encryption and decryption . . . . . . . . . . . . . . 11 3.3. Real-world examples . . . . . . . . . . . . . . . . . . . 12 4. Equivalences of Key Sizes. . . . . . . . . . . . . . . . . . . 13 4.1. Key equivalence against special purpose brute force hardware. . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2. Key equivalence against conventional CPU brute force attack. . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3. A One Year Attack: 80 bits of strength. . . . . . . . . . 16 4.4. Key equivalence for other ciphers . . . . . . . . . . . . 16 4.5. Hash functions for deriving symmetric keys from public key algorithms. . . . . . . . . . . . . . . . . . . . . . 17 4.6. Importance of randomness. . . . . . . . . . . . . . . . . 19 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1. TWIRL Correction. . . . . . . . . . . . . . . . . . . . . 20 6. Security Considerations. . . . . . . . . . . . . . . . . . . . 20 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7.1. Informational References. . . . . . . . . . . . . . . . . 20 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 22 9. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 23
sure that adding the second entry option (the lockbox containing the front door key) is at least as strong as the lock on the front door, in order not to make the burglar's job easier. An implementor designing a system for exchanging symmetric keys using public key cryptography must make a similar decision. Assume that an attacker wants to learn the contents of a message that is encrypted with a symmetric key, and that the symmetric key was exchanged between the sender and recipient using public key cryptography. The attacker has two options to recover the message: a brute-force attempt to determine the symmetric key by repeated guessing, or mathematical determination of the private key used as the key exchange key. A smart attacker will work on the easier of these two problems. A simple-minded answer to the implementor's problem is to be sure that the key exchange system is always significantly stronger than the symmetric key; this can be done by choosing a very long public key. Such a design is usually not a good idea because the key exchanges become much more expensive in terms of processing time as the length of the public keys go up. Thus, the implementor is faced with the task of trying to match the difficulty of an attack on the symmetric key with the difficulty of an attack on the public key encryption. This analysis is not necessary if the key exchange can be performed with extreme security for almost no cost in terms of elapsed time or CPU effort; unfortunately, this is not the case for public key methods today. A third consideration is the minimum security requirement of the user. Assume the user is encrypting with CAST-128 and requires a symmetric key with a resistance time against brute-force attack of 20 years. He might start off by choosing a key with 86 random bits, and then use a one-way function such as SHA-1 to "boost" that to a block of 160 bits, and then take 128 of those bits as the key for CAST-128. In such a case, the key exchange algorithm need only match the difficulty of 86 bits, not 128 bits. The selection procedure is: 1. Determine the attack resistance necessary to satisfy the security requirements of the application. Do this by estimating the minimum number of computer operations that the attacker will be forced to do in order to compromise the security of the system and then take the logarithm base two of that number. Call that logarithm value "n".
A 1996 report recommended 90 bits as a good all-around choice for system security. The 90 bit number should be increased by about 2/3 bit/year, or about 96 bits in 2005. 2. Choose a symmetric cipher that has a key with at least n bits and at least that much cryptanalytic strength. 3. Choose a key exchange algorithm with a resistance to attack of at least n bits. A fourth consideration might be the public key authentication method used to establish the identity of a user. This might be an RSA digital signature or a DSA digital signature. If the modulus for the authentication method isn't large enough, then the entire basis for trusting the communication might fall apart. The following step is thus added: 4. Choose an authentication algorithm with a resistance to attack of at least n bits. This ensures that a similar key exchanged cannot be forged between the two parties during the secrecy lifetime of the encrypted material. This may not be strictly necessary if the authentication keys are changed frequently and they have a well- understood usage lifetime, but in lieu of this, the n bit guidance is sound. SCH95].
For RSA key exchange, assume that Bob has a public key (m) which is equal to p*q, where p and q are two secret prime numbers, and an encryption exponent e, and a decryption exponent d. For the key exchange, Alice sends Bob E = k^e mod m, where k is the secret symmetric key being exchanged. Bob recovers k by computing E^d mod m, and the two parties use k as their symmetric key. While Bob's encryption exponent e can be quite small (e.g., 17 bits), his decryption exponent d will have as many bits in it as m does. GOR93] [LEN93] is the best method today for solving the discrete logarithm problem. The formula for estimating the number of simple arithmetic operations needed to factor an integer, n, using the NFS method is: L(n) = k * e^((1.92 + o(1)) * cubrt(ln(n) * (ln(ln(n)))^2)) Many people prefer to discuss the number of MIPS years (MYs) that are needed for large operations such as the number field sieve. For such an estimation, an operation in the L(n) formula is one computer
instruction. Empirical evidence indicates that 4 or 5 instructions might be a closer match, but this is a minor factor and this document sticks with one operation/one instruction for this discussion. ODL95]. Results indicating that for the Number Field Sieve factoring method, the actual number of operations is less than expected, are found in [DL].
POL78]. The algorithm relies on finding collisions between values computed in a large number space; its success rate is proportional to the square root of the size of the space. Because of Pollard's rho method, the search space in a DH key exchange for the key (the exponent in a g^a term), must be twice as large as the
symmetric key. Therefore, to securely derive a key of K bits, an implementation must use an exponent with at least 2*K bits. See [ODL99] for more detail. When the Diffie-Hellman key exchange is done using an elliptic curve method, the NFS methods are of no avail. However, the collision method is still effective, and the need for an exponent (called a multiplier in EC's) with 2*K bits remains. The modulus used for the computation can also be 2*K bits, and this will be substantially smaller than the modulus needed for modular exponentiation methods as the desired security level increases past 64 bits of brute-force attack resistance. One might ask, how can you compare the number of computer instructions really needed for a discrete logarithm attack to the number needed to search the keyspace of a cipher? In comparing the efforts, one should consider what a "basic operation" is. For brute force search of the keyspace of a symmetric encryption algorithm like DES, the basic operation is the time to do a key setup and the time to do one encryption. For discrete logs, the basic operation is a modular squaring. The log of the ratio of these two operations can be used as a "normalizing factor" between the two kinds of computations. However, even for very large moduli (16K bits), this factor amounts to only a few bits of extra effort. SILIEEE99] [SIL00] has argued that there is a practical limit to the number of machines and the amount of RAM that can be brought to bear on a single problem in the foreseeable future. He sees two problems in attacking a 1024-bit RSA modulus: the machines doing the sieving will need 64-bit address spaces and the matrix row reduction machine will need several terabytes of memory. Silverman notes that very few 64-bit machines
that have the 170 gigabytes of memory needed for sieving have been sold. Nearly a billion such machines are necessary for the sieving in a reasonable amount of time (a year or two). Silverman's conclusion, based on the history of factoring efforts and Moore's Law, is that 1024-bit RSA moduli will not be factored until about 2037. This implies a much longer lifetime to RSA keys than the theoretical analysis indicates. He argues that predictions about how many machines and memory modules will be available can be with great confidence, based on Moore's Law extrapolations and the recent history of factoring efforts. One should give the practical considerations a great deal of weight, but in a risk analysis, the physical world is less predictable than trend graphs would indicate. In considering how much trust to put into the inability of the computer industry to satisfy the voracious needs of factorers, one must have some insight into economic considerations that are more complicated than the mathematics of factoring. The demand for computer memory is hard to predict because it is based on applications: a "killer app" might come along any day and send the memory industry into a frenzy of sales. The number of processors available on desktops may be limited by the number of desks, but very capable embedded systems account for more processor sales than desktops. As embedded systems absorb networking functions, it is not unimaginable that millions of 64-bit processors with at least gigabytes of memory will pervade our environment. The bottom line on this is that the key length recommendations predicted by theory may be overly conservative, but they are what we have used for this document. This question of machine availability is one that should be reconsidered in light of current technology on a regular basis.
The basic result is: if you double the size of the Diffie-Hellman modular exponentiation group, you quadruple the number of operations needed for the computation.
If you double the size of the modulus for RSA, the n-by-n multiplies will take four times as long. Further, the decryption time doubles because the exponent is larger. The overall scaling cost is a factor of 4 for encryption, a factor of 8 for decryption. RFC2409] and is either modular exponentiation ("mod") or elliptic curve ("ecn"). All sizes here and in subsequent tables are in bits.
Alpha 500 MHz compiled with Digital's C compiler, optimized, no platform specific code: group modulus exponent time type size size mod 768 ~150 12 msec mod 1024 ~160 24 msec mod 1536 ~180 59 msec ecn 155 ~150 20 msec ecn 185 ~200 27 msec The following two tables (computed by Eric Young) were originally for RSA signing operations, using the Chinese Remainder representation. For ease of understanding, the parameters are presented here to show the interior calculations, i.e., the size of the modulus and exponent used by the software. Dual Pentium II-350: equiv equiv equiv modulus exponent time size size 256 256 1.5 ms 512 512 8.6 ms 1024 1024 55.4 ms 2048 2048 387 ms Alpha 264 600mhz: equiv equiv equiv modulus exponent time size size 512 512 1.4 ms Recent chips that accelerate exponentiation can perform 1024-bit exponentiations (1024 bit modulus, 1024 bit exponent) in about 3 milliseconds or less.
security requirement is 112 bits; this doesn't mean that 112 bits is recommended. In fact, 112 bits is arguably too strong for any practical purpose. It is used for illustration simply because that is the upper bound on the strength of TripleDES. If one could simply determine the number of MYs it takes to break TripleDES, the task of computing the public key size of equivalent strength would be easy. Unfortunately, that isn't the case here because there are many examples of DES-specific hardware that encrypt faster than DES in software on a standard CPU. Instead, one must determine the equivalent cost for a system to break TripleDES and a system to break the public key protecting a TripleDES key. In 1998, the Electronic Frontier Foundation (EFF) built a DES- cracking machine [GIL98] for US$130,000 that could test about 1e11 DES keys per second (additional money was spent on the machine's design). The machine's builders fully admit that the machine is not well optimized, and it is estimated that ten times the amount of money could probably create a machine about 50 times as fast. Assuming more optimization by guessing that a system to test TripleDES keys runs about as fast as a system to test DES keys, so approximately US$1 million might test 5e12 TripleDES keys per second. In case your adversaries are much richer than EFF, you may want to assume that they have US$1 trillion, enough to test 5e18 keys per second. An exhaustive search of the effective TripleDES space of 2^112 keys with this quite expensive system would take about 1e15 seconds or about 33 million years. (Note that such a system would also need 2^60 bytes of RAM [MH81], which is considered free in this calculation). This seems a needlessly conservative value. However, if computer logic speeds continue to increase in accordance with Moore's Law (doubling in speed every 1.5 years), then one might expect that in about 50 years, the computation could be completed in only one year. For the purposes of illustration, this 50 year resistance against a trillionaire is assumed to be the minimum security requirement for a set of applications. If 112 bits of attack resistance is the system security requirement, then the key exchange system for TripleDES should have equivalent difficulty; that is to say, if the attacker has US$1 trillion, you want him to spend all his money to buy hardware today and to know that he will "crack" the key exchange in not less than 33 million years. (Obviously, a rational attacker would wait for about 45 years before actually spending the money, because he could then get much better hardware, but all attackers benefit from this sort of wait equally.)
It is estimated that a typical PC CPU of just a few years ago can generate over 500 MIPs and could be purchased for about US$100 in quantity; thus you get more than 5 MIPs/US$. Again, this number doubles about every 18 months. For one trillion US dollars, an attacker can get 5e12 MIP years of computer instructions on that recent-vintage hardware. This figure is used in the following estimates of equivalent costs for breaking key exchange systems.
300 * 2^112 = 1.6 * 10^(36) = .02*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2)) Solving this approximately for n yields: n = 10^(734) = 2^(2439) Thus, for general purpose CPU attacks, you can assume that moduli with about 2400 bits will have about the same strength against attack as an 112-bit TripleDES key. This indicates that RSA public key encryption should use a modulus with around 2400 bits; for a Diffie- Hellman key exchange, one could use a slightly smaller modulus, but it not a significant difference. Note that some authors assume that the algorithms underlying the number field sieve will continue to get better over time. These authors recommend an even larger modulus, over 4000 bits, for protecting a 112-bit symmetric key for 50 years. This points out the difficulty of long-term cryptographic security: it is all but impossible to predict progress in mathematics and physics over such a long period of time.
as fast. The time and cost for a brute force attack is approximately 2^(16) more than for TripleDES, and thus, under the assumption that 128 bits of strength is the desired security goal, the recommended key exchange modulus size is about 700 bits longer. If it is possible to design hardware for AES cracking that is considerably more efficient than hardware for DES cracking, then (again under the assumption that the key exchange strength must match the brute force effort) the moduli for protecting the key exchange can be made smaller. However, the existence of such designs is only a matter of speculation at this early moment in the AES lifetime. The AES ciphers have key sizes of 128 bits up to 256 bits. Should a prudent minimum security requirement, and thus the key exchange moduli, have similar strengths? The answer to this depends on whether or not one expect Moore's Law to continue unabated. If it continues, one would expect 128 bit keys to be safe for about 60 years, and 256 bit keys would be safe for another 400 years beyond that, far beyond any imaginable security requirement. But such progress is difficult to predict, as it exceeds the physical capabilities of today's devices and would imply the existence of logic technologies that are unknown or infeasible today. Quantum computing is a candidate, but too little is known today to make confident predictions about its applicability to cryptography (which itself might change over the next 100 years!). If Moore's Law does not continue to hold, if no new computational paradigms emerge, then keys of over 100 bits in length might well be safe "forever". Note, however that others have come up with estimates based on assumptions of new computational paradigms emerging. For example, Lenstra and Verheul's web-based paper "Selecting Cryptographic Key Sizes" chooses a more conservative analysis than the one in this document.
The usual recommendation is to use a good one-way hash function applied to he base material (the result of the key exchange) and to use a subset of the hash function output for the key. However, if the desired key length is greater than the output of the hash function, one might wonder how to reconcile the two. The step of deriving extra key bits must satisfy these requirements: - The bits must not reveal any information about the key exchange secret - The bits must not be correlated with each other - The bits must depend on all the bits of the key exchange secret Any good cryptographic hash function satisfies these three requirements. Note that the number of bits of output of the hash function is not specified. That is because even a hash function with a very short output can be iterated to produce more uncorrelated bits with just a little bit of care. For example, SHA-1 has 160 bits of output. For deriving a key of attack resistance of 160 bits or less, SHA(DHkey) produces a good symmetric key. Suppose one wants a key with attack resistance of 160 bits, but it is to be used with a cipher that uses 192 bit keys. One can iterate SHA-1 as follows: Bits 1-160 of the symmetric key = K1 = SHA(DHkey | 0x00) (that is, concatenate a single octet of value 0x00 to the right side of the DHkey, and then hash) Bits 161-192 of the symmetric key = K2 = select_32_bits(SHA(K1 | 0x01)) But what if one wants 192 bits of strength for the cipher? Then the appropriate calculation is Bits 1-160 of the symmetric key = SHA(0x00 | DHkey) Bits 161-192 of the symmetric key = select_32_bits(SHA(0x01 | DHkey)) (Note that in the description above, instead of concatenating a full octet, concatenating a single bit would also be sufficient.)
The important distinction is that in the second case, the DH key is used for each part of the symmetric key. This assures that entropy of the DH key is not lost by iteration of the hash function over the same bits. From an efficiency point of view, if the symmetric key must have a great deal of entropy, it is probably best to use a cryptographic hash function with a large output block (192 bits or more), rather than iterating a smaller one. Newer hash algorithms with longer output (such as SHA-256, SHA-384, and SHA-512) can be used with the same level of security as the stretching algorithm described above. ECS].
+-------------+-----------+--------------+--------------+ | System | | | | | requirement | Symmetric | RSA or DH | DSA subgroup | | for attack | key size | modulus size | size | | resistance | (bits) | (bits) | (bits) | | (bits) | | | | +-------------+-----------+--------------+--------------+ | 70 | 70 | 947 | 129 | | 80 | 80 | 1228 | 148 | | 90 | 90 | 1553 | 167 | | 100 | 100 | 1926 | 186 | | 150 | 150 | 4575 | 284 | | 200 | 200 | 8719 | 383 | | 250 | 250 | 14596 | 482 | +-------------+-----------+--------------+--------------+ [DL] Dodson, B. and A. K. Lenstra, NFS with four large primes: an explosive experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, (1995) 372-385. [ECS] Eastlake, D., Crocker, S. and J. Schiller, "Randomness Recommendations for Security", RFC 1750, December 1994.
[GIL98] Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design , Electronic Frontier Foundation, John Gilmore (Ed.), 272 pages, May 1998, O'Reilly & Associates; ISBN: 1565925203 [GOR93] Gordon, D., "Discrete logarithms in GF(p) using the number field sieve", SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. [LEN93] Lenstra, A. K. and H. W. Lenstra, Jr. (eds), The development of the number field sieve, Lecture Notes in Math, 1554, Springer Verlag, Berlin, 1993. [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467. [ODL95] RSA Labs Cryptobytes, Volume 1, No. 2 - Summer 1995; The Future of Integer Factorization, A. M. Odlyzko [ODL99] A. M. Odlyzko, Discrete logarithms: The past and the future, Designs, Codes, and Cryptography (1999). [POL78] J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, 32 (1978), 918-924. [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998. [SCH95] R. Schroeppel, et al., Fast Key Exchange With Elliptic Curve Systems, In Don Coppersmith, editor, Advances in Cryptology -- CRYPTO 31 August 1995. Springer-Verlag [SHAMIR03] Shamir, Adi and Eran Tromer, "Factoring Large Numbers with the TWIRL Device", Advances in Cryptology - CRYPTO 2003, Springer, Lecture Notes in Computer Science 2729. [SIL00] R. D. Silverman, RSA Laboratories Bulletin, Number 13 - April 2000, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths [SILIEEE99] R. D. Silverman, "The Mythical MIPS Year", IEEE Computer, August 1999.
BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at email@example.com. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.