Subject: [Cfrg] FourQ draft now available

From: Watson Ladd <[email-masked]>
Date: Thu, 22 Sep 2016 07:05:31 -0700

Dear CFRG,

We would like to announce draft-ladd-cfrg-4q-00, which presents a
high-speed Diffie-Hellman key agreement based on the elliptic curve
FourQ. This scheme is significantly faster than Curve25519, especially
when using endomorphisms. For example, SUPERCOP tests indicate that
one Curve25519 shared secret computation is performed in approximately
156,000 Haswell cycles; our analogous tests with FourQlib indicate
that a shared secret computation is performed in only 56,000 Haswell
cycles (i.e., 2.8 times faster). In some applications, the cost of
public-key operations remains considerable and FourQ is capable of
reducing it, particularly in embedded devices and busy servers.

We hope this draft sees its way to an RFC soon.

Sincerely,
Watson Ladd, Patrick Longa, Richard Barnes

---

From: Michael StJohns <[email-masked]>
Date: Thu, 22 Sep 2016 11:10:17 -0400

Hi -

I hesitate to be the one to say this, and I'm not above suggestive names 
myself, but could we please use a name that doesn't give the impression 
that the IETF is full of college age frat boys?  Say maybe: Q4D?  I 
understand the giggle factor of the name and the implied raised finger 
given to all other curves, but still - this will probably be more 
problem than benefit.

I'm not going to further argue one way or another on this.  But it 
needed to be at least mentioned.

Later, Mike

On 9/22/2016 10:05 AM, Watson Ladd wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 23 Sep 2016 07:17:02 +0100

On 2016-09-22 15:05, Watson Ladd, Patrick Longa & Richard Barnes wrote:

> high-speed Diffie-Hellman key agreement based on the elliptic
> curve FourQ.

Great work!

I feel a bit melancholy that this could be one of the the last non-PQ
kexes.

When does the GLV patent expire again? I seem to remember it being
raised when the paper first came out - has there been any big change
since then (patent grants, etc)? Might it be a problem for this?

I see Michael's point. I like the name anyway. It's short, memorable,
and if there *is* an IP problem, we could always bikeshed about the name
until it's gone and hope no-one has a quantum computer by then. ;)

- -- 
/akr

---

From: Hanno Böck <[email-masked]>
Date: Fri, 23 Sep 2016 08:49:27 +0200

Hi,

On Thu, 22 Sep 2016 07:05:31 -0700
Watson Ladd <[email-masked]> wrote:

> FourQ. 
[...]
> We hope this draft sees its way to an RFC soon.

I wonder if this is something that should really happen.

Having more choices of cryptographic constructions is imho not always
good. It has a cost: More code, more complexity, more stuff to analyze.
Therefore each new cryptographic primitive that gets introduced needs a
good justification. I'm not sure I see this here.

We just introduced curve25519/448 and many people are moving to them.
In the more or less far future we'll probably see movements to some kind
post quantum cryptography. So I only see a relatively small time window
where this curve will be used, therefore I'd like to see more
justification why we should standardize it.

From what I see the major advantage is that FourQ is supposed to be
faster than curve25519. On the flipside I see this:

   Implementations MUST check that input points properly decompress to
   points on the curve.  Removing such checks may result in extremely
   effective attacks.  The curve is not twist-secure: implementations
   using single coordinate ladders MUST validate points before operating
   on them.

From my limited understanding of ecc security this means we introduce a
new elliptic curve which is faster than curve25519, but much more prone
to implementation security flaws.

I'm not saying I'm strictly against standardizing this, but if it's
going to happen I'd like to see better justifications. Where do you see
that curve being used? Are there scenarios where the performance
improvements matter, as in "we would like to add crypto to X, but
curve25519-based crypto just isn't fast enough"? Do you see this
realistically to be used in TLS or other major protocols? Are there
other people on this list that have concrete plans to implement this in
their product/protocol?

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 23 Sep 2016 11:16:06 +0000

> I wonder if this is something that should really happen.

I know what you mean -- should it show up in IETF RFC's as MTI? -- and I agree with you.

I also find the name kinda childish. The rejoinder -- "he started it" -- even more so. 

--  
Senior Architect, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 23 Sep 2016 14:11:00 +0000

Bonjour,

> Le 23 sept. 2016 à 08:49, Hanno Böck <[email-masked]> a écrit :
> 

> […]

> other people on this list that have concrete plans to implement this in

