soft backdoors: ECDSA vs RSA vs EdDSA (aka EC Schnorr) (Re: BlueHat v13 crypto talks - request for leaks ;))

[Adam Back]

Vaudenay's report writes up an attack developed by Daniel Bleichenbacher
which he presented to some standards groups but did not publish.  As a
result of that the DSA standard was modified.  As I recall with about
1million signatures he could recover the private key due to the small bias
from the formual Peter mentioned: k = G(t,KKEY) mod q ie if |n| = 256-bits
where n is the order of the group, then G(t,KKEY) is distributed with a
rectangular distribution in {0,2^256-1} and q is < 2^256-1.  As I read it
Bleichenbacker did not try that hard to optimize his attack, it was enough
to show the NIST/NSA designed DSA RNG was biased enough to break DSA in a
server / automated environment.

Maybe further optimizations would have been possible...  Maybe this DSA flaw
spotted by Bleichenbacker was another NSA soft-sabotage attempt (making
standards security brittle in the knowledge that it some people will fail to
harden it, and also it gives a plausibly deniable backdoor design for
colluding business entities, or double-agents on the payroll (former NSA
people say)).  In fact DSA was even designed by a former NSA cryptographer.
http://en.wikipedia.org/wiki/Digital_Signature_Algorithm (Dr David Kravitz,
a former NSA employee).

The approach I prefer is the deterministic DSA approach where k = MAC(d,M)
where d is the private DSA/ECDSA key and M is the message, plus bias
removal.  Bernsteins EdDSA (which despite the name is actually a Schnorr
signature over an Edwards curve) also uses the same technique.  This is
standardized in an RFC.  If people are going to use DSA/ECDSA they should
use this deterministic DSA.  Personally I prefer EC Schnorr because Schnorr
is just a better, simpler, more secure and more flexible signature (supports
simplel blinding, compact multi-sig, clearer security proofs, better
security margin, less dependence on hash properties etc).  To my mind DSA's
only reason for existence is historic due to patents.  It is inferior by all
metrics to Schnorr, just that Scnorr's patent didnt expire until
http://en.wikipedia.org/wiki/Schnorr_signature feb 2008.

Anyway as Bernstein has put forward EdDSA with parameters and multiple
security, speed, simple constant time, non-key related, nor message
execution time, and provably non-cooked curve parameters (and there perhaps
remains some needless ambiguity about the magic constants used to seed the
ECDSA parameters) there is no reason in my opinion not to use EdDSA aka EC
Schnorr in any new systems.

Of course RSA is good also, and simpler parameter definition, the main
downside being the large keys for same security margin (3072-bit).

Adam

On Tue, Dec 17, 2013 at 06:23:43PM +1300, Peter Gutmann wrote:
>Tom Ritter <tom at ritter.vg> writes:
>>On 14 December 2013 14:51, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
>>
>>> For example if you
>>>  follow DSA's:
>>>
>>>   k = G(t,KKEY) mod q
>>>
>>> then you've leaked your x after a series of signatures, so you need to know
>>> that you generate a large-than-required value before reducing mod q.  The
>>> whole DLP family is just incredibly brittle, a problem that RSA doesn't
>>> have.
>>
>>This is different from the normal 'repeated/non-random k leads to private
>>key', is it not?  Is there a paper/reference I can read more about this
>>attack?
>
>Yes, this is one of several variations of subtle leak-the-private-key issues,
>rather than the standard obvious-leak-the-private-key.  The code comment I've
>got has, alongside other observations:
>
>           The best reference for this is
>           probably "The Insecurity of the Digital Signature Algorithm with
>           Partially Known Nonces" by Phong Nguyen and Igor Shparlinski or
>           more recently Serge Vaudenay's "Evaluation Report on DSA"
>
>Then there's tricks like:
>
>   Suppose that the
>   certificate contains a copy of the certificate signer's DSA parameters,
>   and the verifier of the certificate has a copy of the signer's public key
>   but not the signer's DSA parameters (which are shared with other keys).
>   If the verifier uses the DSA parameters from the certificate along with
>   the signer's public key to verify the signature on the certificate, then
>   an attacker can create bogus certificates by choosing a random u and
>   finding its inverse v modulo q (uv is congruent to 1 modulo q).  Then
>   take the certificate signer's public key g^x and compute g' = (g^x)^u.
>   Then g'^v = g^x.  Using the DSA parameters p, q, g', the signer's public
>   key corresponds to the private key v, which the attacker knows.  The
>   attacker can then create a bogus certificate, put parameters (p, q, g')
>   in it, and sign it with the DSA private key v to create an apparently
>   valid certificate.  This works with the DSA OID that makes p, q, and g
>   unauthenticated public parameters and y the public key, but not the one
>   that makes p, q, g, and y the public key
>
>That's not leaking the private key, but it allows signature forgery via
>another mechanism that's totally unrelated to "was the fundamental DSA
>algorithm implemented correctly".  As I said, the DLP algorithms are really,
>really brittle, you have to worry about all sorts of things that aren't a
>concern with RSA.
>
>Peter.