Subject: [TLS] (EC)DSA potential problems (ECC "brittleness")

From: Peter Gutmann <[email-masked]>
Date: Fri, 11 Oct 2013 12:17:28 +0000

Martin Rex <[email-masked]> writes:

>Which "recommended (until not too long ago) way to generate your k for (EC)
>DSA" are you referring to specifically?

See Adam Back's conveniently-timed post to the Ramdombit crypto list:

-- Snip --

Some may remember Bleichenbacher found a random number generator bias in the
original DSA spec, that could leak the key after soem number of signatures
depending the circumstances.

Its described in this summary of DSA issues by Vaudenay "Evaluation Report
on DSA"

http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1002_reportDSA.pdf

Bleichenbacher's attack is described in section 5.

The conclusion is "Bleichenbacher estimates that the attack would be
practical for a non-negligible fraction of qs with a time complexity of
2^63, a space complexity of 2^40, and a collection of 2^22 signatures.  We
believe the attack can still be made more efficient."

NIST reacted by issuing special publication SP 800-xx to address and I
presume that was folded into fips 186-3.  Of course NIST is down due to the
USG political level stupidity (why take the extra work to switch off the web
server on the way out I dont know).

That means 186-1 and 186-2 were vulnerable.

An even older NSA sabotage spotted by Bleichenbacher?

Anyway it highlights the significant design fragility in DSA/ECDSA not just
in the entropy of the secret key, but in the generation of each and every k
value, which leads to the better (but non-NIST recommended) idea adopted by
various libraries and applied crypto people to use k=H(m,d) so that the
signture is determinstic in fact, and the same k value will only be used
with the same message (which is harmless as thts just reissuing the bitwise
same signature).

-- Snip --

(my ref. for this was "The Insecurity of the Digital Signature Algorithm with
Partially Known Nonces" by Phong Nguyen and Igor Shparlinski, but Vaudenay's
work is a better ref).

>Is or was this part of FIPS 186-x for DSA--or some X9.xx document for ECDSA
>that do not have (not having coughed up the $$), and is that specific issue
>sufficient to enable the attack described in this paper:
>
>  Jean-Charles Faugere, Christopher Goyet and Guenael Renault
>  "Attacking (EC)DSA Given Only an Implicit Hint"
>
>  http://www-polsys.lip6.fr/~goyetc/doc/ImplicitECDSA_Goyet.pdf

No, that's yet another one.

(I did mention that DLP-based PKCs were quite brittle, didn't I? :-).

>Btw. where would one find the information necessary to implement (EC)DSA safe
>with respect to the state-of-the-art?

I don't think there is one, you need to either be aware of a whole pile of
research papers (some of which are only drafts, or tech reports, which means
reading a pile of crypto lists), or to read code comments in a well-maintained
crypto library that mentions the workarounds to various problems.

(Again, my brittleness comment, with RSA you use blinding/const-time modexp
and do a consistency check on your signatures to check for faults and you're
done, with the DLP's its a continuous arms race).

Peter.