Maybe that doesn’t count as a « major protocol », or even as an Internet use, but I see a potential benefit in the C-ITS domain (Cooperative Intelligent Transport Systems), where cars and infrastructure broadcast signed messages up to 10 times per second, maybe more frequently in some specific use-cases. With a 300m reception range in urban areas, that’s a lot of signed messages to check each second, with safety concerns. Current standards (IEEE 1609 and ETSI ITS) use ECDSA under NIST-P256 curve, some are pushing for Brainpool (guess who?), a few people would like to see something new but see resistance. In the corresponding working groups, cryptography is often seen as very costly (bandwidth, CPU, hardware, …), it’s good to see progress in some of these costs.

So yes, there can be a use for this curve, but maybe it’s not CFRG or IRTF’s problem.

Cordialement,
Erwann Abalea

---

From: Hanno Böck <[email-masked]>
Date: Fri, 23 Sep 2016 18:35:45 +0200

On Fri, 23 Sep 2016 14:11:00 +0000
Erwann Abalea <[email-masked]> wrote:

> Maybe that doesn’t count as a « major protocol », or even as an
> Internet use, but I see a potential benefit in the C-ITS domain
> (Cooperative Intelligent Transport Systems), where cars and
> infrastructure broadcast signed messages up to 10 times per second,
> maybe more frequently in some specific use-cases. With a 300m
> reception range in urban areas, that’s a lot of signed messages to
> check each second, with safety concerns. Current standards (IEEE 1609
> and ETSI ITS) use ECDSA under NIST-P256 curve, some are pushing for
> Brainpool (guess who?), a few people would like to see something new
> but see resistance. In the corresponding working groups, cryptography
> is often seen as very costly (bandwidth, CPU, hardware, …), it’s good
> to see progress in some of these costs.

I don't see this as a very convincing case. First of all this strikes
me as a "this may be useful for X" argument, highly speculative and
very different from a "we want to use this in X once it's standardized".

If they currently use P256 and consider switching to brainpool then
probably performance isn't their biggest concern, because it's well
known that the brainpool curves are amongst the slowest options. (I
have some guesses why brainpool is considered, but that has probably
more to do with nationalism than with technology arguments.) I also
wonder if the people who see cryptography as costly base their opinion
on real numbers or just myths (I see this a lot in the TLS space where
people often have unrealistically high ideas about the performance
costs).

Given that my trust in these industries to implement cryptography in a
careful way is limited I'd consider giving them a safer option (aka
curve25519) is probably smarter than giving them one that has
implementation pitfalls.

-- 
Hanno Böck
https://hboeck.de/

---

From: Watson Ladd <[email-masked]>
Date: Fri, 23 Sep 2016 09:46:25 -0700

> good justification. I'm not sure I see this here.

If you don't want to support it, don't do so.

> other people on this list that have concrete plans to implement this in

One of the high-profile uses of Curve25519 is in locking the disk of an
iPhone (do we have a flash compatible term for that yet). This requires a
public key operation on the receipt of any push message, which directly
impacts battery life. With IoT many more devices will have quiescent
states, until an event happens which they need to quickly process.

Realistically it could be used in TLS. Plenty of little known national
curves are. But I think a lot of applications are more demanding then TLS
on crypto performance.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Hanno Böck <[email-masked]>
Date: Sat, 24 Sep 2016 11:58:31 +0200

On Fri, 23 Sep 2016 09:46:25 -0700
Watson Ladd <[email-masked]> wrote:

> One of the high-profile uses of Curve25519 is in locking the disk of
> an iPhone (do we have a flash compatible term for that yet). This
> requires a public key operation on the receipt of any push message,
> which directly impacts battery life. With IoT many more devices will
> have quiescent states, until an event happens which they need to
> quickly process.

I can understand the Apple use case, however I wonder if this is really
an issue, would like to see numbers on that (given all the things an
iphone does I'd assume a curve25519 operation isn't really on top of
the things).
I'm much more worried about your second idea - IoT. Given the
security track record of IoT I'd rather not give them something that
they can mess up easily. Reading the FourQ draft it explicitly says
that it's not twist secure and that point checks have to be
implemented. I'd rather give them something without such pitfalls, aka
curve25519 for now.

> curves are. But I think a lot of applications are more demanding then
> TLS on crypto performance.

