Too many suites?

[jedisct1]

Congrats for the amazing work that has been and keeps being made on this document!

Just a general observation: do so many suites have to be defined?

edwards25519_XMD:SHA-256_ELL2_RO_ is identical to edwards25519_XMD:SHA_512_ELL2_RO_, except that H is SHA-256 instead of SHA-512. Are both really needed?

For the same curve, should a new protocol opt for the suite using SVDW or its counterpart using Simplified SWU? It might be useful for the document to make a recommendation.

In order to facilitate interoperability, increase code reuse and provide guidance to protocol designers, would it make sense to slightly reduce the list, or make one recommendation per curve?

Please apologize if this has been discussed before.

[armfazh]

iirc, the document does not enforce the implementation of all suites, instead it provides examples of suites and their parameters, and also gives guidance on how to generate a new suite.

For the authors: should the document must state which suites to implement?

[kwantam]

My take is that none of the suites should be must-implement, because that depends on the invoking protocol and because this document is more about helping higher-level protocols to make the right choices. But the point is well taken that having too many suites could make this difficult!

Random thoughts:

• I really like the idea of recommending a particular suite for each curve. Or maybe, "for best performance" vs "for simplicity of implementation"?

• I could see getting rid of the SHA-256 / curve25519 suite since ed25519 has pushed people towards combining SHA-512 with curve25519. But I suspect someone will really want to use SHA-256...

• SvdW vs SSWU is a good question. For a library that just wants to implement some map, it makes sense to just support SvdW because it applies to any curve. But for a protocol that is worried about the cost of square roots, it makes sense to pick SSWU. (This goes doubly for curves that require an isogeny map to use SSWU.) So I suspect we'll see a tension between code reuse and optimality (as always, I suppose).

[jedisct1]

Or maybe, "for best performance" vs "for simplicity of implementation"? For a library [...] it makes sense to just support SvdW. But for a protocol, it makes sense to pick SSWU.

Libraries making a choice, and protocols making a different choice is a thing a standard can help avoid.

Recommendations cannot be optimal for every case. The proposed suites may not be optimal anyway (ex: 384 vs 255 bit input for a 2^255-19 field size), so we can't prevent protocol designers from going off track if they really want to.

But having one recommended suite per curve can greatly limit fragmentation, and protocols that cannot be implemented due to incompatible libraries.

[davidben]

As a library author who recently wrote an implementation, please default to removing options. The job of a specification is to make decisions so we have common primitives. Every choice point in the spec is a failure to make a decision. Sometimes that's necessary, but it usually isn't. Where it is, definitely include a recommended one, but that's a baseline expectation. The preferred option is to not define the extra ones in the first place.

The worst outcome would be for different systems to make different choices and implementations are forced to support many variations to cover them all. We should pick as few as possible so everyone's very limited cryptographic testing and implementation efforts can be concentrated on the things that matter.

[chris-wood]

Well said, @davidben! We'd all benefit from more input from folks implementing and using these in protocols before nailing down a minimal set of options. I'll take this to the list to see if we can get some of that feedback!

[armfazh]

This is my proposal for choosing a single suite per group. *Replace RO -> NU, if needed.

Group	Suites
P-256	P256_XMD:SHA-256_SSWURO
P-384	P384_XMD:SHA-512_SSWURO
P-521	P521_XMD:SHA-512_SSWURO
curve25519	curve25519_XMD:SHA-512_ELL2RO
edwards25519	edwards25519_XMD:SHA-512_ELL2RO
curve448	curve448_XMD:SHA-512_ELL2RO
edwards448	edwards448_XMD:SHA-512_ELL2RO
secp256k1	secp256k1_XMD:SHA-256_SSWURO
BLS12381-G1	BLS12381G1_XMD:SHA-256_SSWURO
BLS12381-G2	BLS12381G2_XMD:SHA-256_SSWURO

[chris-wood]

That seems like a reasonable set of choices to me. @kwantam, what do you think?

[kwantam]

Generally these look good to me. Some people might wonder about SHA-512 with curve25519, so we may want to add a comment that this is because of Ed25519.

One small concern: VRF (which should be merging our PR soon, I hope!) is using NU rather than RO. If we remove the NU suites, they will have to add the suite description in their document, which is slightly unfortunate...

Thoughts on how to handle? Should we warn them about this preemptively and try to get them to add the suite definitions now? Should we keep the -NU suites defined for these cases? Something else?

[kwantam]

Ah, one other question: why SVDW for secp256k1? Is it so that we can remove the isogeny map in the appendix?

My guess is that most people who use secp256k1 are very speed sensitive (why else would one use "riskier" Koblitz curves?), so it might make sense to stick with SSWU here, too.

[chris-wood]

Does the VRF document need the NU variant? If not, I'd suggest they use the RO variant instead.

[kwantam]

I think they're concerned about computational cost, and they don't need the RO for the security proof.

@reyzin may be able to chime in here (or I can ping him offline)

[mratsim]

Perhaps the intent of those suite parameters should be clarified? I don't mind having several suites as long as protocol designers are guided towards one suitable for their use case: i.e. if cryptography will be a bottleneck, choose a SSWU suite.

As a library author who recently wrote an implementation, please default to removing options. The job of a specification is to make decisions so we have common primitives. Every choice point in the spec is a failure to make a decision. Sometimes that's necessary, but it usually isn't. Where it is, definitely include a recommended one, but that's a baseline expectation. The preferred option is to not define the extra ones in the first place.

