User:TomYu/PKINIT notes

Diffie-Hellman

• Oakley MODP groups (used in PKINIT) have safe primes as moduli
  • These primes don't satisfy the OpenSSL DH_check() tests, so there can be some confusion when debugging
  • The generator generates the subgroup of order q instead of the whole group. (OpenSSL wants it to generate the whole group -- the test is p = 11 mod 24, which includes the test p = 3 mod 8, which is false if 2 is a quadratic residue mod p.)

D-H number theory

Safe prime 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 one being congruent to 1 mod 3 implies the other is divisible by 3. (This is only true if q ≠ 3.) By Chinese Remainder Theorem, this means p ≡ 5 (mod 6). 2 generates the subgroup of size q if 2 is a quadratic residue mod p. For 2 to be a quadratic residue mod p, it must be ±1 mod 8, and it can't be 1 mod 8 because that would mean that q is not prime.

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