Subject: [TLS] Using Brainpool curves in TLS

From: Johannes Merkle <[email-masked]>
Date: Mon, 14 Oct 2013 17:45:57 +0200

jaust in case that someone hasn't noticed it: our draft on using the Brainpool curves in TLS has been published as RFC 7027
http://www.rfc-editor.org/rfc/rfc7027.txt
-- 
Johannes

---

From: Patrick Pelletier <[email-masked]>
Date: Tue, 15 Oct 2013 00:32:52 -0700

> http://www.rfc-editor.org/rfc/rfc7027.txt

Is support available in any TLS libraries yet?  Do we know which 
libraries are planning on adding support for Brainpool?

--Patrick

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 Oct 2013 11:46:12 +0100

On 15/10/2013 08:32, Patrick Pelletier wrote:
>> jaust in case that someone hasn't noticed it: our draft on using the Brainpool
>> curves in TLS has been published as RFC 7027
> Is support available in any TLS libraries yet?  Do we know which libraries are
> planning on adding support for Brainpool?
> 

Just added support to the OpenSSL development version. Would be interested in
any test servers for interop testing.

Steve.
-- 
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: "Paul Bakker" <[email-masked]>
Date: Tue, 15 Oct 2013 12:56:02 +0200

For now I've just put up a test server at:
141.138.204.107:4433

Running PolarSSL 1.3.1 with Brainpool curves supported..

Let me know if you run into any issues..

Paul

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Dr
> Stephen Henson
> Sent: dinsdag 15 oktober 2013 12:46
> To: [email-masked]
> Subject: Re: [TLS] Using Brainpool curves in TLS
> 
> >> jaust in case that someone hasn't noticed it: our draft on using the
> >> Brainpool curves in TLS has been published as RFC 7027
> Just added support to the OpenSSL development version. Would be
> interested in any test servers for interop testing.
> 
> Steve.
> --
> --
> Dr Stephen N. Henson.
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 Oct 2013 12:14:45 +0100

> For now I've just put up a test server at:

Tried it with the three Brainpool curves and OpenSSL: no problems.

Steve.

---

From: "Paul Bakker" <[email-masked]>
Date: Tue, 15 Oct 2013 13:16:13 +0200

Cool.. First interop proof for both :)

> From: Dr Stephen Henson [mailto:[email-masked]]
> Sent: dinsdag 15 oktober 2013 13:15
> To: Paul Bakker; 'Peter Gutmann'
> Cc: [email-masked]

---

From: "Paul Bakker" <[email-masked]>
Date: Tue, 15 Oct 2013 14:13:42 +0200

Fresh from the oven:
https://polarssl.org/tech-updates/releases/polarssl-1.3.1-released

So: yes.. ;)

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Patrick Pelletier
> Sent: dinsdag 15 oktober 2013 9:33
> To: [email-masked] ([email-masked])

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Oct 2013 08:49:52 -0700

>> planning on adding support for Brainpool?

What problems does this solve? The Brainpool curves still have
unverifiable construction, Weirstrauß form (meaning many corner cases
in addition and the possibility of sending points not on the curve),
primes that are ugly and horribly slow (seriously, randomly picked
primes?),
come courtesy of our friends in the BND, and don't solve any problems
beyond a possible backdoor in NIST curves. What is the rationale
behind these curves as opposed to Curve25519? (The curve given by the
Montgomery equation y^2=x^3+486662x^2+x over the field
F(2^255-19), with canonical basepoint x=9).

The implementation in PolarSSL has a nonconstant pattern of memory
access. Seriously, it isn't 1999 anymore: everyone doing cryptography
should be aware of these issues.
Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Nico Williams <[email-masked]>
Date: Tue, 15 Oct 2013 11:12:39 -0500

> should be aware of these issues.

