0
$\begingroup$

In SafeCurves: choosing safe curves for elliptic-curve cryptography, Daniel J. Bernstein and Tanja Lange characterize Brainpool curves of the twisted variety (e.g. brainpoolP256t1) as not "Safe", specifically failing the "ladder", "twist", "complete" and "ind" criteria.

Which of these critics apply to the corresponding random version of these curves (e.g. brainpoolP256r1), and why?

The random and twisted Brainpool curves share the same field, are cyclic group of the same prime order thus are isomorphic, and as far as I understand the isomorphism is practical. So I wonder what security difference there can be beyond side channel considerations.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

All critics applies in the same way to both the "t" and "r" Brainpool curves.

An efficiently computable isomorphism preserves all the curve's properties. It was done to support $a=-3$ which allows for faster implementation in Jacobian coordinate system.

Specifically:

  • "Ladder" fails for all curves that are not birational equivalent to Montgomery curves, this includes all curves with prime cardinality such as Brainpool.
  • "Twist" fails for all the curves for which the quadratic twist's order doesn't have a large prime subgroup. Brainpool weren't designed to take this property into account, resulting in a "random" order for the twist's cardinality which doesn't have a large prime factor
  • "Complete" fails for all curves that are not birational equivalent to Twisted Edwards curves, this includes all curves with prime cardinality such as Brainpool. Actually a complete addition law has been found for curves of odd order, such as Brainpool, by Renes et. al. but SafeCurves wasn't updated to support that.
  • "Indistinguishability" is a bit more subtle, but basically fails for all curves that are not birational equivalent to Montgomery curves, this includes all curves with prime cardinality such as Brainpool.

That said please consider that SafeCurves was created by a small but vocal part of the crypto community that at the time was strongly criticizing NIST curves and promoting X25519/ed25519. It can be argued that the safe properties were crafted in order to disqualify the family of short Weierstrass curves (like NIST). But that's a discussion for another question.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Other than "twist", which is a fair criticism, all other properties are arguably satisfied by Brainpool curves (there are ladder algorithms, complete addition laws and randomized representation techniques on prime order curves too). It's just the outdated/deliberately restrictive definition of "SafeCurves" that prevent them from applying. Not that I would necessarily recommend Brainpool curves either, but one has to remember that "SafeCurves" is a bit of a publicity stunt. $\endgroup$
    – Mehdi Tibouchi
    Commented Dec 20, 2023 at 12:01
  • $\begingroup$ Is there any "exception-free" coordinates system for Weierstrass curves? $\endgroup$
    – kelalaka
    Commented Dec 20, 2023 at 14:29
  • $\begingroup$ @MehdiTibouchi I completely agree that Safecurve is a publicity stunt, I will edit to add that. That said in the "ladders" description they don't consider the Brier-Joye ladder as valid because it's not as fast as the Montgomery ladder and "creates a conflict between efficiency and security". I guess the same could be argued against the complete formulas. $\endgroup$
    – Ruggero
    Commented Dec 20, 2023 at 20:29
  • $\begingroup$ @kelalaka Thanks. I've added a mention a link to the complete formulas paper $\endgroup$
    – Ruggero
    Commented Dec 20, 2023 at 20:36
  • $\begingroup$ @MehdiTibouchi and by the way I think even "twist" is not a fair criticism. They need °twist" for X25519 as they can't do point check because the y is not transmitted/used. An input point check, which was popular before SafeCurves, eliminates any reason to have twist security and it costs like 7 field operations. $\endgroup$
    – Ruggero
    Commented Dec 20, 2023 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.