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 draft-orman-public-key-lengths (individual in gen area)
Last updated 2013-03-02
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 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.

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. 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

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 front
Show full document text