[Cryptography] IETF discussion on new ECC curves.

Trevor Perrin trevp at trevp.net
Fri Aug 1 14:42:54 EDT 2014


On Thu, Jul 31, 2014 at 3:39 PM, Phillip Hallam-Baker
<phill at hallambaker.com> wrote:
>
> The requirement for a 2^512 bit prime comes directly from the security
> requirement of WF256.

That's not a precise concept.  The attacks relevant to a 256-bit
symmetric key are different from a 512-bit elliptic curve key [1].
And a 512-bit twisted Edwards curve like Microsoft's will have keys of
510 bits, not 512, so you must mean a 514-bit prime?


> And WF256 is currently the upper end of AES,
> SHA2 and SHA3 key sizes.

Scaling up symmetric crypto is low-cost.  AES-256 is only ~40% slower
than AES-128.  SHA512 is *faster* than SHA256 on 64-bit systems.

In contrast, doubling keysizes for asymmetric crypto will often be a
factor of 6-8 slowdown in what is already your crypto bottleneck.

So larger curves bring a significant performance hit.  We need be
careful and balance the security benefit with performance cost.


>> And why primes with efficient reduction?  Aren't even slower random
>> primes THE choice for avoiding suspicion (like Brainpool)?
>
> Not really, we have no objective reason to believe they are more
> secure

We have no objective reason to believe 2^512-569 is less suspicious
than 2^521-1 or 2^448 - 2^224 - 1, though there are objective reasons
why the latter lead to faster implementations.

If you're so worried about primes that support efficient reduction, I
don't understand why 2^512-569 is acceptable.


>> Many people are interested in new curves not due to the backdoor
>> issue, but due to the possibility of higher performance, including
>> high performance at "extra-strength" (>>128 bit) security levels.
>
> Well that depends on whether they want public or private key to be
> fast.

I'd like everything to be fast.  Fast crypto gets used more than slow crypto.

It's true that low-exponent RSA or Rabin can offer very fast signature
verification, but fast EC signatures are competitive [3].  In any case
that's an RSA vs ECC question, I don't think it affects the choice of
curves.


> The most powerful general technique against non trivial crypto is meet
> in the middle type attacks that reduce the work factor to half the key
> length. So taking a computationally infeasible key length and doubling
> it is a defensible choice.

You don't know what sort of cryptanalytic weakening might happen to
EC.  Let's not pretend there's precision here, we're just throwing "a
bunch" more bits onto the key and hoping it helps.


> As soon as you allow performance to factor at all it becomes
> subjective.

I don't agree that performance is a "subjective" criteria.  It depends
on implementation techniques which depend on specific curve decisions
(in particular, field primes that allow efficient reduction, efficient
splitting of field elements into reduced-radix limbs, and Karatsuba).

The current curve proposers have probably not yet put their best foot
forward in terms of efficient implementation and performance analysis.
For example, the Microsoft implementations I believe use full-radix
limbs, so have more room to improve than Goldilocks / Curve41417.  And
we need more comparison and analysis between Curve41417, Goldilocks,
and E-521.

But at some point we should be able to make fairly definitive
statements about which curves are more efficient than others on common
32-bit and 64-bit software platforms.

This may produce a single winner.  If not, it will winnow the field to
a very few choices, at which point we could argue about aesthetics, or
whether whether we want a slightly higher or lower security level, or
whatever.

But what we shouldn't worry about, at that point, is whether we are
being "100% rigid" and choosing the one-and-only "true" curve that
no-one could have steered towards a known-only-to-them weakness.
Because it's impossible to achieve perfect rigidity.  There's a small
amount of room for debate in your "use 512 somewhere" criteria; as
well as in my security-vs-time criteria; as well as in the debate
we're currently having about which criteria to apply.

So rigidity is not an all-or-nothing property  But it can be
quantified.  The NSA/NIST curves are nervous-inducing mainly because
the seed could have been chosen based on a 2^80 search for some
extremely rare weak-curve property.

Once we've winnowed down the field to a few choices, we've improved
rigidity by 20+ orders of magnitude.  The remaining risk is if unknown
weak curves are extremely common (1 out of 3, or something).  But
there's no way to reduce arbitrariness below that level, so any
criteria that winnows curves down to a few choices is equally good
with respect to rigidity.

So rigidity doesn't make your criteria better than mine, and we're
left to argue whether we should focus on an efficiency critiera
(security/time ratio) or a cosmetic criteria (uses round numbers).  I
guess I've expressed my opinion enough on this, but it's something
everyone should think about.


> If the protocol is designed right the attacker has to break the 256
> bit master secret before they can attack the PFS mix in. One scheme
> suggested being using the PFS data to give the IV. I have not checked
> on the security of that yet though.

I'm still not sure what you're describing.  In many protocols the
long-term keys are signature keys, and the ephemeral/"PFS" keys are
DH/ECDH.  Since the lifetime of the signature keys is often shorter
than the confidentiality lifetime we'd like for encrypted data, it's
reasonable to consider ephemeral keys with a *higher* security level
than the long-term keys, not a lower, as you seem to be saying.

For example, OTR uses 1024-bit DSA signatures, and 1536-bit DH keys.
While these numbers look small nowadays, the principle makes sense.

Similarly, it would be reasonable for websites to use an
extra-security curve for ephemeral ECDH in TLS, even if the signatures
were RSA-2048.

Trevor

[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg04820.html
[2] http://research.microsoft.com/pubs/209303/curves.pdf
[3] http://ed25519.cr.yp.to/ed25519-20110926.pdf


More information about the cryptography mailing list