Subject: Re: [Cfrg] Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 2 Mar 2015 16:28:43 +0200

On Wed, Feb 25, 2015 at 02:27:58PM +0000, Alexey Melnikov wrote:
> CFRG chairs are starting another poll:
> 
> Q3: This is a Quaker poll (please answer one of "preferred", "acceptable" or
> "no") for each curve specified below:

Considering entiere space for high-security curve...
 
> 1) 448 (Goldilocks)

Prefer (high-performance curve with well-characterized performance
characteristics, easy to construct signatures).

> 2) 480

No (bad performance on 32-bit[1], marginal with signatures)

> 3) 521

No (too slow and large for signatures, uncertain security benefits[2]).

> 4) other curve (please name another curve that you "prefer" or "accept", or
> state "no")

p=2^414-17  (accept[3])

[1] This is in contrast to stellar performance at 64-bit. And 32-bit
performance still looks to matter (mobile, which is already loaded and
slow!)

[2] The rho complexities are so high that I think it is meaningless to
compare those. Basically, I think that is reasonably likely that anything
that can break any one of these curves can break them all (especially at
WF200+)[4].

[3] There have been decent amount of performance characterization of this
prime, even if there is no good software available. It is WF200+ too.

[4] Some examples:

1) Major advances to ECC cryptoanalysis (no telling what that does to
   ECC)
2) Large quantum computers (totally breaks ECC).
3) Fundamential physics breakthroughs allowing far surpassing current
   theoretical limits (no telling what that does to computational
   capability; however I think this is less likely than large QC).

-Ilari

---

From: David Leon Gil <[email-masked]>
Date: Tue, 3 Mar 2015 17:59:12 -0800

This seems to be about primes, not curves. My comments w.r.t. primes:

448: Preferred. Superb performance, reasonably easy to implement
arithmetic in the field safely.

480, 512, 521: No, no, and no.

--

I actually quite like M521. Mersenne arithmetic is fast when
implemented by experts. And yet it is possible even for a bright
ten-year-old to implement Mersenne multiplication correctly using full
reduction.

--

>> "no") for each curve specified below:

Finally: I take strong exception to the design of this poll.

I cannot see any explanation for the voting method other than that the
chairs are attempting to force the selection of M521 by sleight of
hand. M521 is generally unobjectionable -- only a hard-liner on speed
or 64-byte alignment could reasonably not select it as either
"Acceptable" or "Preferred".

Therefore I must be unreasonable: No, no, and no.

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 3 Mar 2015 18:24:55 -0800

On Wed, Feb 25, 2015 at 8:22 AM, Phillip Hallam-Baker
<[email-masked]> wrote:
> Do we have figures for performance of these versus RSA2048?
>
> Yes, we get a reversal of the public/private speed advantage on signature.
> And that in itself is a huge win on the server side
>
> RSA signature verification takes 0.16 ms on a reasonably current machine
> (signature is 6ms)
>
> http://www.cryptopp.com/benchmarks.html
>
> How much faster/slower one curve is over another matters much less to me
> than whether the curve is faster or slower than what I am already using. I
> am not going to be using P521 or P448 curves on a constrained device, I will
> go for P255.
>
> If we had figures comparing the curve candidates to RSA it would probably be
> illuminating.

It seems to me that, if you're currently using RSA 2048, then you
might as well just use Curve25519.  A higher security margin curve
would be a replacement for RSA 4096 or even larger, I imagine.

--Andy

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 3 Mar 2015 19:20:06 -0800

If it's not too late, I'd like to "update" my vote from the previous round.
I think this is effectively how you might interpret it anyway, but I can
perhaps state it more clearly:

448 - Preferred
480 - No
521 - Accept

On Wed, Feb 25, 2015 at 6:27 AM, Alexey Melnikov <[email-masked]>
wrote:

