Wishlist topic: Please cover the number of Pre-images per point and mapping algorithm more in depth.

[BjoernMHaase]

Hello, H2C team.

Michel, Julia and I (Björn) are currently working on a security proof for CPace, where the main complexity is to properly deal with the different flavours of mapping and their specific properties. I.e. this is strongly related to your work in the H2C team.

I promised to give you a first feedback regarding the present draft. I will go through the draft more in depth soon and keep you synchronized.

One of the objectives is to dig a bit more into the details of the mappings instead of just considering them to be some form of random oracle hashing to the group.

Interrestingly for the security analysis, one of the key features of the mappings actually seems to be the property of invertability.

To give you an idea regarding the properties of the maps that I believe to be important from a theoretical point of view, find enclosed the features that seem to be necessary/helpful for formally reducing the diffie-hellman problems. I'd suggest to name the property "probabilistic invertability".

IMO, all of the maps from the current RFC draft seem to fulfill this requirement set. Essentially, it must be efficient to predetermine the max. numbers of pre-images for any single point on the group. Secondly, there needs to be an efficient function for obtaining all pre-images.

It is my intuition that this invertability guarantees to some extend that no DLP-related structure can be exposed or exploitable by points generated by the map, as long as DLP remains hard. For mappings that employ exponentiations (such as used in TBPEKE or SPAKE2) and which are, thus, not efficiently invertable, some attacks could exist that allow to use some structure in the mapping-generated points for attacking the DLP / DH-style protocols that use the points. (e.g. N,M in SPAKE2 with known DL). Invertible maps could not generate such structure.

(Actually, we will be able to prove security for CPace also for the H2C curve with more uniform distribution, however this will most proably require slightly more work than using the generic encodings with non-uniform distribution.)

Invertability and the structure or the images and the distributions does not presently play an important role in the H2C draft. This is a good idea, when keeping a h2c-user-centric view. Still I think that it might be helpful to add more explicit information on the max. number of pre-images for the different mapping algorithms (SWU, SSWU, Elligator2, ...), as the security bounds seem to depend on this value, at least for CPace.

Björn

[kwantam]

Hi Björn! Thanks for the very detailed suggestion.

There is a very small discussion of this in the "Security Considerations" section: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-10#section-10.1

Am I correctly interpreting your message as requesting even more detail? I think the papers cited in that section give the information you're looking for. Is the idea that you'd prefer to see all of this in one place?

[BjoernMHaase]

Basically, what I am looking for is firstly to keep you synchronized with our findings.

The main point might be, that I'd like to suggest to slightly switch the focus of the RFC.

After reading the draft, I understand that the focus of the team is "let's provide a monolithic black-box construction that could be used as a random oracle hashing directly to group elements such that protocol designers and implementers don't need to dig into the details".

In the course, you provide a construction which basically consists of three (or four) independent substeps: (1) Encode to field, (2) map, (3) (optionally) add two map-generated points and (4) co-factor clearing.

What I'd like to suggest is that there might actually be applications that don't need or want the "big black box" of the full construction but often the big benefit of your work might be the carefully analyzed and well-designed sub-blocks.

In my opinion, this might already be the case of ristretto and decaf, which might happily be using the encode-to-field block and possibly the map but might differ in details for other points.

For CPace, I probably would like to use everything except for the co-factor clearing.

Also for the OPRF, I am convinced that what you actually need for proving security is not a uniform hash2curve but only a well-designed mapping to the curve. As a consequence, by requiring a black-box construction with a uniformly distributed hash, you will in practice be ruling out OPRF constructions using X25519 / X448 and might even have bigger difficulties for proving security when not considering the H2C as a random oracle.

So what I'd like to suggest in practice is: In addition to the black-box approach which I also support, I'd appreciate if you embraced a bit more the "well designed substep" perspective of users.

And for this, it might be helpful to have a bit more (not much more) text and pointers regarding the inner components, e.g. regarding the invertability and known information on the maximum number of pre-images per map.

In fact the information from 10.1 is already very helpful and possibly enough for proving security. Still, if it actually comes out that this small section captures the essence of what is actually needed, a bit more information on the individual mappings might be worth the effort. E.g. I currently don't know whether there is invertability also for plain SWU. For SSWU I did review it already.

One option might be to have the information from section 10.1 regarding the different mappings transferred to the respective mapping sections for Elligator2, SWU, SSWU, etc. with 2-3 short sentences for the different maps (Elligator, SWU, SSWU, ...) regarding the respective limits on the number of preimages and the invertability.?

Yours,

Björn

[kwantam]

Thanks for the detailed clarification!

At a really high level: I'm a bit concerned about shifting the focus of the document, since it's currently in last call. Also, it's not totally clear to me what shifting the focus would entail---your message suggests that it might be enough to just move some text around, but I'm not sure if I've interpreted it correctly.