This is not a library though, it's a core building block of protocols. The risk is that if you don't provide recommendations that address the protocol needs, the designers might create their own assemblage.

The worst outcome would be for different systems to make different choices and implementations are forced to support many variations to cover them all. We should pick as few as possible so everyone's very limited cryptographic testing and implementation efforts can be concentrated on the things that matter.

I agree with the last part but for me the worst would be that if none of the building blocks fit the needs (say SSWU was removed and cryptography was already a bottleneck) and designers have nothing vetted that fits their need.

If we really want to make sure we don't forget an use-case we need to start from the potential users or domains and not from our list of suites, i.e.:

• I design a protocol for embedded device to do X, I cannot compromise on signature size, speed delay are not an issue
  • User question: is there a suite that provides what I need?
• I design a protocol for smart device with user interactivity, I cannot compromise on both signature size and speed, ...
• I design a P2P protocol, I expect a lot of signing, ...
• I design a remote access protocol, ...
• I design a content delivery system (Cable TV ...) with ephemeral keys ...

[davidben]

FWIW, if there are clear needs (protocols where the perf difference between NU and RO is very significant and RO's stronger properties are provably unnecessary), I think it's reasonable to have both NU and RO variations. The cost of supporting both NU and RO, from the code complexity side, is fairly low compared to, say, implementing both SSWU and SVDW for the same curve.

I think the argument against NU would be that NU has more sharp edges than RO and having common primitives be consistently robust is worth some performance hit.

This is not a library though, it's a core building block of protocols. The risk is that if you don't provide recommendations that address the protocol needs, the designers might create their own assemblage.

Ultimately those protocols will call into functions implemented by the cryptographic libraries they use. Diversity in building blocks used by protocols is precisely what inflates a library's maintenance burden. If some variation is indeed necessary, it is necessary, but standards shouldn't include options for the sake of it. Variations must pull their weight.

[armfazh]

Ah, one other question: why SVDW for secp256k1? Is it so that we can remove the isogeny map in the appendix?

Yes, I think SSWU fits better for this curve if performance is a must. So I just update the list.

[reyzin]

Does the VRF document need the NU variant? If not, I'd suggest they use the RO variant instead.

I think they're concerned about computational cost, and they don't need the RO for the security proof.

@reyzin may be able to chime in here (or I can ping him offline)

Right, exactly. If I am not mistaken, the RO variants are twice as expensive as corresponding NU variants. In most applications I can think of (VRF included), NU is sufficient.

[chris-wood]

@reyzin the question here is not necessarily whether it's sufficient, but whether it's necessary. Is that the case for applications you're aware of?

If they're necessary, would you object to the VRF draft registering the NU ciphersuites? That would move them to the application where they're needed, without burdening the main hash-to-curve draft. (@kwantam, what do you think?)

[kwantam]

My general feeling is that if we have users for particular ciphersuites now, we define those ciphersuites in the document. As @davidben says, the difference code-wise between the two is very, very small.

(And we can add further encouragement to pick RO if we're concerned that people will get this wrong.)

[chris-wood]

That’s true, but why burden the document for one use case while risking future applications making the wrong choice? I’m not sure any amount of text will be sufficient in deterring mistakes.

It seems better to have the default focus of this document be on RO encodings. Any application that can afford to relax this property can then define NU variants as needed. In this case, the VRF document would define a NU variant. This reduces risk of using the wrong variant when looking at only this document, satisfies the VRF use case, and exercises the effort we put into the registry. That seems like a win all around. What are the downsides?

[kwantam]

First, I fully admit that downsides depend on perspective! :smile:

But in my mind the document exists to serve upper-level protocols, and from that point of view it's sad to require the VRF folks to specify their own suites (and probably also their own hash-to-curve test vectors) when this is a known use-case and we have the machinery and text already in place to do it for them.

Moreover, as @reyzin's comment indicates, I expect that the document will have plenty of "client" protocols in the future that prefer to use nonuniform hashing. In other words, I don't think it's likely to be just one use-case in the long run. If that's true, and if we leave out NU, those documents will likewise need to define their own suites, which may well end up causing unnecessary fragmentation.

I'd be totally happy to have, in every suite subsection, a note saying something like

fooRO is the RECOMMENDED suite for curve X. fooNU MUST NOT be used in protocols whose security relies on a random oracle. Protocols using fooNU SHOULD carefully analyze the security implications of using a nonuniform encoding.

[chris-wood]

I think we're both trying to predict the future with slightly different objectives. I'm not convinced scary advisory text is sufficient, though I'm not willing to lie down in the road over it either!

So, in the interest of moving forward, I'll add back one NU suite (in #254) for each curve, with the scary warning text, and then we can close out this issue. Sound good?

Edit: #254 is now updated!

[jedisct1]

Sounds good to me.

For implementers, supporting NU and/or RO is pretty much the the same thing, and the scary warning is good enough to encourage protocol designers to use RO as a general recommendation.

[davidben]

SGTM

[reyzin]

Curious: can anyone do a tally of uses of hash-to-curve that require RO vs the ones for which NU suffices? @chris-wood @kwantam -- I don't know who your potential users are besides VRF.

[chris-wood]

@reyzin great suggestion! I'll take a crack at that and share the results here.

Edit: An initial list is here.