> Q3: This is a Quaker poll (please answer one of "preferred", "acceptable"
> or "no") for each curve specified below:
>
> 1) 448 (Goldilocks)
> 2) 480
> 3) 521
> 4) other curve (please name another curve that you "prefer" or "accept",
> or state "no")
>
> If you stated your curve preferences in the poll that ended on February
> 23rd (see the attachment), you don't need to reply to this poll, your
> opinion is already recorded. But please double check what chairs recorded
> (see the attachment).
>
> If you changed your mind or only answered the question about performance
> versa memory usage for curves 512 and 521, feel free to reply.
>
> Once this issues is settled, we will be discussing (in no particular
> order. Chairs reserve the right to add additional questions) implementation
> specifics and coordinate systems for Diffie-Hellman. We will then make
> decisions on signature schemes. Please don't discuss any of these future
> topics at this time.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>

-- 
Tony Arcieri

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 03 Mar 2015 22:11:40 -0800

On 02/25/2015 06:27 AM, Alexey Melnikov wrote:
>
> Q3: This is a Quaker poll (please answer one of "preferred",
> "acceptable" or "no") for each curve specified below:
>
> 1) 448 (Goldilocks)
preferred

acceptable (preferred #2)

acceptable (care less)

> 4) other curve (please name another curve that you "prefer" or "accept",
No. ( Choices by others may be acceptable to me. )

---

From: David Gil <[email-masked]>
Date: Tue, 3 Mar 2015 22:39:39 -0800

Actually, I'll add a prime to my preferred list, as it offers a meaningfully higher level of security than Ed448: 2^607-1

Taking typical non-tight reductions, this gives ~ 256-bit security.

At Mar 3, 2015, 10:12:12 PM, Andrey Jivsov<[email-masked]'> wrote:
preferred

acceptable (care less)

---

From: Benjamin Beurdouche <[email-masked]>
Date: Wed, 4 Mar 2015 09:40:36 +0100

Hi,

> On 25 Feb 2015, at 15:27, Alexey Melnikov <[email-masked]> wrote:
> 
> Q3: This is a Quaker poll (please answer one of "preferred", "acceptable" or "no") for each curve specified below:
> 
> 1) 448 (Goldilocks)

Preferred

Acceptable

Acceptable

> 4) other curve (please name another curve that you "prefer" or "accept", or state "no")

Curve 25519 & Ed-448 Goldilocks preferred, 
No strong opinion yet on others..

Cheers,
B.

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 05 Mar 2015 23:11:45 +0000

> 4) other curve (please name another curve that you "prefer" or 
Thank you for all responses.

521 - 6 preferred, 14 - acceptable
448 - 16 preferred, 4 - acceptable

Very few prefer others (512 NUMS, 480).

So CFRG prefers curve 448.
>
> If you stated your curve preferences in the poll that ended on 
> February 23rd (see the attachment), you don't need to reply to this 
> poll, your opinion is already recorded. But please double check what 
> chairs recorded (see the attachment).
>
> If you changed your mind or only answered the question about 
> performance versa memory usage for curves 512 and 521, feel free to 
> reply.
>
> order. Chairs reserve the right to add additional questions) 
> implementation specifics and coordinate systems for Diffie-Hellman. We 
> will then make decisions on signature schemes. Please don't discuss 
> any of these future topics at this time.

---

From: Benjamin Black <[email-masked]>
Date: Thu, 5 Mar 2015 15:22:38 -0800

What happened to the earlier, vigorous arguments by Robert Ransom, Alyssa
Rowan and Mike Hamburg that Goldilocks448, and perhaps all of the curves
based on large primes, would be covered by Microsoft IP?

---

From: Watson Ladd <[email-masked]>
Date: Thu, 5 Mar 2015 15:41:01 -0800

Were these the arguments made? Or was it that the particular algorithms
discussed by Microsoft in March were patented?

I don't recall any argument of the first form. Perhaps you can provide a
link to am email, or a patent number. But I do recall the second.

