User:TomYu/PKINIT notes

Diffie-Hellman

PKINIT uses the well-known IKE (Oakley) MODP group 2 (RFC 2409, RFC 2412), along with IKE MODP groups 14, and 16 (RFC 3526) when doing Diffie-Hellman key agreement. These groups are modulo safe primes, i.e., p = 2q + 1. They use 2 as a generator, and the primes are chosen so that 2 generates the subgroup of order q, to prevent the leaking of the least significant bit of the private exponent x via the Legendre symbol of the public key g^x.

D-H number theory

A safe prime is of the form p = 2q + 1, where q is prime. To be cryptographically useful, p is a large (odd) prime, therefore p ≡ 1 (mod 2). Also, p ≡ 2 (mod 3), as is q, because either p or q being congruent to 1 (mod 3) implies that the other is divisible by 3. (This is only true if q ≠ 3, which is true for cryptographically useful primes.) By the Chinese remainder theorem, this means p ≡ 5 (mod 6). 2 generates the subgroup of size q if 2 is a quadratic residue mod p. According to the law of quadratic reciprocity, for 2 to be a quadratic residue mod p, p ≡ ±1 (mod 8). If p is a safe prime, it can't be 1 (mod 8) because that would mean that q is not prime.

OpenSSL issues

The OpenSSL DH_check() tests could fail on the IKE MODP groups, because DH_check() applies the test p ≡ 11 (mod 24) for a generator of 2. The prime consequently has to also satisfy the congruences p ≡ 2 (mod 3) and p ≡ 3 (mod 8). The congruence p ≡ ±3 (mod 8) is true if 2 is not a quadratic residue mod p, which means that DH_check() is checking that 2 will generate the entire group modulo p. (p ≡ 5 (mod 8) implies q is an even number.) The code in DH_check() in newer versions of OpenSSL does additional checks if the q parameter is given, which include g^q ≡ 1 (mod p) (g generates the subgroup of order q if q is prime), p ≡ 1 (mod q) (q divides p - 1), and that q is prime. These checks on the q parameter supersede the check that the generator would generate the entire group mod p.

Windows 7 interop

• Windows 7 clients omit the q value in DomainParameters when sending PA-PK-AS-REQ [krbdev.mit.edu #7596]
• Even after allowing the omission of the q value, Windows 7 doesn't seem to deal with Diffie-Hellman group negotiation. (The KDC has to accept the 1024-bit modulus, because the counterproposal of the 2048-bit modulus fails on the client somehow.)