Difference between revisions of "User:TomYu/PKINIT notes"
| Line 1: | Line 1: | ||
== Diffie-Hellman == |
== Diffie-Hellman == |
||
| − | * Oakley MODP groups (used in PKINIT) have safe primes as moduli |
||
| + | PKINIT uses the well-known Oakley MODP groups ({{rfcref|2412}}) when doing Diffie-Hellman key agreement. These groups are modulo safe primes, i.e., ''p'' = 2''q'' + 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 via the [[wp:Legendre symbol|Legendre symbol]] of the public key. |
||
| − | ** 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 === |
=== D-H number theory === |
||
| − | + | A safe prime is of the form ''p'' = 2''q'' + 1, where ''q'' is prime. To be cryptographically useful, ''p'' is a large 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 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. |
|
| + | |||
| + | === OpenSSL issues === |
||
| + | |||
| + | The OpenSSL DH_check() tests cannot succeed on the Oakley 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''. The code in DH_check in newer versions of OpenSSL does additional checks if the ''q'' parameter is given, which include ''g''<sup>''q''</sup> ≡ 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. |
||
=== Windows 7 interop === |
=== Windows 7 interop === |
||
Revision as of 16:47, 11 April 2013
Diffie-Hellman
PKINIT uses the well-known Oakley MODP groups (RFC 2412) 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 via the Legendre symbol of the public key.
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 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 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.
OpenSSL issues
The OpenSSL DH_check() tests cannot succeed on the Oakley 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. The code in DH_check in newer versions of OpenSSL does additional checks if the q parameter is given, which include gq ≡ 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.
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.)
