User:TomYu/PKINIT notes - Revision history

TomYu at 03:58, 12 April 2013

2013-04-12T03:58:02Z

TomYu at 21:47, 11 April 2013

2013-04-11T21:47:38Z

TomYu at 02:10, 11 April 2013

2013-04-11T02:10:51Z

TomYu: New page: == 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 debug...

2013-04-08T20:35:55Z

New page: == 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 debug...

New page

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

* Windows 7 clients omit the ''q'' value in DomainParameters when sending PA-PK-AS-REQ {{bug|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.)

@@ Line 1: / Line 1: @@
 == Diffie-Hellman ==
-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.
+PKINIT uses the well-known IKE (Oakley) MODP group 2 ({{rfcref|2409}}, {{rfcref|2412}}), along with IKE MODP groups 14, and 16 ({{rfcref|3526}}) 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 ''x'' via the [[wp:Legendre symbol|Legendre symbol]] of the public key ''g''<sup>''x''</sup>.
 === 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.
+A safe prime is of the form ''p'' = 2''q'' + 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 [[wp:Chinese remainder theorem|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 [[wp:Quadratic reciprocity|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 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.
+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''<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.  These checks on the ''q'' parameter supersede the check that the generator would generate the entire group mod ''p''.
 === Windows 7 interop ===

@@ Line 1: / Line 1: @@
 == Diffie-Hellman ==
 === D-H number theory ===
-Safe prime ''p'' = 2''q'' + 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.
+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.
 === Windows 7 interop ===

@@ Line 4: / Line 4: @@
 ** 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''.)
 * Windows 7 clients omit the ''q'' value in DomainParameters when sending PA-PK-AS-REQ {{bug|7596}}