On Sat, Dec 14, 2013 at 2:55 AM, Tom Ritter <tom@ritter.vg> wrote:

I can answer for Cryptopocalype. :) I had a follow-up blog post after Black Hat, but the crux is looking for the next crypto black swan. Joux's work in optimizing the function field sieve for fields of a small characteristic has been a significance improvement kind of out of left field. If he or anyone else made improvements to the FFS for fields of a large characteristic or the GNFS - we would be in a bad way. The security margin on the ECDLP is greater than DL or factoring and while we've got the algorithms, the implementations are sometimes missing and the ability to pivot, in software update mechanisms, in CAs, everywhere - is completely missing. ECC has other attributes that make it attractive too, so let's get the plumbing ready, so we can support a quick pivot away from RSA and over to ECC if we have to...

thanks! for posterity, the post is at: http://ritter.vg/blog-cryptopocalypse_followup.html

On 14 December 2013 14:51, Peter Gutmann <pgut001@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? -tom

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@ritter.vg> writes:

...

On 14 December 2013 14:51, Peter Gutmann <pgut001@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.

On Sat, Dec 14, 2013 at 11:51 AM, Peter Gutmann <pgut001@cs.auckland.ac.nz> wrote:

[topic hijack in 3.. 2... ]

Peter's BlueHat talk on congitively flawed humans also excellent: http://www.cs.auckland.ac.nz/~pgut001/pubs/psychology.pdf so cypherpunks, if you write code that you want to be useful: don't write code with assumptions and admonishments inherently unheedable. write code with awareness and compensation for silly human inclinations!