search

davidben / merkle-tree-certs

Other
9 stars 4 forks source link

Is it worthwhile to reduce reliance on collision resistance from our hash? #45

Open bwesterb opened 1 year ago

bwesterb commented 1 year ago

There has always been a significant gap between (chosen prefix) collision and (second) preimage attacks on hashes. It would be neat if we do not have to assume (chosen prefix) collision resistance of our hash to prevent certain classes of attacks. I'd say it's a nice-to-have, but not a must.

Incomplete list of changes:

  1. For each batch, the CA generates a 16 byte randomizer R which is used as input to Hash{Assertion,Node,Empty}. We can either put the randomizer in the proof (in the bikeshed certificate) or pass it along in the signed window.
davidben commented 1 year ago

With a CA-provided randomizer, we'd still rely on second preimage resistance for transparency, right? (I.e. we couldn't halve the hash size.) Though I suppose we wouldn't rely on it for authenticity.

bwesterb commented 1 year ago

Yes, you're right: even with the CA-provided randomiser, we would still rely on collision resistance to prevent the CA from providing two world views. Indeed, if we'd truncate hashes to 16 bytes, then with 2^64 work, a CA could find two different batches with the same root hash.

I guess we couldn't get rid of that without significant modifications (see #48). Still I think it might be worthwhile to reduce reliance of collision resistance.