Subject: [Cfrg] Comparing ECC curves

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 23 Jul 2014 18:28:03 -0400

Thanks to all the presenters, some thoughts on comparing like with like:

1) How do we compare algorithm A taking X cycles and offering a work
factor 2^Y with algorithm B taking 2X cycles and offering a work
factor 2^(Y+Z)?

My answer here is that I am interested in the yield ratio i.e.
[attacker work factor] / [defender effort]. so having the defender do
twice as much work to get an improvement of one bit is not a win.

We can define an exclusion rule: B, is definitely not going to be
interesting as an alternative to A if Z >= 1. Doubling the work factor
is not a win if I have to do twice as much work.

But that still leaves open the question of how much defender effort it
is worth to increase the difficulty by a factor of two.

2) Should the security levels be maximums or minimums?

Looking through the Microsoft presentation I see that they have chosen
work factors of 128, 192 and 256 bits. This is reasonable of course
but maybe not the best way to compare like with like. Because the real
limitations here are the machine resources which nowadays come in
units of 64 bits.

What I am really interested in is how much security you can provide
for an n*64 bits wide datapath. I do not want to have to mess about
with a129 bits to achieve 128 bits security. If someone can do the
math significantly faster then I'll take 127 bits. But I certainly
don't want to go below 120 bits unless the advantages were phenomenal.

3) Do we need to consider 2^192 work factor?

I can't see any case where I am interested in a work factor of 2^192.
Either I am willing to make some concession to performance or I want
it gold plated and 2^256. I would quite like to see the 2^192 work
factor nuked.

The only reason for going above 2^128 is that I don't trust the
algorithm. Its not about increasing the work factor by 2^64, its about
increasing the safety margin in the case of a cryptanalytic attack. I
have seen attacks that reduce the work factor to the root of the
intended one (i.e. 2^n becomes 2^(n/2)). I can't think of a better one
that has been discovered offhand (most are not that good of course).
So 2^256 makes me feel like I am sufficiently protected against
algorithm compromise while 2^192 is kinda marginal.

---

From: Benjamin Black <[email-masked]>
Date: Wed, 23 Jul 2014 15:33:49 -0700

On Wed, Jul 23, 2014 at 3:28 PM, Phillip Hallam-Baker <[email-masked]
> wrote:

> it gold plated and 2^256. I would quite like to see the 2^192 work
Phillip,

This was our conclusion, as well. If you haven't seen it, here's the NUMS
TLS draft which only specifies the twisted Edwards curves at 128 and 256
bit security levels:
http://tools.ietf.org/id/draft-black-tls-numscurves-00.txt

Ben

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 23 Jul 2014 16:07:06 -0700

Hi Phillip,

This has also been discussed on the [email-masked] list.  Trevor Perrin and I have discussed roughly the following:

There’s nothing magical about 128, 192 or 256-bit security levels.  We are hedging against improvements in the math of attacking ECC, not against specific levels of improved compute power.  So other things being equal, a bigger group order is better, but the question is how big a group order (and thus how good a hedge) can be bought for a given performance budget.  DJB has also advanced this argument in favor of Curve41417, and I’ve advanced it in favor of Ed448-Goldilocks.

Obviously we want only a few curves of fairly different security levels, so something aimed at 2^160 work isn’t interesting.  We should pay attention to which curves are efficient, i.e. attain the best security level compared to their performance.  Ideally, it would be best to select only two new curves instead of three, i.e. a 128-ish-bit secure one and a much stronger one.

Since Karatsuba multiplication is suitable for the curves in question, we should expect EC software to take time proportional to T(group size) := log(group size) ^ (1 + log 3 / log 2) time.  So a simple benchmark would be that, other things being equal, we should look especially closely at curves where T(group size) / (time for ECDH or sign or verify) is largest.  Obviously this will vary by platform and implementation, but it seems like a reasonable benchmark between security levels.