Sincerely,
Watson Ladd
>>> If you changed your mind or only answered the question about
performance versa memory usage for curves 512 and 521, feel free to reply.

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 5 Mar 2015 15:41:30 -0800

Hi Benjamin,

Robert Ransom was concerned about Microsoft’s paper and code release possibly containing material based on the patent US7602907.  This wasn’t particularly to do with the curve, but with the combs algorithm for fast fixed-point multiplications.  If this is a problem with any curve, it’s equally a problem for (implementations of) every curve.  I believe that Robert was motivated in this pursuit by a deep-seated conviction that Microsoft was trying to pull something shady, but Alyssa and I just want to make sure that the patent landscape is clear so that nobody infringes by accident.

Since my code uses signed all-bits set combs, and if I understand correctly your patent specifically covers modified LSB-set combs, I don’t believe that my implementation has patent problems.  Again, this is a property of the implementation and not of the curve.

I asked if you and/or the Microsoft legal team concurred with this analysis.  You said that your team was unaware of the patent and didn’t use it intentionally, but that you would ask legal if it happened to be covered, and whether they thought the Goldilocks code might be affected.  Nearly 6 months have passed and we haven’t heard anything from legal.  Do you have an update for us?

Cheers,
— Mike

> On Mar 5, 2015, at 3:22 PM, Benjamin Black <[email-masked]> wrote:
> 
> What happened to the earlier, vigorous arguments by Robert Ransom, Alyssa Rowan and Mike Hamburg that Goldilocks448, and perhaps all of the curves based on large primes, would be covered by Microsoft IP?
> 
> On Thu, Mar 5, 2015 at 3:11 PM, Alexey Melnikov <[email-masked] <mailto:[email-masked]>> wrote:
> If you stated your curve preferences in the poll that ended on February 23rd (see the attachment), you don't need to reply to this poll, your opinion is already recorded. But please double check what chairs recorded (see the attachment).
> 
> If you changed your mind or only answered the question about performance versa memory usage for curves 512 and 521, feel free to reply.
> 
> Once this issues is settled, we will be discussing (in no particular order. Chairs reserve the right to add additional questions) implementation specifics and coordinate systems for Diffie-Hellman. We will then make decisions on signature schemes. Please don't discuss any of these future topics at this time.
> 
> [email-masked] <mailto:[email-masked]>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>
>

---

From: Benjamin Black <[email-masked]>
Date: Thu, 5 Mar 2015 15:54:30 -0800

As you say, it would be equally a problem for every curve, which was my
argument repeatedly rejected by Alyssa and Robert. As they have never made
a statement, public or private, of which I am aware withdrawing their
assertions, I can only assume they still believe what they said. If they
would like to pipe up and explain that they no longer hold those views
that'd be swell.

I cannot comment on Microsoft as I am no longer there.

On Thu, Mar 5, 2015 at 3:41 PM, Michael Hamburg <[email-masked]> wrote:

> Hi Benjamin,
>
> Robert Ransom was concerned about Microsoft’s paper and code release
> possibly containing material based on the patent US7602907.  This wasn’t
> particularly to do with the curve, but with the combs algorithm for fast
> fixed-point multiplications.  If this is a problem with any curve, it’s
> equally a problem for (implementations of) every curve.  I believe that
> Robert was motivated in this pursuit by a deep-seated conviction that
> Microsoft was trying to pull something shady, but Alyssa and I just want to
> make sure that the patent landscape is clear so that nobody infringes by
> accident.
>
> Since my code uses signed all-bits set combs, and if I understand
> correctly your patent specifically covers modified LSB-set combs, I don’t
> believe that my implementation has patent problems.  Again, this is a
> property of the implementation and not of the curve.
>
> I asked if you and/or the Microsoft legal team concurred with this
> analysis.  You said that your team was unaware of the patent and didn’t use
> it intentionally, but that you would ask legal if it happened to be
> covered, and whether they thought the Goldilocks code might be affected.
> Nearly 6 months have passed and we haven’t heard anything from legal.  Do
> you have an update for us?
>
> Cheers,
> — Mike
>
> On Thu, Mar 5, 2015 at 3:11 PM, Alexey Melnikov <[email-masked]
> > wrote:
>

