Incorrect Implementation

In [RS97], an attack on an implementation of the recursive authentication protocol is described. The implementation decision which leads to the attack is straightforward. The server computes the certificates as $K_{ab} \bigoplus \mathsf{Hash}_{K_a}\{Na\}$,where `$\bigoplus$' represents the bitwise XOR of two bit strings.

To see that this is insecure, note that (with three agents in the chain) the server returns certificates of the form

$$K_{ab} \bigoplus \mathsf{Hash}_{K_a}\{Na\}, K_{ab} \bigoplu... ...Hash}_{K_b}\{Nb\}, K_{cs} \bigoplus \mathsf{Hash}_{K_c}\{Nc\},$$

Anyone in possession of these certificates (and they are all broadcast across the network) can compute xor'd pairs of session keys, as

$$K_{ab} \bigoplus \mathsf{Hash}_{K_b}\{Nb\} \bigoplus K_{bc} \bigoplus \mathsf{Hash}_{K_b}\{Nb\} = K_{ab} \bigoplus K_{bc}$$

Thus if the enemy knows one session key, he may compute all others.