Subject: Re: [Cfrg] Ed448 hash choice

From: Bryan Ford <[email-masked]>
Date: Mon, 2 Nov 2015 15:53:37 +0900

Echoing the comment I just made in the CFRG meeting:

I have a purely performance concern about using SHA3-512 for the prehash.  As I believe others have pointed out, SHA3-512 was specified by the Keccak designers based on an extremely conservatively pessimistic interpretation of NIST’s requirements, namely to provide “the maximum possible security that a hash with a 512-bit output can provide.”  This over-conservative interpretation led them to specify SHA3-512 basically so as to provide 256-bit collision resistance and *512-bit* preimage attack resistance.  Which in practice almost no one actually expects or needs of a hash function with a 512-bit output.

To my knowledge Ed448 doesn’t remotely need 512-bit preimage attack resistance, and the downside of this conservative configuration is that SHA3-512 operates the internal Keccak sponge at a much lower rate than SHAKE256.  In particular, if I recall correctly SHA256 processes 136 useful data bytes per Keccak sponge transformation (capacity is 512 bits so rate is 1600-512=1088 bits), whereas SHA3-512 processes only 72 useful data bytes per Keccak transformation (capacity is 1024 bits so rate is 1600-1024=1088 bits).  Thus, by using SHA3-512 for the prehash, we’re cutting the performance of the prehash in half for no security benefit that I can discern.

Why do we even care about the performance of SHA3-512?  If it was the internal hash that used it, I wouldn’t be worried at all, since the internal hash is only ever used to hash small fixed-length messages and hence its cost will definitely be dwarfed by the cost of the public-key operation.  But the prehash is precisely the hash that *can* get used to process large messages: e.g., a 1GB iso image or software distribution whose signature some future version of OpenPGP wants to authenticate using Ed448.  So I fear that using SHA3-512 for this for no apparent security benefit is at the very least going to draw “how on earth did they make that decision” type complaints down the road from people who care about performance, or worse, perhaps even lead some developers not to use Ed448 for this reason.

The obvious alternative that I would propose is simply to use SHAKE256 for both internal hash and prehash.

Of course even SHAKE256 isn’t currently as blazingly fast as say BLAKE2 when implemented in software, but Keccak seems very likely to be “in line” at some point to be the next crypto-primitive hardware vendors start embedding in instruction sets alongside (or instead of) AESNI, and if/when that happens, I expect that going with SHAKE256 for both hashes will turn out to have been a really good decision.  And even if that doesn’t happen, there’s nothing wrong with it not being the very fastest hash out there as long as we’re not artificially tying its legs together by using SHA3-512.

Thanks
Bryan

---

From: Yoav Nir <[email-masked]>
Date: Mon, 2 Nov 2015 16:28:29 +0900

Two comments about this:

1. Keccak^H^H^H^H^H^H SHA-3 may be in-line, but so far there has been little interest: none of the protocols in the security area (TLS, IKE/IPsec, SSH) has a specification to use it, and nobody has even bothered to define OIDs for RSA-with-SHA3 or ECDSA-with-SHA3. If it gets specified here, it is going to be a first for either IETF or IRTF.

2. Signing a gigabyte buffer is a strange use-case. In protocols like TLS and IKE and all the PKIX protocols, signatures go over a 1- 2-KB certificates, or similar sized transcripts or messages. Mail signing is somewhat larger, but still doesn’t usually exceed very few gigabytes. I’m not saying that big data use-cases don’t exist at all, but they are so rare that we should not bother to optimize for them.  They can always pre-hash themselves and use something fast like Blake2 as part of the protocol before calling the signature function.

Yoav

> On 2 Nov 2015, at 3:53 PM, Bryan Ford <[email-masked]> wrote:
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 2 Nov 2015 14:52:22 +0000

On 11/2/15, 2:28 , "Cfrg on behalf of Yoav Nir" <[email-masked] on
behalf of [email-masked]> wrote:

