Computer Security Exam August 2010
Question One
a)
$A$ will receive $m = g^y \mod p$ and calculate $m^x = g^{xy} \mod p$
$B$ will receive $n = g^x \mod p$ and calculate $n^y = g^{xy} \mod p$
b)
A passive attacker will only receive $m = g^y$ and $n = g^x$, the DHP
problem is the task of taking these and producing $g^{xy}$ without
knowledge of $x$ or $y$.
The DHP problem is presumed to be intractable.
c)
An active attacker $E$ can intercept and block the transmission of $m$
and $n$ then set up their own key exchanges for $A$ and $B$ independently.
$E$ can then decrypt messages sent from one principal, read them, then
encrypt them with the key for the other principal and send them on.
$E$ can also modify the messages if they so desire.
d)
$K_1 = g^{xy+ab} \mod p$:

$A$ will compute $(g^y)^x \cdot (g^b)^a = g^{yx+ba}$

$B$ will compute $(g^x)^y \cdot (g^a)^b = g^{xy+ab}$
$K_2 = g^{ay+bx} \mod p$:

$A$ will compute $(g^y)^a \cdot (g^b)^x = g^{ya+bx}$

$B$ will compute $(g^x)^b \cdot (g^a)^y = g^{xb+ay}$
$K_3 = g^{ay+bx+xy} \mod p$:

$A$ will take the same steps as for $K_2$ then multiply by the
original DiffieHellman key.

$B$ will do the same.
e)
Passive attacker:
In each step, a passive attacker can only ever acquire $g^k$ where $k$
is one of $a, b, x, y$ and as such is still thwarted by the intractability
of the DHP problem.
Active attacker:
In each of the cases, the active attacker will not know $a$ or $b$. In
each case, knowledge of $a$ and $b$ would be required for a MITM attack.
As the DLP problem is intractable the attacker cannot compute $a$ or $b$.
f)
Case $K_1$:
The attacker $E$ with knowledge of $a$ and $b$ can calculate $g^{ab}$
easily, but this reduces the problem to a passive attack on the original
DiffieHellman, which we know is intractable.
Case $K_2$:
$E$ knows $a$ and $b$
and $g^x$ and $g^y$, as a result, $E$ can easily
compute both $g^{ay}$ and $g^{bx}$, so $K_2$ is compromised.
Case $K_3$:
$E$ can calculate $g^{ay}$ and $g^{bx}$ in the same way as case $K_2$ but
this again just reduces the problem to a passive attack on the original
DiffieHellman and is intractable