# User:TomYu/PKINIT notes

Line 1: | Line 1: | ||

== Diffie-Hellman == |
== 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 === |
=== 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 === |
=== 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 === |
=== Windows 7 interop === |

## Latest revision as of 23:58, 11 April 2013

## Contents |

## [edit] 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* = 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 Legendre symbol of the public key *g*^{x}.

### [edit] 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 (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.

### [edit] 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*.

### [edit] 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.)