BlueHat v13 crypto talks - request for leaks ;)

[Peter Gutmann]

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.