Support for SHA-3 and SHAKE / cSHAKE

[mimoo]

The current draft only seems to standardize the algorithms with SHA-2. I'd like to see support for SHA-3 and SHAKE (and cSHAKE) if possible so that we don't have to write an extension/another RFC later on.

using cSHAKE would allow to replace the hash and HKDF with one algorithm.

[kwantam]

Thanks for bringing this up!

The SHA-3 part of this request appears to be easily handled by creating a ciphersuite (but please let me know if this does not seem correct). As such, it shouldn't require an extension or another RFC even if we don't specify SHA-3--based suites.

Regarding (c)SHAKE:

I'm sure you're aware of my comments in the other thread, but for the sake of completeness, here's a link: cfrg/draft-irtf-cfrg-bls-signature#10. To rehash and slightly expand my comments there:

To me it does not appear that there's a compelling reason to use (c)SHAKE rather than HKDF:

• HKDF works just fine for SHA-3; in contrast, there's no sensible notion of "compatibility" between SHA-2 and (c)SHAKE.

• (c)SHAKE is slightly cheaper than HKDF-SHA3, but there's categorically no reason to optimize the cost of HKDF invocations in hash-to-curve---that cost is fully in the noise.

• The hash-to-curve draft is already quite complex. From my perspective, the bar is very high for specifying multiple KDFs given that HKDF already works for everything.

• I'm aware of and reasonably sympathetic to the argument that some codebases will already have a (c)SHAKE implementation and won't want to add HKDF, but I'm skeptical of the practical benefit given that there are compact and extremely mature implementations of HKDF, whereas (c)SHAKE is new and comparatively obscure.

But: let's discuss further! Opinions are made to be changed :)

CC @chris-wood @armfazh

[mimoo]

Hey @kwantam thanks for the response!

The hash-to-curve draft is already quite complex. From my perspective, the bar is very high for specifying multiple KDFs given that HKDF already works for everything.

I can agree that supporting more algorithms means having a more complex specification. I'm usually against making a specification more complex. So for once, I'm going to support a side I'm not used to support :)

But I have good arguments!

The reason is that we are investigating using cSHAKE in place of hash functions, KDFs, and so on. and getting rid of dependencies we don't need. If this draft would switch to cSHAKE exclusively, it would actually be much simpler than the current one.

HKDF works just fine for SHA-3; in contrast, there's no sensible notion of "compatibility" between SHA-2 and (c)SHAKE.

It is true that HKDF works fine for SHA-3/SHAKE, but it also makes little sense to implement it on top of something that already provides pretty much the same API as HKDF. Realistically, we are probably going to just use (c)SHAKE instead and risk diverging from the specification. How costly would it be to add HKDF to the name of the ciphersuite?

I'm skeptical of the practical benefit given that there are compact and extremely mature implementations of HKDF, whereas (c)SHAKE is new and comparatively obscure.

cSHAKE is pretty much the same construction as SHA-3. So I wouldn't say obscure. If we talk about support from libraries, then I agree.

[kwantam]

@mimoo thanks for the clarifications 👍

The reason is that we are investigating using cSHAKE in place of hash functions, KDFs, and so on. and getting rid of dependencies we don't need. If this draft would switch to cSHAKE exclusively, it would actually be much simpler than the current one.

Obviously it's easy to disagree about what qualifies as "much simpler," but count me as strongly skeptical. The maximum possible simplification would be obtained by replacing HKDF-H with cSHAKE256. But let's think about how much that actually simplifies the document:

• It doesn't significantly simplify the hash-to-base-field section. At best, it means that we could get rid of the discussion of H's output length.

• It doesn't significantly simplify the ciphersuites. At best, it means that we could remove H.

Moreover, note that the above simplifications are not intrinsic to the choice of cSHAKE: we could instead require everyone to use HKDF-SHA2-512, whereupon we'd also get the above simplifications. So the claim about simplification appears to be a generic argument for fixing one hash function, not an argument for using cSHAKE.

But beyond that, to first order there does not appear to be any interest in using SHA-3 other than yours (please interpret "yours" broadly---I surmise that you are speaking on behalf of your employer). So you can certainly understand how from my perspective the suggestion to require everyone to use SHA-3 isn't even remotely plausible. This means that the only option is to specify multiple KDFs, and that is not a simplification.

In other words, specifying cSHAKE would, under any remotely plausible interpretation, dramatically increase the complexity of the standard.

It is true that HKDF works fine for SHA-3/SHAKE, but it also makes little sense to implement it on top of something that already provides pretty much the same API as HKDF.

As far as I can tell, the above effectively restates the argument that it's more efficient to use cSHAKE than to use HKDF-SHA3. In a narrow sense, there's no doubt that this is true.

