Notes - Computer Security MT24, Diffie-Hellman key exchange
Flashcards
Describe the Diffie-Hellman key exchange @algorithm, which Alice and Bob can use to generate a symmetric session key over an insecure channel.
Key generation:
- Alice picks a random integer $s _ a$.
- Bob picks a random integer $s _ b$.
- Alice and Bob agree on a large prime number $p$ and a number (not necessarily prime) $g$.
Determining symmetric session key:
- Alice sends Bob $a := g^{s _ a} \pmod p$
- Bob sends Alice $b := g^{s _ b} \pmod p$
- Alice computes $b^{s _ a} \pmod p$
- Bob computes $a^{s _ b} \pmod p$.
- Now Alice and Bob both have the integer $g^{s _ a s _ b} \pmod p$, which they can use to generate a session key.
@Define the discrete logarithm problem.
Given $m$, $n$ and $m^x \pmod n$, compute $x$.
The discrete logarithm problem is:
- Given $m$, $n$ and $m^x \pmod n$, compute $x$.
The Diffie-Hellman key exchange algorithm for determining a session key is as follows:
-
Key generation:
- Alice picks a random integer $s _ a$.
- Bob picks a random integer $s _ b$.
- Alice and Bob agree on a large prime number $p$ and a number (not necessarily prime) $g$.
-
Determining symmetric session key:
- Alice sends Bob $a := g^{s _ a} \pmod p$
- Bob sends Alice $b := g^{s _ b} \pmod p$
- Alice computes $b^{s _ a} \pmod p$
- Bob computes $a^{s _ b} \pmod p$.
- Now Alice and Bob both have the integer $g^{s _ a s _ b} \pmod p$, which they can use to generate a session key.
If an attack has an efficient algorithm for the discrete logarithm problem, how can they break the Diffie-Hellman key exchange algorithm?
- Alice picks a random integer $s _ a$.
- Bob picks a random integer $s _ b$.
- Alice and Bob agree on a large prime number $p$ and a number (not necessarily prime) $g$.
- Alice sends Bob $a := g^{s _ a} \pmod p$
- Bob sends Alice $b := g^{s _ b} \pmod p$
- Alice computes $b^{s _ a} \pmod p$
- Bob computes $a^{s _ b} \pmod p$.
- Now Alice and Bob both have the integer $g^{s _ a s _ b} \pmod p$, which they can use to generate a session key.
- From $a$ they can compute $s _ a$ and from $b$ they can compute $s _ b$.
- Since $g$ and $p$ are known, they can determine the session key $g^{s _ a s _ b}$.
The Diffie-Hellman key exchange algorithm for determining a session key is as follows:
-
Key generation:
- Alice picks a random integer $s _ a$.
- Bob picks a random integer $s _ b$.
- Alice and Bob agree on a large prime number $p$ and a number (not necessarily prime) $g$.
-
Determining symmetric session key:
- Alice sends Bob $a := g^{s _ a} \pmod p$
- Bob sends Alice $b := g^{s _ b} \pmod p$
- Alice computes $b^{s _ a} \pmod p$
- Bob computes $a^{s _ b} \pmod p$.
- Now Alice and Bob both have the integer $g^{s _ a s _ b} \pmod p$, which they can use to generate a session key.
Why is this algorithm insecure against a man-in-the-middle attack?
- Alice picks a random integer $s _ a$.
- Bob picks a random integer $s _ b$.
- Alice and Bob agree on a large prime number $p$ and a number (not necessarily prime) $g$.
- Alice sends Bob $a := g^{s _ a} \pmod p$
- Bob sends Alice $b := g^{s _ b} \pmod p$
- Alice computes $b^{s _ a} \pmod p$
- Bob computes $a^{s _ b} \pmod p$.
- Now Alice and Bob both have the integer $g^{s _ a s _ b} \pmod p$, which they can use to generate a session key.
An attacker could share their own $a$ and $b$ with Bob and Alice, rather than letting them see each others.