Computer Security Exam August 2010

Question One


$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$


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.


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.


$K_1 = g^{xy+ab} \mod p$:

$K_2 = g^{ay+bx} \mod p$:

$K_3 = g^{ay+bx+xy} \mod p$:


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$.


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 Diffie-Hellman, 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 Diffie-Hellman and is intractable