[Cryptography] SHA-3 FIPS-202: no SHAKE512 but SHAKE128; confusing SHAKE security

ianG iang at iang.org
Fri Aug 14 15:15:06 EDT 2015


On 9/08/2015 15:08 pm, Sebastian Gesemann wrote:
> On Wed, Aug 5, 2015 at 11:41 PM, Michal Bozon <michal.bozon at cesnet.cz> wrote:
>> Hi.
>> There is new fresh FIPS-202 standardizing SHA-3.
>>
>> In addition to SHA3-{224,256,384,512}, SHAKE-{256,512} were expected.
>> However, we got SHAKE-{128,256} instead.
>>
>> So in addition to four fixed hash functions with 224 up to 512 bit
>> security,
>
> That's not their security. Their security is 112 up to 256. We don't
> use 512 bits of output because we need a preimage resistance of 2^512.
> We use 512 bits of output because they are necessary for collision
> resistance of 2^256.
>
>> there are two "expandable-output" functions (XOF) with only
>> max. 128 vs max. 256 bit security.
>
> 128 and 256 are the "standard security levels" we know from AES already.
>
> Even in the quantum computer context, 256 is perfectly fine and 512
> rather meaningless.
>
>> So what is the point of their expansion?
>
> The SHAKEs can be used as a DRBG (deterministic random bit generator)
> or an MGF (mask generation function, something you use in RSA-OAEP and
> RSA-PSS, for example).
>
> You can also use them if you need a faster hash. Just pick the desired
> security level (s=128 or s=256), an appropriate digest length d and
> use SHAKE-s with d bits of output. If you care about collision
> resistance use d=2s, otherwise d=s should be fine. So, with the SHAKEs
> you are pretty flexible in that you can choose the security level s
> and output length d independently for a better security/speed
> trade-off. Given SHAKE-s with d bits of output you get a 1st and 2nd
> preimage resistance of 2^min(s, d) and a collision resistance of
> 2^min(s, d/2).

so picking the smaller convenient s=128, and d of 128 for ephemeral 
purposes, I get these strengths:

collision   = 64.
1,2preimage = 128.

Good enough for government work.  For longer term general stuff, s=128 
and d=256

collision   = 128
1,2preimage = 128.


> In the quantum computer context (using Grover's algorithm) this should
> drop down to preimage resistance of 2^min(2s/3, d/2) and a collision
> resistance of 2^min(2s/3, d/3) I believe.


Taking the s=128 and d=256 above I would then have:

collision   = 85
1,2preimage = 85.

Which is probably enough in the short term for most purposes to create a 
breathing room for upgrade.

So if we live in a world where Quantum is a threat we need to deal with, 
we'd like to jump to s=256 and up to say d=512:

collision   = 170
1,2preimage = 170.

Does all that make sense?



One of the things that has emerged in the last N years or so is that it 
is up to the protocol designer to present a good cipher suite that is 
balanced.  Letting a user choose different algorithms has proven to be a 
bad idea -- the user doesn't know more than us, and to a pretty good 
confidence level knows much less.  So to some extent we've lent on this 
idea that for a 128 bit strength we need a 256 bit hash, a 128 bit 
cipher, etc etc as is now popularised by the Suite B list.

But Sponge is challenging us to get a bit more precise about our 
calculations.  The good thing here is that the tools described above 
aren't hard to deal with.  The annoying thing might be that the idea of 
us being able to deliver an algorithmic smorgasbord is receding, but 
nobody I know has come up with a good reason for preserving that as a 
feature (as opposed to the more general argument that we need the 
flexibility to swap out entire suites).



So if people want to go full IoT, can we ask:  what does that mean?  Can 
we draw the line and say the OpenPGP offering here is CipherSuiteIoT 
which means x/y/z in numbers and params and no more no less?

PHB:
 > IOT looks set to create a demand
 > for an absolutely minimal cryptographic
 > suite. One signature algorithm, one
 > exchange algorithm, both on the same
 > curve, one authenticated encryption
 > mode, one digest/pseudorandom function.


Or are we offering full cipher flexibility to those IoT designers, and 
thus forcing them to implement all the multiples, because they won't 
know what other designers will choose, etc?

My thinking right now is that (assuming we're doing this) we should put 
in the draft a recommendation that precisely identifies a minimum 
most-popular obligatory to implement suite that covers as far down as we 
can get it.  And leave the rest up to the market?



iang


More information about the cryptography mailing list