---

From: Benjamin Black <[email-masked]>
Date: Thu, 5 Mar 2015 15:56:30 -0800

The arguments were suggested on the list, but made explicitly in private
communication. I do not feel comfortable making private communication
public, though I understand this puts me in the minority.

On Thu, Mar 5, 2015 at 3:41 PM, Watson Ladd <[email-masked]> wrote:

> > What happened to the earlier, vigorous arguments by Robert Ransom,
> Alyssa Rowan and Mike Hamburg that Goldilocks448, and perhaps all of the
> curves based on large primes, would be covered by Microsoft IP?
>
> > On Thu, Mar 5, 2015 at 3:11 PM, Alexey Melnikov <
> [email-masked]> wrote:
> >>
> February 23rd (see the attachment), you don't need to reply to this poll,
> your opinion is already recorded. But please double check what chairs
> recorded (see the attachment).
> >>>

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 06 Mar 2015 01:41:14 +0000

> [BB] What happened to the earlier, vigorous arguments by Robert 
> Ransom, Alyssa Rowan and Mike Hamburg that Goldilocks448, and 
> perhaps all of the curves based on large primes, would be covered 
> by Microsoft IP?

I don't recall saying that. Perhaps you misunderstood?

> [MH] …Alyssa and I just want to make sure that the patent
> landscape is clear so that nobody infringes by accident.

Mike is correct. It wasn't the curves in the (now-expired) NUMS draft
that concerned me, but that we might've chosen curves based on
benchmarked reference implementations covered by undisclosed patents. It
would have been a problem if the only elegant implementations of the
curves we'd picked were patented. Fortunately, that is not the case!

> [MH] Since my code uses signed all-bits set combs, and if I 
> understand correctly your patent specifically covers modified 
> LSB-set combs, I don’t believe that my implementation has patent 
> problems. Again, this is a property of the implementation and not 
> of the curve.

The advice I have received matches Mike's (and my) interpretation -
I don't think Ed448-Goldilocks (the curve or reference implementation)
has any IPR problems (although I obviously cannot make any warranties or
guarantees!).

>> [MH] Nearly 6 months have passed and we haven’t heard anything 
>> from legal. Do you have an update for us?
> [BB] I cannot comment on Microsoft as I am no longer there.

Noted.

Perhaps the other co-authors of the (expired) NUMS draft could?

- -- 
/akr

---

From: Benjamin Black <[email-masked]>
Date: Thu, 5 Mar 2015 18:54:27 -0800

There are only two possibilities:

1) The combs in the reference implementations of Goldilocks448 and NUMS 512
are not the same, in which case you have an existence proof of there being
multiple techniques to achieve high performance and there never was a
legitimate IPR concern.
2) The combs in the reference implementations of Goldilocks448 and NUMS 512
are the same, in which case you have the IPR concern express previously.

Which is it?

