Possible crypto backdoor in RFC-2631 Diffie-Hellman Key Agreement Method

Georgi Guninski guninski at guninski.com
Thu Sep 3 04:27:21 PDT 2015

Possible crypto backdoor in RFC-2631 Diffie-Hellman Key Agreement Method

I am n00b at crypto so this might not make any sense.

In DH, if one can select group parameters (g,q,p) he can break both parties
private very fast time IMHO.

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

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 modulo $p_i$ for the public keys.

Apply the Chinese remainder theorem to get the privates keys.

(This is well known method for DL and for this reason
the group order must be prime [160 bits ;)]).

Would be interested how implementations implement this MAY.

Let me know if there is better list for this.


More information about the cypherpunks mailing list