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.