On Thu, Mar 5, 2015 at 5:41 PM, Alyssa Rowan <[email-masked]> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJU+QWNAAoJEOyEjtkWi2t6FMAP/RquQAG8gsziWlEpJdokNU/K
> 8fU93nyF9N+mECT4uV7wyzEhwSWPI4/VF1Uqu8zzMSlLj9qjye6XrCDU0XLMLcYr
> jdQT9fhGEQc0w+WnLnmJNhKfGJfeSlLznu+ohlNdMFNmgecHsNOpdP95g4IJnITh
> k6WwwaBZoNoqi4dAZSsy62XGteAu6YrecG8HuU82aUKw8YC+5TvTNnDIgNKfUCqt
> 0y3DBWl8XEvo0o1PCpD7hp2nodWnNuBJTx9W4i2yDWqzzNSLJcYFPG1/ewI4Q8vS
> rv76EaFbchu9f/qbza/Yu6I5Ngg2u/MdUyDUa6JmvCnDiJrso0T62hfx1fLmAKrW
> Ia3t0nFw0bKxkHhNbC9Mlzp0s+ROZLvnSM9x4nxlN2ZAPhnzT0SOC24/fWVqtntu
> NU7rADaJ35H5d9Up91yhCmUlFdxzt/JeVPi84xUUYvKmNY4LFiqIZiYbzCwhTVmd
> c+wJChZXAmW7isqveqylEjXpf21LKDGPJyRFiiMX3gwmjKSbn0+L2ZkQoY+mZ2sK
> xdVa9tjbgtWASAO6w+I/kxSMCXWvmvCMKvog+/RnKxz9xOqRjxytOSFpCOYpjQ1r
> FYth11iakCwkPPIQBcZ6/m8G1DpKiF1XctOUyw9/HMoo7l0I0NKFmGpYU/5NIWlD
> Q37S6dr3bFx5qRl1W15J
> =lDFt
> -----END PGP SIGNATURE-----
>

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 05 Mar 2015 20:54:51 -0800

On 03/05/2015 06:54 PM, Benjamin Black wrote:
> 1) The combs in the reference implementations of Goldilocks448 and 
> NUMS 512 are not the same, in which case you have an existence proof 
> of there being multiple techniques to achieve high performance and 
> there never was a legitimate IPR concern.
> 2) The combs in the reference implementations of Goldilocks448 and 
> NUMS 512 are the same, in which case you have the IPR concern express 
> previously.
>
> Which is it?

Hi Benjamin,

The combs are different (SABS vs mLSBS), but it does not follow that 
there was no IPR
concern.  The '907 patent could have covered SABS in addition to mLSBS, 
or some
other patent could have read on either or both, or I could have misread 
your code and it
wasn't doing anything patented, etc.

I said in my second public email on the subject -- the one in which I 
apologized for rashly
drafting the first an hour and a half earlier --

"""
I expect (though I am not sure) that any patents that may turn up will 
not affect which
curves should be chosen, either because they can be worked around or 
because they
apply equally to all curves.  However, it is likely that patents will 
influence protocols and
internal algorithms, and perhaps also things coordinate choice or point 
encoding.
Conceivably the result could be relevant to the Montgomery vs Edwards 
discussion,
particularly if there is no IPR-free version of the comb algorithm.
"""

Again, the '907 issue was not about curve choice, at least not for me.

Cheers,
-- Mike

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 06 Mar 2015 07:58:45 +0000

On 06/03/2015 02:54, Benjamin Black wrote:
> There are only two possibilities: […] Which is it?

Ah, you misunderstood. Let me clarify my thought process for you:

• mLSB and SABS combs are different comb techniques.
  - mLSB is (I believe, based on advice given to me) patented.
  - SABS is (I believe, based on advice given to me) clear.

• The NUMS proposal used/referenced mLSB in ECCLib and the paper.
  - It didn't mention the mLSB patent, so we didn't know.
  - You claimed you didn't know either.

• You said ECClib passed MS's legal review for Apache2 licence release.
  - Apache2 [paraph.] (conditionally) grants for that Work/Contribution.
    · Anyone but MS releasing ECClib → trouble?
  - Apache2 is incompatible with, for example, GPLv2 (e.g. Linux!)
    · Anyone reusing ECClib's mLSB design, but not ECClib? → trouble?
  - We didn't know about the patent, so that could have been disastrous.
    · I don't want any trouble. [insert Jackie Chan meme here]

• However, thanks to Mike (& Robert etc), we know about it now.
  - Curve25519 reference implementation & draft doesn't use combs.
  - And Ed448-Goldilocks reference implementation uses SABS combs.
  - So, we no longer have a problem. I consider it a closed issue.

