Key Management Considerations for the TCP MD5 Signature Option
RFC 3562

Network Working Group                                           M. Leech
Request for Comments: 3562                               Nortel Networks
Category:Informational                                         July 2003

                   Key Management Considerations for
                     the TCP MD5 Signature Option

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

Abstract

   The TCP MD5 Signature Option (RFC 2385), used predominantly by BGP,
   has seen significant deployment in critical areas of Internet
   infrastructure.  The security of this option relies heavily on the
   quality of the keying material used to compute the MD5 signature.
   This document addresses the security requirements of that keying
   material.

1. Introduction

   The security of various cryptographic functions lies both in the
   strength of the functions themselves against various forms of attack,
   and also, perhaps more importantly, in the keying material that is
   used with them.  While theoretical attacks against the simple MAC
   construction used in RFC 2385 are possible [MDXMAC], the number of
   text-MAC pairs required to mount a forgery make it vastly more
   probable that key-guessing is the main threat against RFC 2385.

   We show a quantitative approach to determining the security
   requirements of keys used with [RFC2385], which tends to suggest the
   following:

      o  Key lengths SHOULD be between 12 and 24 bytes, with larger keys
         having effectively zero additional computational costs when
         compared to shorter keys.

Leech                        Informational                      [Page 1]
RFC 3562    Considerations for the TCP MD5 Signature Option    July 2003

      o  Key sharing SHOULD be limited so that keys aren't shared among
         multiple BGP peering arrangements.

      o  Keys SHOULD be changed at least every 90 days.

1.1. Requirements Keywords

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT",
   and "MAY" that appear in this document are to be interpreted as
   described in [RFC2119].

2. Performance assumptions

   The most recent performance study of MD5 that this author was able to
   find was undertaken by J. Touch at ISI.  The results of this study
   were documented in [RFC1810].  The assumption is that Moores Law
   applies to the data in the study, which at the time showed a
   best-possible *software* performance for MD5 of 87Mbits/second.
   Projecting this number forward to the ca 2002 timeframe of this
   document, would suggest a number near 2.1Gbits/second.

   For purposes of simplification, we will assume that our key-guessing
   attacker will attack short packets only.  A likely minimal packet is
   an ACK, with no data.  This leads to having to compute the MD5 over
   about 40 bytes of data, along with some reasonable maximum number of
   key bytes.  MD5 effectively pads its input to 512-bit boundaries (64
   bytes) (it's actually more complicated than that, but this
   simplifying assumption will suffice for this analysis).  That means
   that a minimum MD5 "block" is 64 bytes, so for a ca 2002-scaled
   software performance of 2.1Gbits/second, we get a single-CPU software
   MD5 performance near 4.1e6 single-block MD5 operations per second.

   These numbers are, of course, assuming that any key-guessing attacker
   is resource-constrained to a single CPU.  In reality, distributed
   cryptographic key-guessing attacks have been remarkably successful in
   the recent past.

   It may be instructive to look at recent Internet worm infections, to
   determine what the probable maximum number of hosts that could be
   surreptitiously marshalled for a key-guessing attack against MD5.
   CAIDA [CAIDA2001] has reported that the Code Red worm infected over
   350,000 Internet hosts in the first 14 hours of operation.  It seems
   reasonable to assume that a worm whose "payload" is a mechanism for
   quietly performing a key-guessing attack (perhaps using idle CPU
   cycles of the infected host) could be at least as effective as Code
   Red was.  If one assumes that such a worm were engineered to be
   maximally stealthy, then steady-state infection could conceivably
   reach 1 million hosts or more.  That changes our single-CPU

Leech                        Informational                      [Page 2]
RFC 3562    Considerations for the TCP MD5 Signature Option    July 2003

   performance from 4.1e6 operations per second, to somewhere between