# 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 Diffie-Hellman 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 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