(EDIT: to be clear: SHA-3 does not provide the same API as HKDF. cSHAKE does, but no one is arguing to use cSHAKE inside HKDF.)

But in the broader context of the standard, the more important question is: how does the cost/benefit of using HKDF-SHA3 compare to the cost/benefit of specifying multiple KDFs? And there, it seems to me that the cost of HKDF-SHA3 vs cSHAKE is effectively zero (because the cost of the hashing is in the noise), whereas the cost of specifying multiple KDFs is high (because it increases the complexity of the document).

So to me, what you say in the quote above is articulating an aesthetic preference, not a technical justification.

Realistically, we are probably going to just use (c)SHAKE instead and risk diverging from the specification. How costly would it be to add HKDF to the name of the ciphersuite?

This appears to be a statement that you have no intention of following the standard unless the document is modified to reflect what you've already decided to do. (Please correct me if I'm wrong.)

I want to be clear: that is a totally fine decision, though I hope you do not follow that course.

In any case, I'm sure you can see that, from my perspective, this is not a persuasive argument either for or against change: since everyone else who is currently implementing (to my knownedge) prefers to use HKDF-SHA2, either choice means that someone will violate the standard.

cSHAKE is pretty much the same construction as SHA-3.

Exactly! and I have no hesitation in claiming that compared to HKDF and SHA-2, SHA-3 is obscure.

But the point is: even if SHA-3 were exactly as popular as SHA-2 (which certainly isn't true now, and indeed may never become true), that would not be enough to justify ruling out the use of SHA-2 in the standard.

Meanwhile, the current standard explicitly provides for the use of SHA-3 (see #137). Yes, it is very slightly sub-optimal. But please see above regarding aesthetic vs technical justifications.

[mimoo]

I think I can agree with most of your points. I still think that if we're writing an RFC today, it doesn't make sense to not include SHA-3 or constructions that will probably grow or even replace the current ones in the future.

everyone else who is currently implementing

how many people are doing this? It sounds like one request is already a pretty big percentage :D

[kwantam]

Thanks for the quick response 👍

I still think that if we're writing an RFC today, it doesn't make sense to not include SHA-3 or constructions that will probably grow or even replace the current ones in the future.

With apologies (I may be misinterpreting), the above appears to be saying that nothing short of fully optimizing for SHA-3 (in this case, by using SHAKE rather than HKDF) counts as "including" it in the standard. If indeed that's what the statement means, I think it's reasonable to regard that as a tendentious characterization.

We certainly do consider SHA-3 important, and the current document is perfectly compatible with its use. If it would be helpful for us to explicitly list ciphersuites and test vectors for SHA-3, that's absolutely something we will consider! (but I'm sure you can understand that I can't promise to do it before consulting with my co-authors).

how many people are doing this? It sounds like one request is already a pretty big percentage :D

As @JustinDrake points out, everyone who has been participating in the bi-weekly BLS signatures teleconference appears to prefer some variant of SHA-2. Concretely, the BLS sigs README lists a few reference implementations, and those are all using SHA-2.

[kwantam]

How costly would it be to add HKDF to the name of the ciphersuite?

By the way, a small suggestion:

If you prefer to specify a ciphersuite that uses cSHAKE instead of HKDF, I'd recommend indicating this in the ciphersuite ID to avoid confusion. For example, you might consider ciphersuite names simliar to the following:

BLS12381G1-SHA3256-SSWU-RO:KDF=cSHAKE-

Or perhaps

BLS12381G1-SHA3256:KDF=cSHAKE-SSWU-RO-

This will help ensure orthogonality to folks using HKDF-SHA3.

[mimoo]

With apologies (I may be misinterpreting), this appears to be saying that nothing short of fully optimizing for SHA-3 counts as including it. I think it's reasonable to regard this as a tendentious characterization.

Not sure I understand this paragraph

If it would be helpful for us to explicitly list ciphersuites and test vectors for SHA-3, that's absolutely something we will consider

cool!

[burdges]

I'd personally suggest specifying only for cloneable XoFs like SHAKE128 and Blake2x but relegate HKDF to some legacy algorithms appendix, but yeah the speed does not matter here. It's possible memory usage matters for some very small devices, but those can always do something custom.

[kwantam]

I'm leaning towards adding some words in the document (maybe in the hash_to_base section, or in the ciphersuites section) about how one could define new suites that use variants of hash_to_base, e.g., built on different PRGs.

I'm really not inclined to define multiple hash_to_base variants because of issues with exploding complexity. But on the other hand, doing it now means that we can try and make sure that domain separation is done correctly, etc...