[Cryptography] my comment to NIST about reducing capacity in SHA-3

[Zooko Wilcox-OHearn]

Date: Tue, 1 Oct 2013 15:45:27 -0400
From: zooko <zooko at zooko.com>
To: Multiple recipients of list <hash-forum at nist.gov>
Subject: Re: On 128-bit security

Folks:

Here are my personal opinions about these issues. I'm not expert at
cryptanalysis. Disclosure: I'm one of the authors of BLAKE2 (but not
one of the authors of BLAKE).

I personally do not believe that there is any secret agenda behind
this proposal, even though I believe that there was a secret agenda
behind Dual EC DRBG.

One reason that I believe that the motivation behind this proposal is
the stated motivation of improving performance, is that Joan Daemen
told me in person in January of 2013 that the Keccak team had
considered defining a reduced Keccak to compete with BLAKE2, but had
decided against it because they didn't want to disrupt the SHA-3
standardization process.

Apparently they changed their minds, and apparently their fears of
disruption turned out to be prescient!

I also do not think that a "security level" of 2^256 is necessarily
better than a "security level" of 2^128. *Maybe* it is better, but I'm
not aware of any examples where that sort of distinction has turned
out to matter in practice, and I can't really judge if it is likely to
matter in the future (except, of course, if you forget to take into
account multi-target issues…). I suspect nobody else can, either.

However, even though I *personally* would have confidence that a
Keccak with a 256-bit capacity would be safe and would be free of
maliciously induced weakness, I want a standard to be widely accepted
in addition to being safe.

This is the "Caesar's wife must be above suspicion" argument. It isn't
enough to make a secure standard, but also we need other people to
have confidence in it.

And, I don't know if we can persuade people that "no it isn't actually
backdoored/weakened". It may be the kind of thing where if that's the
conversation we're having then we've already lost.

Would it make sense to go ahead and standardize
SHA3-as-a-replacement-for-SHA2 by standardizing the form of Keccak
which is most widely accepted by cryptographers and which is closest
to what was studied during the contest, and then separately offer
SHAKE and reduced-for-speed-Keccak as additional new things?

A lot of uses of secure hash functions don't need to be particularly
efficient. In my slides about BLAKE2
(https://blake2.net/acns/slides.html) I argue that there are use-cases
where efficiency is critical, but it is equally true that there are
common and important use cases where a 576-bit capacity Keccak would
be fine, e.g. public key certificates.

-------

Joan Daemen, one of inventors of AES and one of the inventors of
Keccak (SHA-3), replied to my mailing list post as follows:

Date: Fri, 4 Oct 2013 05:08:07 -0400
From: Joan DAEMEN <joan.daemen at st.com>
To: Multiple recipients of list <hash-forum at nist.gov>
Subject: RE: On 128-bit security

Hello all,

Zooko wrote:

> I personally do not believe that there is any secret
> agenda behind this proposal, even though I believe that
> there was a secret agenda behind Dual EC DRBG.
>
> One reason that I believe that the motivation behind
> this proposal is the stated motivation of improving
> performance, is that Joan Daemen told me in person in
> January of 2013 that the Keccak team had considered
> defining a reduced Keccak to compete with BLAKE2, but
> had decided against it because they didn't want to
> disrupt the SHA-3 standardization process.
>
> Apparently they changed their minds, and apparently
> their fears of disruption turned out to be prescient!

Yes, Zooko and I met at the end-of-Ecrypt II event on Tenerife early
2013 (24° C in January!).
I don't remember our conversation in detail, but I I'm sure Zooko is
citing me correctly because that is what we were thinking about at the
time.

Actually, what we had in mind was to propose something like "Keccak2"
to compete with BLAKE2 by drastically cutting the number of rounds,
e.g., down to 12 rounds for Keccak-f[1600], but otherwise keeping the
algorithm as it is. That might have sent the wrong message indeed, but
we just didn't do it.

In contrast, the capacity is an integral parameter of the Keccak
family that we even proposed as user-tunable in our SHA-3 submission.
Matching the capacity to the security strength levels of [NIST SP
800-57] is simply exploiting that flexibility.

Kind regards,

Joan, also on behalf of my Keccak companions

-------

Regards,

Zooko Wilcox-O'Hearn

Founder, CEO, and Customer Support Rep
https://LeastAuthority.com
Freedom matters.