For example, on Intel Sandy Bridge, Microsoft’s Ed-384-mers takes 617kcy to compute a shared secret (not counting decompression).  Ed448-Goldilocks takes 674kcy (counting decompression) and Ed-512-mers takes 1293kcy (not counting decompression).  So their “efficiency” scores on that platform are roughly 7.7, 10.5, and 7.7 respectively.

This is why Trevor and I (and perhaps also DJB?) believe that a fast, ordinary-security curve like Curve25519 and a high-security curve like Goldilocks or Curve41417 would be a good pair of alternatives in future deployments.

Cheers,
— Mike

On Jul 23, 2014, at 3:28 PM, Phillip Hallam-Baker <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 23 Jul 2014 19:17:02 -0400

On Wed, Jul 23, 2014 at 6:33 PM, Benjamin Black <[email-masked]> wrote:
> On Wed, Jul 23, 2014 at 3:28 PM, Phillip Hallam-Baker
> <[email-masked]> wrote:
>>
>>
> TLS draft which only specifies the twisted Edwards curves at 128 and 256 bit
> security levels: http://tools.ietf.org/id/draft-black-tls-numscurves-00.txt

Just trying to push back on the idea we need the options .. :-)

Similarly, I am not interested in a set of curves that is
hyperoptimized for TLS and can't be used for S/MIME. When we were
discussing random curves, changing the curve was pretty much the same
as changing the key. Now that we are doing the close to powers of 2
curves with highly optimized code, changing the curve is like changing
to a whole new algorithm.

As far as the code is concerned it is better to think about them as
choosing between ECDHE-25519 and ECDHE-256p rather than ECDHE with a
named curve. Changing the curve is going to select a different
implementation.

The end product I want from this is a set of backup public key
algorithms that can be made a RECOMMENDED algorithm with a view to
making them a MUST algorithm replacing RSA-2048 at some point in the
future. I want to encourage dedicated hardware support, etc. etc.

This means that I really don't want TLS to go and choose something
that is going to fail if we try to apply it to S/MIME or PGP. We can
use DH for email encryption but only one of the keys can be ephemeral.
The recipient key is going to have to be static.

I would suggest as a way forward here we look at the protocol
requirements for TLS, PKIX and S/MIME as they represent the two poles
of protocol design. I would be rather surprised to find IPSEC, SSH
etc. to have dramatically different requirements to TLS. S/MIME and
PGP on the other had are store and forward which makes them very
different beasts. I would also separate out TLS and PKIX because one
is a single protocol and the other is infrastructure.

[DNSSEC does actually have a different requirement from PKIX, data
size, but that is probably not going to be a deciding factor between
curves]

It would clearly be nuts for the IETF to choose a curve that does not
work well for TLS. But I don't see the differences between the curves
on TLS being so great that we should accept a curve that we can't use
in every reasonable protocol.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 23 Jul 2014 18:10:40 -0700

> future. I want to encourage dedicated hardware support, etc. etc.

Why will that happen with these curves when it didn't with the NIST
curves vs. RSA?
Yes, I'm aware of patent issues that used to exist, but this was an
unforced error in
standardization: RSA is of a similar vintage.

> The recipient key is going to have to be static.

Not being at IETF 90 I can't comment on the standardization, but I
certainly can comment
on the cryptography. All protocols use ECDH and signatures, and any
twisted Edwards curve
will work for both. The only debate is how to represent points for
ECDH, which exact prime to use,
and the exact curve to use. There are many implemented, functioning
systems using Curve25519
and Ed25519 and friends, without any problems.

(What you propose for email encryption is in fact what ECIES does,
which is what OpenPGP does)

> size, but that is probably not going to be a deciding factor between

Point compression can dramatically shrink keys. The patent expires next Tuesday,
and Curve25519 never infringed upon it.

However, DNSSEC still uses RSA, despite ECC existing and making sizes
much smaller.

> in every reasonable protocol.

That won't happen.

Sincerely,
Watson Ladd

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

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 23 Jul 2014 22:56:26 -0400