They are RFC'ed, but are they actually used?
This is actually more an example of the bloat things I'd like to avoid:
People put crypto in RFCs because of national pride ("we need our
German elliptic curves" - seriously, I heard that multiple times), not
because of technical arguments.

The FourQ case is different - there is a technical argument (speed),
but I still wonder if that's good enough to justify an RFC.

-- 
Hanno Böck
https://hboeck.de/

---

From: David Jacobson <[email-masked]>
Date: Sat, 24 Sep 2016 22:06:34 -0700

> but I still wonder if that's good enough to justify an RFC.
I used to work in the mobile device industry.  For a long time most 
mobile devices used 2048 bit RSA with exponent 3 because it was the 
fastest thing available to verify a signature.   Security conscious 
companies adopted 2048 bit RSA with exponent 65537 for added safety.   
So I suggest that these are the reference points for deciding whether 
FourQ has a good chance of getting traction based on performance.

I find the automotive collision avoidance case quite compelling.  It 
will be challenging to verify hundreds of messages per second.

If you are worried about crypto being done in an unsafe way (for 
example, not doing necessary checks) there is a simple fix:  Supply 
working code that is safe and decently optimized.  Sometimes "reference 
code" has truly terrible performance, and is only useful as the "other 
party" in a validation setup.  (SNOW 3G is a prime example.)

To facilitate adoption, make it easy for developers to get this 
algorithm approved by their legal department.
1.  Do whatever you can to allay fears that something might be 
patented.  Just having the basic inner algorithm unencumbered is not 
enough.  it must be the case the combination of the optimized inner 
algorithm as actually implemented and all the checks required for 
safety, i.e. everything in that supplied code, is unencumbered.  I'm 
aware that some standards bodies are constrained in what the can do 
regarding patents.  But do what you can, perhaps working outside any 
standards body.
2.  Release the code under a generous minimally-constraining license 
(e.g. BSD), or put it in the public domain.

    --David Jacobson

---

From: Watson Ladd <[email-masked]>
Date: Sun, 25 Sep 2016 09:09:31 -0700

On Sat, Sep 24, 2016 at 10:06 PM, David Jacobson
<[email-masked]> wrote:
> I used to work in the mobile device industry.  For a long time most mobile
> devices used 2048 bit RSA with exponent 3 because it was the fastest thing
> available to verify a signature.   Security conscious companies adopted 2048
> bit RSA with exponent 65537 for added safety.   So I suggest that these are
> the reference points for deciding whether FourQ has a good chance of getting
> traction based on performance.
>
> I find the automotive collision avoidance case quite compelling.  It will be
> challenging to verify hundreds of messages per second.
>
> If you are worried about crypto being done in an unsafe way (for example,
> not doing necessary checks) there is a simple fix:  Supply working code that
> is safe and decently optimized.  Sometimes "reference code" has truly
> terrible performance, and is only useful as the "other party" in a
> validation setup.  (SNOW 3G is a prime example.)
>
> To facilitate adoption, make it easy for developers to get this algorithm
> approved by their legal department.
> 1.  Do whatever you can to allay fears that something might be patented.
> Just having the basic inner algorithm unencumbered is not enough.  it must
> be the case the combination of the optimized inner algorithm as actually
> implemented and all the checks required for safety, i.e. everything in that
> supplied code, is unencumbered.  I'm aware that some standards bodies are
> constrained in what the can do regarding patents.  But do what you can,
> perhaps working outside any standards body.
> 2.  Release the code under a generous minimally-constraining license (e.g.
> BSD), or put it in the public domain.

The optimizations are patented, but not by us. Point compression
patents expired in 2008. As for the question of other patents, consult
a lawyer: there is no way to know which patents may or may not apply.

---

From: William Whyte <[email-masked]>
Date: Sun, 25 Sep 2016 18:15:26 +0200

Hi all,

> I find the automotive collision avoidance case quite compelling.  It will
be challenging to verify hundreds of messages per second.

V2V applications are unlikely to change from NIST p256 / Brainpool r256 at
this point.

Cheers,

William

On Sun, Sep 25, 2016 at 7:06 AM, David Jacobson <[email-masked]>
wrote:

> mobile devices used 2048 bit RSA with exponent 3 because it was the fastest
> thing available to verify a signature.   Security conscious companies
> adopted 2048 bit RSA with exponent 65537 for added safety.   So I suggest
> that these are the reference points for deciding whether FourQ has a good
> chance of getting traction based on performance.
>
> I find the automotive collision avoidance case quite compelling.  It will
> be challenging to verify hundreds of messages per second.
>
> not doing necessary checks) there is a simple fix:  Supply working code
> that is safe and decently optimized.  Sometimes "reference code" has truly