NIST hash function design competition

Travis H. solinym at gmail.com
Thu Jul 13 04:06:36 EDT 2006


On 7/11/06, "Hal Finney" <hal at finney.org> 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 majordomo at metzdowd.com



More information about the cryptography mailing list