RE: DH group exchange (Re: SSH key algorithm updates)

[Peter Gutmann <[e-mail]>]

Mark D. Baushke <[e-mail]> writes:

>The root case is the selection of the generator g in RFC 4419 is not
>sufficient to meet FIPS requirements.

Since RFC 4419 doesn't specify that q is included in the DH keying material,
how do you even verify that it meets FIPS requirements?  You can't actually
perform the FIPS tests on it because one of the parameters is missing.  At
best you can do a test on... well, I'll post my source code comment:

/* There is a further check that we can perform on p, but it's rather
   problematic because it only works for "safe" primes (primes of the form p =
   2p' + 1), and even then the checks depend on your religious inclinations,
   you've got the choice of either choosing a value where the generated DH
   secret is limited to half the possible values, or one where you leak a bit
   of the secret exponent.  For example for g=2, if p is congruent to 11 mod
   24 then g is a quadratic nonresidue and the DH secret covers all possible
   values but you leak the LSB of the secret exponent, but if p is congruent
   to 11 mod 23 then g is a quadratic residue and the DH secret only covers
   half the possible values, but you don't leak any bits of the exponent (for
   OpenSSH's g=5, the values are 3 and 7).

   Once you go to more general values of g, or FIPS 186 primes which should be
   easily verifiable but aren't because the PKCS #3 form discards the q value
   that you need for the verification, there isn't really any checking that
   can be done.  The result is an ugly yes-biased test that can say
   "definitely safe" but only "possibly unsafe" (unless we're willing to deal
   with lots of false positives).

   Because of this we only complain about problems in debug mode, if we
   enabled the rejection of unverifiable primes in release code we'd Get
   Letters... */
switch( BN_get_word( g ) )
	{
	case 2:
		/* Oakley primes, congruent to 11 mod 24 = leaks LSB, 
		   congruent to 23 mod 24 = only covers half the possible 
		   values */
		modWord = BN_mod_word( p, 24 );
		assert_nofuzz( modWord == 11 || modWord == 23 );
		break;

	case 5:
		/* Used by OpenSSH for no known reason */
		modWord = BN_mod_word( p, 10 );
		assert_nofuzz( modWord == 3 || modWord == 7 );
		break;

	default:
		assert_nofuzz( DEBUG_WARN );
	}

Oh, if anyone knows of any other commonly-used magic values I'm missing there,
let me know.

The real fix though would be to publish a quick update to '4419 specifying a
SSH_MSG_KEX_DH_GEX2_GROUP which includes the full set of DH parameters so that
the DH values could be fully verified.

Peter.