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

[Peter Gutmann]

Alfonso De Gregorio <alfonso.degregorio at gmail.com> writes:

>Sure, the questions are: What is the origin of the current wording of the
>standard, that opens an avenue for lax checks for group parameters? Or, if,
>as you correctly pointed out, an implementation MAY NOT check group
>parameters, which entity deserves credit for it?

You need to go back to the original source of all the DLP stuff, which is DSA
/ FIPS 186.  Now that didn't require any validation of anything until FIPS
186-3 came along in June 2009, and that in turn points to SP 800-89, which has
a section 4 "Assurance of Domain Parameter Validity".  This one gets really
complicated because you can get the domain parameters from all over the place
(generated yourself, provided for you by a third party, found at the bottom of
a locked filing cabinet stuck in a disused lavatory with a sign on the door
saying 'Beware of the Leopard', ...).

So if you generate them yourself, you're OK.  If you get them from a CA then
you don't need to care because if the CA wants to attack you then they can
just issue a forged cert in your name and don't need to worry about
backdooring the params (in any case using shared params is a bad idea because
they allow forgery of signatures on certificates. Suppose that the certificate
contains a copy of the certificate signer's DSA parameters, and the verifier
of the certificate has a copy of the signer's public key but not the signer's
DSA parameters (which are shared with other keys). If the verifier uses the
DSA parameters from the certificate along with the signer's public key to
verify the signature on the certificate, then an attacker can create bogus
certificates by choosing a random u and finding its inverse v modulo q (uv is
congruent to 1 modulo q).  Then take the certificate signer's public key g^x
and compute g' = (g^x)^u. Then g'^v = g^x.  Using the DSA parameters p, q, g',
the signer's public key corresponds to the private key v, which the attacker
knows.  The attacker can then create a bogus certificate, put parameters (p,
q, g') in it, and sign it with the DSA private key v to create an apparently
valid certificate).

Finally, if you get them from the disused lavatory then you deserve everything
you get^H^H^H^H^H^H^H^HFIPS 186-3 has validation requirements that use the
optional j and seed parameters, but I've never seen them used anywhere so even
though the validation requirements exist, you can't apply them.

The real question though is, why would anyone use parameters they didn't
generate themselves?  All DSA implementations I've seen (apart from some
experimental code from the 1990s, which also encoded the j/seed values)
generate all the parameters themselves, it's not like ECDSA where everyone
ends up using some shared values that a "trusted" external party provides
them.

Peter.