> standardization: RSA is of a similar vintage.

Several reasons.

First off, we had this philosophy that lots of algorithm choices was a
good thing. It is only recently that it is generally acknowledged that
adding stronger algorithms does not improve security. Only stopping
using weak algorithms helps matters.

So back in the mid 90s we had dozens of symmetric ciphers and RSA and
DSA and DH and it was thought to be a good thing. Then we got the idea
that there should be as few algorithms as possible, preferably one
good one. And now I am pushing for a scheme where we have one REQUIRED
and one RECOMMENDED per type of algorithm and make no other
recommendations except in unusual circumstances where a legacy
transition is in progress.

The main reason we haven't had consensus across the IETF on mandatory
to implement algorithms before is that the decisions were taken at
different times and the field moved on. So the mandatory to implement
algorithms for quite a few specs are now out of date. S/MIME requires
3DES for example. This was changed for SIP but not for mail as far as
I can see.

It is possible that some people used to enjoy algorithm discussions.
At this point I think we all realize that the discussion is necessary
but not so much fun that I want to have it repeated for each working
group.

But the main reason I want to change that practice is that when we
decided to move to AES in place of 3DES, that was a decision made
independent of any particular protocol but implementation required us
to make changes to every protocol separately. That is silly and
tedious and lots of makework for authors and the IESG.

Hence the rationale for this draft:

http://tools.ietf.org/html/draft-hallambaker-consensuscrypto-00

The idea of this is that future protocols would not make MTI choices
of algorithms, they would reference the consensus RFC and leave it at
that. If we change our idea of what necessary crypto is, the consensus
RFC would be made obsolete and replaced by a new one.

The reason for having backup algorithms is that unless we are in panic
mode (like Google starts selling a Quantum Computer just for S&G) the
pattern should be that the new REQUIRED algorithm is a previous
RECOMMENDED algorithm. Since they are backup algorithms there is a
requirement that they be constructed in a distinctly different fashion
(e.g. SHA-3 is a logical backup to SHA-2 because it is spongeworthy).
The backups also need to be distinctly stronger.

I will also note that it looks like we now have a pretty strong
primary and backup for hash functions and MACs and seem to be
approaching consensus on public key (RSA plus ECC exact scheme to be
decided). That leaves a gap for backup encryption algorithm.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 23 Jul 2014 20:50:40 -0700

> RFC would be made obsolete and replaced by a new one.

While I agree with the overall sentiment (excess agility is harmful,
we need to mandate two ciphers to
have a backup, crypto should be centralized by someone who knows what
they are doing), treating
this decision as though your draft was already ready doesn't work. In
particular this decision has to
be made assuming the status quo with regards to algorithms.

There are good reasons to have both CCM and GCM for example. A
nonce-reuse resistant protocol would
be more expensive than either, but potentially useful in cases where
protocols that fail when nonces are reused
would not be.

In particular the Great Cleanup has yet to begin: having consensus
crypto now requires reworking everything
to use it. That said, I don't think that twisted Edwards curves have
any difficulties in protocols that can negotiate
usable curves: they represent points for both signatures and ECDH.
(I do think we should compress the points: avoid nastiness).

We're going to have to change the order of encrypt then MAC in PGP
(which has no MAC), Kerberos(!),
SSH(!!), the record protocol in TLS (!!!) to get them all to be the
same. If we use AEAD it's the same issue.
Add that to the real problems of backwards compatibility and
implementation update cycles,
 and I'm not sure we can do it in a reasonable time frame.

> decided). That leaves a gap for backup encryption algorithm.

RSA is slow, requires big keys, and is usually used incorrectly in
IETF protocols:
OAEP should be be used instead of PKCS 1.5 encryption. Interesting TLS
has decided to use
DHE and ECDH, with no proposal to put RSA back on, except for
signatures (which sadly
are not PSS).

Sincerely,
Watson Ladd

---

