secure hash modes for rijndael

[Bram Cohen]

sha-256 is ridiculously slow, so I've done some thinking about hash modes
for rijndael.

To begin with, there's the issue of padding - this can be done by
appending a 1 and then padding with zeros to the next multiple of a block
size. If the data to be hashed is already a multiple of a block size and
doesn't end in a 1 to begin with, no padding is necessary. This gets rid
of a lot of unnecessary work for hashing small files.

Making a hash requires two fixed keys, the logical values for them are all
0 and all 1 bits.

First, compute CBC MACs using the two fixed keys (a CBC MAC is where
encrypt the first block, xor with the second, encrypt again, xor with the
third, etc.) Call the two MACs A and B. Now encrypt A using B and B with
it's last byte xored with FF using A (the xor is in case the data is only
a single block length, making A and B both be the original
file). Concatenate those two values together and that's the hash.

I believe this algorithm is quite secure. It produces an output twice the
length of the block size, which should be as resistant to birthday attacks
as the block cipher is to regular attacks. It has a hash rate of 1/2,
which makes sense since it's output is twice as large. Even at that rate,
it's still much faster than sha.

It would be nice if there was an algorithm which used rijndael with 256
bit blocks to produce a hash of 256 bits and had a hash rate of 1, but I
haven't been able to come up with one.

One neat trick - if you have a short file (about 20 bytes) and want a 160
bit hash of it, you can encrypt the file using itself as the key.

I think releasing a sha256 standard at all was a bad idea - sha1 will last
a while yet, and a standard hashing mode for rijndael will work much
better. This is a very serious issue with regards to blob identification,
since you can't just switch your metadata to refer to the same files but
using a different hash function. I strongly urge everyone who indexes
blobs to continue using sha1 until a decent hashing algorithm has been
picked as the next standard.

-Bram Cohen

Soko! puzzle game - http://ch.havenco.com:4201/




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