>Two comments about this:
>
>1. Keccak^H^H^H^H^H^H SHA-3 may be in-line, but so far there has been
>little interest: none of the protocols in the security area (TLS,
>IKE/IPsec, SSH) has a specification to use it, and nobody has even
>bothered to define OIDs for RSA-with-SHA3 or ECDSA-with-SHA3. If it gets
>specified here, it is going to be a first for either IETF or IRTF.

I suspect that everybody is waiting for NIST to provide the first
signature draft with SHA-3.

>2. Signing a gigabyte buffer is a strange use-case.

It is a corner case. But those do exist.

---

From: Gilles Van Assche <[email-masked]>
Date: Tue, 3 Nov 2015 16:39:42 +0100

On 11/02/2015 07:53 AM, Bryan Ford wrote:
> To my knowledge Ed448 doesn’t remotely need 512-bit preimage attack
> resistance, and the downside of this conservative configuration is
> that SHA3-512 operates the internal Keccak sponge at a much lower rate
> than SHAKE256. In particular, if I recall correctly SHA256 processes
> 136 useful data bytes per Keccak sponge transformation (capacity is
> 512 bits so rate is 1600-512=1088 bits), whereas SHA3-512 processes
> only 72 useful data bytes per Keccak transformation (capacity is 1024
> bits so rate is 1600-1024=1088 bits). Thus, by using SHA3-512 for the
> prehash, we’re cutting the performance of the prehash in half for no
> security benefit that I can discern.

I agree.

And to come back to a comment that Dan made some time ago:

On 10/19/2015 07:52 PM, Dan Brown wrote:
> In the message digesting, no inputs are secrets, yet resisting forgery
> depends on the security of H. For these types of no-secret security
> properties, I feel that the extra-large pipe of 1024 in SHA3-512 is a
> reasonable security cushion for the hash, i.e. compensation for the
> lack of a secret input.

The safety margin of Keccak is provided mainly by the number of rounds,
identical both for SHA3-512 and SHAKE128. Although it is true that
increasing the capacity has some impact on the safety margin too (by way
of decreasing the degrees of freedom of the attacker), its main effect
is on the generic security, which is clearly high enough for SHAKE256.

Martin Schläffer explained it in a nice way on the hash forum (see
attached mail).

Kind regards,
Gilles

---

From: Bryan Ford <[email-masked]>
Date: Wed, 4 Nov 2015 02:11:56 +0900

On Monday, November 2, 2015, Yoav Nir <[email-masked]> wrote:

> IKE/IPsec, SSH) has a specification to use it, and nobody has even bothered
> to define OIDs for RSA-with-SHA3 or ECDSA-with-SHA3. If it gets specified
> here, it is going to be a first for either IETF or IRTF.

You seem to be arguing here against using the Keccak/SHA3/SHAKE suite at
all, which is an issue completely orthogonal to my concern. I thought it
had basically been decided that there was a consensus to use the
Keccak-based suite, and I wasn't proposing to change that, only to change
which precise Keccak-based constructions to use (SHA3-512 vs SHAKE256).  I
don't see how existing adoption or lack thereof of Keccak/SHA3 has anything
to do with  the performance concern I raised.

Also, I believe a lot of the reason people have been holding back from
deploying Keccak/SHA3 is that it still hadn't been formally locked-in and
blessed by NIST until very recently. I don't see why (completely
understandable) reluctance to use a not-yet-officially-standardized
standard  before it's officially a standard should count against it after
it's actually become an official standard. :)

> 2. Signing a gigabyte buffer is a strange use-case. In protocols like TLS
> and IKE and all the PKIX protocols, signatures go over a 1- 2-KB
> certificates, or similar sized transcripts or messages. Mail signing is
> somewhat larger, but still doesn’t usually exceed very few gigabytes. I’m
> not saying that big data use-cases don’t exist at all, but they are so rare
> that we should not bother to optimize for them.  They can always pre-hash
> themselves and use something fast like Blake2 as part of the protocol
> before calling the signature function.

 It seems to me that OpenPGP might very well end up adopting this signing
