[ccache] Questions about two hot functions in ccache

[Justin Lebar]

Skimming the VHASH paper, it looks like it runs at about 1 cycle per
byte on a 64-bit Core 2 Merom machine when generating a 128-bit
digest.  (They don't have timings for 32-bit x86.)  It looks like they
just run the hash algorithm twice (with different keys) to generate a
128-bit digest.

I couldn't find great numbers on MD4, but [1] says 3.8cpb on really
old hardware.  Who knows what that would be today.

-Justin

[1] http://books.google.com/books?id=Xq4M8YTSeloC&pg=PA75&lpg=PA75&dq=md4+cpb&source=bl&ots=rtrQSLDtoG&sig=bh0mr2SN9_p0NCEF6_ZmxoadTTw&hl=en&ei=C52-TLXZPIuyngfy8f3JBw&sa=X&oi=book_result&ct=result&resnum=1&sqi=2&ved=0CBIQ6AEwAA#v=onepage&q=md4%20cpb&f=false

On Wed, Oct 20, 2010 at 12:34 AM, Martin Pool <mbp at canonical.com> wrote:
> On 20 October 2010 17:44, Justin Lebar <justin.lebar at gmail.com> wrote:
>> My cryptographically-inclined friend suggested we use a universal hash
>> function or something a bit stronger, such as VHASH.
>>
>> These functions take a "key", which we could choose at random and fix
>> in the code.
>>
>> VHASH outputs 64-bit digests with collision probability 2^61, so in
>> expectation you'd need to hash 2^30 files before you saw a collision.
>> If that wasn't good enough, we could compute two VHASH digests with
>> different keys and concatenate them.
>
> Is VHASH expected to be faster than MD4?  I don't think adding more
> strength will help with anything.  The odds of an accidental MD4
> collision are low, and I don't know of any attack by which being able
> to predict or produce ccache collisions accomplishes anything for the
> attacker.  (If they can write to the cache you have bigger problems.)
>
> --
> Martin
>