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:

https://cpunks.org/pipermail/cypherpunks/2015-September/009007.html

 

1. RFC-2631 Diffie-Hellman Key Agreement Method

https://tools.ietf.org/html/rfc2631

 

The main problem appears:

https://tools.ietf.org/html/rfc2631#section-2.2.2

 

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.

Outcomes