scheme (I hope so), and OpenPGP signatures are used all over the place to
sign large software distributions for example.

Why make performance suck twice as much as it needs to, unless someone has
a solid argument that SHAKE256 is less secure than SHA3-512 in this
context?  I haven't heard anyone suggest such an argument. And it seems
hard to imagine such an argument would hold up if the signing scheme
uses SHAKE256 for the internal hash anyway - weakest-link and all that.

B

> Yoav
>
> > On 2 Nov 2015, at 3:53 PM, Bryan Ford <[email-masked]
> <javascript:;>> wrote:
> >
> > I have a purely performance concern about using SHA3-512 for the
> prehash.  As I believe others have pointed out, SHA3-512 was specified by
> the Keccak designers based on an extremely conservatively pessimistic
> interpretation of NIST’s requirements, namely to provide “the maximum
> possible security that a hash with a 512-bit output can provide.”  This
> over-conservative interpretation led them to specify SHA3-512 basically so
> as to provide 256-bit collision resistance and *512-bit* preimage attack
> resistance.  Which in practice almost no one actually expects or needs of a
> hash function with a 512-bit output.
> >
> resistance, and the downside of this conservative configuration is that
> SHA3-512 operates the internal Keccak sponge at a much lower rate than
> SHAKE256.  In particular, if I recall correctly SHA256 processes 136 useful
> data bytes per Keccak sponge transformation (capacity is 512 bits so rate
> is 1600-512=1088 bits), whereas SHA3-512 processes only 72 useful data
> bytes per Keccak transformation (capacity is 1024 bits so rate is
> 1600-1024=1088 bits).  Thus, by using SHA3-512 for the prehash, we’re
> cutting the performance of the prehash in half for no security benefit that
> I can discern.
> >
> > Why do we even care about the performance of SHA3-512?  If it was the
> internal hash that used it, I wouldn’t be worried at all, since the
> internal hash is only ever used to hash small fixed-length messages and
> hence its cost will definitely be dwarfed by the cost of the public-key
> operation.  But the prehash is precisely the hash that *can* get used to
> process large messages: e.g., a 1GB iso image or software distribution
> whose signature some future version of OpenPGP wants to authenticate using
> Ed448.  So I fear that using SHA3-512 for this for no apparent security
> benefit is at the very least going to draw “how on earth did they make that
> decision” type complaints down the road from people who care about
> performance, or worse, perhaps even lead some developers not to use Ed448
> for this reason.
> >
> > Of course even SHAKE256 isn’t currently as blazingly fast as say BLAKE2
> when implemented in software, but Keccak seems very likely to be “in line”
> at some point to be the next crypto-primitive hardware vendors start
> embedding in instruction sets alongside (or instead of) AESNI, and if/when
> that happens, I expect that going with SHAKE256 for both hashes will turn
> out to have been a really good decision.  And even if that doesn’t happen,
> there’s nothing wrong with it not being the very fastest hash out there as
> long as we’re not artificially tying its legs together by using SHA3-512.
> >
> > Thanks
> > Bryan
> >
> > [email-masked] <javascript:;>

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 3 Nov 2015 09:14:36 -0800

On Tue, Nov 3, 2015 at 9:11 AM, Bryan Ford <[email-masked]> wrote:

> I thought it had basically been decided that there was a consensus to use
> the Keccak-based suite
>

I count several people who do not prefer Keccak. I would suggest leaving
determinations of consensus to the chairs.

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Wed, 4 Nov 2015 03:05:16 +0900

> On 4 Nov 2015, at 2:11 AM, Bryan Ford <[email-masked]> wrote:
> 
> On Monday, November 2, 2015, Yoav Nir <[email-masked] <mailto:[email-masked]>> wrote:
> Two comments about this:
> 
> You seem to be arguing here against using the Keccak/SHA3/SHAKE suite at all, which is an issue completely orthogonal to my concern. I thought it had basically been decided that there was a consensus to use the Keccak-based suite, and I wasn't proposing to change that, only to change which precise Keccak-based constructions to use (SHA3-512 vs SHAKE256).  I don't see how existing adoption or lack thereof of Keccak/SHA3 has anything to do with  the performance concern I raised. 