One possibility might be to add a pointer to papers that discuss the relevant properties in the Security Considerations section (if they're not already---but I think they are, in Section 10.1, no?). I think this is much more likely to fly, because adding detailed technical discussion is probably outside the scope of an RFC: this document is not intended to specify all possible properties of the components, only to describe how to use them in a way that is both secure and compatible with others' usage. Other relevant properties---especially ones covered thoroughly in other documents---probably are out of scope.

Finally: your message above mentions SWU. Do you mean SvdW? The document does not cover SWU, and that seems almost certain to remain true.

I'm curious to hear what other folks think here. @chris-wood? @armfazh?

[BjoernMHaase]

Do you mean SvdW. Yes.

Actually I misread it and thought that plain SWU is still in the draft, but obviously you have removed plain SWU some revisions ago.

Right now I am trying to dig through the properties of SvdW. (Kind of difficult again, if you don't have access to springer journals, except for IACR publications, and university libraries have shut down access completely to people extern to the university ...).

Do you have at hand, whether the SvdW map is also invertible, i.e. you can efficiently obtain all preimages?

[kwantam]

I believe the original paper discusses at least the number of points in the image:

https://works.bepress.com/andrew_shallue/1/download/

Fouque and Tibouchi look at SvdW at Latincrypt 2012:

https://hal.inria.fr/hal-01094321/document

Probably there will be a bit of tweak necessary for the specific formulation of SvdW that we use, but I'd guess it wouldn't be so bad...

[BjoernMHaase]

Thank you for the pointers!

As you said, limits for the size of the image are provided in the original paper and as I understand it from a first look, also invertability is available, but I will have to re-read it with a bit more time. (Actually its again about Skalba's equation and inverting will most surely involve a couple of square roots, just as for the other maps.)

In the latincrypt paper, I had the impression that this probably only covers the special case of Barreto–Naehrig Curves.?

Thanks.

Yours,

Björn.

[chris-wood]

[EDITED]

FWIW, I'm opposed to changing the fundamental abstraction in this document.

I'd like to follow up on one comment @BjoernMHaase made above:

Also for the OPRF, I am convinced that what you actually need for proving security is not a uniform hash2curve but only a well-designed mapping to the curve. As a consequence, by requiring a black-box construction with a uniformly distributed hash, you will in practice be ruling out OPRF constructions using X25519 / X448 and might even have bigger difficulties for proving security when not considering the H2C as a random oracle.

Indeed, a random oracle is not needed for the OPRF, though that's what the draft currently uses for NIST curves. We probably could use the non-uniform variant (encode_to_curve) abstraction, though I think certain analyses may need to be updated as a result.

[BjoernMHaase]

Hello Christopher,

I just was about to comment about clearing the co-factor in the map for CPace, which now seems to have been removed/edited.

I believe generally, that any protocol working on a group with co-factor will have to carefully analyze the design regarding this complexity. I don't see, how a co-factor cleared mapping could avoid that analysis. It might rather create a false sense of security to believe that the co-factor complexity was already handled by the hash2curve construction and become harmful.

It is my experience that it's always best to clearly attribute the responsibilities for solving a specific problem to exactly one individual or team. If you split responsibilities to two or more parties, each of them might falsely believe that the other partner already has resolved the problem.

As such, I believe that, as Hash2Curve could not comprehensively deal with the co-factor issues, it should also not try at providing a partial mitigation. In my opinion it should not include any co-factor clearing except for a strong statement in the security section: "We porpousefully did not consider this important aspect because we could not take off this load from your sholders and stress, that it will be necessary for you as a user to carefully analyze the implications for your protocol."

[BjoernMHaase]

There is a second aspect in Christopher's reply which deals whether uniform or non-uniform constructions should be preferred.

I believe, regarding the OPRF construction for instance, that it might be worth considering is that definitions that allow for single-coordinate algorithms (such as X-coordinate only scalar multiplication on NIST curves or X25519/X448) might be an easier starting point for side-channel protected implementations. Often this approach might also be preferable from an implementation-security point of view for NIST curves.

If I recall correctly, many protocols, such as TLS only use the x coordinate of the DH results for the session key generation and I believe this is specifically in order to also encourage single-coordinate scalar multiplication implementations.

When using protocols using points generated by the non-uniform mappings, the "Map twice and add" procedure might actually be the only substep of the whole protocol that requires the full group structure. As a result single-coordinate algorithms would be ruled out for this protocol. This is most probably not a severe issue in practice for the NIST curves, as I believe that most implementations actually use full group elements anyway.

However requiring the "map twice and add" effectively rules out simple X22519 and X448-based implementations.

For the security analysis, on the other hand, it might be worth having the same construction on all of the curves (i.e. no difference between NIST/Brainpool and Edwards/Montgomery) ...

This draws me to the conclusion that preferring the non-uniform maps might be the preferrable strategy.

Moreover at least regarding reduction of the Diffie-Hellman problems to the standard prime-order problems I come to the conclusion that the security bounds for the non-uniform mappings will actually be tighter than for the "map twice and add" hash2curve constructions.

BTW, I'd be willing to contribute to the security analysis of OPRF constructions with non-uniform mappings, which I believe to be straight-forward with the definition of the inverse probabilistic map above.

[chris-wood]

@BjoernMHaase given lack of activity on this issue, I think we should close this out. I don't think providing a possibly-unsafe abstraction (without cofactor clearing) is pragmatic. Unless there is some reason that CPace cannot use the encode_to_curve abstraction, I suggest we close this issue with no action. (I'll note that it seems plausible for CPace implementations to "clear" the cofactor with h_eff = 1, which is a no-op.)

@kwantam, how much would you dislike this? :-)

[chris-wood]

Ping @kwantam :)

[kwantam]

I agree that it would be better if this h2c document gave a totally safe abstraction. Another document might give a possibly-unsafe abstraction, with lots of warnings to implementors and a pointer to the h2c doc as suited for most applications, but I worry that with the document as complex as it is, adding possibly-unsafe constructions would be dangerous.

[chris-wood]

Sounds good. Closing as a result.