We speculate that if protocol designers fail to spot this inadequacy in the speci¬-

cation of their protocols, the protocol implementers are also highly unlikely to spot

this inadequacy until speci¬c attacks have been demonstrated, as suggested by Ble-

ichenbacher [4].

Having identi¬ed the ¬‚aw in the security proof for the MT-authenticator, we provide

a revised MT-authenticator. As a result, protocols using the revised encryption based

MT-authenticator will no longer be ¬‚awed due to their use of this MT-authenticator.

The notation used throughout this section is as follows: the notation {·}KU denotes

an encryption of some message m under U™s public key, KU ; and MACK (m) denotes

the computation of MAC digest of some message m under key K.

8.4.1 Encryption-Based MT-Authenticator

Figure 8.2 describes the encryption based MT-authenticator, which is based on a

public-key encryption scheme indistinguishable under chosen-ciphertext attack and

the authentication technique used by Krawczyk [20]. Note that the speci¬cation of

the encryption-based MT-authenticator does not specify the deletion of the received

nonce vA from B™s internal state before sending out the last message. Note that vA is

also the one-time MAC key.

A B

sid, m

←’ ’ ’

’ ’ ’’

Choose nonce vA Choose message m

sid, m, {vA }KB

’’ ’ ’

’ ’ ’’ Decrypt {vA }KB

sid, m, MACvA (m, A)

Verify MACvA (m, A) ←’ ’ ’

’ ’ ’’ Compute MACvA (m, A)

Fig. 8.2 Bellare“Canetti“Krawczyk encryption-based MT-authenticator

8.4 An MT-Authenticator 139

8.4.2 Flaw in Existing Security Proof Revealed

In the usual tradition of reductionist proofs, the existing MT-authenticator proof [3]

assumes that there exists an adversary A who can break the MT-authenticator. An

encryption-aided MAC forger, F , is constructed using such an adversary, A , against

the unforgeability of the underlying MAC scheme. Subsequently, the encryption-

aided MAC forger, F , can be used to break the encryption scheme. The MAC forger,

F , who has access to a MAC oracle, is easily constructed as follows:

• guess at random an index i,

• for all but the i-th session, generate a key vk and answer queries as expected,

• if A calls a Session-State Reveal4 on any session other than the i-th session, the

response can easily be simulated,

• if A calls a Session-State Reveal on the i-th session, F aborts.

The assumption is that if A has a non-negligible advantage against the underlying

protocol, then F has a non-negligible probability of forging a MAC digest.

Consider the scenario shown in Attack 8.4. When A asks for the one-time MAC

key, vk , with a Session-State Reveal query, it is perfectly legitimate since this ses-

sion with SID of sid j is not the i-th session with SID of sidi . Recall that sessions

with non-matching SIDs (i.e., sidi = sid j ) are non-partners.

A

A B

sid j , m

←’ ’ ’

’ ’ ’’

Intercept

sidi , m

←’ ’ ’

’ ’ ’’ Fabricate

sidi , m , {vA }KB

’’ ’ ’

’ ’ ’’ Intercept

sid j , m, {vA }KB

’’ ’ ’

’ ’ ’’

Fabricate

sid j , m, MACvA (m, A)

←’ ’ ’

’ ’ ’’

Session’State Reveal(sid j )

’’ ’ ’

’ ’ ’’

sidi , m , MACvA (m , A) v

← ’ A’ ’

←’ ’ ’

’ ’ ’’ ’’ ’ ’

Fabricate

Attack 8.4: An example execution of encryption-based MT-authenticator

F is unable to answer such a query since vA is a secret key. Note that the MAC or-

acle to which F has access is associated with vA , but F does not know vA . Hence,

the proof simulation is aborted and F fails. F does not have a non-negligible prob-

ability of forging a MAC digest (since it fails), although A has a non-negligible

4Note that in the original paper of Bellare, Canetti, and Krawczyk [3], a Session-State Reveal is

known as a Session-Corruption query.

140 8 Errors in Computational Complexity Proofs for Protocols

advantage against the security of the underlying protocol, in violation of the under-

lying assumption in the proof.

We note that in a later independent yet related work by Tian and Wong [24],the

same ¬‚aw in the security proof for the encryption-based MT-authenticator described

in Attack 8.4 was presented.

8.4.3 Addressing the Flaw

We propose that the party concerned in the encryption-based MT-authenticator de-

scribed in Figure 8.2 to delete the received nonce from its internal state before

sending out the MAC digest computed using the received nonce, as described in

Figure 8.3.

A B

sid, m

←’ ’ ’

’ ’ ’’

Choose nonce vA Choose message m

sid, m, {vA }KB

’’ ’ ’

’ ’ ’’ Decrypt {vA }KB

Compute MACvA (m, A)

sid, m, MACvA (m, A)

Verify MACvA (m, A) ←’ ’ ’

’ ’ ’’ Delete vA

Fig. 8.3 A revised encryption-based MT-authenticator

As a result, the adversary, A , will not be able to obtain the value of vA using a

Session-State Reveal query. In the proof of the security of the MT-authenticator,

therefore, the encryption-aided MAC forger, F , will be able to answer such a query

because F is no longer required to return the value of vA . Attack 8.4 will no longer

be valid, since A will no longer be able to obtain the value of vA and fabricate a

MAC digest.