[tahoe-dev] elliptic curves with verifiably pseudorandom parameters Re: #466 state-of-the-patch

[Samuel Neves]

I understand most of this is marketing, but I'll throw out a dissenting
opinion anyway.

The Dual_EC_DRBG potential backdoor is not dependent on the curve
parameters used. The security of this method lies on the fact that it is
hard to compute the discrete logarithm of the two randomly chosen points
P and Q. In Appendix A.1 of [2], NIST gives two points usable by this
method. However, they give no proof of random generation of said points.
This may lead to believe they actually know the logarithm of Q = xP. In
Appendix A.2, they give the option to use custom points for this, thus
avoiding the potential backdoor.

In any case, this same attack could be easily ported to Brainpool
curves; the issue is NOT in the curve parameters themselves. NIST curves
are, too, randomly generated, as can be checked in Appendix D.1.1.4 of
[1]. Appendix D.1.1.5 also allows one to use his own base points.

So the question comes down to whether the curve itself is secure. It
does resist all known attacks. The special prime number used leads to
much faster arithmetic than a randomly chosen one (this might be
relevant for embedded platforms). But unlike the prime fields used in
classic public-key cryptosystems, elliptic curves aren't known to be
less safe by using a 'simpler' prime: index calculus on elliptic curves,
even if it was practical, would not find relations faster (besides
faster arithmetic) since the smoothness concept is lifted from the
integers to actual points in the curve.

Of course, it does no harm to change to a more paranoid set of
parameters. I'm just making the case of there being no *immediate need*
to do so.

Best regards,
Samuel Neves

[1] http://csrc.nist.gov/publications/PubsFIPS.html#186-3
[2] http://csrc.nist.gov/publications/PubsSPs.html#800-90

On 14-02-2011 07:19, Zooko O'Whielacronx wrote:
> (Part two in an on-going series of comments on this ticket, at a rate
> of approximately one per night, apparently. :-))
>
> Here is my pitch for why we should consider using Brainpool curves
> instead of NIST curves. The key technical difference is that the
> Brainpool parameters were generated in a verifiably pseudorandom way,
> so they are unlikely to have some sort of backdoor built into the
> choice of parameters:
>
> http://tools.ietf.org/html/rfc5639
>
> An example of a potential backdoor being built into the choice of
> elliptic curve parameters was shown by Shumow and Ferguson in the
> "Dual_EC_DRBG" PRNG. Schneier wrote up a good explanation:
>
> http://www.schneier.com/essay-198.html
>
> I don't know whether any such backdoor is even possible in ECDSA. What
> I do know is that the verifiably pseudorandom parameters of the
> Brainpool curves eliminate one such potential backdoor.
>
> I really don't like "popularity contests" in general, but when
> choosing a crypto primitive, if there is a legitimate constituency
> that distrusts an option then that is a good reason to use a different
> option. I don't want some potential future users to distrust
> Tahoe-LAFS because it relies on the NIST curves (even if the majority
> of potential future users trust the NIST curves).
>
> What we're talking about here is basically geo-politics, I guess.
> People who trust NIST and NSA to be honest and/or to be on their side
> are fine with the NIST curves, but those people should also be fine
> with the Brainpool curves. The first significant user base to go with
> the Brainpool curves is the German federal government, who sponsored
> the development of the Brainpool curves and are now deploying them.
>
> Note that you do not have to trust the German federal government to be
> satisfied using the Brainpool curves! This is because they are
> generated with a specific PRNG using SHA-1, seeded with π. See
> http://tools.ietf.org/html/rfc5639 .
>
> Note this is a similar "marketing" issue to why I want Tahoe-LAFS to
> continue using AES in addition to another stream cipher even though I
> personally think that alternatives such as XSalsa20 are safer than
> AES. For people out there who disagree with me and think that AES is
> safer, I don't want to reduce their trust in Tahoe-LAFS by using
> XSalsa20 alone.
>
> One practical matter is that Brainpool curves are not yet implemented
> in OpenSSL, which python-ecdsa uses for interop testing. If anyone out
> there knows how to push these patches along in the OpenSSL process,
> please do so:
>
> http://rt.openssl.org/Ticket/Display.html?id=2239&user=guest&pass=guest
> http://rt.openssl.org/Ticket/Display.html?id=2359&user=guest&pass=guest
>
> I suspect that a good way to push these patches along would be to
> provide a patch that adds some Known-Answer Tests.
>
> Regards,
>
> Zooko
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at tahoe-lafs.org
> http://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev