[Cryptography] please dont weaken pre-image resistance of SHA3 (Re: NIST about to weaken SHA3?)

[Adam Back]

On Tue, Oct 01, 2013 at 12:47:56PM -0400, John Kelsey wrote:
> The actual technical question is whether an across the board 128 bit
> security level is sufficient for a hash function with a 256 bit output. 
> This weakens the proposed SHA3-256 relative to SHA256 in preimage
> resistance, where SHA256 is expected to provide 256 bits of preimage
> resistance.  If you think that 256 bit hash functions (which are normally
> used to achieve a 128 bit security level) should guarantee 256 bits of
> preimage resistance, then you should oppose the plan to reduce the
> capacity to 256 bits.  

I think hash functions clearly should try to offer full (256-bit) preimage
security, not dumb it down to match 128-bit birthday collision resistance.

All other common hash functions have tried to do full preimage security so
it will lead to design confusion, to vary an otherwise standard assumption. 
It will probably have bad-interactions with many existing KDF, MAC,
merkle-tree designs and combined cipher+integrity modes, hashcash (partial
preimage as used in bitcoin as a proof of work) that use are designed in a
generic way to a hash as a building block that assume the hash has full
length pre-image protection.  Maybe some of those generic designs survive
because they compose multiple iterations, eg HMAC, but why create the work
and risk to go analyse them all, remove from implementations, or mark as
safe for all hashes except SHA3 as an exception.

If MD5 had 64-bit preimage, we'd be looking at preimages right now being
expensive but computable.  Bitcoin is pushing 60bit hashcash-sha256 preimage
every 10mins (1.7petaHash/sec network hashrate).

Now obviously 128-bits is another scale, but MD5 is old, broken, and there
maybe partial weakenings along the way.  eg say design aim of 128 slips
towards 80 (in another couple of decades of computing progress).  Why design
in a problem for the future when we KNOW and just spent a huge thread on
this list discussing that its very hard to remove upgrade algorithms from
deployment.  Even MD5 is still in the field.

Is there a clear work-around proposed for when you do need 256?  (Some
composition mode or parameter tweak part of the spec?) And generally where
does one go to add ones vote to the protest for not weakening the
2nd-preimage propoerty?

Adam