Indeed, constant-time operation is a very big deal.  A curve could be
perfectly secure in the ECDLP sense and yet be utterly insecure due to
side channels.  There are no standard curves that we can trust to be
secure in both senses; DJB's curves are very likely secure enough in
the ECDLP sense (certainly given current *public* research) and they
are secure in the other sense; they are also quite fast.
http://safecurves.cr.yp.to/

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Oct 2013 18:40:49 -0700

> are secure in the other sense; they are also quite fast.
Note Bena: Being safe against side channels is a property of the
implementation, not the curve.
DJB's implementations are constant time, and the curves have
properties that make it easier to be constant time,
but it is trivial to introduce backdoors into implementations of them.

---

From: Nico Williams <[email-masked]>
Date: Tue, 15 Oct 2013 21:25:07 -0500

> properties that make it easier to be constant time,

That's what I was referring to, yes.

> but it is trivial to introduce backdoors into implementations of them.

Do you mean that it's easier to backdoor implementations of specific
EC curves than, say, RSA?  I would think that implementations of...
just about anything can be backdoored with relative ease.

Nico
--

---

From: [email-masked] (Martin Rex)
Date: Wed, 16 Oct 2013 04:52:42 +0200 (CEST)

> just about anything can be backdoored with relative ease.

I assume that he might have meant what is also indicated on the
referenced Web Site http://safecurves.cr.yp.to/
that it is extremely difficult to implement ECC and _NOT_ hang yourself,

It would not surprise me at all if the vast majority of ECC
implementations would be found to be vulnerable to serious
weaknesses, when carefully analyzed, and that the problems found
in the RSA part would be *MUCH* smaller in comparison.

-Martin

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Oct 2013 20:33:46 -0700

> that it is extremely difficult to implement ECC and _NOT_ hang yourself,
I mean exactly what I said: no more and no less. Implementations must
be carefully
audited to establish freedom from side-channels, no matter what
primitive they implement.
> in the RSA part would be *MUCH* smaller in comparison.
I really do not know how one is supposed to measure this, or why it matters.
A few well-audited implementations designed for maximum clarity should suffice
for all most all purposes.

---

From: [email-masked] (Martin Rex)
Date: Wed, 16 Oct 2013 07:34:08 +0200 (CEST)

> primitive they implement.

That is the theory.

Now practice is an entirely different matter.

If you look through the algorithms in the appendices of FIPS 186-3,
you'll find a lot of algorithms that contain conditionals.

If the algorithm will have to be used inband for an asymmetric
crypto operation, those algorithms leak timing information
when processing secret values.

If a crypto operation needs an ephemeral random and secret prime,
this would apply to the necessary primality tests.

If the algorithm described by the underlying specification is not
100% constant time, why would you expect implementations
to have this property?

-Martin

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 16 Oct 2013 09:21:15 +0200

> unverifiable construction, 

This is plain wrong. Obviously, you have not read RFC 5639. The construction of the Brainppol curves is completely
verifiable, only based on the fundamental constants Pi and e.

Johannes

---

From: Tom Ritter <[email-masked]>
Date: Wed, 16 Oct 2013 09:32:53 -0400

> verifiable, only based on the fundamental constants Pi and e.

Repeating others arguments:

"Several unexplained decisions: Why SHA-1 instead of, e.g., RIPEMD-160
or SHA-256? Why use 160 bits of hash input independently of the curve
size? Why pi and e instead of, e.g., sqrt(2) and sqrt(3)? Why handle
separate key sizes by more digits of pi and e instead of hash
derivation? Why counter mode instead of, e.g., OFB? Why use
overlapping counters for A and B (producing the repeated
26DC5C6CE94A4B44F330B5D9)? Why not derive separate seeds for A and B?"

http://safecurves.cr.yp.to/rigid.html

