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