I am not arguing against Keccak. I am only arguing against your assertion that it is going to be the next primitive included in general purpose hardware. Intel only included AES-NI after AES became the the one symmetric cipher used for everything. For certain applications significant part of CPU time was spent on AES, so Intel decided to optimize that. I don’t think we’re ever going to see a server / VPN gateway / OCSP responder that is constrained by CPU power to perform SHA-3. 10 years ago, when HMAC was the king of message authentication codes I would agree that accelerating a hash function was the second most important thing (after symmetric encryption), but not now.

> Also, I believe a lot of the reason people have been holding back from deploying Keccak/SHA3 is that it still hadn't been formally locked-in and blessed by NIST until very recently. I don't see why (completely understandable) reluctance to use a not-yet-officially-standardized standard  before it's officially a standard should count against it after it's actually become an official standard. :)
>  
>  It seems to me that OpenPGP might very well end up adopting this signing scheme (I hope so), and OpenPGP signatures are used all over the place to sign large software distributions for example.
> 
> Why make performance suck twice as much as it needs to, unless someone has a solid argument that SHAKE256 is less secure than SHA3-512 in this context?  I haven't heard anyone suggest such an argument. And it seems hard to imagine such an argument would hold up if the signing scheme uses SHAKE256 for the internal hash anyway - weakest-link and all that. 

No reason except to avoid using a primitive that is not used anywhere else. If SHAKE256 is going to be in all cryptographic libraries anyway, then I have no objection to using it.

Yoav

---

From: Bryan Ford <[email-masked]>
Date: Wed, 4 Nov 2015 04:58:33 +0900

> On Nov 4, 2015, at 3:05 AM, Yoav Nir <[email-masked]> wrote:
>> On 4 Nov 2015, at 2:11 AM, Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:
>> 
> I am not arguing against Keccak. I am only arguing against your assertion that it is going to be the next primitive included in general purpose hardware.

Fair enough, sorry for misinterpreting your argument.

> Intel only included AES-NI after AES became the the one symmetric cipher used for everything. For certain applications significant part of CPU time was spent on AES, so Intel decided to optimize that. I don’t think we’re ever going to see a server / VPN gateway / OCSP responder that is constrained by CPU power to perform SHA-3. 10 years ago, when HMAC was the king of message authentication codes I would agree that accelerating a hash function was the second most important thing (after symmetric encryption), but not now.

Indeed, it’s completely speculative when hardware vendors will decide to embed the “next” crypto primitive in their hardware, or which one that will be.  My reasons for thinking Keccak may end up getting into hardware are (a) Keccak was designed, and selected by NIST, specifically in part on the basis of its efficient hardware-implementation properties; and (b) while the SHA3 standard specifies its use only as a hash function, its underlying sponge construction is immediately usable and interesting for many purposes such as efficient authenticated encryption (e.g., several CAESAR competitors build on it), so hardware vendors would be killing two birds (state-of-the-art hash and state-of-the-art encryption) with one stone (KeccakNI :) ).  But again this is completely my personal speculation, I don’t ask or expect anyone to agree with it, and in any case it’s unrelated to my SHA3-512 vs SHAKE256 point.

> No reason except to avoid using a primitive that is not used anywhere else. If SHAKE256 is going to be in all cryptographic libraries anyway, then I have no objection to using it.

SHAKE256 is a trivial variation on SHA3-*, each of which just call into the underlying Keccak sponge with slightly different parameters and behavior.  Besides, if SHAKE256 is used as Ed448’s internal hash as was suggested (and which I would support), it’s got to be in any crypto library implementing Ed448 anyway, so it shouldn’t be too difficult to call the same function for the prehash as well. ;)

Cheers
Bryan