I'm not sure I agree with them fully, but I also don't have very much
context. (My thoughts when reading that is "Why sqrt(2) and sqrt(3)
instead of pi and e - what makes those constants more trustworthy?")

-tom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 16 Oct 2013 16:25:10 +0200

> instead of pi and e - what makes those constants more trustworthy?")
I think the point is not that sqrt(2) and sqrt(3) would be better constants that
pi, e, or any other constant. It's just that there are a few bits of freedom in
the choice of parameters, which makes the curve "not fully rigid".

This is obviously not a security concern unless you believe there is a class of
weak curves with quite high density, which would IMO be very bad news for ECC in
general, not only these particular curves.

Which is probably why the authors of the page chose a nice green color and check
symbol for both "fully rigid" and "somewhat rigid", as opposed to the
frightening red color of the other classe of curves.

Manuel.

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 16 Oct 2013 17:10:21 +0200

> 26DC5C6CE94A4B44F330B5D9)? Why not derive separate seeds for A and B?"

The fact that the source of the seeds is explained is a huge step towards complete transparency as compared to the NIST
curves. Your arguments refer to the procedure for derivation of the parameters from the fundamental constants. There is
no canonical choice for such a procedure; the most obvious approach was to take it from ANSI X9.62, which we did.
Admittedly, we introduced a slight change: we use the first two PRNG outputs as coefficients a and b, whereas ANSI uses
the first PRNG output as r=a^3/b^2 and selects a and b arbitrarily with that relation); but this change is rather small
and quite straightforward. IMO there is really not much room left for conspiracy theories.

Anyone who is so paranoid (in the positive way which is useful for IT security professionals) to fear that a backdoor
may have been built in by tuning the parameter generation procedure should also question all design criteria for any
other curve, including Curve25519. There is always room for choices.

Johannes

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 16 Oct 2013 17:15:09 +0200

>> instead of pi and e - what makes those constants more trustworthy?")

sqrt(2) and sqrt(3) are much less fundamental than Pi or e. If you ask mathematicians for the most fundamental
constants, you will get 1, Pi, e, i, and maybe 2.

I am not sure how to use the imaginary unit i in an algorithm though ;-)

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Oct 2013 08:21:33 -0700

> other curve, including Curve25519. There is always room for choices.
Curve25519 picks the smallest value of A that meets the parameters.
Once the prime, shape, and all restrictions are selected, the result
is deterministic. Brainpool is close enough that I would say "quite
rigid" as opposed to "deterministic construction". Basically, the
length of a PARI script to generate the curve should be short.

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 16 Oct 2013 17:45:42 +0200

>> instead of pi and e - what makes those constants more trustworthy?")

Also, Pi and e as transcendental numbers seem more "unstructured" as any (square or higher-order) root. Just imagine an
imaginary hash function taking as a first step the square of the input string taken as integer. Surely, SHA-1 does not
work this way but the "unstructuredness" of transcendental numbers seems more robust against any kind of arithmetic
processing.

> general, not only these particular curves.

In support of this argument let me summarize my answers to the assessment on http://safecurves.cr.yp.to/rigid.html

Q: Why SHA-1 instead of, e.g., RIPEMD-160 or SHA-256?
A: Procedure follows ANSI X9.62

Q: Why use 160 bits of hash input independently of the curve size?
A: 160 bit is the minimal amount of input entropy needed to allow maximum entropy n the hash value.

Q: Why pi and e instead of, e.g., sqrt(2) and sqrt(3)?
A: Most mathematicians will acknowledge that pi and e are more fundamental than sqrt(2) and sqrt(3). Furthermore, as
transcendental numbers they are more robust w.r.t the "unstructuredness" of their decimal representation.

Q: Why handle separate key sizes by more digits of pi and e instead of hash derivation?
A: Follows the KISS principle. But, yes, there was a very small degree of freedom.

Q: Why counter mode instead of, e.g., OFB?
A: Counter mode? We didn't use block ciphers. If you refer to the counter used in computation of hash values, this
follows ANSI X9.62.

Q: Why use overlapping counters for A and B (producing the repeated 26DC5C6CE94A4B44F330B5D9)?
A: I admit that this is unfortunate. And yes, there was a very small degree of freedom.

Q: Why not derive separate seeds for A and B?
A: Yes, there was a very small degree of freedom.

You see, there is not much freedom in the choices made, which implies that implanting a back door would have required  a
very large class of weak curves or great luck.

