[Cfrg] Some observations after the ECC interim meeting

[Patrick Longa Pierola <[e-mail]>]

Dear all,
In our presentation at the CFRG meeting we were especially interested in drawing some attention to some issues that are very relevant when using Edwards and Montgomery curves. In particular,

-   when computing the Montgomery ladder in constant time there is a potential failure case if the scalar matches 0 (mod r) or 0 (mod r'), where r and r' are the prime orders of the subgroups generated on the Montgomery curve and its quadratic twist, respectively. We noted that Curve25519 avoids this issue (together with dealing with subgroup attacks) by restricting the scalar values to 2^254 + 8{0,1,...,2^251-1}. This design feature does not match the standard practice in cryptography that is to allow the scalar value to be in the full range [1, r-1]. For example, when working with Ed25519 there is a restriction of scalars to less than half of such full range. Refer to slide 10 in [1].

-   when using the Montgomery ladder for key exchange (computed with one variable-base scalar multiplication) there are engineering issues that need to be addressed: is key generation being computed on the Montgomery form or the Edwards form? If it is computed using the Montgomery form then there is a significant performance impact (option referred to as "hybrid 1" in our presentation; see slides 23-24 in [1]). One can certainly use the Edwards form instead (this option corresponds to "Hybrid 2" in the same slides) but one then needs to deal with issues such as point conversion, special point formatting for transmission, etc. Another potential issue with this second alternative is that good solutions might be protocol-specific, instead of generic. Our performance results indicate that there is no need to deal with these potential issues (issues that are relevant, e.g., to the TLS handshake using PFS, and that might be even more difficult to deal with in different protocols) because all the computations can be performed purely on the twisted Edwards form of the curve. This also brings to the table the possibility of using only one curve form (twisted Edwards) for signatures and key exchange (and any other possible ECC operations), instead of defining different curve forms for different ECC operations. This unification might bring several benefits in practice.

Finally, we point out that the current effort of moving forward with only one curve targeting *one security level* (i.e., 128-bit) might bring the risk of having inconsistencies once future additions are done at other security levels. We suggest instead to first have a solid curve selection that includes all the security levels, with strong consistency in the design.

Best regards,

Patrick


[1] Patrick Longa, "Selecting Elliptic Curves for Cryptography", talk given at the interim teleconference meeting, April 2014. http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf