From: Matt Blaze <mab@research.att.com>
Date: Tue, 6 Feb 1996 19:19:28 +0800
To: cypherpunks@toad.com
Subject: Report available: "Minimal Key Lengths for Symmetric Ciphers"
Message-ID: <199602060707.CAA01434@nsa.tempo.att.com>
MIME-Version: 1.0
Content-Type: text/plain


At the request of the Business Software Alliance (BSA), an ad hoc
panel of seven cryptologists and computer scientists met last November
to address the question of the minimum key length required to provide
adequate security against exhaustive search in commercial applications
of symmetric cryptosystems.  We have just completed our report.

We adopted a simple, and somewhat conservative, methodology in an
effort to gain a realistic understanding of what size keys might
actually be vulnerable in practice.  It is common in analysis of key
length to give all benefit of the doubt to the capabilities of the
potential attacker and to make very generous assumptions about the
technology and resources that might be available to mount an attack.
In our analysis, however, we assumed that the attacker would employ
only conventional, commercially-mature technologies and would be
limited by budget and time constraints.  We used several different
technologies to design attack strategies that accommodate the budgets
of various hypothetical attackers, from individual ``hackers'' to
well-funded enterprises.  Our conclusions, therefore, represent an
approximation of an ``upper bound'' on the strength of various size
keys; I believe more efficient attacks than those we considered might
also be possible and should be taken into account by the prudent
cryptosystem designer.

The abstract of the report follows below.

A PostScript copy of the full text of the report is available in
     ftp://ftp.research.att.com/dist/mab/keylength.ps
An ASCII version is available in
     ftp://ftp.research.att.com/dist/mab/keylength.txt

(The report will also likely appear on the BSA's web site shortly).

-matt (speaking only for himself)

=======================================================================
	      Minimal Key Lengths for Symmetric Ciphers
	       to Provide Adequate Commercial Security

		    A Report by an Ad Hoc Group of
		Cryptographers and Computer Scientists

			      Matt Blaze (1)
			   Whitfield Diffie (2)
			   Ronald L. Rivest (3)
			    Bruce Schneier (4)
			  Tsutomu Shimomura (5)
			    Eric Thompson (6)
			    Michael Wiener (7)

			     January 1996


			       ABSTRACT

    Encryption plays an essential role in protecting the privacy of
electronic information against threats from a variety of potential
attackers.  In so doing, modern cryptography employs a combination of
_conventional_ or _symmetric_ cryptographic systems for
encrypting data and _public key_ or _asymmetric_ systems for
managing the _keys_ used by the symmetric systems.  Assessing the
strength required of the symmetric cryptographic systems is therefore
an essential step in employing cryptography for computer and
communication security.

    Technology readily available today (late 1995) makes 
_brute-force_ attacks against cryptographic systems considered adequate
for the past several years both fast and cheap.  General purpose
computers can be used, but a much more efficient approach is to employ
commercially available _Field Programmable Gate Array (FPGA)_
technology.  For attackers prepared to make a higher initial
investment, custom-made, special-purpose chips make such calculations
much faster and significantly lower the amortized cost per solution.

    As a result, cryptosystems with 40-bit keys offer virtually no
protection at this point against brute-force attacks.  Even the U.S.
Data Encryption Standard with 56-bit keys is increasingly inadequate.
As cryptosystems often succumb to `smarter' attacks than brute-force
key search, it is also important to remember that the keylengths
discussed here are the minimum needed for security against the
computational threats considered.

    Fortunately, the cost of very strong encryption is not
significantly greater than that of weak encryption.  Therefore, to
provide adequate protection against the most serious threats ---
well-funded commercial enterprises or government intelligence agencies
--- keys used to protect data today should be at least 75 bits long.
To protect information adequately for the next 20 years in the face of
expected advances in computing power, keys in newly-deployed systems
should be at least 90 bits long.

-----------------------------------------
1. AT&T Research, mab@research.att.com
2. Sun Microsystems, diffie@eng.sun.com
3. MIT Laboratory for Computer Science, rivest@lcs.mit.edu
4. Counterpane Systems, schneier@counterpane.com
5. San Diego Supercomputer Center, tsutomu@sdsc.edu
6. Access Data, Inc., eric@accessdata.com
7. Bell Northern Research, wiener@bnr.ca