ECDSA vs EDDSA

[Pete Stephenson]

On Mon, Nov 10, 2014 at 1:16 PM, Peter Lebbing <peter at digitalbrains.com> wrote:
> I can give two significant differences between ECDSA and EdDSA:
>
> 1) Signature creation is deterministic in EdDSA; ECDSA requires high
> quality randomness for each and every signature to be safe (just as
> regular ol' DSA). If low-quality randomness  is used an attacker can
> compute the private key. Using XKCD's get_random()[1] function as in the
> Playstation 3 (as exposed by Fail0verflow) makes it trivial to compute
> the private key. More specifically, using the same random number for two
> different signatures is enough to trivially compute it.
>
> Werner has mentioned that deterministic operation is a prerequisite for
> him to consider an OpenPGP Card smartcard implementation due to lack of
> trust in on-card generated entropy.

As Kristian mentioned, deterministic DSA [RFC 6979] solves this
problem for both regular DSA and ECDSA.

I've been under the (possibly erroneous) impression that GnuPG has
used deterministic DSA for some time now. I'd hope that it does the
same for ECDSA.

If so, a quality source of randomness is needed only for key
generation, not for each signature.

> 2) The process by which the actual parameters of Ed25519 have been
> chosen is completely open. It is possible to create a backdoor by very
> careful choice of the parameters; this means that there exists a chance
> that the NIST and (I believe also) the Brainpool curves have been chosen
> in a way that there is a secret backdoor only known to the organisation
> that selected the parameters.

While the NIST curves are suspicious in that they utilize an
unexplained "random" seed[1], I don't see how the Brainpool curves
were chosen for nefarious purposes.

Indeed, pages 6 and 7 of
http://www.ecc-brainpool.org/download/Domain-parameters.pdf shows the
exact process to derive both the seed and the pseudo-random primes
used in those curves.

At http://safecurves.cr.yp.to/rigid.html, djb says the Brainpool
curves are "mostly rigid" and has only a limited number of criticisms:
"Why SHA-1 instead of, e.g., RIPEMD-160 or SHA-256? Why use 160 bits
of hash input independently of the curve size? Why pi and e instead
of, e.g., sqrt(2) and sqrt(3)? Why handle separate key sizes by more
digits of pi and e instead of hash derivation? Why counter mode
instead of, e.g., OFB? Why use overlapping counters for A and B
(producing the repeated 26DC5C6CE94A4B44F330B5D9)? Why not derive
separate seeds for A and B?"

There's several other standards (such as RCF 3526) that generate
primes, in part, using large powers of pi. It seems to me to be a
reasonable "nothing up my sleeve" number. As for the other concerns,
would the use of (for example) SHA1 vs. SHA256 or the use of counter
mode as part of the generation algorithm give the malicious
standards-writer some advantage?

Maybe, but it seems much less likely to be manipulated than, say, the
NIST curves or ANSSI FRP256v1, and more likely to be the result of
some ordinary technical decision-making.

[1] It's certainly possible that NIST/NSA just used /dev/random or
some other quality source of randomness for the seed, but there's no
way to *prove* that, so the seeds for the NIST curves are not above
suspicion. Still, it would require a *lot* of effort to get a
particular output of SHA1 that had certain useful properties. Would
the NSA expend that effort? Who knows?

Cheers!
-Pete

-- 
Pete Stephenson