Results of Using the Analyzer

We posed four questions to the Analyzer. In the first two, we asked it whether or not if could find X and ecbc(K,X,notsent) or X and dcbc(K,X,notsent), using our initial model of chosen pairs for cipher block chaining. The Analyzer found these attacks easily in a few seconds. For chosen ciphertext, the Analyzer found an attack in four steps.

1.

Host A encrypts message header from honest user U at to dishonest user V at Host B.

2.

V sends IV and encrypted header EH on to B.

3.

V appends notsent to EH as the next part of the encrypted message. This is also sent to B.

4.

B decrypts message, and returns dcbc(K,X,notsent) to the intruder, where X is the last part of the encrypted header. The intruder of course has already learned this from Step 2.

The Analyzer also produced the trivial chosen plaintext attack: The intruder includes notsent as part of a message to be encrypted. Since the input X to ecbc(K,X,notsent) is just the previous encrypted block of the message, the intruder is easily able to produce X and ecbc(K,X,notsent) in this way.

This was the spurious attack. In the actual ESP protocol, the attacker would see X, but would not see it before it sent notsent to the to the host to be encrypted. Thus it would not be able use its knowledge of X to influence its choice of notsent. Realization of our mistake lead not only to a revision of the specification, which is in progress, but to the revision of our definition of chosen pairs that we described in Section 3.3.

The Analyzer also found a number of attacks similar to Bellovin's. We generated a spoofing attack by asking the Analyzer if it could find a state in which Host A could enter a state in which its value for the originator of a message was an honest user U2, but the value for the decrypted block was notsent. It returned, among other things, the following path:

1,2,3.

Host A encrypts a message M1 from dishonest user V to some user U1 at host B. The first part of the message is a header for a message M2 from an honest user U2. The rest is the spoofed message the intruder wants to send. After encrypting, the intruder removes the encrypted message header. V sends the three encrypted blocks to B, passing off the first block as the IV. A fourth random block could be included to make up the entire packet, although this step was not included by the Analyzer.

4.

B decrypts the apparent first part of the message, and accepts that as the header.

5.

B decrypts the apparent rest of the message, and accepts that as the message from E.

Bellovin describes a similar attack in [3]. In his attack a a legitimate message M2 is sent from U1 to U2. The intruder constructs a message M1, and then cuts off the portions after the headers on M1 and M2. The last portion of M1 is appended to the first part of M2. This attack is somewhat stronger than ours, since it allows an intruder to hijack a session without necessarily knowing the header associated with that session. We expect that we can also produce this attack as we continue our search.

The Analyzer found an unauthorized disclosure attack in seven steps. We produced this by representing a block of a message produced to be sent from user(U1,honest) at host A to user(U2,honest) at host B as message(user(U1,honest),user(U2,honest),ts(host(A),N),Num) where Num indicates the block's position in the packet and ts(host(A),N) is a host timestamp guaranteeing the uniqueness of the message. The following path of attack was found:

1,2.

Honest user U1 at Host A encrypts a message to another honest user U2 at Host B. This takes two steps in the Analyzer, one to encrypt the header, and one to encrypt the rest of the message (actually, the first word of the rest of the message; this was all the Analyzer needed to find the attack). The result of this is IV1, EncryptedHeader1, Message1.

3.

Another user U3 at Host A encrypts a message to dishonest user V at Host B. In this case, all we are interested in is the header, so this only takes one step. The result of this is IV2, Encryptedheader2.

The intruder sends the message IV2, EncryptedHeader2, EncryptedHeader1, Message1 to Host B.

4.

Host B decrypts the header, and concludes that the remainder of the message will be for the dishonest user V.

5.

Host B uses EncryptedHeader 2 to decrypt Encrypted Header1, which is garbage.

6.

Host B uses EncryptedHeader1 to decrypt Message1.

7.

Host B passes Message1 to the intruder.

Note that the garbage decryption of EncryptedHeader1 is also passed on to the intruder, but, since this does not aid in the attack, it does not appear in the search.

This is exactly the unauthorized disclosure attack found by Bellovin.