[Cryptography] RSA equivalent key length/strength

James A. Donald jamesd at echeque.com
Sun Sep 29 19:54:32 EDT 2013


On 2013-09-30 03:14, Lodewijk andré de la porte wrote:
> 2013/9/29 James A. Donald <jamesd at echeque.com 
> <mailto:jamesd at 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 at gmail.com>  <mailto: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>  <mailto:tor-talk at lists.torproject.org>
    Subject: Re: [tor-talk] NIST approved crypto in Tor?
    Reply-To:tor-talk at lists.torproject.org  <mailto:tor-talk at lists.torproject.org>

    On Sat, Sep 7, 2013 at 4:08 PM, anonymous coward
    <anonymous.coward at posteo.de>  <mailto: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.

    On Sat, Sep 7, 2013 at 8:09 PM, Gregory Maxwell<gmaxwell at gmail.com>  <mailto:gmaxwell at 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).


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20130930/876a912c/attachment.html>


More information about the cryptography mailing list