[Cryptography] IETF discussion on new ECC curves.

[Phillip Hallam-Baker]

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.


> Gratz to Microsoft, whatever their past sins, for making a
> recommendation that marks them out as DEFINITELY not playing
> that role in the current round.

Its important to remember that organizations are made up of people. In
this case the person driving this is Brian LaMacchia who is well known
in the community. He set up the PGP key server most people still use
at MIT.

It also goes the other way. Saying 'I trust the NSA' is ridiculous
because it is an organization made up of people. I do trust some of
those people. But there are also some people in very senior positions
I don't trust and with cause. I don't trust them to tell the President
what they are doing, there is a long history of abuses there. And I
certainly don't trust them to interpret their oath to uphold the
constitution in a reasonable fashion. In fact its rather clear that
they model their interpretation of the constitution to fit an agenda.

> The minute that there is suspicion that someone might be
> trying to influence the debate for purposes of subverting
> security, it raises a hard question....  one which sounds
> like a paranoid wearing a too-tight hat, but which must be
> raised....

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.

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.


Since I am doing PKI and static encrypted data, I have long term
security concerns and any decision I take now will have long term
consequences. I want 50+years security on stored data keys and at
least 20+ years on PKI key signing keys.

So for me 2^512-569 is the logical choice.


For the TLS group, there is a big performance issue and so a 2^128
work factor is defensible, particularly for PFS keys. I would even
defend deriving a 256 bit key for AES 256 from a 256 master secret and
a 128 bit PFS mixin.

DNSSEC is a trickier question. I would argue for the harder work
factor regardless but I can see how the key size could be a concern
given the constraints of DNS.


>
> Is at all reasonable to suspect that the same properties
> that make a given calculation faster might also make it
> easier to analyze or reverse?

Of course, it almost certainly is the case that is Curve25519 takes
50% of the time that an alternative takes then cryptanalysis takes no
more than 50%. But that is fine. I care about the work factor ratio,
how much harder the problem is for the attacker than the defender

What would worry me a lot is if the work factor was reduced by a lot
more than half, like an order of magnitude.


> IOW, when we look for 'fast' curves, is there a "reasonable
> to  suspect" chance that we're thereby looking for 'weak'
> curves by some mathematical attack that we may finally notice
> next week or the week after - but which the hypothetical
> parties attempting to influence the debate may be aware of
> now?

That is an unsolvable problem. Particularly where GCHQ and NSA are
concerned. Nobody who is credible in the US or IETF crypto world is
more than one degree of separation from very senior NSA people or two
degrees away from the current NSA director and all the living
predecessors.

I know DJB and he isn't a good enough actor to be an undercover mole.
The NSA would have far more valuable work for him to do than peddling
bongoed crypto for use by US companies.


Another reason I don't think the NSA would be behind all this is the
NOBUS doctrine 'nobody but us' [1].

https://www.techdirt.com/articles/20131005/02231624762/national-insecurity-how-nsa-has-put-internet-our-security-risk.shtml

Peddling a set of curves that were created so that there is a backdoor
only the NSA can use is compatible with NOBUS. Only the generator of
the curves can use them.

These curves were not made by the NSA and any weird mathematical trick
that is hidden inside is a property of nature that the Russians or our
rapidly dwindling supply of national foes might find and use against
us. That would be contrary to NOBUS.