From: Patrick Longa Pierola <[email-masked]>
Date: Thu, 24 Jul 2014 06:36:09 +0000

> Phillip Hallam-Baker wrote:
> Looking through the Microsoft presentation I see that they have chosen work factors of 128, 192 and 256 bits. This is reasonable of course but maybe not the best  
> way to compare like with like. Because the real limitations here are the machine resources which nowadays come in units of 64 bits.

> What I am really interested in is how much security you can provide for an n*64 bits wide datapath. I do not want to have to mess about with a129 bits to achieve 128
> bits security. If someone can do the math significantly faster then I'll take 127 bits. But I certainly don't want to go below 120 bits unless the advantages were
> phenomenal.

An important related point: I haven't seen any result in the literature demonstrating any meaningful performance advantage when dropping one bit from 256 to 
255 bits, or from 384 to 383, or from 512 to 511 (case of primes with the form 2^m - c). Our experiments [1] reveal that one bit less injects less than 4% of performance 
improvement. Under this light, we prefer the conservative approach: keep a traditional 2 x s bitlength, which is multiple of a computer word of 64 bits (for a bit-security
level s = {128,192,256}), maximize ECDLP security and make the curve generation process as simple and rigid as possible. This also helps to keep curve design at different
security levels consistent. And, arguably, all this together avoids some potential errors and ease the work of implementers. At the other side of the spectrum, I haven't seen
any performance advantage of increasing the prime bitlength beyond 2 x s. It is actually potentially counterproductive: in [1] we show that increasing the field
representation by one word (which happens when moving from 512 bits to 521 bits for example) degrades performance by a factor 1.2. In this case, the performance
issues make the conservative approach even more attractive, taking as a bonus all the benefits mentioned above. 

[1] http://eprint.iacr.org/2014/130.pdf    

> Either I am willing to make some concession to performance or I want it gold plated and 2^256. I would quite like to see the 2^192 work factor nuked.

> The only reason for going above 2^128 is that I don't trust the algorithm. Its not about increasing the work factor by 2^64, its about increasing the safety margin in the
> case of a cryptanalytic attack. I have seen attacks that reduce the work factor to the root of the intended one (i.e. 2^n becomes 2^(n/2)). I can't think of a better one
> So 2^256 makes me feel like I am sufficiently protected against algorithm compromise while 2^192 is kinda marginal.

Totally agreed. We should give preference to 128 and 256-bit sec levels.

Patrick

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 24 Jul 2014 09:25:53 -0400

> be made assuming the status quo with regards to algorithms.

I don't think so. The Status Quo emerged from the days when each WG
made the choice of algorithms independently. We have already decided
to only make that decision in CFRG.

The reason for pointing to the draft is that it makes the argument in
greater detail, not to suggest it was a decision already made.

We discussed the need for the draft in SECDIR and I was asked to write
it. So far, yours is the first response...

> protocols that fail when nonces are reused

There we get into protocol design and the question is whether we
should standardize on 'AES' for encryption or AES-CBC / AES-GCM, etc.

I would really like to standardize on AES-GCM going forward for new
protocols. But right now I can't use that in Windows .NET without
writing my own AES code. Hmmm.

For existing protocols written before encrypt and authenticate became
fashionable, I would not want to go back and try to retrofit use of an
E&A scheme. That would certainly not be something to do in the
consensus draft.

> to use it.

No, not at all. The idea of stating what the consensus is so that an
implementation can state that it complies with RFC-6071 and RFC-XXXX
and tell people that it will interoperate securely with
implementations that comply with either.

So if HMAC-SHA1 is specified as MTI in the base spec and
HMAC-SHA-2-256 as MTI in RFC-XXXX, then an implementation claiming to
be compliant with both would have to implement both.

What this approach does not fully address is what to do if the base
spec specifies MD5 and there is no RFC that has come out saying 'do
not use MD5'.

> same.

