RE: NIST hash function design competition
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
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
* 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
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
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]
Re: NIST hash function design competition
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]
NIST hash function design competition
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]
