NIST hash function design competition

Hal Finney hal at finney.org
Tue Jul 11 14:53:52 EDT 2006


James Donald writes:
> My understanding is that no actual vulnerabilities have
> been found in Rijndael.  What has been found are reasons
> to suspect that vulnerabilities will be found.

Yes, I think that's correct on the theoretical side.  I was also thinking
of some of the implementation issues which have shown up, particularly
timing and cache attacks.  AES is proving to be difficult to immunize
against these problems.  A good discussion by Bernstein is presented
in http://cr.yp.to/antiforgery/cachetiming-20050414.pdf, where he asks,
regarding this AES issue, "How did this happen?":

: Was the National Institute of Standards and Technology unaware of
: timing attacks during the development of AES? No. In its â"Report on the
: development of the Advanced Encryption Standard," NIST spent several pages
: discussing side-channel attacks, specifically timing attacks and power
: attacks. It explicitly considered the difficulty of defending various
: operations against these attacks.  For example, NIST stated in [19,
: Section 5.1.5] that MARS was â"difficult to defend" against these attacks.
:
: Did NIST decide, after evaluating timing attacks, that those attacks
: were unimportant? No. Exactly the opposite occurred, as discussed below.
:
: So what went wrong? Answer: NIST failed to recognize that table lookups
: do not take constant time. â"Table lookup: not vulnerable to timing
: attacks," NIST stated in [19, Section 3.6.2]. NIST's statement was,
: and is, incorrect.
:
: NIST went on to consider the slowness of AES implementations designed
: to protect against side-channel attacks. For example, NIST stated
: that providing â"some defense" for MARS meant â"severe performance
: degradation." NIST stated in [19, Section 5.3.5] that Rijndael gained a
: "major speed advantage over its competitors when such protections are
: considered." This statement was based directly on the incorrect notion
: that table lookups take constant time. NIST made the same comment in
: its "summary assessments of the finalists," and again in its concluding
: paragraph explaining the selection of Rijndael as AES.  See [19, Section
: 6.5] and [19, Section 7].

This is an example of a case where there doesn't seem to have been
enough time during the AES process for people to notice this oversight.
It probably didn't help that analysts had to spread their effort over
five main candidates.

Maybe it would be a good idea for NIST to add an extra phase where they
announce their proposed finalist, and ask everyone to focus all their
attention on potential weaknesses in this one function.  Since this is
exactly what will happen anyway immediately after the selection is made,
it might make sense to build a buffer period into the process to let
people take their final shots.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list