[15] in cryptography@c2.net mail archive

home help back first fref pref prev next nref lref last post

Attn: FIPS for AES Comments

daemon@ATHENA.MIT.EDU (Bill Stewart)
Fri Jan 3 01:04:55 1997

Date: Thu, 02 Jan 1997 17:31:20 -0800
To: AES@nist.gov
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: cryptography@c2.net

To: Director, Computer Systems Laboratory, 
        Attn: FIPS for AES Comments, 
        Technology Building, Room A231, 
        National Institute of Standards and Technology, 
        Gaithersburg, MD 20899.

NIST[Docket No. 960924272-6272-01]  RIN 0693-ZA13 is a request for comments
on draft minimum acceptability requirements and draft criteria to evaluate 
candidate algorithms for a new Advanced Encryption Algorithm.

I am commenting on the criteria as an individual, and not as a 
representative of my employer.  I work in the telecommunications/
computer industry, including security analysis and some cryptography.

Overall, the drafts and process look good, and I'm quite pleased
to see a commitment to an open process from NIST, as opposed to another 
closed process such as the CCEP and Clipper projects.  

Unfortunately, there is also one very serious process problem, 
which may make the proposed selection approach unworkable and illegal
unless addressed carefully by NIST and the Administration.
The problem is the conflict between an open process, 
with submission requirements (B.1 and B.2) for complete algorithm 
specification, security analyses, and working source code,
vs. the International Trafficking in Arms Regulations and
other existing, announced, and proposed export policies which prohibit or 
require licensing or prior jurisdictional determination for "export" of
source code, technical data, and cryptographic components,
including open publishing on the Internet, discussion with foreigners,
export of machine-readable media, and possibly even of paper documentation.
While the NIST and NSA can reasonably operate in this environment,
industry, academia, and non-US cryptographic experts cannot 
adequately participate in open discussions without some assurance of
legal protection and the ability to exchange information with each other.

How does NIST propose to address this issue?  International participation
is a particularly important issue, given the expertise of people such as
Biham, Shamir, Lai, and other non-US academic cryptographers and 
the need for interoperation and efficiency for telecommunications and finance 
implementations.

An important part of an open process is positioning AEA/AES as a recognized
symmetric algorithm for non-military applications, since the military 
generally uses closed standards, while the commercial world generally 
prefers a negotiation among a family of encryption algorithms, including
- export-approved trivial and near-trivial algorithms,
        such as RC4/40 and RC4/128 with 88-bit exposed salts
        and the US and GSM cell-phone encryption algorithms,
        plus algorithms that may be approved in the future,
- fallback DES support
- slow but secure algorithms like Triple-DES
- fast newer algorithms such as RC4, RC5, and Blowfish 
- hardware implementations, including proprietary systems and
        accelerators for (Triple) DES
- fast-setup algorithms for some applications and
        slower-setup high-throughput algorithms for others.
- block vs stream cyphers depending on application

There are three of the design criteria that have problems, 
some technical and some organizational/political.

A.3  AES shall be designed so that the key length may be increased as needed.

The straightforward technical problem is with criterion A.3:        
It's a good goal, but it unfortunately excludes the most important
existing candidate symmetric cypher algorithm, Triple-DES.
Triple-DES may be slow and clumsy to implement in software,
but it's very well understood, allows reuse of existing designs,
and is secure enough for probably the next 50 years of computer speed growth.
It's possible to accommodate Triple-DES into the criterion by
treating it as part of a family of DES, 3-DES, 5-DES, 7-DES, etc., 
but it's inelegant and stretches the wording of the criterion.

A more complex problem with criterion A.3 (and thus A.6) is that the 
relationships between strength and key length are not simple:  
An algorithm that performs very securely for longer keys may be very weak
with shorter keys which permit optimized attack methods, 
and encryption speed may or may not differ significantly with key length.
        (For instance, with DES, the key schedule is relatively slow for 
        single keys, but recent work has shown that a brute-force keyspace 
        search in Grey-code order can reduce the key-schedule work for
        additional keys to a small fraction of the single-key time.
        Pre-computation attacks work quite well on algorithms like RC4/40,
        but fail on variants like RC4/128 with revealed 88-bit salts,
        even though both have the same size secret key and similar speed.)
This means that keylengths chosen for political reasons, e.g. 56 bit
limits for exportable algorithms, may affect different candidate
algorithms to very different extents.  In particular, an algorithm that's
as strong as possible for short key lengths may be slow with longer keys,
or may require a very long setup time (e.g. Blowfish), and an algorithm
that's a very good choice for realistic commercial-strength key lengths
maybe too weak at exportable lengths.

A.2  AES shall be a symmetric block cipher.

Block cyphers are probably more important than stream cyphers,
and this is probably a good choice.  However, the issues of streaming
and block chaining need to be addressed - some algorithms like DES
and Triple-DES can work well in either block chaining or codebook modes,
while others such as RC4 require more care for some environments.

The security of some applications is also quite sensitive to block sizes.
For instance, known plaintext attacks may be more effective with
shorter block sizes because of short standard file/data headers.

A.1  AES shall be publicly defined.

"Publicly defined" needs to be defined carefully, and publicly. 
DES suffered reputation problems for years because of the
"What does the NSA _really_ know about the S-Box Structure?" uncertainties,
which were increased when people discovered efficiencies due to
group structures in the S-boxes, and really only abated after the
discovery of differential cryptanalysis by Biham and Shamir and
the confirmation that the NSA had used those techniques to strengthen DES.

It's especially important to have open public discussion of the
tradeoffs and criteria for selecting between algorithms.  For instance,
the comparisons between Digital Signature Algorithm vs. RSA signatures 
depend on the relative importance of signature speed vs. verification speed,
and industry generally viewed both NIST's and PKP's positions on 
that issue to be motivated more by ownership concerns than technical ones.

                        Thanks!  
                                Bill Stewart
                                stewarts@ix.netcom.com
                                Mountain View, CA.

 
---------------
References:     [Federal Register: January 2, 1997 (Volume 62, Number 1)]
                [Notices]   [Page 93-94]
                Federal Register Online via GPO Access [wais.access.gpo.gov]

http://jya.com/aes010297.txt


home help back first fref pref prev next nref lref last post