secure hash modes for rijndael

[Jeroen C. van Gelderen]

Pete Chown wrote:
[...]
> On the subject of these hash functions...  I looked at some benchmark
> figures and SHA-256 is not substantially faster than Rijndael-256 with
> Davies-Meyer.  I wonder why there was so much energy put into the AES
> process, and then SHA-256 was given to us by the NSA with no public
> review, almost as an afterthought.

Could you give a URL for the benchmarks you looked at?

> I'm not saying that SHA-256 is deliberately broken.  If that was what
> the NSA wanted they would go for a broken AES not a broken hash.  In
> fact I'm just wondering what is going on because SHA-256 seems like a
> bit of a waste of time.
> 
> Do the NSA know something about Rijndael-256 that we don't?  Also, do
> they know something about SHA-1 that we don't?  This might explain why
> the new revision is so much slower...

According to [1], a C implementation of SHA-256 is not much 
slower than SHA-1 on either Alpha or Itanium:

BeeCrypt 2.0.0, egcs-2.91.66, RedHat Linux 6.2, Alpha EV6.7 667, 2048 RAM
SHA-1   : 24.80  MB/sec
SHA-256 : 19.27  MB/sec

BeeCrypt 2.0.0, gcc-2.9-ia64, Linux64, Itanium 666, 2048 RAM
SHA-1   : 9.60   MB/sec
SHA-256 : 7.12   MB/sec


On the ia32 architecture however the difference is quite immense [1]:

BeeCrypt 2.0.0, gcc-2.95.3, Mandrake Linux 7.[0|1], PIII 800, 4096 RAM
SHA-1   : 39.00  MB/sec
SHA-256 : 18.60  MB/sec


This suggests that the difference is caused by some kind of
platform deficiency. My guess is that a lack of registers is
the root cause of the problem; Looking at the SHA-256 algorithm
internals we see that it uses 8 32-bit state variables. The 
ia32 platform has 7 32-bit registers available in the best case
and 5 or 6 on average. This means an awful lot of register 
spills and hence slow memory accesses in the performance 
critical inner loop of the SHA-256 algorithm. 

Using a better compiler (one that generates more efficient 
spills), unrolling the loops and implementing SHA-256 in ia32 
assembly should increase the speed of SHA-256 on ia32 quite a 
bit.

Cheers,
Jeroen

[1] http://www.virtualunlimited.com/products/beecrypt/benchmarks.html

-- 
Jeroen C. van Gelderen - jeroen at vangelderen.org

"A government that robs Peter to pay Paul can always depend
  upon the support of Paul."  --  George Bernard Shaw



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