9
$\begingroup$

When I do:

openssl ecparam -list_curves

I get, among other entries:

brainpoolP512r1: RFC 5639 curve over a 512 bit prime field
brainpoolP512t1: RFC 5639 curve over a 512 bit prime field

Apparently the "t" means it is a twisted ECC curve. Is this slightly more secure or slightly less secure? I'd rather give up a few milliseconds of performance than give up any security margin.

$\endgroup$
2
  • 1
    $\begingroup$ Twisted curves are isomorphic and therefore have the same security strength. $\endgroup$
    – user27950
    Dec 20, 2016 at 13:22
  • $\begingroup$ @MaartenBodewes Behind the hot water pipes ... youtube.com/watch?v=52a7QbLr4ys $\endgroup$ Dec 20, 2016 at 20:25

1 Answer 1

12
$\begingroup$

TL;DR: There is no difference.

Given an elliptic curve $E$ defined over $\mathbb{F}_p$ for some prime $p$, we say that a second curve $E_t$ defined over $\mathbb{F}_p$ is a twist of $E$ when $E_t\cong E$. That is, when there is an isomorphism between $E_t$ and $E$, defined over $\bar{\mathbb{F}}_p$ (the algebraic closure of $\mathbb{F}_p$).

From this we can conclude that every curve is a twisted curve, as every curve is isomorphic to itself. Thus the definition of a regular curve versus a twisted curve is nonsensical, there is no difference.

You may be left wondering why we care about twists in the first place. Well, it turns out that given some curve $E/\mathbb{F}_p$, in some cases one can force a user to work on some twist of $E$ instead (there could be many twists). This twist could have different security properties (notice the definition of twist with respect to $E$), which could in turn lead to an attack. This is an example of a so-called invalid-curve attack.

Edit: Note that ${\tt brainpoolPXXXr1}$ and ${\tt brainpoolPXXXt1}$ are trivial twists (see Definition 9.5.1). That means that the security properties are essentially the same. The reason why both these curves are specified, is because ${\tt brainpoolPXXXr1}$ is pseudo-randomly generated (and therefore supposedly leaving them unable to create backdoors), yet has large curve parameters. By specifying ${\tt brainpoolPXXXt1}$ which has $A=-3$, we can make some improvements in the curve arithmetic, making operations more efficient (see EFD).

$\endgroup$
5
  • $\begingroup$ Could you explain (more clearly) why the twisted curves are named for brainpool in the first place? $\endgroup$
    – Maarten Bodewes
    Dec 20, 2016 at 14:17
  • 1
    $\begingroup$ That is actually quite simple, and has nothing to do with security. In fact, the standard does not seem to mention twist attacks at all. They pseudo-randomly generate some curves which satisfy some pre-defined properties (chapter 3 of the standard), and one of the requirements is that a curve $E$ (i.e. brainpoolPXXXr1) is isomorphic over $\mathbb{F}_p$ to a curve $E_t$ with $A=-3$ (i.e. brainpoolPXXXt1). This isomorphic curve is a twist, and the reason we want $A=-3$ is because arithmetic simplifies. $\endgroup$ Dec 20, 2016 at 14:42
  • $\begingroup$ OK, now for the last step, the reason for this is that this simplification allows for fast implementation of the curve, right? I mean the question is directly about the twisted curves as mentioned in the brainpool page. You correctly specify why there is no security difference, but it still doesn't really explain why the named curve is listed in the first place. $\endgroup$
    – Maarten Bodewes
    Dec 20, 2016 at 15:40
  • $\begingroup$ I'm not sure if I understand you correctly. The twist is named precisely because it allows for fast curve arithmetic, and the document does not mention any other reason (as far as I can see). See tools.ietf.org/html/rfc5639 section 2.2.3. $\endgroup$ Dec 20, 2016 at 16:15
  • 1
    $\begingroup$ Looks like you understand me, I just tried to make the information in the comments part of the answer. And although I have extensively worked with these curves I'd rather have the answer be provided by a certain CurveEnthusiast :) $\endgroup$
    – Maarten Bodewes
    Dec 20, 2016 at 18:18

Your Answer

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

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