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

John Kelsey crypto.jmk at gmail.com
Wed Oct 16 09:23:09 EDT 2013


On Oct 15, 2013, at 5:59 PM, Adam Back <adam at cypherspace.org> wrote:
...
> On Tue, Oct 15, 2013 at 05:47:27PM -0400, John Kelsey wrote:.
> 
>> More broadly, anything you can do to a SHA3 version with much less than
>> 2^{c/2} work, you could also do to *any* hash function with the same
>> output size.
> 
> I think what you just said is an attack of work less than 2^128 is harmless
> on both a weakened SHA3 preimage and SHA2.  But that is not an argument for
> reducing the preimage strength to 2^128.  Actually I dont understand the
> argument for weakening it.  Is there a pointer to a rationale? - so far it
> makes no sense - unless its micro-optimization to the massive detriment of
> preimage security if you care about that.

There is a small but noticable performance improvement for having SHA3-256 have a capacity of 256 bits.  There is a big performance improvement for having SHA3-512 have a capacity of 512 bits.  In both cases, these performance improvements come at the cost of allowing attacks which are above the security level we normally claim for the hash functions.  

In the case of SHA3-512, it's hard to imagine any crypto application needing more than 256 bits of security, and almost nothing else in our crypto toolkit (NIST's or the bigger community's) tries to get higher security than that.  Personally, I think demanding a loss of performance to reach security levels higher than 256 bits is nuts.  It's trading real performance off against imaginary, cosmetic security.

In the case of SHA3-256, there's more of an argument to be made, because while you really ought not to be using a 256-bit hash function and expecting more than 128 bits of security, we do care about being able to reach security levels higher than 128 bits.  There are random number generators and key derivation functions which use a 256 bit hash to generate keys with 256 bits of security.  Now, the NIST functions that do this look fine with SHA3-256 in them, and I think yu could get proofs for their security.  (There is a proof of the PRF security of the Keccak PRF which probably applies, but I'm not sure it's as well nailed down as the indifferentiability bound.). As you said, somewhere there may be someone counting on that higher preimage resistance, though I don't know of any actual examples.  

> Adam

--John


More information about the cryptography mailing list