[147327] in cryptography@c2.net mail archive
Re: [Cryptography] RSA equivalent key length/strength
daemon@ATHENA.MIT.EDU (James A. Donald)
Mon Sep 30 00:08:58 2013
X-Original-To: cryptography@metzdowd.com
Date: Mon, 30 Sep 2013 09:54:32 +1000
From: "James A. Donald" <jamesd@echeque.com>
CC: cryptography <cryptography@metzdowd.com>
In-Reply-To: <CAHWD2rKsCcjkRGSQ2P-kqOUKL6PmsPJNj8Tuf5NtDnNefO2DrQ@mail.gmail.com>
Reply-To: jamesd@echeque.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
This is a multi-part message in MIME format.
--===============6230299000336828179==
Content-Type: multipart/alternative;
boundary="------------000700030502010508020307"
This is a multi-part message in MIME format.
--------------000700030502010508020307
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
On 2013-09-30 03:14, Lodewijk andré de la porte wrote:
> 2013/9/29 James A. Donald <jamesd@echeque.com
> <mailto:jamesd@echeque.com>>
>
> (..) fact, they are not provably random, selected (...)
>
> fixed that for you
>
> It seems obvious that blatant lying about qualities of procedures must
> have some malignant intention, yet ignorance is as good an
> explanation. I don't think lying the other way would solve anything.
> It's obviously not especially secure.
The NIST ec curves are provably non random, and one can prove that NIST
is lying about them, which is circumstantial but compelling evidence
that they are backdoored:
From: Gregory Maxwell<gmaxwell@gmail.com> <mailto:gmaxwell@gmail.com>
To: "This mailing list is for all discussion about theory, design, and development of Onion Routing."
<tor-talk@lists.torproject.org> <mailto:tor-talk@lists.torproject.org>
Subject: Re: [tor-talk] NIST approved crypto in Tor?
Reply-To:tor-talk@lists.torproject.org <mailto:tor-talk@lists.torproject.org>
On Sat, Sep 7, 2013 at 4:08 PM, anonymous coward
<anonymous.coward@posteo.de> <mailto:anonymous.coward@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.
On Sat, Sep 7, 2013 at 8:09 PM, Gregory Maxwell<gmaxwell@gmail.com> <mailto:gmaxwell@gmail.com> wrote:
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).
--------------000700030502010508020307
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit
<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 2013-09-30 03:14, Lodewijk andré de
la porte wrote:<br>
</div>
<blockquote
cite="mid:CAHWD2rKsCcjkRGSQ2P-kqOUKL6PmsPJNj8Tuf5NtDnNefO2DrQ@mail.gmail.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div class="gmail_extra">2013/9/29 James A. Donald <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:jamesd@echeque.com" target="_blank">jamesd@echeque.com</a>></span>
<div class="gmail_quote">
<blockquote class="gmail_quote">
<div>(..) fact, they are not provably random, selected
(...)</div>
</blockquote>
</div>
fixed that for you<br>
</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">It seems obvious that blatant lying
about qualities of procedures must have some malignant
intention, yet ignorance is as good an explanation. I don't
think lying the other way would solve anything. It's obviously
not especially secure.</div>
</div>
</blockquote>
<br>
<br>
The NIST ec curves are provably non random, and one can prove that
NIST is lying about them, which is circumstantial but compelling
evidence that they are backdoored:<br>
<br>
<blockquote>
<pre>From: Gregory Maxwell <a href="mailto:gmaxwell@gmail.com"><gmaxwell@gmail.com></a>
To: "This mailing list is for all discussion about theory, design, and development of Onion Routing."
<a href="mailto:tor-talk@lists.torproject.org"><tor-talk@lists.torproject.org></a>
Subject: Re: [tor-talk] NIST approved crypto in Tor?
Reply-To: <a href="mailto:tor-talk@lists.torproject.org">tor-talk@lists.torproject.org</a></pre>
<pre>On Sat, Sep 7, 2013 at 4:08 PM, anonymous coward
<a href="mailto:anonymous.coward@posteo.de"><anonymous.coward@posteo.de></a> wrote:</pre>
<blockquote>
<blockquote>
<p>Bruce Schneier recommends <b>*not*</b> to use ECC. It is
safe to assume he knows what he says.</p>
</blockquote>
<p>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.</p>
</blockquote>
<pre>On Sat, Sep 7, 2013 at 8:09 PM, Gregory Maxwell <a href="mailto:gmaxwell@gmail.com"><gmaxwell@gmail.com></a> wrote:</pre>
<p>Okay, I need to eat my words here.</p>
<p>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.</p>
<p>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.</p>
<p>Then I looked at the random seed values for the P-xxxr curves.
For example, P-256r’s seed is
c49d360886e704936a6678e1139d26b7819f7e90.</p>
<p>_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”.</p>
<p>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.</p>
<p>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????</p>
<p>SECG also makes a somewhat curious remark:</p>
<p>“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.”</p>
<p>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).</p>
</blockquote>
<br>
</body>
</html>
--------------000700030502010508020307--
--===============6230299000336828179==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============6230299000336828179==--