Order of operations is a protocol design choice, not an algorithm
choice. Funny thing is that people keep telling me that it is
absolutely vital that the order be one or the other 'because security'
but which is better changes.

Obviously the order is going to have an effect on security. But
changing it has a bigger effect on code. If people wanted consistency
at that level they would have to write drafts for each protocol to
harmonize them all. I don't see the point in that unless it is part of
the ongoing process of rewriting everything in JSON.

> DHE and ECDH, with no proposal to put RSA back on, except for

Well the PKIX stack in the WebPKI is currently limited to RSA2048 in
practice, so I don't know what that means.

The RFC cited in the draft specifies OAEP and PKCS 1.5. It should be
just OAEP. I was looking for the OAEP draft, didn't notice it also has
the PKCS 1.5.

---

From: David Jacobson <[email-masked]>
Date: Thu, 24 Jul 2014 07:26:53 -0700

On 7/23/14 11:36 PM, Patrick Longa Pierola wrote:
[snip]
> An important related point: I haven't seen any result in the 
> literature demonstrating any meaningful performance advantage when 
> dropping one bit from 256 to 255 bits, or from 384 to 383, or from 512 
> to 511 (case of primes with the form 2^m - c). Our experiments [1] 
> reveal that one bit less injects less than 4% of performance 
> improvement. Under this light, we prefer the conservative approach: 
> keep a traditional 2 x s bitlength, which is multiple of a computer 
> word of 64 bits (for a bit-security level s = {128,192,256}), maximize 
> ECDLP security and make the curve generation process as simple and 
> rigid as possible. This also helps to keep curve design at different 
> security levels consistent. And, arguably, all this together avoids 
> some potential errors and ease the work of implementers. At the other 
> side of the spectrum, I haven't seen any performance advantage of 
> increasing the prime bitlength beyond 2 x s. It is actually 
> potentially counterproductive: in [1] we show that increasing the 
> field representation by one word (which happens when moving from 512 
> bits to 521 bits for example) degrades performance by a factor 1.2. In 
> this case, the performance issues make the conservative approach even 
> more attractive, taking as a bonus all the benefits mentioned above. 
[snip]

You are addressing performance.  But what about the ease of making a 
constant time implementation?  The security value of 256 over 255 or 254 
is not much.  It is just that 256 is a nice round number, and might be a 
checkbox item.  If we can accept 255 or 254, it might make constant time 
implementations easier.   Perhaps people who have done constant time 
implementations can comment.

     --David

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 24 Jul 2014 11:11:07 -0400

On Thu, Jul 24, 2014 at 10:26 AM, David Jacobson
<[email-masked]> wrote:
>> An important related point: I haven't seen any result in the literature
>> demonstrating any meaningful performance advantage when dropping one bit
>> from 256 to 255 bits, or from 384 to 383, or from 512 to 511 (case of primes
>> with the form 2^m - c). Our experiments [1] reveal that one bit less injects
>> less than 4% of performance improvement. Under this light, we prefer the
>> conservative approach: keep a traditional 2 x s bitlength, which is multiple
>> of a computer word of 64 bits (for a bit-security level s = {128,192,256}),
>> maximize ECDLP security and make the curve generation process as simple and
>> security levels consistent. And, arguably, all this together avoids some
>> potential errors and ease the work of implementers. At the other side of the
>> spectrum, I haven't seen any performance advantage of increasing the prime
>> bitlength beyond 2 x s. It is actually potentially counterproductive: in [1]
>> we show that increasing the field representation by one word (which happens
>> when moving from 512 bits to 521 bits for example) degrades performance by a
>> factor 1.2. In this case, the performance issues make the conservative
>> approach even more attractive, taking as a bonus all the benefits mentioned
>> above. [1] http://eprint.iacr.org/2014/130.pdf
>
> [snip]
>
> constant time implementation?  The security value of 256 over 255 or 254 is
> not much.  It is just that 256 is a nice round number, and might be a

