Re: NIST hash function design competition

2006-07-21 Thread Travis H.

On 7/20/06, Florian Weimer [EMAIL PROTECTED] wrote:

Is this about Colin Percival's work?


The paper was by Dan Berstein; Percival's comments are specific to
hyperthreading, but I think djb's research showed that it's applicable
to non-HT architectures as well.
--
Follow where reason leads -- Zeno || Unix guru for rent or hire
http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


RE: NIST hash function design competition

2006-07-21 Thread Whyte, William
Useful references are
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf -- the Bernstein paper
www.wisdom.weizmann.ac.il/~tromer/papers/cache.pdf - related work by
  Eran Tromer.

William

 -Original Message-
 From: [EMAIL PROTECTED] 
 [mailto:[EMAIL PROTECTED] On Behalf Of Travis H.
 Sent: Friday, July 21, 2006 9:09 AM
 To: Florian Weimer
 Cc: Hal Finney; [EMAIL PROTECTED]; cryptography@metzdowd.com
 Subject: Re: NIST hash function design competition
 
 On 7/20/06, Florian Weimer [EMAIL PROTECTED] wrote:
  Is this about Colin Percival's work?
 
 The paper was by Dan Berstein; Percival's comments are specific to
 hyperthreading, but I think djb's research showed that it's applicable
 to non-HT architectures as well.
 -- 
 Follow where reason leads -- Zeno || Unix guru for rent or hire
 http://www.lightconsulting.com/~travis/ --
 GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484
 
 -
 The Cryptography Mailing List
 Unsubscribe by sending unsubscribe cryptography to 
 [EMAIL PROTECTED]
 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: NIST hash function design competition

2006-07-20 Thread Florian Weimer
* Travis H.:

 On 7/11/06, Hal Finney [EMAIL PROTECTED] wrote:
 : 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.

 That's interesting, since it is in line with conventional reasoning
 about algorithms.  I've skimmed his paper, and I've taken a class on
 computer architecture and I haven't the foggiest idea where the
 variable timing comes from.  Does anyone know if any of the following
 account for the phenomenon?

 1) cache fills as we ascend through memory
 2) additions (base+index) taking non-constant time (could be fixed
 with pointers if we're going sequentially)
 3) virtual memory considerations (e.g. fetching new a page for a higher 
 address)
 4) TLB misses

Is this about Colin Percival's work?  IIRC, it's mainly about shared
associative caches which leak information about what addresses are
being cached across trust boundaries.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: NIST hash function design competition

2006-07-13 Thread Travis H.

On 7/11/06, Hal Finney [EMAIL PROTECTED] wrote:

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


That's interesting, since it is in line with conventional reasoning
about algorithms.  I've skimmed his paper, and I've taken a class on
computer architecture and I haven't the foggiest idea where the
variable timing comes from.  Does anyone know if any of the following
account for the phenomenon?

1) cache fills as we ascend through memory
2) additions (base+index) taking non-constant time (could be fixed
with pointers if we're going sequentially)
3) virtual memory considerations (e.g. fetching new a page for a higher address)
4) TLB misses

Some more detailed discussion of CPU trends and how they affect hash
performance is also welcome.  How exactly does data pipelining affect
hash run times more than a cipher?
--
Resolve is what distinguishes a person who has failed from a failure.
Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: NIST hash function design competition

2006-07-11 Thread James A. Donald

Hal Finney wrote:
 I had not heard that there had been an official
 decision to hold a new competition for hash functions
 similar to AES.  That is very exciting! The AES
 process was one of the most interesting events to have
 occured in the last few years in our field.

 Seemed like one of the lessons of that effort was
 that, even though it was successful in terms of
 attracting the interest and hard work of some of the
 top researchers in the field, in the end we have
 learned considerably more about Rijndael's
 vulnerabilities only after the process was over.

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.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: NIST hash function design competition

2006-07-11 Thread Hal Finney
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 [EMAIL PROTECTED]


NIST hash function design competition

2006-07-10 Thread Hal Finney
I was registering today for the Crypto conference and discovered that
immediately afterwards, and at the same site in Santa Barbara, CA, NIST
is holding a two-day workshop on hash function design.  The information
is here:

http://www.csrc.nist.gov/pki/HashWorkshop/index.html

In response to the SHA-1 vulnerability that was announced in Feb. 2005,
NIST held a Cryptographic Hash Workshop on Oct. 31-Nov. 1, 2005 to solicit
public input on its cryptographic hash function policy and standards. NIST
continues to recommend a transition from SHA-1 to the larger approved
hash functions (SHA-224, SHA-256, SHA-384, and SHA-512). In response
to the workshop, NIST has also decided that it would be prudent in
the long-term to develop an additional hash function through a public
competition, similar to the development process for the block cipher in
the Advanced Encryption Standard (AES).

I had not heard that there had been an official decision to hold a new
competition for hash functions similar to AES.  That is very exciting!
The AES process was one of the most interesting events to have occured
in the last few years in our field.

Seemed like one of the lessons of that effort was that, even though it was
successful in terms of attracting the interest and hard work of some of
the top researchers in the field, in the end we have learned considerably
more about Rijndael's vulnerabilities only after the process was over.
Perhaps the intrinsic difficulty of cryptography makes this kind of outcome
inevitable.  But hopefully the hashing competition will learn from the AES
experience and make sure that it takes as much time as it needs to take.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]