[tor-talk] NIST approved crypto in Tor?

[Eugen Leitl]

----- Forwarded message from Gregory Maxwell <gmaxwell at gmail.com> -----

Date: Sun, 8 Sep 2013 06:44:57 -0700
From: Gregory Maxwell <gmaxwell at gmail.com>
To: "This mailing list is for all discussion about theory, design, and development of Onion Routing."
	<tor-talk at lists.torproject.org>
Subject: Re: [tor-talk] NIST approved crypto in Tor?
Reply-To: tor-talk at lists.torproject.org

On Sat, Sep 7, 2013 at 8:09 PM, Gregory Maxwell <gmaxwell at gmail.com> wrote:
> On Sat, Sep 7, 2013 at 4:08 PM, anonymous coward
> <anonymous.coward at posteo.de> wrote:
>> Bruce Schneier recommends *not* to use ECC. It is safe to assume he
>> knows what he says.
>
> I believe Schneier was being careless there.  The ECC parameter sets
> commonly used on the internet (the NIST P-xxxr ones) were chosen using
> a published deterministically randomized procedure.  I think the
> notion that these parameters could have been maliciously selected is a
> remarkable claim which demands remarkable evidence.

Okay, I need to eat my words here.

I went to review the deterministic procedure because I wanted to see
if I could repoduce the SECP256k1 curve we use in Bitcoin. They don't
give a procedure for the Koblitz curves, but they have far less design
freedom than the non-koblitz so I thought perhaps I'd stumble into it
with the "most obvious" procedure.

The deterministic procedure basically computes SHA1 on some seed and
uses it to assign the parameters then checks the curve order, etc..
wash rinse repeat.

Then I looked at the random seed values for the P-xxxr curves. For
example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90.

_No_ justification is given for that value. The stated purpose of the
"veritably random" procedure "ensures that the parameters cannot be
predetermined. The parameters are therefore extremely unlikely to be
susceptible to future special-purpose attacks, and no trapdoors can
have been placed in the parameters during their generation".

Considering the stated purpose I would have expected the seed to be
some small value like ... "6F" and for all smaller values to fail the
test. Anything else would have suggested that they tested a large
number of values, and thus the parameters could embody any undisclosed
mathematical characteristic whos rareness is only bounded by how many
times they could run sha1 and test.

I now personally consider this to be smoking evidence that the
parameters are cooked. Maybe they were only cooked in ways that make
them stronger? Maybe????

SECG also makes a somewhat curious remark:

"The elliptic curve domain parameters over (primes) supplied at each
security level typically consist of examples of two different types of
parameters — one type being parameters associated with a Koblitz curve
and the other type being parameters chosen verifiably at random —
although only verifiably random parameters are supplied at export
strength and at extremely high strength."

The fact that only "verifiably random" are given for export strength
would seem to make more sense if you cynically read "verifiably
random" as backdoored to all heck. (though it could be more innocently
explained that the performance improvements of Koblitz wasn't so
important there, and/or they considered those curves weak enough to
not bother with the extra effort required to produce the Koblitz
curves).
-- 
tor-talk mailing list - tor-talk at lists.torproject.org
To unsusbscribe or change other settings go to
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5