My understanding here is that DJB has a curve with 255 bits that he
claims operates a lot faster than the 256 bit alternatives. I do not
know how that affects the work factor but what I do know is that I
really don't care.

E-521 seems to have been chosen as the fastest prime giving a work
factor of at least 2^256. If someone finds a prime that gives a work
factor of 2^240 and is 30% faster, I would have to think about which I
preferred.

Comparing performance of symmetric algorithms is easier in some ways
as every strong 128 bit cipher has the exact same work factor. So we
are arguing over whether they are strong and which is faster (which
can of course be complex as it might be architecture dependent).

The problem I am trying to explore here is how we compare two
different proposals that deliver slightly different work factors.

Another point to consider here is that the whole PKIX world is
currently using 2048 bit keys and we have infrastructure built out to
support them. Any of these choices is going to be dramatically faster
and have shorter keys.

We use public keys with an effective work factor of 2^120 because that
is the best compromise of strength versus inconvenience, not because
that is a work factor we are happy with. From an architectural point
of view I would like my long term public keys that I use repeatedly to
be a lot stronger than my ephemeral keys and session keys.

So people implementing just one curve should probably be looking at
the curves giving a work factor of approx 2^256 rather than the
shorter ones. There are certainly people who think they need the
absolute best performance and go for the shorter ones. But thats most
likely to be driven by key size constraints trying to shoehorn into
UDP packets and twitter packets.

---

From: Patrick Longa Pierola <[email-masked]>
Date: Thu, 24 Jul 2014 15:15:06 +0000

-----Original Message-----
From: David Jacobson [mailto:[email-masked]] 
Sent: Thursday, July 24, 2014 7:27 AM
To: Patrick Longa Pierola; Phillip Hallam-Baker; [email-masked]
Subject: Re: [Cfrg] Comparing ECC curves

[snip]

> David Jacobson wrote:
> You are addressing performance.  But what about the ease of making a constant time implementation?  The security value of 256 over 255 or 254 is not much.  It is
> just that 256 is a nice round number, and might be a checkbox item.  If we can accept 255 or 254, it might make constant time implementations easier.   Perhaps
> people who have done constant time implementations can comment.

All our implementations supporting different bitlenghts (255, 256, 383, 384, 511 and 512) are constant-time. They follow the standard approach using the
minimal word representation (e.g., 4 words to represent 255 and 256-bit field elements). Another alternative is to use an extended, unsaturated representation (e.g., in
the case of 255 and 256-bit one would use 5 words). Although the choice and preference is somehow subjective and depends on a given implementer's preference,
ultimately every prime under discussion can be implemented in any of these two methods. So really the difficulty of implementation is not a differentiating factor
in this case.

Patrick

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 24 Jul 2014 09:53:03 -0700

> factor of 2^240  and is 30% faster, I would have to think about which I
It may interest you to know that that the prime 2^480 - 2^240 - 1 is 
about 40% faster than 2^512 - 569 on modern 64-bit Intel processors, 
meaning that each field operation takes about 60% of the time.  For 
example, on Haswell a field multiply mod 2^480 - 2^240 - 1 costs about 
121 cycles, and addition (with no reduce, because of reduced radix) 
takes fewer cycles than the pipeline (it's just two AVX2 add instructions).

I believe it is also about that much faster on than 2^521 - 1 on Sandy 
Bridge, but only by 20% or so on Haswell due to an implementation of 
multiplication mod 2^521-1 using 3-way Karatsuba/Chung-Hasan with AVX2.  
It uses 9 limbs of 58 bits each organized as (Z[w]/(w^3-2))[t]/(t^3-w), 
and needs AVX2 for all the adding.

I don't know how the three primes stack up on ARM.

-- Mike

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 24 Jul 2014 13:23:13 -0400

On Thu, Jul 24, 2014 at 12:53 PM, Mike Hamburg <[email-masked]> wrote:
> It may interest you to know that that the prime 2^480 - 2^240 - 1 is about
> 40% faster than 2^512 - 569 on modern 64-bit Intel processors, meaning that
> each field operation takes about 60% of the time.  For example, on Haswell a
> field multiply mod 2^480 - 2^240 - 1 costs about 121 cycles, and addition
> (with no reduce, because of reduced radix) takes fewer cycles than the
> pipeline (it's just two AVX2 add instructions).
>
> multiplication mod 2^521-1 using 3-way Karatsuba/Chung-Hasan with AVX2.  It
> uses 9 limbs of 58 bits each organized as (Z[w]/(w^3-2))[t]/(t^3-w), and
> needs AVX2 for all the adding.

Hmm, that is good for performance I guess. But doesn't help making a decision.

Talking to folk, I see the current concerns raised:

1) Nothing up my sleeves.
2) Key size.
3) Ability to support encryption and signature with one set of code.
4) Performance.
5) Work factor