-- 
Johannes

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 16 Oct 2013 17:53:57 +0200

> Curve25519 picks the smallest value of A that meets the parameters.
Why the smallest, not the largest negative? Why using little /big endian (don't know which was used) instead of the
other? Why choosing exactly these conditions (you phrase it "parameters").

Don't get me wrong. I admit that the construction of Curve25519 is extremely rigid, and even more rigid than that of the
Brainpool curves. I only point to the fact that there is no perfect rigidity.

> rigid" as opposed to "deterministic construction". Basically, the

I think we can agree on that statement.

> length of a PARI script to generate the curve should be short.

Good idea, minimal Kolmogorov complexity should be a good formal definition.

-- 
Johannes

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Oct 2013 11:29:25 -0500

> other? Why choosing exactly these conditions (you phrase it "parameters").

Endianness has no impact on the mathematics involved.

Smallest because there is such a thing (as opposed to largest, which
is unbound).  It could have been smallest absolute value, allowing one
more degree of freedom.  Perhaps there's a class of attacks that works
with positive As and not with negative As (or vice-versa)?  But that
seems unlikely.

> Brainpool curves. I only point to the fact that there is no perfect rigidity.

Agreed.  I like DJB's curve constructions because as much as possible
is explained verifiably.

> I think we can agree on that statement.

Agreed.

But the SafeCurves site doesn't focus only on construction rigidity,
and it doesn't discount Brainpool on account of rigidity in its
construction.  SafeCurves also covers other issues.  SafeCurves
declares Brainpool curves not safe according to the following
criteria:

 - feasibility of efficient constant-time implementation
   http://safecurves.cr.yp.to/ladder.html

 - twist security
   http://safecurves.cr.yp.to/twist.html

   IIUC this means that when using non-twist secure curves one has to
validate that peers' public keys are on the curve being used, which in
turn would require exchanging not just public keys but also Schnorr
signatures (and, of course, verifying those signatures before using
peers' public keys for any other purpose).

 - completeness
   http://safecurves.cr.yp.to/complete.html

   This is an argument that's purely about implementation complexity
and performance.  I'm not sure how concerned to be about this -- less
than about the previous two concerns above, no doubt.

 - indistinguishability of public key values from random
   http://safecurves.cr.yp.to/ind.html

   No EC curve has this.  But for some curves one can construct a
mapping between any point and some small set of non-points all of
which can then be mapped right back into the original.  And such a
mappings can be made constant-time in the case of the three given safe
curves.  But no such mappings are known for the other curves
(including Brainpool).

   This is primarily a problem for protocols aiming for privacy
protection and for some ZKPPs (e.g., EKE) (but not for, say, J-PAKE,
which, incidentally, uses Schnorr signatures to verify public key
validity).

Nico
--

---

From: Michael D'Errico <[email-masked]>
Date: Wed, 16 Oct 2013 10:02:30 -0700

Johannes Merkle wrote:
> 
> sqrt(2) and sqrt(3) are much less fundamental than Pi or e. If you
> ask mathematicians for the most fundamental constants, you will get
> 1, Pi, e, i, and maybe 2.
> 

Well, they are all related to each other as 1 - e^(i * Pi) = 2 so you
can omit one of them.  :-)

Mike

---

From: Anders Rundgren <[email-masked]>
Date: Wed, 16 Oct 2013 19:43:06 +0200

Brainpool just hit another protocol:

http://webpki.org/papers/keygen2/keygen2.junit.run.html#ProvisioningInitializationRequest.BrainpoolOption.1

anders

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 17 Oct 2013 10:59:59 +0200

>    http://safecurves.cr.yp.to/twist.html

These properties are clearly beneficial to secure implementations against side-channels and active attacks. But you can
still achieve this resistance with other curves. The approach of Brainpool was different; we gave clear hints to the
necessity of implementation security but left the details completely to the implementors.

> peers' public keys for any other purpose).

Although I am familiar with Schnorr signatures, I don't understand how they should be used for point validation.

Typically, you need to check that the public key satisfies the curve equation. For IKE, there was an RFC published on
how to do this during key agreement.

If you receive a compressed key, it suffices to uncompress the key; if successful, the resulting point is on the curve.

Johannes

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Oct 2013 10:55:10 -0500

> necessity of implementation security but left the details completely to the implementors.

I would say that providing hints as to how to implement in constant
time >> providing hints that implementations should be constant-time.
Everyone knows the latter.  Not everyone knows how to achieve that.

> If you receive a compressed key, it suffices to uncompress the key; if successful, the resulting point is on the curve.

Yeah, that was a thinko; please excuse me.  Validating that the point
is on the curve was the point.  The fact that some curve has twist
security means that for DH there's no need to validate that public
keys are points on the curve -- i.e., all other things being equal,
such a curve is faster than a curve that doesn't have this feature.
Faster is important.

Nico
--

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 17 Oct 2013 18:25:15 +0200

On 17/10/2013 17:55, Nico Williams wrote:
> The fact that some curve has twist
> keys are points on the curve

Not if your peer sends you (x, y). Your statement is true only in ECDH schemes
where the peers sends only x (and you don't attempt to find y).

Manuel.

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Oct 2013 11:40:39 -0500

> where the peers sends only x (and you don't attempt to find y).

Fair enough, but as the subject was Brainpool vs. Curve25519...

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 18 Oct 2013 09:22:09 +0200

> Fair enough, but as the subject was Brainpool vs. Curve25519...

If I may reformulate my point: twist-security is relevant only for curves
suitable for use with schemes where only the x coordinate is transmitted, and no
attempt to reconstruct y is needed on the receiving side. Which means, curves
for which formulas exist for point multiplication using only the x coordinate.
To the best of my knowledge (read: after looking up the explicit formulas
database) no such formulas exist for short Weierstrass curves. Let's try with
pseudo-code:

If (has efficient x-only formulas)
	may transmit only x, and if doing so:
		if (is twist-secure)
			no need to validate x
		else
			need to validate x
else
	need to transmit or reconstruct y, so:
	if (y transmitted entirely)
		need to validate (x,y) explicitly
	else
		(x,y) implicitly validated while reconstructing y

As you can see, twist-security is irrelevant in the second branch, to which
short-Weierstrass curves (which can't be transformed to Montgomery form, such as
Brainpool curves) belong unless some magical x-only formulas are discovered.

So you may argue that Curve25519 has performance-without-sacrificing-security
advantages for DH over Brainpool curves and I certainly won't contradict you on
that point, but citing twist security as relevant here would be putting the cart
before the horse IMO.

Manuel.

PS: just kidding (almost?), but one could argue that brainpoolP384r1, as used in
TLS for ECDH now, is *less* secure because of twist-security, if people start
thinking that they don't need to validate public keys for this curve...

---

From: Watson Ladd <[email-masked]>
Date: Fri, 18 Oct 2013 08:35:31 -0700

> database) no such formulas exist for short Weierstrass curves. Let's try with
This isn't true: See Brier-Joye ladders. They aren't used because of
efficency problems, but they
solve the incompleteness issues.
> thinking that they don't need to validate public keys for this curve...
Invalid curve attacks mean validation on short Weierstraß curves is
always required.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Fri, 18 Oct 2013 18:30:46 +0200

> solve the incompleteness issues.

I stand corrected, I wasn't previously aware of these formulas and missed them
when I checked the EFD page. Thanks for bringing them to my attention.

>> If (has efficient x-only formulas)

Anyway, since I took care to add "efficient" here, this doesn't change the
evaluation of this condition...

> Invalid curve attacks mean validation on short Weierstraß curves is

Which was precisely my point: people should *not* start thinking validation
isn't required (regardless of whether the curve is twist-secure or not), when
they are receiving an (x,y) pair. I'm sorry if that wasn't clear enough from my
messages, I really thought it was.

Manuel.