[Ach] djb on timing weaknesses of ECDSA implementations (& how to design EC signature systems)

ianG iang at iang.org
Sun Mar 23 16:16:48 CET 2014

On 23/03/2014 14:45 pm, Aaron Zauner wrote:
> interesting: http://blog.cr.yp.to/20140323-ecdsa.html

On deprecating DSA, he says:

 DSA was "invented" by NSA's David Kravitz, according to a patent
application filed secretly in July 1991. It was proposed as a standard
by NIST the next month. NIST didn't admit NSA's role until after a
lawsuit was filed by Computer Professionals for Social Responsibility.
NIST memos state that the "reasons for the selection" of DSA are
summarized in an NSA document; as far as I know, that document is still
classified Top Secret.

NIST received many public objections to DSA. (As NIST put it: "the
number of negative comments was significantly larger than normally
received for a proposed Federal Information Processing Standard".) For
example, here are some of Rivest's comments:

    "It is my belief that the NIST proposal represents an attempt to
install weak cryptography as a national standard, and that NIST is doing
so in order to please the NSA and federal law enforcement agencies. ...
A U.S. standard, even if weak and flawed, may be widely used overseas,
making NSA's job easier. "

Technical topics of the objections included DSA's obviously breakable
260 security level (DSA was limited to 512-bit moduli); the lack of an
accompanying encryption mechanism; DSA's poor performance; DSA's
unnecessary computation of an inverse "each time a message is to be
signed"; and DSA's requirement of a cryptographically strong random
number for each signature (Rivest wrote "the poor user is given enough
rope with which to hang himself"). I'll say more later about the
random-number part.

NIST made one change, namely allowing 1024-bit moduli, and then issued
DSA as a standard in 1994. Later NIST extended the standard to ECDSA,
allowing 15 different elliptic curves that had been chosen by Jerry
Solinas at NSA.

More information about the Ach mailing list