[cryptography] RFC-2631, fips 186-3 and openssl's implementation of DSA appear broken (and possibly backdoored)

Georgi Guninski guninski at guninski.com
Sat Sep 5 07:04:54 EDT 2015


Per discussions on cypherpunks and this blog:

https://j.ludost.net/blog/archives/2015/09/05/rfc-2631_fips_186-3_and_openssls_implementation_of_dsa_appear_broken_and_possibly_backdoored/index.html


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.

(Peter Gutmann confirmed this)

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) {
        DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
        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.

Session:

 ./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



Troll friendly:  libressl-2.2.3 appears affected too,
independent verification would be appreciated.



More information about the cryptography mailing list