Determining Strengths For Public Keys Used For Exchanging Symmetric Keys
RFC 3766
Document  Type 
RFC  Best Current Practice
(April 2004; No errata)
Also known as BCP 86
Was draftormanpublickeylengths (individual in gen area)



Last updated  20130302  
Stream  IETF  
Formats  plain text pdf html  
Stream  WG state  (None)  
Consensus  Unknown  
Document shepherd  No shepherd assigned  
IESG  IESG state  RFC 3766 (Best Current Practice)  
Telechat date  
Responsible AD  Steven Bellovin  
Send notices to  ho@alum.mit.edu, paul.hoffman@vpnc.org 
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. Abstract Implementors 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 largescale 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. Orman & Hoffman Best Current Practice [Page 1] RFC 3766 Determining Strengths for Public Keys April 2004 Table of Contents 1. Model of Protecting Symmetric Keys with Public Keys. . . . . . 2 1.1. The key exchange algorithms . . . . . . . . . . . . . . . 4 2. Determining the Effort to Factor . . . . . . . . . . . . . . . 5 2.1. Choosing parameters for the equation. . . . . . . . . . . 6 2.2. Choosing k from empirical reports . . . . . . . . . . . . 7 2.3. Pollard's rho method. . . . . . . . . . . . . . . . . . . 7 2.4. Limits of large memory and many machines. . . . . . . . . 8 2.5. Special purpose machines. . . . . . . . . . . . . . . . . 9 3. Compute Time for the Algorithms. . . . . . . . . . . . . . . . 10 3.1. DiffieHellman Key Exchange . . . . . . . . . . . . . . . 10 3.1.1. DiffieHellman with elliptic curve groups. . . . . 11 3.2. RSA encryption and decryption . . . . . . . . . . . . . . 11 3.3. Realworld examples . . . . . . . . . . . . . . . . . . . 12 4. Equivalences of Key Sizes. . . . . . . . . . . . . . . . . . . 13 4.1. Key equivalence against special purpose brute force hardware. . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2. Key equivalence against conventional CPU brute force attack. . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3. A One Year Attack: 80 bits of strength. . . . . . . . . . 16 4.4. Key equivalence for other ciphers . . . . . . . . . . . . 16 4.5. Hash functions for deriving symmetric keys from public key algorithms. . . . . . . . . . . . . . . . . . . . . . 17 4.6. Importance of randomness. . . . . . . . . . . . . . . . . 19 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1. TWIRL Correction. . . . . . . . . . . . . . . . . . . . . 20 6. Security Considerations. . . . . . . . . . . . . . . . . . . . 20 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7.1. Informational References. . . . . . . . . . . . . . . . . 20 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 22 9. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 23 1. Model of Protecting Symmetric Keys with Public Keys Many books on cryptography and security explain the need to exchange symmetric keys in public as well as the many algorithms that are used for this purpose. However, few of these discussions explain how the strengths of the public keys and the symmetric keys are related. To understand this, picture a house with a strong lock on the frontShow full document text