[Cryptography] IETF discussion on new ECC curves.

[Phillip Hallam-Baker]

On Thu, Jul 31, 2014 at 3:25 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Thu, Jul 31, 2014 at 9:12 AM, Phillip Hallam-Baker
> <phill at hallambaker.com> wrote:
>> On Wed, Jul 30, 2014 at 4:42 PM, Bear <bear at sonic.net> wrote:
>>>
>>>> On Mon, Jul 28, 2014 at 7:48 PM, Bear <bear at sonic.net> wrote:
>>>> > On Sat, 2014-07-26 at 14:32 -0400, Phillip Hallam-Baker wrote:
>>>
>>>> > So the first fermat-test prime number below 2^512 is 2^512 - 569? It's
>>>> > a nice nothing-up-my-sleeve number, anyhow. What's the problem with it?
>>>> > Are there some requirements I don't know?
>>>
>>>> Yep, that is exactly what Microsoft did. The problem is that it is not
>>>> exceptional speed wise. The fast moduli are 2^521 and 2^480.
>>>
>>> Despite the non-exceptional speed, 512 = 2^9 is THE next
>>> nothing-up-my-sleeve number for a bit width, and 2^512 -
>>> 569 is therefore THE next nothing-up-my-sleeve number for
>>> an exponent modulus.
>>>
>>> The minute there is debate, there is reasonable suspicion
>>> that someone is trying to influence the debate for purposes
>>> of subverting security.
>>
>> Exactly.
>
> There's always room for debate.
>
> E.g. why are you pushing so hard for 2^512-569?  What do you know
> about it I don't?  Why do you want the high-security curve to be a
> slow one that will be used less than a faster one?

The requirement for a 2^512 bit prime comes directly from the security
requirement of WF256. And WF256 is currently the upper end of AES,
SHA2 and SHA3 key sizes.


> 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 and using random curves introduces the risk of them being
bongoed and thus require lots of controls that are not necessary for
the NUMS approach where there is only one solution for a particular
security level.



> (Though of course "random" primes requires a verifiably-pseudorandom
> process, so more to debate there too, see BADA55....)

Yep, rigidity is good here.



> Many people (like myself) think it's unlikely that NIST/NSA backdoored
> those curves.  There's no known algorithm that could have done so.
> Even if you hypothesize an undiscovered 1-in-a-trillion "bad curve"
> property, NIST/NSA choosing curves to match this property would leave
> government systems vulnerable to any adversary who discovered that
> property.

Not if it was a public key system type property similar to using a
composite modulus in RSA (see Moti Yung)


> 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. To use ECC we have to go to Diffie Hellman and as someone
pointed out to me this morning, our performance advantage flips on
signatures from the verify being fast to the sign.



>> At the IRTF meeting I suggested we split the baby and adopt 2^255-19
>> for fast encryption and 2^512-569 for signature and high security
>> encryption. I am thinking that is the right approach.
>
> I don't think you should make a decision ignoring performance
> criteria.  There's not much reason to think that a 2^256 security
> level will provide security over a longer or shorter duration than
> 2^224 or 2^260.  At that level you're worried about unpredictable
> break-throughs, e.g. quantum computing which would destroy the
> security of all these.  Moore's law will never get there.

No, my specific concern is that there is a hole in the algorithm that
makes it vulnerable to a currently unknown form of cryptanalysis.

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.

We know that the reason that there is a 256 bit key size in AES has
nothing to do with a potential weakness in Curve 2^256-569.




> There's also not much reason to think that fixating on an particular
> bit length and prime form is less arbitrary than choosing based on
> objective performance criteria, IMO.
>
>
>> DJB does have some deployment momentum for his curve. There is a switching cost.
>>
>> If someone is worried that the NSA has bongoed the curves or has a way
>> to bongo them then they should be using the 2^512 curve and not
>> Curve25519.It is pointless worrying too much about the minutiae of
>> lower security options.
>
> That doesn't follow, and is unfair to 25519.  25519 was chosen based
> on objective performance and rigidity criteria.

As soon as you allow performance to factor at all it becomes
subjective. This is not a big problem for Curve25519 but it is really
problematic for WF256 where there isn't a clearly best curve. E521
requires a data path that is not a multiple of 64 which means that
dedicated hardware has to be very dedicated.



> Performance is an issue for many systems, not just the web  - think
> mobile or embedded, e.g.

My current mobile phone is faster than the fastest computer at CERN
when we built the Web.


> And these systems would *also* like to have a viable "extra-strength"
> curve option.
>
> An extra-strength curve that is twice as fast (which is the current
> Goldilocks vs 2^512-569 ratio) would be applicable in more places.

More choices is not necessarily better. We get a factor of two
improvement just by waiting 18 months.



>> I would even
>> defend deriving a 256 bit key for AES 256 from a 256 master secret and
>> a 128 bit PFS mixin.
>
> I'm not sure what key agreement you're imagining.  For long-term
> confidentiality, there is a small argument that one might want
> *larger* ephemeral DH keys compared to identity keys, as identity keys
> are probably replaced more quickly, and confidentiality might have to
> last for decades.

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.