STS Protocol

The station-to-station (STS) protocol [12] uses a signature in the exchanged messages to add authentication to the well-known Diffie-Hellman protocol [11]. This uses arithmetic in the multiplicative group of a finite field of prime order with generator $\alpha$. Exponents x and y are chosen randomly by A and B respectively and are used to form the session key $K = \alpha^{xy}$. The messages in a successful protocol run are as follows.

1.

$A \longrightarrow B: A,B,\alpha^x$

2.

$B \longrightarrow A: B,A,\alpha^y, \{S_B(\alpha^y, \alpha^x)\}_{K_{AB}}$

3.

$A \longrightarrow B: A,B,\{S_A(\alpha^x,\alpha^y)\}_{K_{AB}}$

Here $S_X(.)$ represents the signature by the principal X on the string in the brackets, while $\{M\}_K$ denotes encryption of message M using key K . The particular signature algorithm chosen does not matter for the protocol. Consider how the good key goal is achieved for A .

1.

The signature in message 2 can only be formed by B .

2.

It is not a replay from an old protocol run since A knows that $\alpha^x$ was fresh.

3.

The signature alone does not imply that B knows $K_{AB}$. Therefore the encryption with $K_{AB}$ is necessary to provide assurance that B really knows $K_{AB}$.

Thus it appears that A gains key confirmation, as well as good key with B , from message 2. With regard to user oriented goals, it seems clear that both users achieve liveness of the other, since each receives a signed message containing a value it knows to be fresh. Entity authentication is more problematic since there is no explicit inclusion of identifiers in the signed messages which could be used to deduce the desired communications partner. Recently Lowe [17] has proposed an attack on the STS protocol. The attack does not affect the key establishment properties but is addressed at whether entity authentication is achieved.

Suppose I is an intruder who wishes to attack the protocol.

• I intercepts a protocol run started by A and masquerades as B .
• In parallel I starts a protocol run with B while masquerading as A .

The attack runs as follows, where $I_X$ denotes I masquerading as principal X .

1.

$A \longrightarrow I_B: A,B,\alpha^x$

1'.

$I \longrightarrow B: I,B,\alpha^x$

2'.

$B \longrightarrow I: B,I,\alpha^y, \{S_B(\alpha^y, \alpha^x)\}_{K_{AB}}$

2.

$I_B \longrightarrow A: B,A,\alpha^y, \{S_B(\alpha^y, \alpha^x)\}_{K_{AB}}$

3.

$A \longrightarrow I_B: A,B,\{S_A(\alpha^x,\alpha^y)\}_{K_{AB}}$

The attack is very simple; I is doing little more than relaying each message that passes between A and B . What is the result? B has no indication that A has engaged in the protocol and yet A has completed a successful run, apparently with B .

Is this a successful attack on the STS protocol? The answer must be that is depends what it was believed that STS achieves.

• After the attacking run it is clear that the good key goal has not been broken.
• Key confirmation has indeed been achieved: A can be sure that B knows the shared key.
• A does not know that B knows the key is good for use with A . In other words the mutual belief in key goal does not apply.
• The attack shows that A would be wrong to conclude, after a successful run, that B wishes to communicate with her. Thus entity authentication (using the proposed extensional definition) is not achieved.

Thus the attack is valid if mutual belief in the key was a protocol goal. It may also be valid if entity authentication was a goal. However, it is interesting to note that Syverson and Van Oorschot prove in their logic [28] that the protocol satisfies their goal SVO2, which they term entity authentication. Lowe proposes [17] that the identity of the other party be included in the signatures in order to overcome the attack. This also allows an informal argument that the extensional definition of entity authentication is achieved, if the included identifier is interpreted as the name of the entity with which communication is desired.