My point here is meeting a work factor precisely is much less
important to me than performance.

But the other argument raised is that if you drop the requirement for
hitting the work factor exactly and allow a tradeoff between work
factor and performance this clouds the argument for 'nothing up my
sleeves'.

I think that is actually a good argument. If the requirement is for
256 and nothing less, that is completely defensible. Opening the door
to performance/work factor tradeoffs makes the decision subjective and
we get back to the problem of the proposers proving that there is
nothing up their sleeves.

The objective here is not to decide which algorithms are good, it is
deciding which to reject. I am arguing for each of those criteria as
criteria for reducing the search space.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 24 Jul 2014 13:52:00 -0400

> 3) Ability to support encryption and signature with one set of code.

You missed:
   6) constant-time operation

---

From: Mike Jones <[email-masked]>
Date: Thu, 24 Jul 2014 17:58:00 +0000

> I would really like to standardize on AES-GCM going forward for new protocols. But right now I can't use that in Windows .NET without writing my own AES code. Hmmm.

See http://blogs.msdn.com/b/shawnfa/archive/2009/03/17/authenticated-symmetric-encryption-in-net.aspx for an example using the authenticated encryption support in .NET.  Substitute CngChainingMode.Gcm for CngChainingMode.Ccm in the code and you're off to the races using GCM in .NET.

				-- Mike

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 24 Jul 2014 11:46:49 -0700

>    6) constant-time operation

I’d like to add:
  7) difficulty of implementation.

I think that 2), 3) and 6) are close to even across every option.

2) Every curve can use point compression once the patent expires, even if they don’t use the Montgomery ladder.  So the key size is the same as the field size, +- a few bits.

3) Weierstrass has this by default.  The other options proposed are all twisted or untwisted Edwards, or Montgomery.  These three forms are all isomorphic or isogenous to each other depending on the field, so you can pick your representation.  The isomorphisms and isogenies tend to be cheap and simple enough not to matter very much.

For a stronger curve (384-bit field and above), Bos-Costello-Longa-Naehrig and I did work which suggests that the Montgomery ladder is only 5% faster than twisted Edwards, and only if you’re compressing points.  So implementations can use twisted Edwards for everything if they want simplicity.  Montgomery-compatible point formats might still be desirable, but they aren’t that important.

6) To my knowledge, all the options we’ve discussed support constant-time operation.  The Weierstrass options are complex but doable.  The full-size packed options (field size 256, 384, 512) are slightly tricky but not that bad.

So that leaves:

1) NUMS.  I think we can all agree that this favors the BCLN curves and Curve25519.

4) Performance.  This trades off with work factor, but overall I think it favors non-BCLN curves (Curve25519, Ed448-Goldilocks, a 480-bit cousin of Goldilocks, possibly E-521) and within the BCLN curves it favors the twisted Edwards ones.

5) Work factor.  It’s clear what this is for every curve, but it isn’t clear what the ideal set of options is.

7) Difficulty of implementation.  This favors cofactor-4 curves, because constant-time Weierstrass is tricky (but doable and not horribly slow; see BCLN).

Cheers,
— Mike