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

[ianG]

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.