I hope that clears things up and we can move on.

- -- 
/akr

---

From: Benjamin Black <[email-masked]>
Date: Fri, 6 Mar 2015 00:32:52 -0800

You repeatedly insisted (based on advice given to you?) I "prove" there
were other techniques by which the sort of curves being discussed here. I
explained repeatedly that all these alternative implementations of similar
curves meant that either all of them were infringing, in which case there
couldn't be some nefarious plot to patent troll as everyone would already
be infringing, or they were existence proofs of non-infringing techniques.
Neither of those leaves any room for Microsoft patent trolling, which is
what you insinuated (based on advice given to you?) we were doing and
Robert stated outright.

What is clear is there was never an IP problem and the facts (based on
advice given to you?) support exactly what I said from the start. You
helped manufacture (based on advice given to you?) this issue and
participated in baseless, inappropriate and personal maligning of me and
others from Microsoft. CFRG, IETF and the people who rely on the output of
these processes deserve better. Good day.

On Thu, Mar 5, 2015 at 11:58 PM, Alyssa Rowan <[email-masked]> wrote:

> iQIcBAEBCgAGBQJU+V4sAAoJEOyEjtkWi2t6f0IP/iu5x3DkeghGqE8GJ7Y9OJIq
> +z/KfP5g80JnShEFfsvfoX9MoNaJA5LlWxsR3NFXxJHcI1qwvsXIUvHuL3GBsWgT
> jvRgJwZSkUpdD1Y50IPeo1ZAliLJ6SU8wlrEvgGEt3ZsYNM7L/SaBLpTB8X+oNl9
> CNp9NyWO2PSTbHrseQl1JWpZj4JbonevVDK2amheq5atzkQnkOd3bcvOA3FQp9zS
> 7jwuTZyFWzyCgI3JNBF2IAEzV9l8wl1O/MbvQlrjcPkGWIQCHVM45ZTUHBN+T+PL
> SBo/MX85LD+eckOV9L+hS8+uF9q6v9M4DTyiuumB2A+wX+DF98/6tz1kPEDUN0Vf
> R5PMIbb05Q4LpwLVo4WAX9iyALuLah4cmaX15MWvQmZF4YqcCaBqzWgIvQyBhfkl
> 2IQQqfsQp/OYC0XyDoWNJjs/sD0JCxccSIkH0hRjPdOg2K6htZVq3cPfoMSh37C/
> SMP6x9pWmkVz8cZKZd4CarfwOws463mID9qG5pVIjioWCCadUI71wOasHN8eg6dp
> X4utBrKuZLpwAfa4u8CHZf3fGUfkY3wvErBtBjkNCCa1cCq5EMqkyaBNwja6iWxp
> aCvudkPpifrjPcJwIDdfAuWsUd8PDzprg41hCK+h+jwdW5QjQDK+GgK15+Zjf/8I
> f9T8DWnJ6A+M/5In2oLq
> =4KTO

---

From: Benjamin Black <[email-masked]>
Date: Fri, 6 Mar 2015 00:40:28 -0800

I have always agreed and continue to agree that the IP question is
unrelated to curve choice. Thank you for the apology.

On Thu, Mar 5, 2015 at 8:54 PM, Mike Hamburg <[email-masked]> wrote:

>> 1) The combs in the reference implementations of Goldilocks448 and NUMS
>> 512 are not the same, in which case you have an existence proof of there
>> being multiple techniques to achieve high performance and there never was a
>> legitimate IPR concern.
>> 2) The combs in the reference implementations of Goldilocks448 and NUMS
>> 512 are the same, in which case you have the IPR concern express previously.
>>
>> Which is it?
>>
>
> Hi Benjamin,
>
> The combs are different (SABS vs mLSBS), but it does not follow that there
> was no IPR
> concern.  The '907 patent could have covered SABS in addition to mLSBS, or
> some
> I expect (though I am not sure) that any patents that may turn up will not
> affect which