[Cryptography] IETF discussion on new ECC curves.

[Phillip Hallam-Baker]

On Fri, Aug 1, 2014 at 2:42 PM, Trevor Perrin <trevp at trevp.net> wrote:
> 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?

The attacks are also a lot more expensive than one AES operation. So
we don't need to be precise to the bit. Work factor is not an exact
measure and nor is performance. They all depend on assumptions.
Performance differs on AMD, Intel, ARM, FPGA and work factor can
reduce dramatically when people are allowed to assume they have an
Exabyte of RAM for scratch storage.

Microsoft presented multiple options for the curve that we would still
need to consider the pros and cons for, not just twisted Edwards.

Here the competitors on offer are:

E-521
E-512
E-480
E-448

E-480 is not just slightly less secure than E-512, the work factor is
reduced by 2^16, that's 65,536 times less security than we asked for.
And the so-called 'Goldilocks curve' is twice as fast but the E-512 is
4 billion times harder to break.

E-521 is only an order of magnitude more secure and. It is a little
faster on typical architectures but dramatically slower on machines
with an internal 512 bit data bus like most modern GPUs.

So no, I think the argument for the 512 bit prime is pretty clear.


Note however that all the same arguments actually argue for accepting
Curve25519 even though it isn't exactly WF128


>> 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.

Yep, one reason I only use SHA-512.


> 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.

No. I disagree.

Tell people to pick one or the other. They can have bleeding edge
performance with a curve that is chosen for speed or they can choose a
curve with no security compromises.

It is as simple as that: Performance or No-Security-Compromise.

I don't want you to be deciding that I should be using a curve that is
three or seven orders of magnitude less secure than I asked for in the
name of 'security'. If you want performance go for the smaller curve.


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

The problem is that the arguments have to be understood by people who
are not in the field. And that means that they have to be straight as
a die.

To start using these curves we have to explain why we are not using
the NIST curves. And that has nothing to do with performance. It isn't
even that we think they have been bongoed. We know who generated them
after all. If he could think up the seed for his RNG we might be able
to go back to using them.

The reason that we are changing is that we cannot make an unqualified
argument to someone not in the field that there is no possibility that
they have been bongoed. And once we put that possibility on the table
we have to make sure that nobody can raise the same argument against
us.


>> 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.

We could argue for doing more than doubling the WF exponent but
anything less means we are eating into our safety margin.

Meet in the middle is always going to be of interest in an attack on a
function with an input and an output.

>
>> 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).

It depends on what machine you have for a start. Performance has
always been highly subjective.


> 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.

Exactly. I don't think we are going to find performance is a useful
discriminator. It certainly isn't an interesting criteria for me at
WF256.

If I want performance I will go for a shorter key.


>> 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.

I would not use DSA to authenticate the ephemeral key. I would use
ECDH to establish a master secret and use that to authenticate the PFS
exchange and derive the encryption keys as a one-way function of both.

That way I have WF256 encryption guaranteed and WF128 forward secrecy.

It also makes far better sense from the design of the handshake as it
saves a round trip.

The reason we used to use DSA with DH was to avoid the RSA patent. It
is not an approach I like because it creates a non-repudiable proof
that someone was a party to a communication which is information I
don't need to leave.