Performance tuning for the XO

[C. Scott Ananian]

On 9/22/07, Albert Cahalan <acahalan at gmail.com> wrote:
> You don't seem terribly committed to any particular hash.
> How about picking one that the Geode is especially good at?
> You have AES acceleration hardware, and there are several
> ways to turn a block cipher like AES into a hash.

This is actually surprisingly hard.  There are cryptoanalytic attacks
which establish broad vulnerabilities in all block-cipher-as-hash
constructions which don't rekey frequently.  The accepted
constructions rekey every 16 bytes.  And the result is a 128-bit hash
function, which is not very strong.

See http://en.wikipedia.org/wiki/One-way_compression_function :
| Using a block cipher to build the one-way compression function for a
hash function is
| usually much slower than using a specially designed one-way
compression function in
| the hash function. This is because all known secure constructions do
the key scheduling
| for each block of the message. It has been shown that without
repeated key scheduling it
| is impossible to construct a secure block cipher based hash
function[1]. In practice
| reasonable speeds are achieved provided the key scheduling of the
selected block cipher
| is not a too heavy operation.
|
| [1] John Black, Martin Cochran, and Thomas Shrimpton. On the Impossibility of
| Highly-Efficient Blockcipher-Based Hash Functions. Advances in Cryptology --
| EUROCRYPT '05, Aarhus, Denmark, 2005

Note that this attack also applies to trying to use a MAC as a hash function.

AES was selected to support fast rekeying (
http://csrc.nist.gov/CryptoToolkit/aes/round2/r2report.pdf ).
I had a discussion with the AMD folk about the key scheduling speed of
the Geode's implementation, however, and they were not optimistic that
one could rekey every block (as required by any secure AES-as-hash
construction) and obtain good performance.  It's been on my to-do list
for a while to test that assumption, but more pressing tasks have
intervened.

If you want to play around with timing this yourself, the AES features
are described in section 6.11 (page 510) of the Geode LX reference
manual linked from http://wiki.laptop.org/go/Geode_instruction_set.

> (too late wish: hashing in the NAND controller chip)

I'd settle for storing a hash in the filesystem metadata, so that we
don't have to rehash files which haven't changed since they were last
hashed.  For upgrades, this is a very common case.
 --scott

-- 
                         ( http://cscott.net/ )