Sat Sep 5 10:49:05 EEST 2015

RFC-2631, fips 186-3 and openssl's implementation of DSA appear 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.

2. From the openssl 1.0.1p source: crypto/dsa/dsa_ossl.c:329

   i = BN_num_bits(dsa->q);
    /* fips 186-3 allows only different sizes for q */
    if (i != 160 && i != 224 && i != 256) {
        return -1;

Forcing small subgroups smells to me...

3. openssl 1.0.1p accepts composite $q$ in sign/verify
and over SSL (DSA). The attack in (1) works the same way.


 ./apps/openssl s_server -accept 8080 -cert ./cacert2.pem -key ./key-comp2.key -HTTP

 openssl s_client -connect localhost:8080

 Server public key is 1204 bit
 Verify return code: 18 (self signed certificate)

 sage: q=0x008000000000000000001d8000000000000000012b
 sage: factor(q)
 604462909807314587353111 * 1208925819614629174706189

Posted by jcrank | Permanent link