AnsweredAssumed Answered

OPENSSL implementation of DSA appears broken (and possibly backdoored)

Question asked by _ck_ on Sep 5, 2015
Latest reply on Sep 6, 2015 by Lily Wilson

RFC-2631, fips 186-3 and openssl's implementation of DSAappear broken (and possibly backdoored) | ___



The discsussion, certs and keys are at this thread:


1. RFC-2631 Diffie-Hellman Key Agreement Method


The main problem appears:


2.2.2. Group Parameter Validation

  The ASN.1 for DH keys in [PKIX] includes elements j and validation-

  Parms which MAY be used by recipients of a key to verify that the

  group parameters were correctly generated. Two checks are possible:


  1. Verify that p=qj + 1. This demonstrates that the parameters meet

  the X9.42 parameter criteria.

  2. Verify that when the p,q generation procedure of [FIPS-186]

  Appendix 2 is followed with seed 'seed', that p is found when

  'counter' = pgenCounter.



The main problem appears MAY.


As I read it, implementation MAY NOT verify it.


Sketch of the attack:


Chose $q$ product of small primes $p_i$.


Solve the discrete logarithm in the $p_i$ subgroups for the public keys.


Apply the Chinese remainder theorem to get the privates keys.