<table><caption>**Figure 13:** Chosen-prefix collision for SHA-1. The colors show the **prefix**, the **birthday bits**, and the **near-collision blocks**. Both messages lead to the same SHA-1 value: 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0</caption><thead><tr><th></th><th>Message A</th><th>Message B</th></tr></thead><tbody><tr><td>0x0000</td><td>99 04 0d 04 7f e8 17 80 01 20 00 ff 4b 65 79 20<br>69 73 20 70 61 72 74 20 6f 66 20 61 20 63 6f 6c<br>6c 69 73 69 6f 6e 21 20 49 74 27 73 20 61 20 74<br>72 61 70 21 79 c6 1a f0 af cc 05 45 15 d9 27 4e</td><td>99 03 0d 04 7f e8 17 80 01 18 00 ff 50 72 61 63<br>74 69 63 61 6c 20 53 48 41 2d 31 20 63 68 6f 73<br>65 6e 2d 70 72 65 66 69 78 20 63 6f 6c 6c 69 73<br>69 6f 6e 21 1d 27 6c 6b a6 61 e1 04 0e 1f 7d 76</td></tr><tr><td>0x0040</td><td>73 07 62 4b 1d c7 fb 23 98 8b b8 de 8b 57 5d ba<br>7b 9e ab 31 c1 67 4b 6d 97 43 78 a8 27 73 2f f5<br>85 1c 76 a2 e6 07 72 b5 a4 7c e1 ea c4 0b b9 93<br>c1 2d 8c 70 e2 4a 4f 8d 5f cd ed c1 b3 2c 9c f1</td><td>7f 07 62 49 dd c7 fb 33 2c 8b b8 c2 b7 57 5d be<br>c7 9e ab 2b e1 67 4b 7d b3 43 78 b4 cb 73 2f e1<br>89 1c 76 a0 26 07 72 a5 10 7c e1 f6 e8 0b b9 97<br>7d 2d 8c 68 52 4a 4f 9d 5f cd ed cd 0b 2c 9c e1</td></tr><tr><td>0x0080</td><td>9e 31 af 24 29 75 9d 42 e4 df db 31 71 9f 58 76<br>23 ee 55 29 39 b6 dc dc 45 9f ca 53 55 3b 70 f8<br>7e de 30 a2 47 ea 3a f6 c7 59 a2 f2 0b 32 0d 76<br>0d b6 4f f4 79 08 4f d3 cc b3 cd d4 83 62 d9 6a</td><td>92 31 af 26 e9 75 9d 52 50 df db 2d 4d 9f 58 72<br>9f ee 55 33 19 b6 dc cc 61 9f ca 4f b9 3b 70 ec<br>72 de 30 a0 87 ea 3a e6 73 59 a2 ee 27 32 0d 72<br>b1 b6 4f ec c9 08 4f c3 cc b3 cd d8 3b 62 d9 7a</td></tr><tr><td>0x00c0</td><td>9c 43 06 17 ca ff 6c 36 c6 37 e5 3f de 28 41 7f<br>62 6f ec 54 ed 79 43 a4 6e 5f 57 30 f2 bb 38 fb<br>1d f6 e0 09 00 10 d0 0e 24 ad 78 bf 92 64 19 93<br>60 8e 8d 15 8a 78 9f 34 c4 6f e1 e6 02 7f 35 a4</td><td>90 43 06 15 0a ff 6c 26 72 37 e5 23 e2 28 41 7b<br>de 6f ec 4e cd 79 43 b4 4a 5f 57 2c 1e bb 38 ef<br>11 f6 e0 0b c0 10 d0 1e 90 ad 78 a3 be 64 19 97<br>dc 8e 8d 0d 3a 78 9f 24 c4 6f e1 ea ba 7f 35 b4</td></tr><tr><td>0x0100</td><td>cb fb 82 70 76 c5 0e ca 0e 8b 7c ca 69 bb 2c 2b<br>79 02 59 f9 bf 95 70 dd 8d 44 37 a3 11 5f af f7<br>c3 ca c0 9a d2 52 66 05 5c 27 10 47 55 17 8e ae<br>ff 82 5a 2c aa 2a cf b5 de 64 ce 76 41 dc 59 a5</td><td>c7 fb 82 72 b6 c5 0e da ba 8b 7c d6 55 bb 2c 2f<br>c5 02 59 e3 9f 95 70 cd a9 44 37 bf fd 5f af e3<br>cf ca c0 98 12 52 66 15 e8 27 10 5b 79 17 8e aa<br>43 82 5a 34 1a 2a cf a5 de 64 ce 7a f9 dc 59 b5</td></tr><tr><td>0x0140</td><td>41 a9 fc 9c 75 67 56 e2 e2 3d c7 13 c8 c2 4c 97<br>90 aa 6b 0e 38 a7 f5 5f 14 45 2a 1c a2 85 0d dd<br>95 62 fd 9a 18 ad 42 49 6a a9 70 08 f7 46 72 f6<br>8e f4 61 eb 88 b0 99 33 d6 26 b4 f9 18 74 9c c0</td><td>4d a9 fc 9e b5 67 56 f2 56 3d c7 0f f4 c2 4c 93<br>2c aa 6b 14 18 a7 f5 4f 30 45 2a 00 4e 85 0d c9<br>99 62 fd 98 d8 ad 42 59 de a9 70 14 db 46 72 f2<br>32 f4 61 f3 38 b0 99 23 d6 26 b4 f5 a0 74 9c d0</td></tr><tr><td>0x0180</td><td>27 fd dd 6c 42 5f c4 21 68 35 d0 13 4d 15 28 5b<br>ab 2c b7 84 a4 f7 cb b4 fb 51 4d 4b f0 f6 23 7c<br>f0 0a 9e 9f 13 2b 9a 06 6e 6f d1 7f 6c 42 98 74<br>78 58 6f f6 51 af 96 74 7f b4 26 b9 87 2b 9a 88</td><td>2b fd dd 6e 82 5f c4 31 dc 35 d0 0f 71 15 28 5f<br>17 2c b7 9e 84 f7 cb a4 df 51 4d 57 1c f6 23 68<br>fc 0a 9e 9d d3 2b 9a 16 da 6f d1 63 40 42 98 70<br>c4 58 6f ee e1 af 96 64 7f b4 26 b5 3f 2b 9a 98</td></tr><tr><td>0x01c0</td><td>e4 06 3f 59 bb 33 4c c0 06 50 f8 3a 80 c4 27 51<br>b7 19 74 d3 00 fc 28 19 a2 e8 f1 e3 2c 1b 51 cb<br>18 e6 bf c4 db 9b ae f6 75 d4 aa f5 b1 57 4a 04<br>7f 8f 6d d2 ec 15 3a 93 41 22 93 97 4d 92 8f 88</td><td>e8 06 3f 5b 7b 33 4c d0 b2 50 f8 26 bc c4 27 55<br>0b 19 74 c9 20 fc 28 09 86 e8 f1 ff c0 1b 51 df<br>14 e6 bf c6 1b 9b ae e6 c1 d4 aa e9 9d 57 4a 00<br>c3 8f 6d ca 5c 15 3a 83 41 22 93 9b f5 92 8f 98</td></tr><tr><td>0x0200</td><td>ce d9 36 3c fe f9 7c e2 e7 42 bf 34 c9 6b 8e f3<br>87 56 76 fe a5 cc a8 e5 f7 de a0 ba b2 41 3d 4d<br>e0 0e e7 1e 01 f1 16 2b db 6d 1e af d9 25 e6 ae<br>ba ae 6a 35 4e f1 7c f2 05 a4 04 fb db 12 fc 45</td><td>c2 d9 36 3e 3e f9 7c f2 53 42 bf 28 f5 6b 8e f7<br>3b 56 76 e4 85 cc a8 f5 d3 de a0 a6 5e 41 3d 59<br>ec 0e e7 1c 20 1f 16 3b 6f 6d 1e b3 f5 25 e6 aa<br>06 ae 6a 2d fe f1 7c e2 05 a4 04 f7 63 12 fc 55</td></tr><tr><td>0x0240</td><td>4d 41 fd d9 5c f2 45 96 64 a2 ad 03 2d 1d a6 0a<br>73 26 40 75 d7 f1 e0 d6 c1 40 3a e7 a0 d8 61 df<br>3f e5 70 71 88 dd 5e 07 d1 58 9b 9f 8b 66 30 55<br>3f 8f c3 52 b3 e0 c2 7d a8 0b dd ba 4c 64 02 0d</td><td>41 41 fd db 9c f2 45 86 d0 a2 ad 1f 11 1d a6 0e<br>cf 26 40 6f f7 f1 e0 c6 e5 40 3a fb 4c d8 61 cb<br>33 e5 70 73 48 dd 5e 17 65 58 9b 83 a7 66 30 51<br>83 8f c3 4a 03 e0 c2 6d a8 0b dd b6 f4 64 02 1d</td></tr></tbody></table>
<table><caption>**Table 9:** Differences in the state after each block, and output differences at the end of the trail (before the feed-forward).</caption><thead><tr><th>Block</th><th colspan="2">State difference</th></tr></thead><tbody><tr><td>Birthday</td><td>u</td><td>u</td></tr><tr><td>Block 1</td><td>u</td><td>u</td></tr><tr><td>Block 2</td><td>u</td><td>u</td></tr><tr><td>Block 3</td><td>u</td><td>u</td></tr><tr><td>Block 4</td><td>u</td><td>u</td></tr><tr><td>Block 5</td><td>u</td><td>u</td></tr><tr><td>Block 6</td><td>u</td><td>u</td></tr><tr><td>Block 7</td><td>u</td><td>u</td></tr><tr><td>Block 8</td><td>u</td><td>u</td></tr><tr><td>Block 9</td><td>u</td><td>u</td></tr></tbody></table><table><thead><tr><th>Block</th><th colspan="2">Output difference</th></tr></thead><tbody><tr><td>Block 1</td><td>u</td><td>u</td></tr><tr><td>Block 2</td><td>u</td><td>u</td></tr><tr><td>Block 3</td><td>u</td><td>u</td></tr><tr><td>Block 4</td><td>u</td><td>u</td></tr><tr><td>Block 5</td><td>u</td><td>u</td></tr><tr><td>Block 6</td><td>u</td><td>u</td></tr><tr><td>Block 7</td><td>u</td><td>u</td></tr><tr><td>Block 8</td><td>u</td><td>u</td></tr><tr><td>Block 9</td><td>u</td><td>u</td></tr></tbody></table>
# Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH

Karthikeyan Bhargavan

INRIA

karthikeyan.bhargavan@inria.fr

Gaëtan Leurent

INRIA

gaetan.leurent@normalesup.org

*Abstract*—In response to high-profile attacks that exploit hash function collisions, software vendors have started to phase out the use of MD5 and SHA-1 in third-party digital signature applications such as X.509 certificates. However, weak hash constructions continue to be used in various cryptographic constructions within mainstream protocols such as TLS, IKE, and SSH, because practitioners argue that their use in these protocols relies only on second preimage resistance, and hence is unaffected by collisions. This paper systematically investigates and debunks this argument.

We identify a new class of transcript collision attacks on key exchange protocols that rely on efficient collision-finding algorithms on the underlying hash constructions. We implement and demonstrate concrete credential-forwarding attacks on TLS 1.2 client authentication, TLS 1.3 server authentication, and TLS channel bindings. We describe almost-practical impersonation and downgrade attacks in TLS 1.1, IKEv2 and SSH-2. As far as we know, these are the first collision-based attacks on the cryptographic constructions used in these popular protocols.

Our practical attacks on TLS were responsibly disclosed (under the name SLOTH) and have resulted in security updates to several TLS libraries. Our analysis demonstrates the urgent need for disabling all uses of weak hash functions in mainstream protocols, and our recommendations have been incorporated in the upcoming Token Binding and TLS 1.3 protocols.

# I. INTRODUCTION

Hash functions, such as MD5 and SHA-1, are widely used to build authentication and integrity mechanisms in cryptographic protocols. They are used within public-key certificates, digital signatures, message authentication codes (MAC), and key derivation functions (KDF).

Permission to freely reproduce all or part of this paper for noncommercial purposes is granted provided that copies bear this notice and the full citation on the first page. Reproduction for commercial purposes is strictly prohibited without the prior written consent of the Internet Society, the first-named author (for reproduction of an entire paper only), and the author's employer if the paper was prepared within the scope of employment.

NDSS '16, 21-24 February 2016, San Diego, CA, USA
Copyright 2016 Internet Society, ISBN 1-891562-41-X
http://dx.doi.org/10.14722/ndss.2016.23418

However, recent practical attacks on MD5 and almost-practical attacks on SHA-1 have led researchers and practitioners to question whether these uses of hash functions in popular protocols are still secure.

The first collision on MD5 was demonstrated in 2005 [38], and since then, collision-finding algorithms have gotten much better. Simple MD5 collisions can now be found in seconds on a standard desktop. In response, protocol experts reviewed the use of MD5 in Internet protocols such as Transport Layer Security (TLS) and IPsec [16], [15], [3]. Despite some disagreement on the long-term impact of collisions, they concluded that most uses of hash functions in these protocols were not affected by collisions. Consequently, MD5 continues to be supported (alongside newer, stronger hash algorithms) in protocols like TLS and IPsec.

In 2009, an MD5 collision was used to create a rogue CA certificate [36], hence breaking the security of certificate-based authentication in many protocols. A variant of this attack was used by the Flame malware to disguise itself as a valid Windows Update security patch [34]. Due to these high-profile attacks, there is now consensus among certification authorities and software vendors to stop issuing and accepting new MD5 certificates. Learning from the MD5 experience, software vendors are also pro-actively phasing out SHA-1 certificates, since collisions on SHA-1 are believed to be almost practical [35].

This leaves open the question of what to do about other uses of MD5 and SHA-1 in popular cryptographic protocols. Practitioners commonly believe that collisions only affect non-repudiable signatures (like certificates), but that signatures and MACs used within protocols are safe as long as they include unpredictable contents, such as nonces [16], [15]. In these cases, protocol folklore says that a second preimage attack would be required to break these protocols, and such attacks are still considered hard, even for MD5.

Conversely, theoretical cryptographers routinely assume collision-resistance in proofs of security for these protocols. For example, various recent proofs of
TLS [17], [22], [11] assume collision-resistance even though the most popular hash functions used in TLS are MD5 and SHA-1. Whom shall we believe? Either it is the case that cryptographic proofs of these protocols are based on too-strong (i.e. false) assumptions that should be weakened, or that practitioners are wrong and collision resistance is required for protocol security.

This paper seeks to clarify this situation by systematically investigating the use of hash functions in the key exchanges underlying various versions of TLS, IPsec, and SSH. We demonstrate that, contrary to common belief, collisions can be used to break fundamental security guarantees of these protocols. We describe a generic class of attacks called transcript collision attacks, and detail concrete instances of these attacks against real-world applications. In particular, we demonstrate how a man-in-the-middle attacker can impersonate TLS 1.2 clients, TLS 1.3 servers, and IKEv2 initiators. We also show how a network attacker can downgrade TLS 1.1 and SSH-2 [39] connections to use weak ciphers. We implement proofs-of-concept exploit demos for three of these attacks to demonstrate their practicality, and provide attack complexities for the others. We believe that ours are the first hash collision-based attacks on the cryptographic constructions within these protocols.

We do not claim to have found all transcript collision attacks in these protocols; nor do we think that our attack implementations are the most efficient. Still, our results already provide enough evidence for us to strongly recommend that weak hash functions like MD5 and SHA-1 should be immediately disabled from Internet protocols. Partly due to recommendations by us and other researchers, these hash functions and other weak constructions based on them have been removed from the draft version of the TLS 1.3 protocol.

**Outline** Section II introduces transcript collision attacks on authenticated key exchange protocols. Section III outlines the state-of-the-art in collision-finding algorithms for MD5, SHA-1, and their concatenation. Section IV describe the TLS protocol, and Section V describes concrete attacks on various versions of TLS and three proof-of-concept demos. Section VI describes concrete attacks on IKE and SSH. Section VII summarizes the impact of our attacks and disclosure status. Section VIII concludes.

## II. TRANSCRIPT COLLISION ATTACKS ON AUTHENTICATED KEY EXCHANGE

Authenticated Key Exchange (AKE) protocols are executed between two parties, usually called client and server or initiator and responder, in order to establish a shared session key that can be used to encrypt subsequent messages. A typical example is the SIGMA' protocol depicted in Figure 1. This protocol is a variant

<figure><img src="image_98.png" /><figcaption>Fig. 1. SIGMA': A mutually-authenticated key exchange protocol</figcaption></figure>

of the basic SIGMA (sign-and-mac) protocol from [21] which served as the inspiration for the key exchanges used in many protocols including IKE, OTR, and JFK.

In SIGMA', the initiator $A$ first sends a message $m_1$ to $B$, consisting of Diffie-Hellman public value $g^x$, along with some protocol-specific parameters $info_A$ that may include, for example, a nonce, a protocol version, a proposed ciphersuite, etc. $B$ responds with a message $m_2$ containing its own Diffie-Hellman public value $g^y$ and some parameters $info_B$. $A$ and $B$ have now completed an anonymous Diffie-Hellman exchange and can compute the shared secret $g^{xy}$ and use it to derive the session key. However, before using the session key, they authenticate each other by exchanging digital signatures over the protocol transcript hash($m_1|m_2$) using their long-term signing keys ($sk_A, sk_B$). (Digital signature algorithms typically hash their arguments before signing them, and we have chosen to make this hashing explicit in our presentation of SIGMA'.) By signing the transcript, $A$ and $B$ verify that they agree upon all the elements of the key exchange, and in particular, that a network attacker has not tampered with the messages. Finally, $A$ and $B$ also prove to each other that they know the session key $g^{xy}$ by exchanging MACs computed with this key over their own identities.

Like other AKE protocols, SIGMA' aims to prevent message tampering, peer impersonation, and session key leakage, even if the network and other clients and servers are under the control of the adversary. Formally, authenticating the transcript guarantees matching conversations, that is, that the two parties agree on each others identity and other important protocol parameters.

**Transcript Collision Attacks** The alert reader will notice that SIGMA' does not in fact guarantee that $A$ and $B$ agree on the message sequence $m_1|m_2$; it only guarantees that they agree on the hash of this sequence. What if a network attacker were to tamper with the messages, so that $A$ and $B$ see different message sequences but the hashes of the two sequences is the same? In that case, the protocol will proceed to completion but the integrity and authentication guarantees no longer hold.

Figure 2 illustrates such an attack. The man-in-the-
<figure><img src="image_99.png" /><figcaption>Fig. 2. Man-in-the-middle credential forwarding attack on SIGMA'. The attacker creates a transcript collision by tampering with the messages shown in red. At the end of the protocol, the client and server have seemingly authenticated each other, but the attacker knows both connection keys, and hence can read or write any data.</figcaption></figure>

middle (MitM) intercepts messages sent between A and B. It sends its own message $m'_1 = g^{x'}|info'_A$ to B and it sends its own response $m'_2 = g^{y'}|info'_B$ to A. Suppose it can choose these messages such that the authenticated transcripts match:

$$ \text{hash}(m_1|m'_2) = \text{hash}(m'_1|m_2) $$

We call this a transcript collision. Now, MitM can simply forward A's signature over this transcript to B and vice versa. A and B will accept the signatures since the hashed transcripts match and the signing keys are correct. However, the MitM knows the session keys $(g^{x'y}, g^{xy'})$ on both connections (since it knows $x'$, $y'$). Hence, the MitM has fully hijacked both connections and can now send messages to B pretending to be A and to A pretending to be B. This is an impersonation attack that breaks peer authentication.

If the boundaries between the messages $m_1$ and $m_2$ are not clearly demarcated, there are a number of trivial attacks that can ensure that $m_1|m'_2 = m'_1|m_2$ with no need for hash collisions. In the examples of this paper, we will assume that each message (and each message field) is prefixed with its length, so that we can focus on attacks that rely on weaknesses in the hash function.

### A Generic Transcript Collision

The main challenge in implementing the attack in Figure 2 is that the MitM has to compute the messages $m'_1$ and $m'_2$ after receiving $m_1$ but before the responder has sent its response $m_2$. The feasibility of the attack depends on the contents and formats of these messages.

Suppose the responder B always sends the same message $m_2$ for every request; that is, it uses the same (static) Diffie-Hellman value $g^y$ and same parameters $info_B$. (This situation occurs, for example in protocols like QUIC, where the server uses a static configuration.) In that case, after receiving $m_1$, the MitM can compute

a transcript collision by finding $x'$, $y'$, $info'_A$, $info'_B$ such that $\text{hash}(m_1|m'_2) = \text{hash}(m'_1|m_2)$. The amount of work required to find such a collision depends on the hash function. As we will see in the next section, such collisions require $2^{N/2}$ work for hash functions that produce $N$ bits. Hence, for MD5, such a collision would require the MitM to compute $2^{64}$ MD5 hashes, which may well be achievable by powerful adversaries.

### A Chosen-Prefix Transcript Collision

We now consider a more efficient attack that works even when B sends an unpredictable $m_2$ containing a fresh (ephemeral) Diffie-Hellman value $g^y$ and a previously unknown $info_B$. However, we assume that the length of $m_2$ ($M$) is fixed and known to MitM. Moreover, suppose that in the second message of SIGMA', $info_B$ is allowed to have arbitrary length and arbitrary contents. That is, even if $info_B$ has junk data at the end, A will accept the message. Specifically, suppose that $info_B = \text{len}_B|data_B$ where $data_B$ is opaque data that will be ignored by A. (We will see several examples of such “collision-friendly” messages in TLS, IKE, and SSH.) Finally, we assume that the hash function uses the Merkle-Damgård construction [29], [7], so that it obeys the length extension property: if $\text{hash}(x) = \text{hash}(y)$ then $\text{hash}(x|z) = \text{hash}(y|z)$. (Strictly speaking, this property only holds when the lengths of $x$, $y$ are equal and a multiple of the hash function block size.)

Under all these conditions, MitM can compute a transcript collision by finding two collision bitstrings $C_1, C_2$ of $L_1$ and $L_2$ bytes respectively, such that:

$$ \text{hash}(m_1|\underbrace{[g^{y'}|\text{len}'_B|C_1|-]}_{m'_2}) = \text{hash}(\underbrace{[g^{x'}|C_2]}_{m'_1}) $$

where $\text{len}'_B = L_1 + M$. Note that we have left empty space (written $-$) of size $M$ bytes that still needs to be filled after $C_1$ in $info'_B$. As we will see in the next section, this kind of collision is called a chosen-prefix collision and is typically achievable with far less work than a generic collision attack. For example, a chosen-prefix collision in MD5 requires the MitM to compute about $2^{39}$ MD5 hashes, which takes only a few CPU hours.

After receiving $m_1$ from A and computing $C_1, C_2$, MitM now sends $m'_1$ to B. When B responds with $m_2$ (of size $M$ bytes), MitM now stuffs $m_2$ at the end of $info'_B$ (in place of $-$) and sends $m'_2$ to A. Due to the length extension property, we have:

$$ \text{hash}(m_1|\underbrace{[g^{y'}|\text{len}'_B|C_1|m_2]}_{m'_2}) = \text{hash}(\underbrace{[g^{x'}|C_2]}_{m'_1}|m_2) $$
That is, the MitM has obtained a transcript collision and the impersonation attack succeeds.

The attack here exploits hash collisions in combination with flexible protocol-specific message formats, and as we will see, this is one of the main novel *tricks* that we use to mount various attacks in this paper.

**Other Transcript Collisions** The transcript collisions described above are not the only attacks possible on such protocols. In some cases, MitM may not be able to use its own Diffie-Hellman values $g^{x'}$, $g^{y'}$ but it may still be able to tamper with the protocol parameters (e.g. ciphersuites) in $info'_A$, $info'_B$. In such cases, the MitM does not have full control over either connection (i.e. it cannot impersonate A or B) because it does know the session keys, but it may still be able to downgrade the protocol parameters to use weak, breakable ciphers.

In other cases, the message format may lend itself to simpler *common-prefix* collisions that require even less work than chosen-prefix collisions. Such collisions on MD5 can be found in seconds even on standard desktops. In the next section, we will discuss these different types of collisions in more detail (some technical details of previous results are given in the Appendix), and in the remainder of the paper, we will exploit them to mount transcript collision attacks on real-world protocols.

### III. HASH FUNCTION CRYPTANALYSIS

A hash function $H: \{0, 1\}^* \to \{0, 1\}^N$ maps arbitrary length binary strings to strings of $N$ bits. Broadly speaking, a cryptographic hash function is expected to behave like a randomly selected function from the set of all functions from $\{0, 1\}^* \to \{0, 1\}^N$; building input/output values with specific properties should be as hard for $H$ as for a random function. More concretely, a cryptographic hash functions should meet four goals:

1) **Preimage resistance:** Given a target value $\overline{H}$, it should be hard to find $x$ such that $H(x) = \overline{H}$

2) **Second-preimage resistance:** Given an input $x$, it should be hard to find a second input $x' \neq x$ such that $H(x') = H(x)$

3) **Chosen-prefix collision resistance:** Given prefixes $P$ and $P'$, it should be hard to find a pair of values $x, x'$ such that $H(P'|x') = H(P|x)$.

4) **Collision resistance:** For a hash function $H$, it should be hard to find a pair of inputs $x \neq x'$ such that $H(x') = H(x)$.

The expected security of a hash function is defined as the complexity of the best generic attack, i.e. the best attack that works on any hash function, without using any specific property of the design. For preimages or second-preimages, the best attack is a brute-force

search: an adversary has to try about $2^N$ random inputs in order to find a preimage. However, for collisions, there is a generic attack with complexity $2^{N/2}$ because of the birthday paradox. If an adversary computes the images of a set of $2^{N/2}$ inputs, this defines about $2^N$ pairs of inputs, and there is a high probability that one of these pairs is a collision.

**Generic collision attacks** While a naive collision attack requires to store $2^{N/2}$ images of the hash function, it is possible to mount a parallel and memory-less attack with a very small overhead [37]. This generic collision attack is very powerful: it can use meaningful messages, and can easily be used for chosen-prefix collisions (see details in Appendix).

**Concatenation** To strengthen protocols against collisions in any one hash function, it may be tempting to use a combination of two independent hash functions. For example, TLS versions up to 1.1 use a concatenation of MD5 and SHA-1. While the output length of this construction is 288 bits, it does not offer the security of a 288-bit hash function. In particular, Joux described a multi-collision attack that breaks the concatenation of two hash functions with roughly the same effort as breaking the strongest one of the two [18].

**Shortcut collision attacks** In the last decade, hash function cryptanalysis has been a very active research area, and more efficient attacks have been discovered on widely used hash functions. The (estimated) complexity of the best attacks currently known against MD5 and SHA-1 are the following:

<table><tr><td>MD5</td><td>Common-prefix collision: 2<sup>16</sup> [36]<br/>Chosen-prefix collision: 2<sup>39</sup> [36]</td></tr><tr><td>SHA-1</td><td>Common-prefix collision: 2<sup>61</sup> [35]<br/>Chosen-prefix collision: 2<sup>77</sup> [35]</td></tr><tr><td>MD5 | SHA-1</td><td>Common-prefix collision: 2<sup>67</sup> [18]<br/>Chosen-prefix collision: 2<sup>77</sup> [18]</td></tr></table>

Shortcut collision attack usually return messages with random-looking blocks that are not controlled by the adversary. This makes it harder to use these messages in a real attack, but we will see that in many cases we can still have meaningful messages by stuffing the random blocks in non-significant sections.

**Implementation of attacks** Since generic collision attacks can be easily parallelized and require little memory, they can efficiently be implemented in GPUs. In particular, an attack against MD5 require $2^{64}$ computations. This is well within reach for a motivated adversary: it would cost around $165 000 on Amazon EC2 (using a spot price of 8 €/h for a g2.2xlarge instance doing 2.5 GH/s). Dedicated hardware would be significantly more efficient, but require a large investment. As
a point of comparison, the current Bitcoin network is able to compute up to $2^{59}$ SHA-256 hashes per second.

We have implemented this attack against the 96-bit MAC used for the Finished message of TLS 1.1. Our demo took 20 days using four Tesla K20Xm GPUs, which is comparable to the expected time we can derive from hash function benchmarks.

For a chosen-prefix collision, an important part of the computation is spent constructed differential paths, and this is much harder to parallelize on GPU. We used the HashClash software [33] by Marc Stevens to perform this computation. Stevens et al.'s estimate that the chosen-collision attack should require $2^{39}$ hash computations, or 35 core-hours [36]. In order to build the collision as fast as possible, we modified the software to take better advantage of parallelism. The hashclash software spends most of its time building differential paths, with a forward step, a backward step, and a connection step. We realized that the backward step uses a limited number of potential starting points, and we precomputed the results for all possible starting points. In addition, we merged the forward and connection steps, in order to avoid the serialization and deserialization of the result. With these optimisations, we can build a chosen-prefix collision in one hour with a 48 cores machine, using a few gigabytes of RAM (the original code required at least 3 hours). We believe the time can be further reduced, but this will require a significant rewrite of the hashclash software to allow parallelism across several machines, or to rewrite it for GPUs.

## IV. THE TLS HANDSHAKE PROTOCOL

The Transport Layer Security protocol (TLS) [8] is perhaps the most widely used secure channel protocol. Many versions of TLS are used on the Internet; the latest released version is TLS 1.2 [8], while TLS 1.3 [9] is currently undergoing standardization at the IETF.

Figure 3 depicts a typical handshake in TLS (in versions 1.0 to 1.2). The client first sends a hello message CH that contains a fresh random client nonce $n_c$ and various protocol parameters $ex_c$, including the protocol version, supported list of ciphersuites, and various protocol extensions. Each extension is prefixed by its length and can contain a payload of up to $2^{16}$ bytes. Notably, the client hello may include extensions that the server does not understand or support, and the server will ignore them.

The server responds to the client hello with a series of messages (from SH to SHD). The server hello SH contains a fresh server nonce $n_s$ and parameters $ex_s$, including the server's chosen version, ciphersuite, and protocol extensions. In most ciphersuites, the server then sends its public-key certificate SC. In Ephemeral Diffie-Hellman (DHE) ciphersuites, SC is followed by a server

<figure><img src="image_100.png" /><figcaption>Fig. 3. TLS 1.2: A mutually-authenticated DHE handshake. Fields shown in red indicate parts of the handshake that can contain arbitrary-length opaque data (useful for stuffing collision blocks). Handshake transcripts ($log_1, log_2, log_3$) refer to the concatenation of all messages up to (and including) the current one. Messages SCR, CC, CCV are optional and only appear when client certificate authentication is used. NPN is optional and only appears when the client and server support the next-protocol-negotiation extension. The tls-unique channel binding is a connection identifier that may be used by applications to bind user authentication tokens, such as cookies and passwords, to the underlying TLS channel to prevent credential forwarding.</figcaption></figure>

key exchange message SKE that contains an ephemeral public value $g^y$ along with a description of the Diffie-Hellman group chosen by the server, including the prime $p$ and generator $g$. The server signs these values to protect them from tampering and to prove that it knows the private key ($sk_S$) for the certificate:

$$ \text{sign}(sk_S, \text{hash}(n_c|n_s|p|g^y)) $$

The signature and hash algorithm used for this signature is chosen by the server based on its certificate as well as the supported algorithms indicated by the client within an optional signature-algorithms extension in the client hello. In TLS versions before 1.2, the hash algorithm was fixed to be MD5 | SHA-1 but TLS 1.2 allows clients and servers to choose any hash algorithm they both support (MD5, SHA-1, SHA-256, etc.) Hence in TLS 1.2, each digital signature is prefixed with identifiers for the chosen signature and hash algorithm.

If the server wants the client to authenticate itself with a public-key certificate, it then sends a certificate request message SCR indicating the certificate types and signature algorithms it supports, as well as an optional list of distinguished names $dn$ for the client certification authorities that it trusts. As with hello extensions, each distinguished name can be $2^{16}$ bytes long and can contain arbitrary data that the client will ignore if it does not recognize the name. The server's message flight then ends with the server hello done message SHD.

The client then sends its own certificate CC if the
server asked for it, and its own Diffie-Hellman key share $g^x$ in a client key exchange message CKE. If the client sent a certificate, it must prove that it knows the private key $sk_C$ by sending a client certificate verify CCV message with a signature over the full message log up to this point in the protocol:

$$ \operatorname{sign}(sk_C, \operatorname{hash}(\underbrace{CH|SH|SC|SKE|SCR|SHD|CC|CKE}_{\log_2 1})) $$

At this point, the client and server both derive a session master secret $ms$ and authenticated encryption keys for both directions ($k_1, k_2$). The client sends a change cipher spec message to indicate that the subsequent messages it sends will be encrypted (with $k_1$.) This message is not technically part of the handshake protocol and does not appear in the authenticated transcript, and so it is not shown in Figure 3.

If the client and server both indicate support for the next-protocol-negotiation extension [24] in their hello messages, the client then sends an encrypted extensions message NPN containing a selected application layer protocol (e.g. http/1.1 or spdy/3). The protocol name is ASCII-encoded and then padded to the nearest multiple of 32 bytes (to avoid leaking information via the encrypted message length.)

The client then sends an encrypted finished message CFIN containing a MAC of the full handshake log $log_2$ using the master secret $ms$. In TLS 1.0 and 1.1, this MAC is computed using a combination of HMAC-MD5 and HMAC-SHA-1, whereas in TLS 1.2, it uses HMAC-SHA-256. In all these versions, the result of the MAC is then truncated to 12 bytes (96 bits):

$$ \operatorname{mac}_{96}(ms, \operatorname{hash}(\underbrace{CH|SH|SC|SKE|SCR|SHD|CC|CKE|CCV|NPN}_{\log_2 2})) $$

When a server receives CFIN, it verifies that the client agrees with it on the full message log and on the master secret. It responds by sending its own change cipher spec message to turn on encryption and a server finished message SFIN that contains a 96-bit MAC over the full handshake log $log_3$ using the master secret $ms$.

At the end of the handshake, both client and server have authenticated each other, proved knowledge of the master secret, and agreed upon the message log. They can now start encrypting application data to each other using the connection keys ($k_1, k_2$).

In most common TLS usage scenarios, clients are not authenticated using certificates. The handshake authenticates only the server and the client-side user is authenticated within the application using a challenge-response protocol based on a password or some other bearer token (e.g. HTTP cookie). Such application-level authentication protocols are known to be vulnerable to

a general class of credential forwarding attacks unless the application-level credential is channel bound to the TLS connection (e.g. see [5]). In such attacks, a client C connects to a malicious server M and authenticates with some credential over TLS, but M forwards the authentication message over another TLS channel to S, thereby logging in as C at S. The attack is prevented if the authentication protocol embeds a unique identifier for the underlying TLS channel, so that a message sent over one channel cannot be forwarded over another. One such identifier, called tls-unique, defined in [2], uses the contents of the CFIN message as a unique identifier for the TLS connection. This tls-unique channel binding is used by a number of emerging application-level authentication protocols, such as SCRAM [28], FIDO [14], and Token Binding [32], specifically to avoid credential-forwarding attacks.

## V. TRANSCRIPT COLLISION ATTACKS ON TLS

As we saw in the previous section, TLS uses a variety of hash constructions to implement key security mechanisms like client and server authentication, handshake integrity, and channel binding. We now demonstrate weaknesses in these constructions and show how they can be exploited to mount practical transcript collision attacks on real-world clients and servers.

### A. Breaking TLS 1.2 Client Authentication using a Chosen-Prefix Transcript Collision

Suppose a client C uses the same certificate to connect to two different servers A and S. We show that if A is malicious, it can force C to create a signature (in CCV) that A can use to impersonate C at S, as depicted in Figure 4. Here, A acts as a man-in-the-middle between C and S. Note, however, that A uses its own certificate $cert_A$ and does not rely on knowing any long-term secrets belonging to C or S.

Recall that the client signs the transcript hash($log_1^c$); so the key idea of the attack is to compute a collision between this client-side transcript and the server-side transcript hash($log_1^s$), even though the two connections see different message sequences. When the MitM A receives a client hello from C, it responds with its own hello SH', certificate SC', key exchange SKE'. It then initiates a connection with the server S by sending a carefully crafted client hello CH'. A now runs both connections in parallel. It will receive a hello SH, certificate SC, key exchange SKE, and certificate request SCR from S. We assume that the length of these messages SH|SC|SKE|SCR is fixed (= M) and is known in advance.

Note that A needs to choose CH' before it receives any messages from S. A can compute CH' and SCR' as follows. A uses a chosen-prefix collision to find two bit-strings ($C_1, C_2$) of length $L_1$ and $L_2$ bytes respectively
<figure><img src="image_101.png" /><figcaption>Fig. 4. Man-in-the-middle client signature forwarding attack on TLS 1.2. The client C connects to a malicious server A and offers to authenticate with its certificate cert<sub>C</sub>. The attacker A computes a chosen-prefix collision on the client signature transcript hash(<i>log</i><sub>1</sub><i>)</i>, and uses it to impersonate the client at a different server S. Messages that the attacker controls are labeled in red. A sends a bogus Diffie-Hellman group (<i>k</i><sup>2</sup> − k, k) to C; we use <i>k</i> = <i>g</i> here for simplicity.</figcaption></figure>

such that $C_1$ appears within the last distinguished name $dn'$ in SCR' and $C_2$ appears within the last extension $ex'_c$ in CH':

$$ = \underbrace{\text{hash}(\text{CH}|\text{SH}'|\text{SC}'|\text{SKE}'|\text{SCR}'(C_1|-))}_{ex'_c} $$

Furthermore, we set the length of $dn'$ in SCR' to be $L_1 + M$, so that it still has $M$ bytes (denoted by $-$) that need to be filled in after $C_1$.

Now, A sends CH' to S, receives SH|SC|SKE|SCR in response, and stuffs these messages into the remaining M bytes in SCR' and sends it to C. At this point the hash of the message transcripts in the two connections coincide, assuming that the hash function satisfies the length extension property:

$$ = \underbrace{\text{hash}(\text{CH}|\text{SH}|\text{SC}'|\text{SKE}'|\text{SCR}'(C_1|\text{SH}|\text{SC}|\text{SKE}|\text{SCR}))}_{ex'_c} $$

From this message onwards, the hash of the handshake log in both connections will remain the same. A then forwards the server hello done SHD to C. In response, C sends a certificate CC, a key exchange CKE, and a certificate verify CCV that contains a signature over the transcript hash(<i>log</i><sub>1</sub><sup>c</sup>) which is now the same as

hash(<i>log</i><sub>1</sub><sup>s</sup>). A simply forwards these messages to S, pretending to be C, and S accepts these messages.

**Controlling the master secret** Even though S has accept C's certificate on its connection with A, A cannot complete the connection unless it knows the master secret on its connection with S. The master secret is computed from <i>g</i><sup>xy</sup> so A needs to know the <i>x</i> corresponding the <i>g</i><sup>x</sup> that C sent in its key exchange message CKE. In order to accomplish this task, we rely on a key forcing attack in the DHE handshake.

When A sends SKE' to C, it does not send a valid Diffie-Hellman group (<i>p</i>, <i>g</i>). Instead, it chooses an arbitrary public value <i>k</i> = <i>g</i><sup>x'</sup> and sets <i>p</i> = <i>k</i><sup>2</sup> − k and <i>g</i> = <i>k</i>. This <i>p</i> value is clearly not a prime, and it has the property that no matter what private value <i>x</i> is generated by C, we will have <i>g</i><sup>x</sup> mod <i>p</i> = <i>k</i>. Hence, by choosing such a bogus Diffie-Hellman group, A can force C to send a CKE with a public value that it controls.

To complete the attack, we assume that S always uses the same Diffie-Hellman group (<i>p</i>, <i>g</i>). A chooses some <i>x'</i> and sets <i>k</i> = <i>g</i><sup>x'</sup> mod <i>p</i>. It then sends SKE' to C with the bogus group (<i>k</i><sup>2</sup> − k, <i>k</i>) and the public value <i>k</i>. Now, the CKE sent by C will contain <i>k</i>, and A will forward it to S. A will then forward C's signature CCV as usual. The master secret between A and S will be derived from <i>g</i><sup>xy</sup> mod <i>p</i>, but A knows <i>x'</i> and hence can compute this value. Consequently, A can complete the handshake and impersonate C at S.

We observe that the attack here relies on the client not validating the Diffie-Hellman groups it receives from the server. From our experiments, we find that most TLS libraries do not validate the groups they receive in the server key exchange, probably because checking for primality is expensive. In some libraries, the value <i>k</i><sup>2</sup> − <i>k</i> is rejected because it is an even number. In those cases, we find that we can use <i>p</i> = <i>k</i><sup>2</sup> − 1 and with 50% probability, the client will compute <i>g</i><sup>x</sup> = <i>k</i>, allowing the attack to succeed. This weakness in TLS-DHE has been noted before [6] and a new protocol extension aims to fix it by allowing only well-known Diffie-Hellman groups [12]. However, an optional extension cannot prevent our attack scenario, since A could always pretend to not support the extension and mount the attack anyway.

Note that the attack only relies on DHE between C and A; the connection between A and S can use ECDHE or RSA and the attack would still work. In other words, such transcript collisions can also be used to mount cross-protocol attacks in the sense of [26].

**Attack Complexity** The transcript collision attack requires A to compute a chosen-prefix collision for the hash function used in the client signature. In TLS
versions before 1.2, the default hash function is a concatenation of MD5 and SHA-1 and hence requires computing $2^{77}$ MD5 and SHA-1 hashes. In TLS 1.2, if the signature uses SHA-1, the cost is $2^{77}$ hashes. Remarkably, TLS 1.2 also allows RSA-MD5 signatures, and for such signatures, the cost of the collision is only $2^{39}$ MD5 hashes. Below, we describe our proof-of-concept implementation that relies on RSA-MD5.

Note that these cost estimates are per-connection because the collision needs to be computed once for each client nonce $n_c$. Usually, these nonces are generated with a strong random number generator. However, in some cases the client random can become predictable due to implementation bugs (e.g. see CVE-2015-0285 in OpenSSL). We also observe that it is commonly believed that these nonces only need to be unique, not unpredictable. For example, the OpenSSL library uses `RAND_pseudo_bytes` to generate the client and server random, whereas it uses `RAND_bytes` to generate other key material; the former succeeds even when there is not enough entropy in the system. If the client nonce were predictable, or if it were to be repeated with high frequency, the collision can be computed offline at leisure, making SHA-1 collisions almost feasible. Even though our attack below does not rely on predictable nonces, it offers yet another justification for the need for strongly random nonces in TLS.

**Implementing a Proof-Of-Concept** To implement the attack, we need a client that is willing to sign with RSA-MD5 and a server that is willing to accept such signatures. We found a number of TLS libraries that support RSA-MD5 client signatures, including certain versions of OpenSSL, GnuTLS, Oracle and IBM Java, and BouncyCastle. (See Section VII for more details.) In particular, all major Java web application servers and the default TLS servers on Red Hat Enterprise Linux (6 and 7) accept RSA-MD5 signatures.

For our demo, we set up a man-in-the-middle attack between a standard Java HTTPS client and a Java HTTPS server (with default configurations.) The MitM implements Figure 4. In order to setup the collision while preserving the TLS message formats, the attacker needs to carefully set the length fields in various places in CH' and SCR'. For example, in CH' it needs to set consistent lengths for the full hello message, for the extensions field, and for the last extension. Furthermore, the MitM needs to make sure that the two prefixes have a length that is a multiple of the MD5 block size (512 bits). To achieve this, we fill up the last extension in CH' and the last distinguished name in SCR' with enough zero bytes until the prefixes are block-aligned.

As explained in Section III, the chosen-prefix collision can be computed in one hour on a 48 core workstation using a modified version of the hashclash

software [33]. In our demo, A accepts the client hello and then keeps the client-side TLS connection alive until a collision has been found. Most TLS connections can be kept alive by sending regular warning alerts; Java clients are willing to keep the connection open indefinitely. Keeping the client waiting for an hour is not always practical, but we note that some unsupervised TLS clients (such as git) are used to perform long-running connections to web APIs, and long connection times may not be noticed. In any case, the collision search scales well with computational power and can be significantly sped up by a powerful adversary.

Once the collision has been found, A connects to S to completes the attack and is able to impersonate C at S and read and write data that only C should have access to. Hence, the demo shows that A is able to break TLS 1.2 client authentication between mainstream TLS clients and servers. The precise handshake traces exhibiting the collision are available from our website.

## B. Breaking TLS 1.2 Server Authentication using a Generic Transcript Collision

The key to our attack above on TLS 1.2 client authentication is that the client is willing to sign the hash of the full message log, and the format of various TLS messages is flexible enough to allow the attacker to stuff meaningless collision blocks and server-side messages into them. A similar chosen-prefix transcript collision attack would not work on TLS 1.2 server authentication because the server signature transcript does not contain flexible-size elements.

In DHE handshakes, the signature covers only the client and server nonces and the server's Diffie-Hellman key share: $\text{sign}(sk_S, \text{hash}(n_c|n_s|p|g|g^y))$. So, the only part of the signed value that the attacker may control is the client nonce $n_c$ which is fixed-length (32 bytes), half the size of one MD5 block.

This prevents the use of shortcut collision attacks against MD5, but generic attacks based on the small 128-bit MD5 hash length are still possible, and not too far from being practical.

**Collecting and storing signatures.** To mount a transcript collision attack on TLS 1.2 server authentication, an attacker first has to collect a large number, say $2^x$, of RSA-MD5 signatures signed by the server. The attacker may do this by passively observing RSA-MD5 connections to the server, but since such connections may be rare, it may have to actively connect to the server to obtain a sufficient number of signatures. Once these signatures (and the corresponding hashes) have been collected and stored, the attacker can impersonate the server to any client.
Upon receiving a client hello message including the client nonce $n_c$, the attacker chooses a DH secret $y'$ and computes the MD5 hashes of the transcripts $n_c|n_s|p|g|g'^y$ for a series of random server nonces $n_s$, until the hash matches a value that was collected previously. Finding this collision requires the attacker to compute about $2^{128-x}$ MD5 hashes and then look them up in the stored signature database. When a match is found, the stored signature can be used by the attacker to forge the server's SKE message for the current connection, and hence impersonate the server.

The complexity of this attack on TLS 1.2 server authentication is therefore $2^{128-x}$ MD5 hashes per connection, in addition to $2^x$ connections performed before-hand, and $2^x$ storage. The attacker can trade-off between these costs—the more signatures he can collect, the less he has to compute per connection. For example, if it is feasible to collect, store, and search through $2^{64}$ signatures, then the per-connection cost is $2^{64}$ hashes. Although we have described the attack in terms of MD5, a similar but more expensive attack can be mounted on RSA-SHA1 server signatures, which would require $2^{160-x}$ computation per-connection.

**Practical Impact of the Attack.** Both the precompu-
tation and per-connection cost of the attack is currently
out of reach for academic researchers, but might be
within the capabilities of well-resourced adversaries.

A prerequisite for the attack is to find servers that
would be willing to sign their SKE messages with
RSA-MD5. Internet-wide scans show that about 31%
of the Alexa top 1 million websites support RSA-
MD5 signatures.<fnref n="1" /> This subset includes popular websites
hosted by Akamai, such as microsoft.com.

A second question is whether TLS clients would accept RSA-MD5 signatures. Most popular web browsers and TLS libraries do not offer RSA-MD5 as one of the supported signature algorithm in the client hello. This might lead one to believe that they would not accept RSA-MD5 server signatures. However, we found and reported security bugs in NSS (the library used by Firefox and some versions of Chrome), GnuTLS (used in curl and git), and BouncyCastle; these libraries (and applications that rely on them) incorrectly accept RSA-MD5 signatures even if they have been explicitly disabled. For example, Firefox will accept an RSA-MD5 signature from a website, even though it is not supposed to. Furthermore, other TLS libraries such as versions of OpenSSL (up to version 1.0.1e), mbedTLS, and Java routinely offer and accept RSA-MD5 signatures.

Consequently, if an attacker has the resources to
achieve the server impersonation attack, a large number

<figure><img src="image_102.png" /><figcaption>Fig. 5. TLS 1.3: A server-authenticated 1-RTT (EC)DHE handshake based on draft 10 of the specification. The client and server send their key shares within the hello messages and all subsequent handshake messages are encrypted. The server signs the current handshake transcript hash($log_2$) in a new SCV message.</figcaption></figure>

of TLS clients would be affected. To err on the safe side,
we recommend that TLS libraries should immediately
disable all MD5-based signatures.

**Exploiting predictable nonces and keys.** We observe that the precomputation in the above attack can be avoided if the server uses a predictable nonce $n_s$ and predictable DH parameters $p, g, g^y$. In this case, the attacker only has to perform $2^{64}$ computations online. How realistic is this assumption? Many TLS implementations allow DH keys to be reused; in OpenSSL, for example, keys are reused by default unless the application sets the SSL_OP_SINGLE_DH_USE flag. For such servers, the parameters are clearly predictable.

That leaves the server nonce, and as we noted for
clients, a bug in the use of the random number gen-
erator could lead to predictable nonces. Alternatively,
the server may support a recent TLS variant called
Snap-Start [23] that allows the client (and hence the
attacker) to choose the server nonce. That said, we do
not know of any deployed TLS 1.2 implementation that
uses predictable nonces, but this section serves as a
warning to implementors that strongly random nonces
are needed in TLS, and not just for preventing replays.

C. Breaking TLS 1.3 Client and Server Authentication using a Chosen-Prefix Transcript Collision

From the viewpoint of transcript collisions, TLS 1.2
server signatures may seem stronger than client signa-
tures, but not signing enough leads to other security
problems. For example, the server becomes vulnerable

<footnote n="1">¹https://securitypitfalls.wordpress.com/2015/12/07/november-2015-scan-results/</footnote>
to cross-protocol attacks [26] and to downgrade attacks like Logjam [1]. In response to such attacks, the new design of TLS 1.3 requires the server to sign the full handshake log, including the negotiated parameters.

Figure 5 illustrates the standard one-round-trip (1-RTT) message flow in the current draft (version 10) of the TLS 1.3 specification. In comparison to TLS 1.2, this protocol flips the order in which the DH key shares are sent, so that the handshake can complete in one round trip. The key shares are sent within extensions in the hello messages CH and SH. The server no longer sends an SKE message. Instead, it sends a new server certificate verify message SCV just before the finished message. The SCV contains a signature over the hash of the full message log up to this point ($log_2$). Another departure from TLS 1.2 is that all handshake messages after SH are encrypted, in order to protect the privacy of the client and server certificates from passive attackers.

We demonstrate a chosen-prefix transcript collision on TLS 1.3 that breaks both client and server signatures, enabling a full man-in-the-middle attack on the protocol. The attack is similar in spirit to the one on TLS 1.2 client signatures; we use the flexible formats of the client and server hello messages to create a transcript collision immediately after the server hello SH.

The client $C$ wants to connect to $S$, but its messages are intercepted by a network attacker $A$. After $A$ receives the client's CH, it sends its own CH' to the server, receives the servers SH, and sends its own SH' to the client. $A$ now knows the Diffie-Hellman shared secrets on both connections, and it has chosen CH' and SH' such that $hash(CH|SH') = hash(CH'|SH)$. Consequently, $A$ can now simply forward all handshake messages between $C$ and $S$, and both client and server authentication will succeed. $A$ will need to decrypt and reencrypt these messages, but it can do so because it knows the encryption keys on both connections. More importantly, once the handshake is complete, $A$ can read and tamper with application data in both directions.

To compute CH' and SH', $A$ needs to find a chosen-prefix collision $C_1, C_2$ of length $L_1$ and $L_2$ bytes respectively such that $C_1$ appears within the last extension of SH' and $C_2$ appears as the last extension of CH':

$$ \underbrace{\text{hash}(\text{CH}|\text{SH}'(n_s, g^{y'}, C_1|-))}_{ex_s'} = \underbrace{\text{hash}(\text{CH}'(n_c, g^{x'}, C_2|))}_{ex_c} $$

Suppose we know that the server $S$ will respond to CH' with a server hello message SH of known length $M$. Then in SH', we set the length of $ex_s$ to $L_1 + M$ so that there is room for $M$ more bytes after $C_1$. Once $A$ receives SH from $S$, it stuffs this message within this extra space in SH' and sends it to $C$. Hence, after the server hello, the handshake transcripts at the client and server have the same hash. Moreover, due to

the length extension property of the hash function, all subsequent handshake hashes collide. So, $A$ can forward $S$'s signature in SCV to $C$ and $C$'s signature in CCV to $S$, and both will be accepted, even though the DH keys have been tampered with by a man-in-the-middle.

**Implementing a Proof-Of-Concept** Up to draft 7, the TLS 1.3 specification explicitly allowed RSA-MD5 signatures. We wrote a proof-of-concept attack demo based on our own simple prototype implementation of TLS 1.3 that signs with RSA-MD5. As with TLS 1.2 client authentication, we found the chosen-prefix collision in roughly one hour on a single workstation.

As we observed when discussing TLS 1.2, a large number of TLS servers and clients support RSA-MD5 signatures. Consequently, we believe that if TLS 1.3 draft 7 were to be implemented today, it is quite likely that many of its clients and servers would be vulnerable to our man-in-the-middle attack. However, this attack vector was removed from TLS 1.3, at least partly due to our findings, when draft 8 of the protocol explicitly deprecated MD5-based signatures.

### D. Downgrading TLS 1.0-1.1 to Weak Ciphersuites using a Chosen-Prefix Transcript Collision

In TLS, the integrity of the handshake depends upon the MACs exchanged in the Finished messages. If these MACs were broken, the attacker would be free to modify the hello messages to downgrade the connection to an old protocol version or weak ciphersuite, or to delete important extensions such as the renegotiation indication countermeasure [11].

Recall that the Finished MACs are computed over the hash of the full handshake transcript ($hash(log_2)$ and $hash(log_3)$ in Figure 3). In TLS 1.0 and 1.1, this hash function is the concatenation of MD5 and SHA-1. As we saw in Section III, a chosen-prefix collision on this construction can be computed with $2^{77}$ work. We find a man-in-the-middle transcript collision attack on server-authenticated TLS 1.1 that is similar to the TLS 1.3 attack. A network attacker modifies the client and server hellos so that the handshake hashes collide immediately after these two messages; the rest of the handshake is left unchanged. The client authenticates the server and the handshake completes successfully, and although the attacker does not know the master secret, it can downgrade the connection to use any weak algorithm that both the client and server support, but prefer not to use, such as an EXPORT ciphersuite [1], or a weak encryption algorithm like RC4.

A similar transcript collision attack appears in DTLS 1.0, a UDP-based variant of TLS 1.1. In DTLS, the attack can be made even more efficient by exploiting its cookie mechanism. In response to a client hello CH,
<figure><img src="image_103.png" /><figcaption>Fig. 6. Man-in-the-middle credential forwarding attack on tls-unique channel binding. The attack uses a transcript collision to impersonate the client to the server.</figcaption></figure>

A DTLS server can send a hello verify request message HVR containing a cookie. The client is meant to restart the handshake by sending the exact same client hello message but with this cookie included in it. Since the HVR is not authenticated, the arbitrary-length cookie field allows any network attacker to inject data into the transcript, after a known prefix of a fixed length. This allows the chosen-prefix attack to be transformed to an almost common prefix attack, similar to the cookie-based attack on IKEv2 in Section VI-A.

## E. Breaking the tls-unique Channel Binding using a Generic Transcript Collision

Suppose an application-level authentication protocol at C binds its login credential to the tls-unique channel binding [2], so that when the credential is sent from C to A, it cannot be used by A at S. We demonstrate how the attacker A could use a generic collision attack to break this protection.

Figure 6 depicts the attack. It follows the general pattern of the TLS 1.2 client authentication attack, except that it relies on a collision on the transcript MAC in the client finished message, rather than a collision in the hash function. The client C connects to the MitM A who then opens a new connection to S. The attacker sends a SKE' to C that contains a bogus group ($k^2 = 1, k$), thereby forcing the client to send $k^x \mod (k^2 - 1) = k$ in its client key exchange CKE. On the server side, the attacker can send its own CKE' containing any Diffie-Hellman value. Hence, the MitM knows the master secrets $ms^c, ms^s$ and connection keys on both connections.

The goal of the attacker is to make sure that the contents of the client finished message (i.e. the tls-unique) coincide on both connections:

$$mac_{96}(ms^c, log_2^c) = mac_{96}(ms^s, log_2^s)$$

The attacker can use any controlled part of the transcript, but we will set things up carefully so that he can compute the collision as late as possible, in order to reduce the size of the messages to hash. More precisely, we use the certificate request SCR' on the client-side and the NPN message on the server side, which are sent when all other messages in the transcript are already fixed. The attacker uses $C_1$ as the last distinguished name in SCR' and $C_2$ as the padding in the NPN message (after the protocol name "http/1.1"), and computes $(C_1, C_2)$ such that the MAC coincides. Once this collision is found, the MitM sends these two messages on the corresponding connections and completes the handshakes. A can then impersonate C at S by forwarding any application-level channel-bound credentials sent by C (for A) to S.

### Implementing a Proof-Of-Concept
We implemented a man-in-the-middle attacker to demonstrate the attack. We used an OpenSSL client as C and the main Google website as S, since this website supports the next-protocol-negotiation protocol extension. After receiving the client hello CH from the client and the server hello done SHD from the server-side, the MitM runs a generic collision search to compute SCR' and NPN.

For the collision search, we implemented the TLS PRF $mac_{96}$ function using the CUDA framework for NVIDIA GPUs. In TLS versions up to 1.1, this construction is built using MD5 and SHA-1; in TLS 1.2 the construction uses SHA-256. However, the strength of the hash function is immaterial because what we are attacking is the truncated 96-bit MAC. The underlying hash function does not matter. Following the analysis explain in Section III, it should require about $2^{48}$ computations on average to get a collision.

Our implementation runs at 160 MH/s for TLS 1.1 and 113 MH/s for TLS 1.2 on a Tesla K20Xm GPU. This is comparable to the expected speed we can derive from benchmarks of MD5, SHA-1 and SHA-256 on this GPU. It took 20 days to find a collision for TLS 1.1, using four Tesla K20Xm GPUs. Our demo evaluated the PRF about $2^{49.9}$ times, which is rather unlucky: it should take half that number on average. We note that the generic collision attack is completely parallelizable and hence the time for finding a collision can be brought down to an arbitrarily small number by throwing enough computational power at it. Using Amazon EC2, this should cost about $140 for TLS 1.1, and $200 for TLS 1.2. The transcripts are available on our website.
<figure><img src="image_104.png" /><figcaption>Fig. 7. IKEv2: A mutually-authenticated key exchange. Message parts colored in red can have arbitrary length.</figcaption></figure>

**Truncated HMAC is not collision-resistant** A more general lesson to be taken from our attack on tls-unique is that there are many uses of HMAC in cryptographic protocols that are not protected from collisions in the underlying hash function. For example, although HMAC-MD5 may be a good MAC, it is not collision-resistant when the key is known to the attacker. Similarly, when HMAC-SHA256 is truncated to 96 bits, it may still be a good MAC, but it is certainly not a good hash function (since collisions can still be found in $2^{48}$ steps). Consequently, when inspecting the use of hash functions in Internet protocols, it would be a mistake to assume that all uses of HMAC are safe; it is important to look both at the mechanism and its intended security goal. In some cases, we may need HMAC to be both a MAC and a collision-resistant hash function.

## VI. TRANSCRIPT COLLISIONS IN IKE AND SSH

Although the bulk of this paper has focused on collisions in TLS, similar attacks apply to other mainstream protocols like IKEv1, IKEv2, and SSH. We describe two exemplary attacks here.

### A. Breaking IKEv2 Initiator Authentication using a Precomputed Common-Prefix Transcript Collision

Figure 7 depicts the IKEv2 authenticated key exchange protocol, which is similar to the SIGMA protocol discussed in Section II. The initiator first sends an SA_INIT request containing its Diffie-Hellman value $g^x$, nonce $n_i$, and proposed cryptographic parameters $SA_i$, $info_i$. The responder replies with its own public value $g^y$, nonce $n_r$ and parameters $SA_r$, $info_r$. Alternatively, the responder may send a cookie $ck$, thereby asking the initiator to restart the protocol by sending the same SA_INIT request but with $ck$ included in it.

After the SA_INIT exchange, the initiator and responder authenticate each other by signing a portion of the message transcript. Notably the initiator signs:

$$ \text{hash}(\text{SA\_INIT}(ck|\text{SA}_i|g^x|n_i|\text{info}_i)|n_r|\text{mac}(k_i, \text{ID}_i)) $$

Figure 11 in Appendix depicts an attack on IKEv2 initiator authentication that relies on a transcript collision on this signature. The network attacker intercepts the SA_INIT request from $I$ to $R$ and responds with a cookie $ck$. The initiator $I$ restarts the key exchange by including $ck$ in the new SA_INIT request ($m_1$). However, the attacker has chosen $ck$ in a way that the hash of $m_1$ is the same as the hash of a tampered SA_INIT request $m_1'$ that contains the attacker's Diffie-Hellman public value $g^{x'}$. The attacker sends this tampered request $m_1'$ to the responder and upon receiving a response, it tampers with the response to replace $R$'s Diffie-Hellman key $g^y$ with its own key $g^{y'}$. Note that the attacker does not tamper with the nonces $n_i, n_r$.

At this point, the attacker knows the shared secrets $g^{x'y}, g^{xy'}$ and encryption keys on the two connections. Moreover the hash used in the signature transcript collides all the way to the mac($k_i$, ID$_i$). To complete the attack, the attacker must ensure that $k_i$ is that same at $I$ and $R$. It can ensure this by choosing $x', y'$ such that $g^{x'y} = g^{xy'}$ (as discussed below). Thereafter, it can forward $I$'s signature to $R$ and hence impersonate $I$.

**Implementing the Attack** To implement the attack, we must first find a collision between $m_1$ and $m_1'$. We observe that in IKEv2 the length of the cookie is supposed to be at most 64 octets but we found that many implementations allow cookies of up to $2^{16}$ bytes. We can use this flexibility in computing long collisions.

The attacker finds two length-prefixed bitstrings ($C_1, C_2$) of $L$ bytes each such that

$$ \text{hash}(\text{SA\_INIT}(\underbrace{[C_1|-]}_{ck})|-)) = \text{hash}(\text{SA\_INIT}(\underbrace{[C_2|-]}_{ck'})) $$

where the length of $ck$ is set to $L+M$, that is, $ck$ has $M$ empty bytes ready to fill in. We set $M$ to the length of the bitstring $SA_i'|g^{x'}|n_i$ that the attacker wants to send to $R$ in its tampered SA_INIT request $m_1'$. The idea is that the attacker can now stuff the tampered message into $ck$, and can stuff the original message into $info_i'$ to obtain a transcript collision:

$$ \begin{aligned} \text{hash}(\text{SA\_INIT}(\underbrace{[C_1|SA_i'|g^{x'}|n_i]}_{ck}|\text{SA}_i|g^x|n_i|\text{info}_i)|-)) = \\ \text{hash}(\text{SA\_INIT}(\underbrace{[C_2|SA_i'|g^{x'}|n_i]}_{ck}|\underbrace{[\text{SA}_i|g^x|n_i|\text{info}_i]}|-))|-) \end{aligned} $$

The collision ($C_1, C_2$) can be found easily as a chosen-prefix collision attack. Since the collision occurs before any unpredictable value has been included in the message, it can be computed offline; that is, it does not have to be computed while a connection is live. The collision can then be used to break any number of connections between $I$ and $R$. Such collisions are easy to compute for MD5, but we found that even
though MD5 signatures are allowed by the standard, they are not commonly supported by IKEv2 implementations. However, SHA-1 signatures are mandatory for all IKEv2 implementations, so an offline chosen-prefix collision on SHA-1 is enough to mount the attack. The best known complexity of such collisions is currently $2^{77}$, which may be feasible for a powerful adversary (especially if better shortcut attacks on SHA-1 are discovered).

We also observe that the two prefixes are very similar: we only need the length of the cookie to be different. Following the format of IKE message, the length field is on bytes 22 and 23 of the hashed transcript, and all previous bytes must have a fixed value. Hence, we can almost use a common-prefix collision attack, if the collision algorithm introduces a difference in bytes 22-23, and no difference in preceding bytes. For MD5, the most efficient collision attacks do not have a compatible message difference, but it seems possible to build a dedicated attack with complexity below $2^{39}$. However, for SHA-1, all known collision attacks use differences in every message words, and are thus unsuitable.

The final step to implement the attack is to ensure that $g^{xy'} = g^{x'y}$. To achieve this, we rely on a small subgroup confinement attack. To see a simple example, suppose the attacker chose $x' = y' = 0$; then the two shared secrets would have the value 1. This specific solution would not work in practice because most IKEv2 implementations validate the received Diffie-Hellman public value to ensure that it is larger than 1 and smaller than $p-1$. However, many IKEv2 implementations support the Diffie-Hellman groups 22-24 that are known to have many small subgroups. These implementations do not validate the incoming public value, and hence are susceptible to similar small subgroup confinement attacks, as discussed in [5]. To complete our transcript collision attack, the MitM can use one such small subgroup to ensure that the shared values on the two connections are the same with high probability.

## B. Breaking IKEv1 Initiator Authentication with a Generic Transcript Collision

IKEv1, the predecessor of IKEv2, and is also vulnerable to transcript collision attacks. We briefly outline one attack, without giving more details for lack of space. The initiator's signature in IKEv1 is computed as:

$$ \text{sign}(sk_I, \text{prf}(\text{prf}(n_i|n_r, g^{xy}), g^x|g^y|c_i|c_r|SA_i|\text{ID}_i)) $$

A commonly-used PRF function in IKEv1 is HMAC-MD5, and we find a generic transcript collision attack on the outer PRF value that allows initiator impersonation. A man-in-the-middle attacker intercepts a connection between $I$ and $R$; it tries out many random $g^{y'}$ values on the client-side, and many random values

<figure><img src="image_105.png" /><figcaption>Fig. 8. SSH-2: Key exchange and user authentication.</figcaption></figure>

(embedded in) $\text{ID}'$ on the server side, until the PRF values on the two sides collide. It can then forward $I'$'s signature to $R$, even though it knows the Diffie-Hellman shared secret. When the PRF is HMAC-MD5, this generic collision attack costs about $2 * 2^{64}$ HMAC computations per connection.

## C. Downgrading SSH-2 to Weak Ciphersuites with a Chosen-Prefix Transcript Collision

Figure 8 depicts the SSH-2 [39] protocol, which implements yet another variation of an authenticated Diffie-Hellman protocol. The client and server exchange identification strings $V_c, V_s$, negotiate protocol parameters $I_c, I_s$, and perform a Diffie-Hellman exchange $g^x, g^y$. To authenticate the exchange, clients and servers sign a session hash, defined as:

$$ H = \text{hash}(V_c|V_s|I_c|I_s|pk_S|g^x|g^y|g^{xy}) $$

We show that a target collision on this hash value can allow downgrade attacks.

Figure 12 in Appendix depicts a downgrade attack on SSH-2. The network attacker tampers with the key exchange message $I_c$ in one direction and with $I_s$ in the other. It chooses their values in a way such that the following hashes coincide

$$ \text{hash}(V_c|V_s|I_c|\underbrace{C_1}_{I'_s}|\underbrace{-}_{I'_c}) = \text{hash}(V_c|V_s|\underbrace{C_2}_{I'_c}) $$

Using this collision, we leave enough space empty in $I'_s$ to stuff the real $I_s$ inside. Consequently the session hashes on the two sides coincide and the connection is completed. In this attack, the MitM does not tamper with the Diffie-Hellman values and hence it does not know the connection keys. However, it manages to
tamper with both $I_c$ and $I_s$, and can therefore downgrade the negotiate ciphersuite to a weak cryptographic algorithm that the attacker knows how to break.

Implementing the target collision for SSH-2 requires a chosen-prefix attack on SHA-1 which is still considered impractical (at least $2^{77}$ work). Moreover, since the two tampered fields $I_c$ and $I_s$ are meant to be strings (not bitstrings), we cannot use arbitrary collisions. Still, we find this attack to be an interesting illustration of the use of transcript collisions for downgrade attacks.

SSH-2 has a peculiar session hash construction, with the shared secret $g^{xy}$ placed at the end. This makes certain kinds of collision attacks more difficult, but we note that this construction is not particularly secure; since it includes the shared secret, the session hash needs to be *non-leaking* in addition to being collision-resistant [4]. Moreover, if the SSH server reuses its Diffie-Hellman public value, this secret suffix becomes vulnerable to key recovery attacks like on APOP [25].

Other variations of SSH allow for more tampering, which may enable new attacks. The SSH Diffie-Hellman Group Exchange protocol [10] allows SSH servers to choose any Diffie-Hellman group for use in the key exchange. So, like in our TLS attacks, a man-in-the-middle attacker can send a bogus or weak group to the client, and use it to control more fields in the session hash and mount new transcript collision attacks.

## VII. SLOTH: RESPONSIBLE DISCLOSURE AND IMPACT

Table I summarizes the attacks discussed in this paper. Three of our attacks on TLS are already practical; others are within the reach of powerful adversaries.

Our attacks on TLS were publicly disclosed under the acronym SLOTH (security losses from obsolete and truncated transcript hashes) and were assigned a protocol-level CVE-2015-7575. We informed the authors of affected protocol specifications and developers for various TLS libraries. We recommended that protocols and implementations should stop using MD5-based signatures and other weak hash constructions. Our disclosure and recommendations resulted in the following security updates:

1) TLS 1.3 draft 7 stopped truncating the Finished MACs and started using the full HMAC output.

2) TLS 1.3 draft 8 deprecated MD5 signatures.

3) The Token Binding Protocol draft 2 removed tls-unique and moved to a stronger channel binding.

4) Akamai servers disabled support or RSA-MD5 client and server signatures.

5) Red Hat issued backported patches RHEL 6 and 7 to disable MD5 signatures in their version of OpenSSL version 1.0.1e.

6) NSS 3.21 (FireFox 43) disabled support for MD5 server signatures; MD5-based client signatures were already disabled.

7) GnuTLS 3.3.15 disabled MD5 signatures in the default configuration.

8) BouncyCastle Java 1.54 (C# 1.8.1) disabled MD5 signatures in the default configuration.

9) Oracle and IBM are updating the TLS implementation in their Java runtimes to disable MD5 signatures in the default configuration.

10) mbedTLS is being updated to disable MD5 server signatures; MD5 client signatures were already disabled.

These changes impact the Firefox and Android browsers, about 31% of web servers, most Java application servers and their clients, and many other custom applications that use less well-known TLS libraries. We are maintaining a website with the currently known attacks, affected software, and disclosure status at our website:

http://sloth-attack.org

## VIII. CONCLUSIONS

We have demonstrated that the use of MD5 and truncated HMACs for authenticating transcripts in various Internet protocols leads to exploitable chosen-prefix and generic collision attacks. We also showed several unsafe uses of SHA-1 that will become dangerous when more efficient collision-finding algorithms for SHA-1 are discovered. In all cases, the complexity of our transcript collision attacks are significantly lower than the estimated work for a second preimage attack on the underlying hash function. This definitively settles the debate on whether the security of mainstream cryptographic protocols depend on collision resistance. The answer is yes, cryptographers were right. Except in rare cases, mainstream protocols do require collision resistance for protection against man-in-the-middle transcript collision attacks. Consequently, we strongly recommend that weak hash functions like MD5 and SHA-1 should not just be deprecated; they should be forcefully disabled in existing protocols.

An open research question is whether it is possible to design key exchange protocols that will be resilient to new collision attacks. One strategy is to use a commitment scheme (like ZRTP [40]) that would make it more difficult for a man-in-the-middle to tamper with the transcript. However, such schemes may still be vulnerable to certain shortcut collisions [19]. For signatures, randomized hashing [13] provides a different way forward but its integration into a complex protocol like TLS would need to be carefully analyzed.
<table><caption>TABLE I. SUMMARY OF TRANSCRIPT COLLISION ATTACKS ON INTERNET PROTOCOLS</caption><thead><tr><th>Protocol</th><th>Property</th><th>Mechanism</th><th>Attack</th><th>Collision Type</th><th>Precomp.</th><th>Work/conn.</th><th>Preimage</th><th>Wall-clock time</th></tr></thead><tbody><tr><td>TLS 1.2</td><td>Client Auth</td><td>RSA-MD5</td><td>Impersonation</td><td>Chosen Prefix</td><td></td><td>2<sup>39</sup></td><td>2<sup>128</sup></td><td>48 core hours</td></tr><tr><td>TLS 1.3</td><td>Server Auth</td><td>RSA-MD5</td><td>Impersonation</td><td>Chosen Prefix</td><td></td><td>2<sup>39</sup></td><td>2<sup>128</sup></td><td>48 core hours</td></tr><tr><td>TLS 1.0-1.2</td><td>Channel Binding</td><td>HMAC (96 bits)</td><td>Impersonation</td><td>Generic</td><td></td><td>2<sup>48</sup></td><td>2<sup>96</sup></td><td>80 GPU days</td></tr><tr><td>TLS 1.2</td><td>Server Auth</td><td>RSA-MD5</td><td>Impersonation</td><td>Generic</td><td>2<sup>X</sup> conn.</td><td>2<sup>128-X</sup></td><td>2<sup>128</sup></td><td></td></tr><tr><td>TLS 1.0-1.1</td><td>Handshake Integrity</td><td>MD5 | SHA-1</td><td>Downgrade</td><td>Chosen Prefix</td><td></td><td>2<sup>77</sup></td><td>2<sup>160</sup></td><td></td></tr><tr><td>IKE v1</td><td>Initiator Auth</td><td>HMAC-MD5</td><td>Impersonation</td><td>Generic</td><td></td><td>2<sup>65</sup></td><td>2<sup>128</sup></td><td></td></tr><tr><td>IKE v2</td><td>Initiator Auth</td><td>RSA-SHA-1</td><td>Impersonation</td><td>Chosen Prefix</td><td>2<sup>77</sup></td><td>0</td><td>2<sup>160</sup></td><td></td></tr><tr><td>SSH-2</td><td>Exchange Integrity</td><td>SHA-1</td><td>Downgrade</td><td>Chosen Prefix</td><td></td><td>2<sup>77</sup></td><td>2<sup>160</sup></td><td></td></tr></tbody></table>

REFERENCES

[1] D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Zanella-Béguelin, and P. Zimmermann. Imperfect forward secrecy: How Diffie-Hellman fails in practice. In *ACM CCS*, 2015.

[2] J. Altman, N. Williams, and L. Zhu. Channel bindings for TLS. IETF RFC 5929, 2010.

[3] S. Bellovin and E. Rescorla. Deploying a new hash algorithm. In *NDSS*, 2006.

[4] F. Bergsma, B. Dowling, F. Kohlar, J. Schwenk, and D. Stebila. Multi-ciphersuite security of the secure shell (ssh) protocol. In *ACM CCS*, pages 369–381, 2014.

[5] K. Bhargavan, A. Delignat-Lavaud, and A. Pironti. Verified contributive channel bindings for compound authentication. In *NDSS*, 2015.

[6] K. Bhargavan, A. D. Lavaud, C. Fournet, A. Pironti, and P.-Y. Strub. Triple handshakes and cookie cutters: Breaking and fixing authentication over TLS. In *IEEE S&P (Oakland)*, 2014.

[7] I. B. Damgård. A design principle for hash functions. In *CRYPTO’89*, 1990.

[8] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.2. IETF RFC 5246, 2008.

[9] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.3. Internet Draft, 2014.

[10] M. Friedl, N. Provos, and W. Simpson. Diffie-Hellman Group Exchange for the Secure Shell (SSH) Transport Layer Protocol. IETF RFC 4419, 2006.

[11] F. Giesen, F. Kohlar, and D. Stebila. On the security of TLS renegotiation. In *ACM CCS*, 2013.

[12] D. Gillmor. Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS. Internet Draft, 2015.

[13] S. Halevi and H. Krawczyk. Strengthening digital signatures via randomized hashing. In *CRYPTO*, 2006.

[14] B. Hill, D. Baghdasaryan, B. Blanke, R. Lindemann, and J. Hodges. FIDO UAF Application API and Transport Binding Specification v1.0. Draft Specification, 2015.

[15] P. Hoffman. Use of Hash Algorithms in Internet Key Exchange (IKE) and IPsec. IETF RFC 4894, 2007.

[16] P. Hoffman and B. Schneier. Attacks on Cryptographic Hashes in Internet Protocols. IETF RFC 4270, 2005.

[17] T. Jager, F. Kohlar, S. Schäge, and J. Schwenk. On the security of TLS-DHE in the standard model. In *CRYPTO*, 2012.

[18] A. Joux. Multicollisions in iterated hash functions. application to cascaded constructions. In *CRYPTO*, 2004.

[19] J. Kelsey and T. Kohno. Herding hash functions and the nostradamus attack. In *EUROCRYPT*, 2006.

[20] D. Knuth. Seminumerical algorithms, volume 2 of the art of computer programming, 1981.

[21] H. Krawczyk. SIGMA: The SIGn-and-MAc approach to authenticated Diffie-Hellman and its use in the IKE protocols. In *CRYPTO*, 2003.

[22] H. Krawczyk, K. G. Paterson, and H. Wee. On the security of the TLS protocol: A systematic analysis. In *CRYPTO*, 2013.

[23] A. Langley. Transport Layer Security (TLS) Snap Start. Internet Draft, 2010.

[24] A. Langley. Transport Layer Security (TLS) Next Protocol Negotiation Extension. Internet Draft, 2012.

[25] G. Leurent. Practical key-recovery attack against APOP, an MD5-based challenge-response authentication. *IJACT*, 1(1):32–46, 2008.

[26] N. Mavrogiannopoulos, F. Vercauteren, V. Velichkov, and B. Preneel. A cross-protocol attack on the TLS protocol. In *ACM CCS*, 2012.

[27] F. Mendel, C. Rechberger, and M. Schläffer. MD5 is weaker than weak: Attacks on concatenated combiners. In *ASIACRYPT*, 2009.

[28] A. Menon-Sen, N. Williams, A. Melnikov, and C. Newman. Salted Challenge Response Authentication Mechanism (SCRAM) SASL and GSS-API Mechanisms. IETF RFC 5802, 2010.

[29] R. C. Merkle. A certified digital signature. In *CRYPTO’89*, 1990.

[30] J. M. Pollard. A monte carlo method for factorization. *BIT Numerical Mathematics*, 15(3):331–334, 1975.

[31] J. M. Pollard. Monte carlo methods for index computation. *Mathematics of computation*, 32(143):918–924, 1978.

[32] A. Popov, M. Nystroem, D. Balfanz, and A. Langley. The Token Binding Protocol Version 1.0. Internet Draft, 2015.

[33] M. Stevens. Hashclash. https://marc.stevens.nl/p/hashclash/.

[34] M. Stevens. Counter-cryptanalysis. In *CRYPTO*, 2013.

[35] M. Stevens. New collision attacks on SHA-1 based on optimal joint local-collision analysis. In *EUROCRYPT*, 2013.

[36] M. Stevens, A. K. Lenstra, and B. de Weger. Chosen-prefix collisions for MD5 and applications. *IJACT*, 2(4):322–359, 2012.

[37] P. C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications. *J. Cryptology*, 12(1):1–28, 1999.

[38] X. Wang and H. Yu. How to break MD5 and other hash functions. In *EUROCRYPT*, 2005.

[39] T. Ylonen and C. Lonvick. The Secure Shell (SSH) Transport Layer Protocol. RFC 4253 (Proposed Standard), 2006.

[40] P. Zimmermann. ZRTP: Media Path Key Agreement for Unicast Secure RTP. IETF RFC 6189, 2012.
<table><caption>TABLE II. COMPLEXITY OF FINDING COLLISIONS IN VARIOUS HASH CONSTRUCTIONS</caption><thead><tr><th>H</th><th>Collision</th><th>CPC</th></tr></thead><tbody><tr><td>Generic</td><td>2<sup>N/2</sup></td><td>2<sup>N/2</sup></td></tr><tr><td>H<sub>1</sub>|H<sub>2</sub></td><td>2<sup>N<sub>1</sub>/2</sup>N<sub>2</sub>/2 + 2<sup>N<sub>2</sub>/2</sup></td><td>2<sup>N<sub>1</sub>/2</sup>N<sub>2</sub>/2 + 2<sup>N<sub>2</sub>/2</sup></td></tr><tr><td>MD5</td><td>2<sup>16</sup></td><td>2<sup>39</sup></td></tr><tr><td>SHA-1</td><td>2<sup>61</sup></td><td>2<sup>77</sup></td></tr><tr><td>MD5 | SHA-1</td><td>2<sup>67</sup></td><td>2<sup>77</sup></td></tr></tbody></table>

APPENDIX

A. Attacks against Hash Functions

We now give more details about attacks against hash function, considering both generic attacks and dedicated attacks against widely-used functions MD5 and SHA-1. The main results are summarized in Table II.

**Generic collision attacks** While a basic collision attack requires to compute and store $2^{N/2}$ images of the hash function, it is possible to mount a parallel and memory-less attack with a very small overhead. The main idea was introduced by Pollard as the Rho algorithm for factorization [30] and discrete logarithms [31], and was later generalized to collision search. The hash function is first restricted from $\{0, 1\}^* \to \{0, 1\}^N$ to $\{0, 1\}^N \to \{0, 1\}^N$, so that it can be iterated. After some number of steps, a chain of iterations reaches a cycle, and the graph will have the shape of the greek letter $\rho$. On average, the cycle has length $O(2^{N/2})$ and is reached after $O(2^{N/2})$ steps. The point where the tail of the meets with the cycle reveals a collision in the hash function. It can be detected in time $O(2^{N/2})$ with little or no memory, using various cycle detection methods, such as Floyd's algorithm [20] (also known as tortoise and hare).

Some variants of this attack using distinguished points can be parallelized efficiently. We now describe a parallel version of Pollard's Lambda algorithm, as described by van Oorschot and Wiener [37], using c CPUs. Each CPU will compute iteration chains of the function $H$, and stop when reaching a distinguished point, that is a point with some easy to test property. For instance, we stop a computation when the ending point satisfies $x < 2^{N/2} \alpha c$ for some small constant $\alpha$, so that the expected length of a chain is $2^{N/2}/\alpha c$. When a chain is finished, we store the starting point, the length, and the ending point. We generate $\alpha c$ chains in this way, so that the function has been evaluated about $2^{N/2}$ times, and there is a high probability that there was a collision. The important idea of this attack is that if a given point is reached by two different chains, both chain will stop at the same distinguished point. Therefore, we look at the ending points of the chains, and when a collision is detected, we restart the chains from the starting point in

<figure><img src="image_106.png" /><figcaption>Fig. 9. Multi-collision attack</figcaption></figure>

<figure><img src="image_107.png" /><figcaption>Fig. 10. CPC attack against MD5 | SHA-1</figcaption></figure>

order to locate the collision. This attack requires about $2^{N/2}$ evaluations of $H$, and a memory of $\alpha c$ when using c CPUs.

This attack can be tweaked for a chosen-prefix collision attack using an auxiliary function $g: \{0, 1\}^N \to \{0, 1\}^N$ defined as:

$$g(x) = \begin{cases} H(P|x) & \text{if } x \text{ is even} \\ H(P'|x) & \text{if } x \text{ is odd.} \end{cases}$$

Collisions in $g$ can be found with the previous techniques. With probability $1/2$ a collision is $g$ is between an even $x$ and an odd $x'$ (or vice versa), this implies a chosen-prefix collision $H(P|x) = H(P'|x')$. An accurate complexity analysis is provided in [37]: a collision is expected to be found after $\sqrt{\pi 2^N/2}$ evaluations. For a chosen-prefix collision, we expect to find two collisions in $g$ after $\sqrt{\pi 2^N}$ evaluations.

**Concatenation** Collisions in the concatenation of two hash functions $H_1|H_2$ can be found with roughly the same effort as breaking the strongest one of the two, using the multi-collision technique of Joux [18].

The adversary first finds a collision pair $(x_0, x'_0)$ for $H_1$, starting from the initialization value of $H_1$. Then it finds a collision pair $(x_1, x'_1)$ starting from $H_1(x_0) = H_1(x'_0)$. This defines 4 messages with the same $H_1$-digest: $x_0|x_1, x_0|x'_1, x'_0|x_1, x'_0|x'_1$. After $N_2/2$ steps, this defines a set of $2^{N_2/2}$ messages with the
same $H_1$-digest. With high probability, two of these
messages have the same $H_2$-digest as well (see Fig-
ure 9). Therefore, one can find a collision in $H_1|H_2$
with a complexity only $N_2/2 \times 2^{N_1/2} + 2^{N_2/2}$. For
MD5 | SHA-1, this translates to $2^{80}$, roughly as much
as a generic collision attack on SHA-1.

Better attacks against MD5 | SHA-1 result from the
combination of Joux's multicollision technique with
shortcut attacks against SHA-1. A collision attack can
be build for a cost of 64 × 2⁶¹ + 2⁶⁴ ≈ 2⁶⁷ (building
sequentially 64 collisions for MD5). For a chosen-
prefix collision, we first perform a chosen-prefix col-
lision against SHA-1, to generate messages (x, x') such
that SHA-1(P|x) = SHA-1(P'|x'). Then we build
a multicollision in SHA-1 starting from this value,
and we evaluate MD5 over a set of 2⁶⁴ messages
in order to find a collision. The total cost is about
2⁷⁷ + 64 × 2⁶¹ + 2⁶⁴ ≈ 2⁷⁷ (see Figure 10).

Moreover it has been shown that it is possible to
combine cryptanalytic shortcuts both on SHA-1 and
MD5, assuming that collision attacks against SHA-1
improve in the future [27]. This may allow collision
attacks against MD5 | SHA-1 with less than 2⁶⁴ work.
Table II summarizes the currently-known complexities
for computing various hash collisions.

B. Transcript Collision Attacks on IKEv2 and SSH-2

<figure><img src="image_108.png" /><figcaption>Fig. 11. Man-in-the-middle initiator impersonation attack on IKEv2. The initiator *I* connects to the responder *R* but a man-in-the-middle attacker *A* intercepts and tampers with some messages (shown in *red*). *A* computes a collision (*C*₁, *C*₂) between the prefixes of two *SA_INIT* messages that both begin with a cookie payload. Then by sending a carefully crafted cookie to *I*, *A* can trigger a transcript collision on the initiator signature, which it can then forward to *R*, thereby impersonating *I* on a connection that it controls.</figcaption></figure>

<figure><img src="image_109.png" /><figcaption>Fig. 12. Man-in-the-middle downgrade attack on SSH-2. The client *C* connects to a server *S*, but a network attacker *A* tampers with the key exchange messages (shown in *red*) to downgrade them to a weak ciphersuite. To succeed, *A* must compute a chosen-prefix collision on the session hash *H* after receiving *C*'s key exchange message.</figcaption></figure>
# New Generic Attacks Against Hash-based MACs

Gaëtan Leurent<fnref n="1" />, Thomas Peyrin<fnref n="2" />, and Lei Wang<fnref n="2" />

**Abstract.** In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an *n*-bit MAC is built from a hash function with a *l*-bit state ($l \ge n$), there is a well-known existential forgery attack with complexity $2^{l/2}$. However, the remaining security after $2^{l/2}$ computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should require $2^n$ computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should also require $2^l$ computations (or $2^k$ if $k < l$).

In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only $\tilde{O}(2^{l/2})$. In addition, we show a key-recovery attack with complexity $\tilde{O}(2^{3l/4})$ against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instanciated with concrete hash functions.

We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

**Key words:** NMAC, HMAC, hash function, distinguishing-H, key recovery, GOST.

## 1 Introduction

Message Authentication Codes (MACs) are crucial components in many security systems. A MAC is a function that takes a *k*-bit secret key *K* and an arbitrarily long message *M* as inputs, and outputs a fixed-length tag of size *n* bits. The tag is used to authenticate the message, and will be verified by the receiving party using the same key *K*. Common MAC algorithms are built from block ciphers (e.g. CBC-MAC), from hash functions (e.g. HMAC), or from universal

<footnote n="1">¹ Université Catholique de Louvain, Belgium
gaetan.leurent@uclouvain.be</footnote>

<footnote n="2">² Nanyang Technological University, Singapore
thomas.peyrin@gmail.com wang.lei@ntu.edu.sg</footnote>
hash functions (e.g. UMAC). In this paper we study MAC algorithms based on hash functions.

As a cryptographic primitive, a MAC algorithm should meet some security requirements. It should be impossible to recover the secret key except by exhaustive search, and it should be computationally impossible to forge a valid MAC without knowing the secret key, the message being chosen by the attacker (existential forgery) or given as a challenge (universal forgery). In addition, cryptanalysts have also studied security notions based on distinguishing games. Informally, the distinguishing-R game is to distinguish a MAC construction from a random function, while the distinguishing-H game is to distinguish a known MAC construction (e.g. HMAC) instantiated with a known component (e.g. SHA-1) under a random key from the same construction instantiated with a random component (e.g. HMAC with a fixed input length random function).

One of the best known MAC algorithm is HMAC [2], designed by Bellare et al. in 1996. HMAC is now widely standardized (by ANSI, IETF, ISO and NIST), and widely deployed, in particular for banking processes or Internet protocols (e.g. SSL, TLS, SSH, IPSec). It is a single-key version of the NMAC construction, the latter being built upon a keyed iterative hash function $H_K$, while HMAC uses an unkeyed iterative hash function $H$:

$$ \begin{aligned} \text{NMAC}(K_{out}, K_{in}, M) &= H_{K_{out}}(H_{K_{in}}(M)) \\ \text{HMAC}(K, M) &= H(K \oplus \text{opad} \parallel H(K \oplus \text{ipad} \parallel M)) \end{aligned} $$

where opad and ipad are predetermined constants, and where $K_{in}$ denotes the inner key and $K_{out}$ the outer one.

More generally, a MAC algorithm based on a hash function uses the key at the beginning and/or at the end of the computation, and updates an $l$-bit state with a compression function. The security of MAC algorithms is an important topic, and both positive and negative results are known. On the one hand, there is a generic attack with complexity $2^{l/2}$ based on internal collisions and length extension [17]. This gives an existential forgery attack, and a distinguishing-H attack. One the other hand, we have security proofs for several MAC algorithms such as HMAC and sandwich-MAC [2,1,26]. Roughly speaking, the proofs show that some MAC algorithms are secure up to the birthday bound ($2^{l/2}$) under various assumptions on the compression function and hash function.

Thanks to those results, one may consider that the security of hash-based MAC algorithms is well understood. However, there is still a strong interest in the security above the birthday bound. In particular, it is very common to expect security $2^k$ for key recovery attacks if the hash function is sound; the Encyclopedia of Cryptography and Security article on HMAC states explicitly [16] "A generic key recovery attack requires $2^{n/2}$ known text-MAC pairs and $2^{n+1}$ time" (assuming $n = l = k$). Indeed, key recovery attacks against HMAC with a concrete hash function with complexity between $2^{l/2}$ and $2^l$ have been considered as important results [9,24,27]. Similarly, the best known distinguishing-H and state-recovery attacks have a complexity of $2^l$ (or $2^k$ if $k < l$), and distinguishing-
<table><caption>**Table 1.** Comparison of our generic attacks on HMAC, and some previous attacks on concrete hash function. We measure the complexity as the number of calls to the compression function (i.e. number of messages times message length)</caption><thead><tr><th>Function</th><th>Attack</th><th>Complexity</th><th>M. len</th><th>Notes</th><th>Ref</th></tr></thead><tbody><tr><td>HMAC-MD5</td><td>dist-H, state rec.</td><td>2<sup>97</sup></td><td>2</td><td></td><td>[25]</td></tr><tr><td>HMAC-SHA-0</td><td>dist-H</td><td>2<sup>100</sup></td><td>2</td><td></td><td>[12]</td></tr><tr><td>HMAC-HAVAL (3-pass)</td><td>dist-H</td><td>2<sup>228</sup></td><td>2</td><td></td><td>[12]</td></tr><tr><td>HMAC-SHA-1 (43 first steps)</td><td>dist-H</td><td>2<sup>154</sup></td><td>2</td><td></td><td>[12]</td></tr><tr><td>HMAC-SHA-1 (58 first steps)</td><td>dist-H</td><td>2<sup>158</sup></td><td>2</td><td></td><td>[18]</td></tr><tr><td>HMAC-SHA-1 (61 mid. steps)</td><td>dist-H</td><td>2<sup>100</sup></td><td>2</td><td></td><td>[18]</td></tr><tr><td>HMAC-SHA-1 (62 mid. steps)</td><td>dist-H</td><td>2<sup>157</sup></td><td>2</td><td></td><td>[18]</td></tr><tr><td colspan="6"><em>Generic attacks:</em></td></tr><tr><td rowspan="3">hash-based MAC (e.g. HMAC)</td><td>dist-H</td><td>O(2<sup>l/2</sup>)</td><td>2<sup>l/2</sup></td><td></td><td>Sec. 4</td></tr><tr><td>state rec.</td><td>Õ(2<sup>l/2</sup>)</td><td>2<sup>l/2</sup></td><td></td><td>Sec. 5</td></tr><tr><td>dist-H, state rec.</td><td>O(2<sup>l-s</sup>)</td><td>2<sup>s</sup></td><td>s &le; l/4</td><td>full version</td></tr><tr><td rowspan="2">HMAC with a checksum</td><td rowspan="2">key rec.</td><td>O(l &middot; 2<sup>3l/4</sup>)</td><td>2<sup>l/2</sup></td><td></td><td>Sec. 7</td></tr><tr><td>O(l &middot; 2<sup>3l/4</sup>)</td><td>2<sup>l/4</sup></td><td></td><td>full version</td></tr><tr><td>HMAC-MD5*</td><td>dist-H, state rec.</td><td>2<sup>67</sup>, 2<sup>78</sup></td><td>2<sup>64</sup></td><td></td><td>Sec. 4, 5</td></tr><tr><td></td><td></td><td>O(2<sup>96</sup>)</td><td>2<sup>32</sup></td><td></td><td>full version</td></tr><tr><td>HMAC-HAVAL<sup>†</sup> (any)</td><td>dist-H, state rec.</td><td>O(2<sup>202</sup>)</td><td>2<sup>54</sup></td><td></td><td>full version</td></tr><tr><td>HMAC-SHA-1<sup>†</sup></td><td>dist-H, state rec.</td><td>O(2<sup>120</sup>)</td><td>2<sup>40</sup></td><td></td><td>full version</td></tr><tr><td rowspan="2">HMAC-GOST*</td><td rowspan="2">key rec.</td><td>2<sup>200</sup></td><td>2<sup>128</sup></td><td></td><td>Sec. 7</td></tr><tr><td>2<sup>200</sup></td><td>2<sup>64</sup></td><td></td><td>full version</td></tr></tbody></table>

H attacks on HMAC with a concrete hash function with complexity between 2<sup>l/2</sup> and 2<sup>l</sup> have been considered as important results [12,18,25].

**Our contributions.** In this paper we revisit the security of hash-based MAC above the birthday bound. We describe a generic distinguishing-H attack in the single key model and with complexity of only O(2<sup>l/2</sup>) computations, thus putting an end to the long time belief of the cryptography community that the best generic distinguishing-H on NMAC and HMAC requires Ω(2<sup>l</sup>) operations. Instead, we show that a distinguishing-H attack is not harder than a distinguishing-R attack. Our results actually invalidate some of the recently published cryptanalysis works on HMAC when instantiated with real hash functions [12,18,25].

Our method is based on a cycle length detection, like the work of Peyrin et. al [14], but our utilization is quite different and much less restrictive: instead of iterating many times HMAC with small messages and a special related-key, we will use only a few iterations with very long messages composed of almost the same message blocks to observe the cycle and deduct information from it. Overall,

<footnote>* The MD5 and GOST specifications allow arbitrary-length messages</footnote>

<footnote>† The SHA-1 and HAVAL specifications limits the message length to 2<sup>64</sup> bits (and 2<sup>64</sup> bits is 2<sup>54</sup> blocks)</footnote>
unlike in [14], our technique works in the single-key model, for both **HMAC** and **NMAC**, and can be applied for any key size. In addition, leveraging our new ideas, we provide a single-key internal state recovery for any hash-based MAC with only $O(l \cdot \log(l) \cdot 2^{l/2})$ computations.

We also introduce a different approach to reduce the length of the queried messages for distinguishing-H and internal-state-recovery attacks. Due to the limited space, we only give a quick overview of these shorter-message attacks, and refer the reader to the full version of this paper for more details.

Finally, this internal state recovery can be transformed into a single-key key recovery attack on **HMAC** with complexity $O(l \cdot 2^{3l/4})$ when instantiated with a hash function using a checksum, such as the **GOST** hash function [6]. A surprising corollary to our results is that incorporating a checksum to a hash function seems to actually reduce the security of the overall **HMAC** design.

We give an overview of our results, and a comparison with some previous analysis in Table 1.

The description of **HMAC/NMAC** algorithms and their security are given in Section 2 and we recall in Section 3 the cycle-detection ideas from [14]. Then, we provide in Section 4 the generic distinguishing-H attack. We give in Sections 5 and 6 internal state recovery methods, and finally describe our results when the hash function incorporates a checksum in Section 7.

## 2 Hash-based MAC algorithms

In this paper, we study a category of MAC algorithms based on hash functions, where the key is used at the beginning and at the end of the computation, as described in Figure 1. More precisely, we consider algorithms where: the message processing is done by updating an internal state $x$ using a compression function $h$; the state is initialized with a key dependent value $I_k$; and the tag is computed from the last state $x_p$ and the key $K$ by an output function $g$.

$$x_0 = I_K \qquad x_{i+1} = h(x_i, m_i) \qquad \text{MAC}_K(M) = g(K, x_p, |M|)$$

In particular, this description covers **NMAC/HMAC** [2], envelope-MAC [21], and sandwich-MAC [26]. The results described in Sections 4 and 5 can be applied to any hash-based MAC, but we focus on **HMAC** for our explanations because it is the most widely used hash-based MAC, and its security has been widely analyzed already. On the other hand the result of Section 7 is specific to MAC algorithms that process the key as part of the message, such as **HMAC**.

### 2.1 Description of NMAC and HMAC

**A hash function** $H$ is a function that takes an arbitrary length input message $M$ and outputs a fixed hash value of size $n$ bits.

Virtually every hash function in use today follows an iterated structure like the classical Merkle-Damgård construction [13,4]. Iterative hash functions are
<figure><img src="image_110.png" /><figcaption>**Fig. 1.** Hash-based MAC. Only the initial value and the final transformation are keyed.</figcaption></figure>

built upon successive applications of a so-called compression function $h$, that takes a $b$-bit message block and a $l$-bit chaining value as inputs and outputs a $l$-bit value (where $l \ge n$). An output function can be included to derive the $n$-bit hash output from the last chaining variable and from the message length. When $l > n$ (resp. when $l = n$) we say that the hash function is wide pipe (resp. narrow pipe).

The message $M$ is first padded and then divided into blocks $m_i$ of $b$ bits each. Then, the message blocks are successively used to update the $l$-bit internal state $x_i$ with the compression function $h$. Once all the message blocks have been processed, the output function $g$ is applied to the last internal state value $x_p$.

$$x_0 = IV \qquad x_{i+1} = h(x_i, m_i) \qquad \text{hash} = g(x_p, |M|)$$

**The MAC algorithm NMAC [2]** uses two $l$-bit keys $K_{out}$ and $K_{in}$. NMAC replaces the public $IV$ of a hash function $H$ by a secret key $K$ to produce a keyed hash function $H_K(M)$. NMAC is then defined as:

$$\text{NMAC}(K_{out}, K_{in}, M) = H_{K_{out}}(H_{K_{in}}(M)).$$

**The MAC algorithm HMAC [2]** is a single-key version of NMAC, with $K_{out} = h(IV, K \oplus \text{opad})$ and $K_{in} = h(IV, K \oplus \text{ipad})$, where opad and ipad are $b$-bit constants. However, a very interesting property of HMAC for practical utilization is that it can use any key size and can be instantiated with an unkeyed hash function (like MD5, SHA-1, etc. which have a fixed $IV$):

$$\text{HMAC}(K, M) = H(K \oplus \text{opad} \parallel H(K \oplus \text{ipad} \parallel M)).$$

where $\parallel$ denotes the concatenation operation. For simplicity of the description and without loss of generality concerning our attacks, in the rest of this article we assume that the key can fit in one compression function message block, i.e. $k \le b$ (note that $K$ is actually padded to $b$ bits if $k < b$).

## 2.2 Security of NMAC and HMAC

In [1], Bellare proved that the NMAC construction is a pseudo-random function (PRF) under the sole assumption that the internal compression function $h$ (keyed
by the chaining variable input) is a PRF. The result can be transposed to HMAC as well under the extra assumption that $h$ is also a PRF when keyed by the message input.

Concerning key recovery attacks, an adversary should not be able to recover the key in less than $2^k$ computations for both HMAC and NMAC. In the case of NMAC one can attack the two keys $K_{out}$ and $K_{in}$ independently by first finding an internal collision and then using this colliding pair information to brute force the first key $K_{in}$, and finally the second one $K_{out}$.

Universal or existential forgery attacks should cost $2^n$ computations for a perfectly secure $n$-bit MAC. However, the iterated nature of the hash functions used inside NMAC or HMAC allows a simple existential forgery attack requiring only $2^{l/2}$ computations [17]. Indeed, with $2^{l/2}$ queries, an adversary can first find an internal collision between two messages $(M, M')$ of the same length during the first hash call. Then, any extra block $m$ added to both of these two messages will lead again to an internal collision. Thus, the attacker can simply forge a valid MAC by only querying for $M \parallel m$ and deducing that $M' \parallel m$ will have the same MAC value.

Concerning distinguishers on HMAC or NMAC, two types have been discussed in the literature: Distinguishing-R and Distinguishing-H attacks, defined below:

**Distinguishing-R.** Let $\mathcal{F}_n$ be the set of $n$-bit output functions. We denote $F_K$ the oracle on which the adversary $\mathcal{A}$ can make queries. The oracle is instantiated either with $F_K = \text{HMAC}_K$ (with $K$ being a randomly chosen $k$-bit key) or with a randomly chosen function $R_K$ from $\mathcal{F}_n$. The goal of the adversary is to distinguish between the two cases and its advantage is given by

$$Adv(\mathcal{A}) = |\Pr[\mathcal{A}(\text{HMAC}_K) = 1] - \Pr[\mathcal{A}(R_K) = 1]|.$$

Obviously the collision-based forgery attack detailed above gives directly a distinguishing-R attack on NMAC and HMAC. Thus, the expected security of HMAC and NMAC against distinguishing-R attacks is $2^{l/2}$ computations.

**Distinguishing-H.** The attacker is given access to an oracle $\text{HMAC}_K$ and the compression function of the HMAC oracle is instantiated either with a known dedicated compression function $h$ or with a random chosen function $r$ from $\mathcal{F}_l^{b+l}$ (the set of $(b+l)$-bit to $l$-bit functions), which we denote $\text{HMAC}_K^h$ and $\text{HMAC}_K^r$ respectively. The goal of the adversary is to distinguish between the two cases and its advantage is given by

$$Adv(\mathcal{A}) = |\Pr[\mathcal{A}(\text{HMAC}_K^h) = 1] - \Pr[\mathcal{A}(\text{HMAC}_K^r) = 1]|.$$

The distinguishing-H notion was introduced by Kim et al. [12] for situations where the attacker wants to check which cryptographic hash function is embedded in HMAC. To the best of our knowledge, the best known generic distinguishing-H attack requires $2^l$ computations.
**Related-key attacks.** At Asiacrypt 2012 [14], a new type of generic distinguishing (distinguishing-R or distinguishing-H) and forgery attacks for HMAC was proposed. These attacks are in the related-key model and can apply even to wide-pipe proposals, but they only work for HMAC, and only when a special restrictive criterion is verified: the attacker must be able to force a specific difference between the inner and the outer keys (with the predefined values of opad and ipad in HMAC, this criterion is verified when $k = b$). The idea is to compare the cycle length when iterating the HMAC construction on small messages with a key $K$, and the cycle length when iterating with a key $K' = K \oplus \text{opad} \oplus \text{ipad}$.

**Attacks on instantiations with concrete hash functions.** Because of its widespread use in many security applications, HMAC has also been carefully scrutinized when instantiated with a concrete hash function, exploiting weaknesses of some existing hash function. In parallel to the recent impressive advances on hash function cryptanalysis, the community analyzed the possible impact on the security of HMAC when instantiated with standards such as MD4 [19], MD5 [20], SHA-1 [22] or HAVAL. In particular, key-recovery attacks have been found on HMAC-MD4 [9,24] and HMAC-HAVAL [27]. Concerning the distinguishing-H notion, one can cite for example the works from Kim et al. [12], Rechberger et al. [18] and Wang et al. [25].

However, to put these attacks in perspective, it is important to know the complexity of generic attacks, that work even with a good hash function.

# 3 Cycle detection for HMAC

Our new attacks are based on some well-known properties of random functions.

## 3.1 Random mapping properties on a finite set

Let us consider a random function $f$ mapping $n$ bits to $n$ bits and we denote $N = 2^n$. We would like to know the structure of the functional graph defined by the successive iteration of this function, for example the expected number of components, cycles, etc. First, it is easy to see that each component will contain a single cycle with several trees linked to it. This has already been studied for a long time, and in particular we recall two theorems from Flajolet and Odlyzko [7].

**Theorem 1 ([7, Th. 2]).** *The expectations of the number of components, number of cyclic points, number of terminal points, number of image points, and number of k-th iterate image points in a random mapping of size $N$ have the asymptotic forms, as $N \to \infty$:*

(i) # Components: $\frac{1}{2} \log N$

(ii) # Cyclic nodes: $\sqrt{\pi N}/2$

(iii) # Terminal nodes: $e^{-1}N$

(iv) # Image points: $(1 - e^{-1})N$

(v) # k-th iterate images: $(1 - \tau_k)N$, with $\tau_0 = 0$, $\tau_{k+1} = e^{-1+\tau_k}$.
In particular, a random mapping has only a logarithmic number of distinct components, and the number of cyclic points follows the square root of N.

By choosing a random starting point $P$ and iterating the function $f$, one will follow a path in the functional graph starting from $P$, that will eventually connect to the cycle of the component in which $P$ belongs, and we call **tail length** the number of points in this path. Similarly, we call **cycle length** the number of nodes in the cycle. Finally, the number of points in the non-repeating trajectory from $P$ is called the **rho length**, and we call **$\alpha$-node** of the path the node that connects the tail and the cycle.

**Theorem 2 ([7, Th. 3]).** *Seen from a random point in a random mapping of size N, the expectations of the tail length, cycle length, rho length, tree size, component size, and predecessors size have the following asymptotic forms:*

(i) Tail length ($\lambda$): $\sqrt{\pi N/8}$

(ii) Cycle length ($\mu$): $\sqrt{\pi N/8}$

(iii) Rho length ($\rho = \lambda + \mu$): $\sqrt{\pi N/2}$

(iv) Tree size: $N/3$

(v) Component size: $2N/3$

(vi) Predecessors size: $\sqrt{\pi N/8}$

One can see that, surprisingly, in a random mapping most of the points tend to be grouped together in a single giant component, and there is a giant tree with a significant proportion of the points. The asymptotic expectation of the maximal features is given by Flajolet and Sedgewick [8].

**Theorem 3 ([8, VII.14]).** *In a random mapping of size N, the largest tree has an expected size of $\delta_1 N$ with $\delta_1 \approx 0.48$ and the largest component has an expected size of $\delta_2 N$ with $\delta_2 \approx 0.7582$.*

These statistical properties will be useful to understand the advantage of our attacks. We show the functional graph of a simple random-looking function in Figure 4 in the Appendix.

## 3.2 Using cycle-detection to obtain some secret information

In this article and as in [14], we will study the functional graph structure of a function to derive a distinguisher or obtain some secret information. More precisely, in [14] Peyrin et al. observed that the functional graph structure of HMAC was the same when instantiated with a key $K$ or with a related key $K' = K \oplus \text{ipad} \oplus \text{opad}$ (note that in order to be able to query this related-key $K'$, the key $K$ has to be of size $b$ or $b-1$, which is quite restrictive). This is a property that should not exist for a randomly chosen function and they were able to detect this cycle structure by measuring the cycle length in both cases $K$ and $K'$, and therefore obtaining a distinguishing-R attack for HMAC in the related-key model. In practice, the attacker can build and observe the functional graph of HMAC by simply successively querying the previous $n$-bit output as new message input.

In this work, instead of studying the structure of the functional graph of HMAC directly, we will instead study the functional graph of the internal compression
function $h$ with a fixed message block: we denote $h_M(X) = h(X, M)$. We aim to obtain some information on $h_M$ that we can propagate outside the HMAC structure. This is therefore perfectly suited for a distinguishing-H attack, which requires the attacker to exhibit a property of $h$ when embedded inside the HMAC construction. We can traverse the functional graph of $h_M$ by querying the HMAC oracle with a long message composed of many repetitions of the fixed message block $M$. The issue is now to detect some properties of the functional graph of $h_M$ inside HMAC and without knowing the secret key. We explain how to do that in the next section.

# 4 Distinguishing-H attack for hash-based MACs

In the rest of the article, we use the notation $[x]^k$ to represent the successive concatenation of $k$ message blocks $x$, with $[x] = [x]^{1}$.

## 4.1 General description

In order to derive a distinguishing-H attack, we need to do some offline computations with the target compression function $h$ and use this information to compare online with the function embedded in the MAC oracle. We use the structure of the functional graph of $h_{[0]}$ to derive our attack (of course we can choose any fixed message block). We can travel in the graph by querying the oracle using consecutive [0] message blocks. However, since the key is unknown, we do not know where we start or where we stop in this graph. We have seen in the previous section that the functional graph of a random function is likely to have a giant component containing most of the nodes. We found that the cycle size of the giant component of $h_{[0]}$ is a property that can be efficiently tested.

More precisely, we first compute the cycle size of the giant component of $h_{[0]}$ offline; we denote it as $L$. Then, we measure the cycle size of the giant component of the unknown function by querying the MAC oracle with long messages composed of many consecutive [0] message blocks. If no length padding is used in the hash function, this is quite simple: we just compare $\text{MAC}([0]^{2^{l/2}})$ and $\text{MAC}([0]^{2^{l/2}+L})$. With a good probability, the sequence of $2^{l/2}$ zero block is sufficiently long to enter the cycle, and if the cycle has length $L$, the two MAC outputs will collide.

Unfortunately, this method does not work because the lengths of the messages are different, and thus the last message block with the length padding will be different and prevent the cycle collision to propagate to the MAC output. We will use a trick to overcome this issue, even though the basic method remains the same. The idea is to build a message $M$ going twice inside the cycle of the giant component, so that we can add $L$ [0] message blocks in the first cycle to obtain a message $M_1$ and $L$ [0] message blocks in the second cycle to obtain $M_2$. This is depicted in Figure 2: $M_1$ will cycle $L$ [0] message blocks in the first cycle (red dotted arrows), while $M_2$ will cycle $L$ [0] message blocks in the second cycle (blue dashed arrows), and thus they will both have the same length overall.
To perform the distinguishing-H attack, the adversary simply randomly selects an initial message block $m$ and query $M_1 = m \parallel [0]^{2^{l/2}} \parallel [1] \parallel [0]^{2^{l/2}+L}$ and $M_2 = m \parallel [0]^{2^{l/2}+L} \parallel [1] \parallel [0]^{2^{l/2}}$ to the MAC oracle, and deduce that the target function is used to instantiate the oracle if the two MAC values are colliding. The $[1]$ message block is used to quit the cycle and randomize the entry point to return again in the giant component. We give below a detailed attack procedure and complexity analysis.

<figure><img src="image_111.png" /><figcaption>Fig. 2. Distinguishing-H attack</figcaption></figure>

This attack is very interesting as the first generic distinguishing-H attack on **HMAC** and **NMAC** with a complexity lower than $2^l$. However, we note that the very long message length might be a limitation. In theory this is of no importance and our attack is indeed valid, but in practice some hash functions forbid message inputs longer than a certain length. To address this issue we provide an alternative attack in the full version of this paper, using shorter messages, at the cost of a higher complexity.

## 4.2 Detailed attack process

1. (offline) Search for a cycle in the functional graph of $h_{[0]}$ and denote $L$ its length.

2. (online) Choose a random message block $m$ and query the **HMAC** value of the two messages $M_1 = m \parallel [0]^{2^{l/2}} \parallel [1] \parallel [0]^{2^{l/2}+L}$ and $M_2 = m \parallel [0]^{2^{l/2}+L} \parallel [1] \parallel [0]^{2^{l/2}}$.

3. If the **HMAC** values of $M_1$ and $M_2$ collide then output 1, otherwise output 0.

## 4.3 Complexity and success probability analysis

We would like to evaluate the complexity of the attack. The first step will require about $2^{l/2}$ offline computations to find the cycle for the target compression function $h$. It is important to note that we can run this first step several times
in order to ensure that we are using the cycle from the largest component of
the functional graph of $h_{[0]}$. The second step makes two queries of about $2^{l/2} + 2^{l/2} + L \approx 3 \cdot 2^{l/2}$ message blocks each. Therefore, the overall complexity of the
attack is about $2^{l/2+3}$ compression function computations.

Next, we evaluate the advantage of the adversary in winning the distinguishing-H game defined in Section 2.2. We start with the case where the oracle is instantiated with the real compression function $h$. The adversary will output 1 if a collision happens between the HMAC computations of $M_1$ and $M_2$. Such a collision can happen when the following conditions are satisfied:

* The processing of the random block $m$ sets us in the same component (of the functional graph of $h_{[0]}$) as in the offline computation. Since we ensured that the largest component was found during the offline computation, and since it has an average size of $0.7582 \cdot 2^l$ elements according to Theorem 2, this event will happen with probability $0.7582$.

* The $2^{l/2}$ [0] message blocks concatenated after $m$ are enough to reach the cycle of the component, i.e. the tail length when reaching the first cycle is smaller than $2^{l/2}$. Since the average tail length is less than $2^{l/2}$ elements, this will happen with probability more than $1/2$.

* The processing of the block [1] sets us in the same component (of the functional graph of $h_{[0]}$) as in the offline computation; again the probability is $0.7582$.

* The $2^{l/2}$ [0] message blocks concatenated after [1] are enough to reach the cycle of the component; again this happens with probability $1/2$.

The collision probability is then $(0.7582)^2 \times 1/4 \approx 0.14$ and thus we have that $\Pr[\mathcal{A}(\text{HMAC}_K^h) = 1] \ge 0.14$. In the case where the oracle is instantiated with a random function $r$, the adversary will output 1 if and only if a random HMAC collision happens between messages $M_1$ and $M_2$. Such a collision can be obtained if the processing of any of the last $[0]^{2^{l/2}}$ blocks of the two messages leads to an internal collision, therefore with negligible probability $2^{l/2} \cdot 2^{-l} = 2^{-l/2}$. Overall, the adversary advantage is equal to $\text{Adv}(\mathcal{A}) = |0.14 - 2^{-l/2}| \approx 0.14$.

# 5 Internal state recovery for NMAC and HMAC

This section extends the distinguishing-H attack in order to build an internal
state recovery attack.

## 5.1 General description

In order to extend the distinguishing-H attack to a state recovery attack, we
observe that there is a high probability that the $\alpha$-node reached in the online
phase is the root of the giant tree of the functional graph of $h_{[0]}$. More precisely,
we can locate the largest tree and the corresponding $\alpha$-node in the offline phase,
by repeating the cycle search a few times. We note that $\delta_1 + \delta_2 > 1$, therefore
the largest tree is in the largest component with asymptotic probability one (see
**Theorem 3).** Thus, assuming that the online phase succeeds, the $\alpha$-node reached in the online phase is the root of the largest tree with asymptotic probability $\delta_1/\delta_2 \approx 0.63$. If we can locate the $\alpha$-node of the online phase (i.e. we deduce its block index inside the queried message), we immediately get its corresponding internal state value from the offline computations.

Since the average rho length is $\sqrt{\pi 2^{l/2}}$ we can not use a brute-force search to locate the $\alpha$-node, but we can use a binary search instead. We denote the length of the cycle of the giant component as $L$, and the follow the distinguishing-H attack to reach the cycle. We choose a random message block $m$ and we query the two messages $M_1 = m \parallel [0]^{2^{l/2}} \parallel [1] \parallel [0]^{2^{l/2}+L}$ and $M_2 = m \parallel [0]^{2^{l/2}+L} \parallel [1] \parallel [0]^{2^{l/2}}$. If the MAC collide, we know that the state reached after processing $m \parallel [0]^{2^{l/2}}$ is located inside the main cycle. We use a binary search to find the smallest $X$ so that the state reached after $m \parallel [0]^X$ is in the cycle.

The first step of the binary search should decide whether the node reached after $m \parallel [0]^{2^{l/2-1}}$ is also inside the first online cycle or not. More precisely, we check if the two messages $M'_1 = m \parallel [0]^{2^{l/2-1}} \parallel [1] \parallel [0]^{2^{l/2}+L}$ and $M'_2 = m \parallel [0]^{2^{l/2-1}+L} \parallel [1] \parallel [0]^{2^{l/2}}$ also give a colliding tag. If it is the case, then the node after processing $m \parallel [0]^{2^{l/2-1}}$ is surely inside the cycle, which implies that the $\alpha$-node is necessarily located in the first $2^{l/2-1}$ zero blocks. On the other hand, if the tags are not colliding, we cannot directly conclude that the $\alpha$-node is located in the second half since there is a non-negligible probability that the $\alpha$-node is in the first half but the $[1]$ block is directing the paths in $M'_1$ and $M'_2$ to distinct components in the functional graph of $h_{[0]}$ (in which case the tag are very likely to differ). Therefore, we have to test for collisions with several couples $M_1^u = m \parallel [0]^{2^{l/2-1}} \parallel [u] \parallel [0]^{2^{l/2}+L}$, $M_2^u = m \parallel [0]^{2^{l/2-1}+L} \parallel [u] \parallel [0]^{2^{l/2}}$, and if none of them collide we can safely deduce that the $\alpha$-node is located in the second $2^{l/2-1}$ zero blocks. Overall, one such step reduces the number of the candidate nodes by a half and we simply continue this binary search in order to eventually obtain the position of the $\alpha$-node with $\log_2(2^{l/2}) = l/2$ iterations.

## 5.2 Detailed attack process

1. (offline) Search for a cycle in the functional graph of $h_{[0]}$ and denote $L$ its length.

2. (online) Find a message block $m$ such that querying the two messages $M_1 = m \parallel [0]^{2^{l/2}} \parallel [1] \parallel [0]^{2^{l/2}+L}$ and $M_2 = m \parallel [0]^{2^{l/2}+L} \parallel [1] \parallel [0]^{2^{l/2}}$ leads to the same HMAC output. Let $X_1$ and $X_2$ be two integer variables, initialized to the values 0 and $2^{l/2}$ respectively.

3. (online) Let $X' = (X_1 + X_2)/2$. Select $\beta \log(l)$ distinct message blocks $[u]$, and for each of them query the HMAC output for messages $M_1^u = m \parallel [0]^{X'} \parallel [u] \parallel [0]^{2^{l/2}+L}$ and $M_2^u = m \parallel [0]^{X'+L} \parallel [u] \parallel [0]^{2^{l/2}}$. If at least one of the ($M_1^u$, $M_2^u$) pairs leads to a colliding HMAC output, then set $X_2 = X'$. Otherwise, set $X_1 = X'$. We use $\beta = 4.5$ as explained later.

4. (online) If $X_1 + 1 = X_2$ holds, output $X_2$ as the block index of the $\alpha$-node. Otherwise, go back to the previous step.
## 5.3 Complexity and success probability analysis

**Complexity.** We would like to evaluate the complexity of the attack. The first step will require about $2^{l/2}$ offline computations to find the cycle. Again, it is important to note that we can run this first step several times in order to ensure that we are using the cycle from the biggest component of the functional graph of $h_{[0]}$. The second step repeats the execution of the distinguishing-H attack from Section 4, which requires $6 \cdot 2^{l/2}$ computations for a success probability of 0.14, until it finds a succeeding message block $m$. Therefore, after trying a few $m$ values, we have probability very close to 1 to find a valid one. The third and fourth steps will be executed about $l/2$ times (for the binary search), and each iteration of the third step performs $2 \cdot \beta \log(l)$ queries of about $2^{l/2} + 2^{l/2} + L \approx 3 \cdot 2^{l/2}$ message blocks each. Therefore, the overall complexity of the attack is about $3\beta \cdot l \cdot \log(l) \cdot 2^{l/2}$ compression function computations.

**Success probability.** Next we evaluate the success probability that the attacker recovers the internal state and this depends on the success probability of the binary search steps. We start with the case where the node after $m \parallel [0]^{X'}$ is inside the first online cycle. The third step will succeed as long as at least one of the ($M_1^u, M_2^u$) pairs collide on the output (we can omit the false positive collisions which happen with negligible probability). One pair ($M_1^u, M_2^u$) will indeed collide if:

* The random block $[u]$ sends both messages to the main component of the functional graph of $h_{[0]}$. Since it has an expected size of $\delta_2 \cdot 2^l$ (see Theorem 3), this is the case with probability $\delta_2^2$.

* The $2^{l/2} [0]$ message blocks concatenated after $[u]$ are enough to reach the cycle, i.e. the tail length when reaching the second cycle is smaller than $2^{l/2}$. Since the average tail length is smaller than $2^{l/2}$ elements, this will happen with probability $1/2$ for each message.

After trying $\beta \log(l)$ pairs, the probability that at least one pair collides is $1 - (1 - \delta_2^2/4)^{\beta \log(l)}$. If we use $\beta = -1/\log(1 - \delta_2^2/4) \approx 4.5$, this gives a probability of $1 - 1/l$. On the other hand, if the node after $m \parallel [0]^{X'}$ is not inside the cycle, the third step will succeed when no random collision occurs among the $\beta \log(l)$ tries, and such collisions happen with negligible probability. Overall, since there are $l/2$ steps in the binary search, the average success probability of the binary search is $(1 - 1/l)^{l/2} \ge e^{-1/2} \approx 0.6$.

Finally, the attack succeeds if the $\alpha$-node is actually the root of the giant tree, as computed in the offline phase. This is the case with probability $\delta_1/\delta_2$, and the success probability of the full state recovery attack is $\delta_1/\delta_2 \cdot e^{-1/2} \approx 0.38$.

## 6 Internal state recovery with shorter messages

In the full version of the paper, we give an alternative internal-state recovery attack using shorter messages, that can also be used as a distinguishing-H attack
with shorter messages. The attacks of Sections 4 and 5 have a complexity of $O(2^{l/2})$ using a small number of messages of length $2^{l/2}$; on the other hand the alternative attack has a complexity $O(2^{3l/4})$ using $2^{l/2}$ messages of length $2^{l/4}$. More generally, if the message size is limited to $2^s$ blocks ($s \le l/4$), then the attack requires $2^{l-2s}$ messages. Due to space constraints, we only give a brief description of this attack here.

## 6.1 Entropy loss in collisions finding

While the previous attacks are based on detecting cycles in the graph of a random function, this alternative attack is based on the fact that finding collisions by iterating a random function does not give a random collision: some particular collisions are much more likely to be found than others. This fact is well known in the context of collision search; for instance van Oorschot and Wiener [23] recommend to randomize the function regularly when looking for a large number of collisions. In this attack, we exploit this property to our advantage: first we use a collision finding algorithm to locate collisions in $h_M$ with a fixed M; then we query the MAC oracle with messages with long repetitions of the block M and we detect collisions in the internal state; since the collisions found in this way are not randomly distributed, there is a good probability that we will reach one the collisions that was previously detected in the offline phase.

Actually, the attacks of Sections 4 and 5 can also be seen as following this stategy: we use a collision finding algorithm based on cycle detection (following Pollard's rho algorithm), and we know that with a good probability, the collision found will be the root of the giant tree. For the alternative attack, we use a collision finding algorithm similar to [23], but using using fixed length chains. In the full version of the paper, we study the entropy of the distribution of collisions found in this way, and we show that when using chains of length $2^s$, we need about $2^{l/2-s}$ collisions in order to have a match between the online and offline steps. This translates to an attack complexity of $2^{l-s}$, with $s \le l/4$.

# 7 Key recovery for HMAC based on a hash function with an internal checksum

In this section we study HMAC used with a hash function with an internal checksum, such as GOST. We first show that the checksum does not prevent the distinguishing-H and state recovery attack, but more surprisingly the checksum actually allows to mount a full key-recovery attack significantly more efficient than exhaustive search.

A hash function with an internal checksum computes the sum of all message blocks, and uses this sum as an extra input to the finalization function. The sum can be computed for any group operation, but it will usually be an XOR sum or a modular addition. We use the XOR sum $\text{Sum}^{\oplus}$ to present our attack, but it is applicable with any group operation.
The checksum technique has been used to enhance the security of a hash function, assuming that controlling the checksum would be an additional challenge for an adversary. While previous work argued its effectiveness [10], our result reveals a surprising fact that incorporating a checksum into a hash function could even weaken its security in some applications such as HMAC.

A notable example of a hash function with a checksum is the GOST hash function, which has been standardized by the Russian Government [6] and by IETF [5]. HMAC-GOST has also been standardized by IETF [15] and is implemented in OpenSSL. GOST uses parameters $n = l = b$, and uses a separate call to process the message length, as follows:

$$ 
\begin{array}{lll}
x_0 = IV & x_{i+1} = h(x_i, m_i) & x_* = h(x_p, |M|) \\
\sigma_0 = 0 & \sigma_{i+1} = \sigma_i \oplus m_i & \text{hash} = g(x_*, \sigma_p)
\end{array}
$$

If this section we describe the attack on GOST-like functions following this structure; Figure 3 shows an HMAC computation with a GOST-like hash function. We give more general attacks when the output is computed as $g(x_p, |M|, \sigma_p)$ in the full version of this paper.

<figure><img src="image_112.png" /><figcaption>Fig. 3. HMAC based on a hash function with a checksum (dashed lines) and a length-padding block. We only detail the first hash function call.</figcaption></figure>

## 7.1 General description

In HMAC, $K \oplus \text{ipad}$ is prepended to a message $M$, and $(K \oplus \text{ipad}) \parallel M$ is hashed by the underlying hash function $H$. Therefore, the final checksum value is $\sigma_p = \text{Sum}^{\oplus}((K \oplus \text{ipad}) \parallel M) = K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M)$. In this attack, we use the state recovery attack to recover the internal state $x_*$ before the checksum is used and we take advantage of the fact that the value $\sigma_p$ actually contains the key, but can still be controlled by changing the message. We use this to inject a known difference in the checksum, and to perform a kind of related key attack on the finalization function $g$, even though we have access to a single HMAC key.

More precisely, we use Joux's multicollision attack [11] to generate a large set of messages with the same value $\bar{x}$ for $x_*$, but with different values of the
checksum. We detect MAC-collisions among those messages, and we assume
that the collisions happens when processing the checksum of the internal hash
function. For each such collision, we have $g(\bar{x}, K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M)) = g(\bar{x}, K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M'))$, and we compute the input difference $\Delta M = \text{Sum}^{\oplus}(M) \oplus \text{Sum}^{\oplus}(M')$.

Finally, we compute $g(\bar{x}, m)$ offline for a large set of random values $m$, and we collect collisions. Again, we compute the input difference $\Delta m = m \oplus m'$ for each collision, and we match $\Delta m$ to the previously stored $\Delta M$. When a match is found between the differences we look for the corresponding values and we have $K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M) = m$ (or $m'$) with high probability. This gives the value of the key $K$.

**State recovery with a checksum.** First, we note that the checksum $\sigma$ does not prevent the state recovery attacks of Section 5; the complexity only depends on the size $l$ of the state $x$. Indeed, the attack of Section 5 is based on detecting collisions between pairs of messages $M_1 = m \parallel [0]^{2^{l/2}} \parallel [k] \parallel [0]^{2^{l/2}+L}$ and $M_2 = m \parallel [0]^{2^{l/2}+L} \parallel [k] \parallel [0]^{2^{l/2}}$. Since the messages have the same checksum, a collision in the state will be preserved. More generally, the attacks can easily be adapted to use only message with a fixed sum. For instance, we can use random messages with two identical blocks in the attack of Section 5, and messages of the form $m \parallel m \parallel [0]^{2^{l/2}} \parallel [k] \parallel [k] \parallel [0]^{2^{l/2}+L}$ have a checksum of zero.

**Recovering the state of a short message.** Unfortunately, the state we recover will correspond to a rather long message (e.g. $2^{l/2}$ blocks), and all the queries based on this message will be expensive. In order to overcome this issue, we use the known state $x_M$ after a long message $M$ to recover the state after a short one. More precisely, we generate a set of $2^{l/4}$ long messages by appending a random message blocks $m$ twice to $M$. Note that $\text{Sum}^{\oplus}(M \parallel m \parallel m) = \text{Sum}^{\oplus}(M)$. Meanwhile, we generate a set of $2^{3l/4}$ two-block messages $m_1 \parallel m_2$, with $m_1 \oplus m_2 = \text{Sum}^{\oplus}(M)$. We query these two sets to the HMAC oracle and collect collisions between a long and a short message. We expect that one collision correspond to a collision in the value $x_*$ before the finalization function $g$. We can compute the value $x_*$ for the long message from the known state $x_M$ after processing $M$. This will correspond to the state after processing the message $m_1 \parallel m_2$ and its padding block, or equivalently, after processing the message $m_1 \parallel m_2 \parallel [2]$ (because the length block is processed with the same compression function). We can verify that the state is correctly recovered by generating a collision $m \parallel m, m' \parallel m'$ offline from the state $x_*$, and comparing $\text{HMAC}(m_1 \parallel m_2 \parallel [2] \parallel m \parallel m)$ and $\text{HMAC}(m_1 \parallel m_2 \parallel [2] \parallel m' \parallel m')$.

## 7.2 Detailed attack process

For simplicity of the description, we omit the padding block in the following description, and we refer to the previous paragraphs for the details of how to deal with the padding.
1. Recover an internal state value $x_r$ after processing a message $M_r$ through HMAC. Refer to Section 5 for the detailed process.

2. (online) Choose $2^{l/4}$ one-block random messages $m$, query $M_r \parallel m \parallel m$ to HMAC and store $m$ and the corresponding tag.

3. (online) Choose $2^{3l/4}$ one-block random messages $m$, query $(\text{Sum}^{\oplus}(M_r) \oplus m) \parallel m$ to HMAC and look for a match between the tag value and one of the stored tag values in Step 2.

For a colliding pair $(\text{Sum}^{\oplus}(M_r) \oplus m) \parallel m$ and $M_r \parallel m' \parallel m'$, denote $\text{Sum}^{\oplus}(M_r) \oplus m \parallel m$ as $M_1$ and $h(h(x_r, m'), m')$ as $x_1$. Generate a collision $h(h(x_1, u), u) = h(h(x_1, u'), u')$. Query $M_1 \parallel u \parallel u$ and $M_1 \parallel u' \parallel u'$ and compare the tags. If they are equal, the internal state after processing $M_1$ (before the checksum block) is $x_1$.

4. (offline) Generate $2^{3l/4}$ messages that all collide on the internal state before the checksum block by Joux's multicollision. More precisely, choose $2^{l/2}$ random message $m$ and compute $h(x_1, m)$ to find a collision $h(x_1, m_1) = h(x_1, m'_1) = x_2$. Then iterate this procedure to find a collision $h(x_i, m_i) = h(x_i, m'_i) = x_{i+1}$ for $i \le 3l/4$. Denote the value of $x_{3l/4+1}$ by $\bar{x}$.

5. (online) Query the set of messages in Step 4 to HMAC in order to collect tag collisions. For each collision $M$ and $M'$, compute the checksum difference $\Delta M = \text{Sum}^{\oplus}(M) \oplus \text{Sum}^{\oplus}(M')$, and store $(\text{Sum}^{\oplus}(M), \Delta M)$.

6. (offline) Choose a set of $2^{3l/4}$ one-block random message $m$, compute $g(\bar{x}, m)$ and collect collisions. For each collision $m$ and $m'$, compute the difference $\Delta m = m \oplus m'$ and match $\Delta m$ to the stored $\Delta M$ at Step 5. If a match is found, mark $\text{Sum}^{\oplus}(M) \oplus \text{ipad} \oplus m$ and $\text{Sum}^{\oplus}(M) \oplus \text{ipad} \oplus m \oplus \Delta m$ as potential key candidates.

7. (offline) filter the correct key from the potential candidates by verifying a valid message/tag pair.

## 7.3 Complexity and success probability analysis

We need to evaluate the complexity of our key recovery attack.

Step 1: $O(l \cdot \log(l) \cdot 2^{l/2})$

Step 2: $2^{3l/4}$

Step 3: $2 \cdot 2^{3l/4}$

Step 4: $3l/4 \cdot 2^{l/2}$

Step 5: $3l/4 \cdot 2^{3l/4}$

Step 6: $2^{3l/4}$

Step 7: $O(1)$

Overall, the fifth step dominates the complexity, and the total complexity is about $3l/4 \cdot 2^{3l/4}$ compression function computations.

Next we evaluate the success probability of our method. The first step succeeds with a probability almost 1 after several trials. Steps 2 and 3 need to guarantee a collision between a long and a short message. Since there are $2^l$ pairs, one such collision occurs with a probability of $1 - (1 - 2^{-l})^{2^l} \approx 1 - 1/e \approx 0.63$. The success probability of producing no less than $2^{l/2}$ collisions at each of steps 5 and 6 is 0.5 since the expected number of collisions is $2^{l/2}$. Thus the overall success probability is no less than 0.16.
## Conclusion

Our results show that the security of **HMAC** and hash-based MAC above the birthday bound is significantly weaker than previously expected. First, we show that distinguishing-H and state-recovery attacks are not much harder than a distinguishing-R attack, contrary to previous beliefs. Second, we show that the use of a checksum can allow a key-recovery attack against **HMAC** with complexity only $\tilde{O}(2^{3l/4})$. In particular, this attack is applicable to **HMAC-GOST**, a standardized construction.

We give a comparison of our attacks and previous attack against concrete instances of **HMAC** in Table 1, showing that some attacks against concrete instances are in fact less efficient than our generic attacks.

As future works, it would be interesting to find other applications of the internal state recovery for **HMAC**. Moreover, we expect further applications of the analysis of the functional graph, as it might be possible to use other distinguishing properties, such as the tail length, the distance of a node from the cycle, etc.

## Acknowledgments

The authors would like to thank the anonymous referees for their helpful comments. Gaëtan Leurent is supported by the ERC project CRASH. Thomas Peyrin and Lei Wang are supported by the Singapore National Research Foundation Fellowship 2012 (NRF-NRFF2012-06).

## References

1. Bellare, M.: New Proofs for NMAC and HMAC: Security without Collision-Resistance. In Dwork, C., ed.: CRYPTO. Volume 4117 of Lecture Notes in Computer Science., Springer (2006) 602–619

2. Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In Koblitz, N., ed.: CRYPTO. Volume 1109 of Lecture Notes in Computer Science., Springer (1996) 1–15

3. Brassard, G., ed.: Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. In Brassard, G., ed.: CRYPTO. Volume 435 of Lecture Notes in Computer Science., Springer (1990)

4. Damgård, I.: A Design Principle for Hash Functions. [3] 416–427

5. Dolmatov, V.: GOST R 34.11-94: Hash Function Algorithm. RFC 5831 (Informational) (March 2010)

6. FAPSI, VNIIstandart: GOST 34.11-94, Information Technology Cryptographic Data Security Hashing Function (in Russian) (1994)

7. Flajolet, P., Odlyzko, A.M.: Random Mapping Statistics. In Quisquater, J.J., Vandewalle, J., eds.: EUROCRYPT. Volume 434 of Lecture Notes in Computer Science., Springer (1989) 329–354

8. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)
9. Fouque, P.A., Leurent, G., Nguyen, P.Q.: Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. In Menezes, A., ed.: CRYPTO. Volume 4622 of Lecture Notes in Computer Science., Springer (2007) 13–30

10. Gauravaram, P., Kelsey, J.: Linear-XOR and Additive Checksums Don't Protect Damgård-Merkle Hashes from Generic Attacks. In Malkin, T., ed.: CT-RSA. Volume 4964 of Lecture Notes in Computer Science., Springer (2008) 36–51

11. Joux, A.: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In Franklin, M.K., ed.: CRYPTO. Volume 3152 of Lecture Notes in Computer Science., Springer (2004) 306–316

12. Kim, J., Biryukov, A., Preneel, B., Hong, S.: On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1 (Extended Abstract). In Prisco, R.D., Yung, M., eds.: SCN. Volume 4116 of Lecture Notes in Computer Science., Springer (2006) 242–256

13. Merkle, R.C.: One Way Hash Functions and DES. [3] 428–446

14. Peyrin, T., Sasaki, Y., Wang, L.: Generic Related-Key Attacks for HMAC. In Wang, X., Sako, K., eds.: ASIACRYPT. Volume 7658 of Lecture Notes in Computer Science., Springer (2012) 580–597

15. Popov, V., Kurepkin, I., Leontiev, S.: Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms. RFC 4357 (Informational) (January 2006)

16. Preneel, B.: HMAC. In van Tilborg, H.C.A., Jajodia, S., eds.: Encyclopedia of Cryptography and Security (2nd Ed.). Springer (2011) 559–560

17. Preneel, B., van Oorschot, P.C.: MDx-MAC and Building Fast MACs from Hash Functions. In Coppersmith, D., ed.: CRYPTO. Volume 963 of Lecture Notes in Computer Science., Springer (1995) 1–14

18. Rechberger, C., Rijmen, V.: New Results on NMAC/HMAC when Instantiated with Popular Hash Functions. J. UCS 14(3) (2008) 347–376

19. Rivest, R.L.: The MD4 Message Digest Algorithm. In Menezes, A., Vanstone, S.A., eds.: CRYPTO. Volume 537 of Lecture Notes in Computer Science., Springer (1990) 303–311

20. Rivest, R.L.: The MD5 message-digest algorithm. Request for Comments (RFC) 1320, Internet Activities Board, Internet Privacy Task Force (April 1992)

21. Tsudik, G.: Message Authentication with One-Way Hash Functions. In: INFO-COM. (1992) 2055–2059

22. U.S. Department of Commerce, National Institute of Standards and Technology: Secure Hash Standard (SHS) (Federal Information Processing Standards Publication 180-3). (2008) http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf.

23. van Oorschot, P.C., Wiener, M.J.: Parallel Collision Search with Cryptanalytic Applications. J. Cryptology 12(1) (1999) 1–28

24. Wang, L., Ohta, K., Kunihiro, N.: New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. In Smart, N.P., ed.: EUROCRYPT. Volume 4965 of Lecture Notes in Computer Science., Springer (2008) 237–253

25. Wang, X., Yu, H., Wang, W., Zhang, H., Zhan, T.: Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. In Joux, A., ed.: EUROCRYPT. Volume 5479 of Lecture Notes in Computer Science., Springer (2009) 121–133

26. Yasuda, K.: "Sandwich" Is Indeed Secure: How to Authenticate a Message with Just One Hashing. In Pieprzyk, J., Ghodosi, H., Dawson, E., eds.: ACISP. Volume 4586 of Lecture Notes in Computer Science., Springer (2007) 355–369
27. Yu, H., Wang, X.: Full Key-Recovery Attack on the HMAC/NMAC Based on 3 and 4-Pass HAVAL. In Bao, F., Li, H., Wang, G., eds.: ISPEC. Volume 5451 of Lecture Notes in Computer Science., Springer (2009) 285–297

A Additional Figures

<figure><img src="image_113.png" /><figcaption>Fig. 4. Functional graph of Keccak (SHA-3) with 8-bit input and 8-bit output.</figcaption></figure>
# Improved Generic Attacks Against Hash-based MACs and HAIFA

Itai Dinur · Gaëtan Leurent

Received: 1 July 2015 / Accepted: 21 October 2016

This is the author version submitted by the authors.

The published version is available at DOI 10.1007/s00453-016-0236-6.

**Abstract** The security of **HMAC** (and more general hash-based MACs) against state-recovery and universal forgery attacks was shown to be suboptimal, following a series of results by Leurent *et al*. and Peyrin *et al*. These results have shown that such powerful attacks require significantly less than $2^\ell$ computations, contradicting the common belief (where $\ell$ denotes the internal state size). In this work, we revisit and extend these results, with a focus on concrete hash functions that limit the message length, and apply special iteration modes.

We begin by devising the first state-recovery attack on **HMAC** with a HAIFA hash function (using a block counter in every compression function call), with complexity $2^{4\ell/5}$. Then, we describe improved tradeoffs between the message length and the complexity of a state-recovery attack on **HMAC** with a Merkle-Damgård hash function. Consequently, we obtain improved attacks on several **HMAC** constructions used in practice, in which the hash functions limits the maximal message length (e.g., **SHA-1** and **SHA-2**). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to **SHA-1** and **SHA-2**.

Despite their theoretical interest, our attacks do not seem to threaten the practical security of the analyzed concrete **HMAC** constructions.

**Keywords** Hash functions · MAC · **HMAC** · Merkle-Damgård · HAIFA · state-recovery attack · universal forgery attack · GOST · Streebog · **SHA** family

This paper in an extended version of [6], presented at CRYPTO 2014.

Itai Dinur

Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel

E-mail: dinuri@cs.bgu.ac.il

Gaëtan Leurent

Inria, EPI SECRET, France

E-mail: Gaetan.Leurent@inria.fr
# 1 Introduction

MAC algorithms are an important symmetric cryptography primitive, used to verify the integrity and authenticity of messages. The sender of a message uses a MAC function to compute a tag from the message and a shared secret key. The tag is appended to the message and the receiver can recompute the tag using the key, and reject the message when it does not match the received one. The main security requirement of a MAC is the resistance to existential forgery. Namely, after querying the MAC oracle to obtain the tags of some carefully chosen messages, it should be hard for an adversary to forge a valid tag for a different message.

One of the most widely used MAC algorithms in practice is **HMAC**, a MAC construction using a hash function designed by Bellare, Canetti and Krawczyk in 1996 [4]. The algorithm has been standardized by ANSI, IETF, ISO and NIST, and is widely deployed to secure internet communications (e.g. SSL/TLS, SSH, IPSec). As these protocols are widely used, the security of **HMAC** has been extensively studied, and several security proofs [3,4] show that it gives a secure MAC and a secure PRF up to the birthday bound (assuming good properties of the underlying compression function). At the same time, there is a simple existential forgery attack on any iterative MAC with an $\ell$-bit state, with complexity $2^{\ell/2}$, matching the security proof. Nevertheless, security beyond the birthday bound for stronger attacks (such as state-recovery and universal forgery) is still an important topic.

Surprisingly, the security of **HMAC** beyond the birthday bound has not been thoroughly studied until 2012, when Peyrin and Sasaki described an attack on **HMAC** in the related-key setting [23]. Later work focused on single-key security, and included a paper by Naito, Sasaki, Wang and Yasuda [21], which described state-recovery attacks with complexity $2^{\ell/\ell}$. At Asiacrypt 2013, Leurent, Peyrin and Wang [19] gave state-recovery attacks with complexity $2^{\ell/2}$, closing the gap with the security proof. Later, at Eurocrypt 2014, Peyrin and Wang [24] described a universal forgery attack with complexity as low as $2^{5\ell/6}$, a result that was further improved to $2^{3\ell/4}$ at CRYPTO 2014 [11], showing that even this very strong attack is possible with significantly less than $2^\ell$ work.

Some of the generic attacks have also been used as a first step to build specific attacks against **HMAC** with the concrete hash function Whirlpool [12, 13].

These results show that more work is needed to better understand the exact security provided by **HMAC** and hash-based MACs in general.

## 1.1 Our results

In this paper, we provide several important contributions to the security analysis of **HMAC** and similar hash-based MAC constructions. In particular, we devise improved attacks when **HMAC** is used with many popular concrete hash functions, and in several cases our attacks are the first to be applicable to **HMAC**
<figure><img src="image_114.png" /><figcaption>Fig. 1 Tradeoffs between the message length and the complexity for state-recovery attacks</figcaption></figure>

with the given hash function. Some results with concrete instantiations are summarized in Table 1.<fnref n="1" />

As a first contribution, we focus on the HAIFA [5] mode of operation, used in many hash function designs such as BLAKE [1,2], Skein [8], or Streebog [7]. The HAIFA construction uses a block counter to tweak the compression functions, such that they resemble independent random functions, in order to thwart some narrow-pipe attacks (e.g. the second-preimage attack of Kelsey and Schneier [16]). Indeed, the previous attacks against HMAC [19,24] use in a very strong way the assumption that the same compression function is applied to all the message blocks, and thus they cannot be applied to HAIFA. In this work, we present the first state-recovery attack on HMAC using these hash functions, whose optimal complexity is $2^{4\ell/5}$.

In an interesting application of our state-recovery attack on HAIFA (given in Section 8), we show how to extend it into a key-recovery attack on the new Russian standard Streebog, recovering the 512-bit key of HMAC-Streebog with a complexity of $2^{417}$. This key-recovery attack is similar to the one of [19] for Merkle-Damgård, and confirms its surprising observation: adding internal checksums in a hash function (such as Streebog) weakens the design when used in HMAC, even for hash functions based on the HAIFA mode.

As a second contribution of this paper, we revisit the results of the full version of [19] for Merkle-Damgård hash functions (given in [18]), and we prove the conjectures used in its short message attacks. Some of our proofs are of independent interest, as they give insight into the behavior of classical collision search algorithms for random functions. These proofs explain for the first time an interesting phenomenon experimentally observed in several previous works

<footnote n="1">¹ We elaborate on our complexity evaluation in the next Subsection.</footnote>
<table><caption>**Table 1** Complexity of attacks on HMAC instantiated with some concrete hash functions. The state size is denoted as $\ell$, and the maximum message length as $2^s$. For the new results, we give a reference to the Attack number. The figures omit small constants (following the analysis in this paper and previous works), but take into account polynomial factors in $\ell$.</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">Mode</th><th rowspan="2">ℓ</th><th rowspan="2">s</th><th colspan="2">State-recovery</th><th colspan="2">Universal forgery</th></tr><tr><th>[19]</th><th>New</th><th>[24]</th><th>New</th></tr></thead><tbody><tr><td>SHA-1</td><td>MD</td><td>160</td><td>2<sup>55</sup></td><td>2<sup>120</sup></td><td>2<sup>107</sup> (2)</td><td>N/A</td><td>2<sup>132</sup> (8)</td></tr><tr><td>SHA-224</td><td>MD</td><td>256</td><td>2<sup>55</sup></td><td>2<sup>201</sup></td><td>2<sup>192</sup> (4)</td><td>N/A</td><td>N/A</td></tr><tr><td>SHA-256</td><td>MD</td><td>256</td><td>2<sup>55</sup></td><td>2<sup>201</sup></td><td>2<sup>192</sup> (4)</td><td>N/A</td><td>2<sup>228</sup> (7,8)</td></tr><tr><td>SHA-512</td><td>MD</td><td>512</td><td>2<sup>118</sup></td><td>2<sup>394</sup></td><td>2<sup>384</sup> (4)</td><td>N/A</td><td>2<sup>453</sup> (7,8)</td></tr><tr><td>HAVAL</td><td>MD</td><td>256</td><td>2<sup>54</sup></td><td>2<sup>202</sup></td><td>2<sup>192</sup> (4)</td><td>N/A</td><td>2<sup>229</sup> (7,8)</td></tr><tr><td>WHIRLPOOL</td><td>MD</td><td>512</td><td>2<sup>247</sup></td><td>2<sup>384</sup></td><td>2<sup>283</sup> (3)</td><td>N/A</td><td>2<sup>419</sup> (8)</td></tr><tr><td>BLAKE-256</td><td>HAIFA</td><td>256</td><td>2<sup>55</sup></td><td>N/A</td><td>2<sup>213</sup> (5)</td><td>N/A</td><td>N/A</td></tr><tr><td>BLAKE-512</td><td>HAIFA</td><td>512</td><td>2<sup>118</sup></td><td>N/A</td><td>2<sup>419</sup> (5)</td><td>N/A</td><td>N/A</td></tr><tr><td>Skein-512</td><td>HAIFA</td><td>512</td><td>2<sup>90</sup></td><td>N/A</td><td>2<sup>419</sup> (5)</td><td>N/A</td><td>N/A</td></tr></tbody></table><table><thead><tr><th rowspan="2">Streebog</th><th rowspan="2">HAIFA+σ</th><th rowspan="2">512</th><th rowspan="2">∞</th><th colspan="2">Key-recovery</th></tr><tr><th>[19]</th><th>New</th></tr></thead><tbody><tr><td></td><td></td><td></td><td></td><td>N/A</td><td>2<sup>417</sup> (5,B)</td><td>N/A</td><td>2<sup>417</sup> (6,B)</td></tr></tbody></table>

(such as [22]), namely, that the collisions found by such algorithms are likely to belong to a restricted set of a surprisingly small size.

Then, based on our proofs, we describe several new algorithms with various improved tradeoffs between the message length and the complexity as shown in Figure 1. As many concrete hash functions restrict the message size, we obtain improved attacks in many cases: for instance, we reduce the complexity of a state-recovery attack against HMAC-SHA-1 from $2^{120}$ to $2^{107}$ and HMAC-WHIRLPOOL from $2^{384}$ to $2^{283}$ (see Table 1).

Finally, we focus on universal forgery attacks, where the previous attacks of [11,24] are much more efficient than exhaustive search, but require in an inherent way to query the MAC oracle with very long messages of about $2^{\ell/2}$ blocks. Thus, these attacks cannot be applied to many concrete hash functions that limit the message size. On the other hand, our techniques give rise to attacks that can be efficiently applied with much shorter queries to the MAC oracle, and therefore are more widely applicable to concrete hash functions. In particular, we devise the first universal forgery attack applicable to HMAC with SHA-1 and SHA-2 (see Table 1).

## 1.2 Framework of the attacks

In order to recover an internal state computed by the MAC oracle during the processing of some message (namely, mount a state-recovery attack), we use a framework which is similar to the one of [19]. Namely, we match states that are computed offline with (unknown) states that are computed online (during the processing of messages by the MAC oracle). However, as arbitrary states
match with low probability (which does not lead to efficient attacks), we only match *special states*, which have a higher probability to be equal. These special states are the result of iterating random functions using chains, computed by applying the compression function on a fixed message from arbitrary initial states. In this paper, we exploit two types of special states which were also exploited in [19]: states on which two evaluated chains collide, and states on which a single chain collides with itself to form a cycle. We also introduce a third type of special states, which result from the reduction of the image space that occurs when applying a fixed sequence of random functions. This is used in some of our new attacks, and in particular against HAIFA.

As described above, after we compute special states both online and offline, we need to match them in order to recover an online state. However, since the online states are unknown, the matching cannot be performed directly, and we are forced to match the nodes indirectly using *filters*. A filter for a node (state) is a property that identifies it with high probability, i.e., once the filters of two nodes match, then the nodes themselves match with high probability. Since the complexity of the matching steps in a state-recovery attack depends on the complexity of building a filter for a node and testing a filter on a node, we are interested in building filters efficiently. In this paper, we use two types of filters: collision filters (which were also used in [19]) and diamond filters, which exploit the diamond structure (introduced in [15]) in order to build filters for a large set of nodes with reduced average complexity. In fact, we use a novel online construction of the diamond structure via the MAC oracle, whereas such a structure is typically computed offline. In particular, we show that despite the fact that the online diamond filter increases the complexity of building the filter, the complexity of the actual matching phase is significantly reduced, and gives improved attacks in many cases.

### 1.2.1 Complexity evaluation

The complexity of our attacks is calculated in terms of the number of compression function evaluations of the underlying hash functions. Similarly to related papers in the field, we assume that sorting a table can be performed in linear time, while searching a sorted table takes constant time. As the complexities of all our attacks are exponential in the state size $ℓ$, we mostly use the big-O and soft-O ($\tilde{O}$) notation to estimate them (which is common practice in analysis of exponential-time algorithms). These estimations ignore small constants and polynomial factors in $ℓ$ (which are generally linear in our attacks). An exception to this is the more precise complexity evaluation for the attack on **HMAC-Streebog**, given in Appendix B.

### 1.2.2 Outline

The paper is organized as follows. We begin with a description of **HMAC** in Section 2. We then describe and analyze the algorithms used to compute special states in Section 3, and the filters we use in our attacks in Section 4.
Next, we present a simple attack against HMAC with a HAIFA hash function in Section 5, and revisit the results of [19] in Section 6, presenting new tradeoffs for attacks on Merkle-Damgård hash functions. In Section 7, we give more complex attacks for shorter messages. Our key-recovery attack on HMAC with GOST R 34.11-2012 (Streebog) is described in Section 8. Finally, in Section 9, we present our universal forgery attacks with short queries, and conclude in Section 10.

## 2 HMAC and Hash-based MACs

In this paper we study MAC algorithms based on a hash function, such as HMAC. Using a hash function $H$, HMAC is defined as $HMAC(K, M) = H(K \oplus opad \parallel H(K \oplus ipad \parallel M))$, as shown in Figure 2. More generally, we consider a class of iterative designs based on a family of compression functions $h_i$ and a finalization function $g$, represented by Figure 3. We denote the $\ell$-bit internal state as $x_i$ and the $n$-bit output tag as $t$. The message $M$ is divided into $p$ blocks $m_i$, and the MAC is computed as:

$$x_0 = I_K \qquad x_{i+1} = h_i(x_i, m_i) \qquad t = g(K, x_p, |M|).$$

The message processing updates the internal state starting from a key-dependant value $I_K$, and the output is produced with a key-dependant finalization function $g$. In particular, we note that the state update does not depend on the key. Our description covers HMAC [4], Sandwich-MAC [27] and envelope-MAC [26] with any common hash function. The hash function can use the message length in the finalization process, which is a common practice, and the round function can depend on a block counter, as in the HAIFA mode. If the hash function uses the plain Merkle-Damgård mode, the round functions $h_i$ are all identical (this is the model analyzed in previous attacks [19,24]).

In this work, we assume that with very high probability, an arbitrary collision on the tag of two messages of the same length is a result of a collision on the final internal states $x_p$. This greatly simplifies the description of the attacks, and does not restrict the scope of our results. This assumption can be realized by altering the original scheme such that the new tag length is made larger than $\ell$. Indeed, from a function $MAC_1(K, M)$ with an output of $n$ bits, we can build a function $MAC_2(K, M)$ with a $2n$-bit output by appending message blocks $[0]$ and $[1]$ to $M$, as $MAC_2(K, M) = MAC_1(K, M \parallel [0]) \parallel MAC_1(K, M \parallel [1])$. Our attacks applied to $MAC_2$ can immediately be turned to attacks on $MAC_1$ with a multiplicative penalty of 2.

In our attacks, we evaluate chains of the compression function $h$ (or $h_i$ for HAIFA) with a fixed message input block $[b]$ (usually $[b] = [0]$), and typically simplify our notation and define $f(x) = h(x, [b])$ (or $f_i(x) = h_i(x, [b])$ for HAIFA). We assume that the function $f$ (or each $f_i$) is chosen from all $\ell$-bit mappings uniformly at random. This implies that our analysis captures most (but not all) choices of underlying hash functions.
<figure><img src="image_115.png" /><figcaption>**Fig. 2** HMAC with a HAIFA hash function. There are two hash function calls, each of them using the key at the beginning.</figcaption></figure>

<figure><img src="image_116.png" /><figcaption>**Fig. 3** Hash-based MAC with HAIFA. Only the initial value and the final transformation are keyed.</figcaption></figure>

# 3 Description and Analysis of Collision Search Algorithms

In this section, we describe the collision search algorithms which are used in our state-recovery attacks in order to compute special states. We then analyze these algorithms (assuming they are applied to random functions) and prove the two conjectures of [19]. Lemma 1 proves the first conjecture, while Lemma 3 proves the second conjecture.

## 3.1 Collision search algorithms

We use standard collision search algorithms which evaluate chains starting from arbitrary points. Namely, a chain $\vec{x}$ starts from $x_0$, and is constructed iteratively by the equation $x_i = f_i(x_{i-1})$ up to $i = 2^s$ for a fixed value of $s$. We consider two different types of collisions between two chains $\vec{x}$ and $\vec{y}$: free-offset collisions ($x_i = y_j$ for any $i, j$, with all the $f_i$'s being equal), and same-offset collisions ($x_i = y_i$).
### 3.1.1 Free-offset collision search

When searching offline for collisions in iterations of a single random function $f$, we evaluate $2^t$ chains starting from arbitrary points, and extended to length $2^s$.

Assuming that $2^s \cdot 2^{t+s} \le 2^\ell$ (i.e., $2s+t \le \ell$), then we are at (or below) the birthday paradox threshold and therefore each of the chains is not expected to collide with more than one other chain in the structure. This implies that the structure contains a total of about $2^{t+s}$ distinct points, and (according to the birthday paradox) we expect it to contain a total of $2^c = \Theta(2^{2(t+s)-\ell})$ collisions. We can easily recover all of these collisions in $O(2^{t+s}) = O(2^{(c+\ell)/2})$ time by storing all the evaluated points and checking for collisions in memory.

We note that we can reduce the memory requirements of the algorithm by using the parallel collision search algorithm of van Oorschot and Wiener [22]. However, in this paper, we generally focus on time complexity and do not try to optimize the memory complexity of our attacks.

### 3.1.2 Cycle search

Cycles are created when a chain collides with itself while iterating a single random function $f$. In order to search offline for a cycle of length $O(2^s)$ (for $s \le \ell/2$), we evaluate $2^{\ell-2s}$ chains starting from arbitrary points, and extended to length $2^s$. The probability that a chain collides with itself to form a cycle is equal (up to a constant factor) to the probability that its first half (of length $2^{s-1}$) collides with its second half, which occurs with probability $\Theta(2^{2s-\ell})$. Thus, we expect to find a cycle within the evaluated $2^{\ell-2s}$ chains.

### 3.1.3 Same-offset collision search

While free-offset collisions are the most general form of collisions, they cannot always be efficiently detected and exploited by our attacks. In particular, they cannot be efficiently detected in queries to the online oracle (as a collision between messages of different lengths would lead to different values after the finalization function). Furthermore, if the hash function uses the HAIFA iteration mode, it is also not clear how to exploit free-offset collisions offline, as the colliding chains do not merge after the collision (and thus we do not have any easily detectable non-random property).

In the cases above, we are forced to only use collisions that occur at the same offset. When computing $2^t$ chains of length $2^s$, a pair of chains collides at the same offset with probability of roughly $2^{s-\ell}$. As we have $2^{2t}$ pairs$^2$ of chains, we expect to find about $2^{2t+s-\ell}$ same-offset collisions.

We note that the computation above assumes that pairs of chains behave (almost) independently, which is the case when the total number of collisions

<footnote>$^2$ More precisely, there are $2^{2t-1}$ unordered pairs of chains. However, our analysis is correct up to small constants.</footnote>
in the structure of chains is relatively small. More precisely, the computation assumes that a constant fraction of the chains do not collide with any other chain, so that the chain structure contains $\Theta(2^{s+t})$ distinct points. When the iteration functions $f_i$ are all equal, the condition reduces to $2s + t \le l$ (as calculated for free-offset collision search). However, when the iteration functions $f_i$ are distinct, we only have to consider collisions at the same offset. In order to collect the $2^{2t+s-l}$ same-offset collisions, we require that a constant fraction of the chains do not collide with any other chains, implying that $2t + s - l < t$, or $s + t \le l$.

*Locating collisions online.* Online collisions are detected by sorting and comparing the tags obtained by querying the MAC oracle with chains of a fixed length $2^s$. If we find two messages such that $\text{MAC}(M) = \text{MAC}(M')$, we can easily compute the message prefix that gives the (unknown) collision state, as described in [19]. Namely, if we denote by $M|_i$ the $i$-block prefix of $M$, then we find the smallest $i$ such that $\text{MAC}(M|_i) = \text{MAC}(M'_i)$ using binary search. This algorithm queries the MAC oracle with $O(s)$ messages of length $O(2^s)$, and thus the time complexity of locating a collision online is $s \cdot 2^s = \tilde{O}(2^s)$.

## 3.2 Analysis of the collision search algorithms

In this section, we provide useful lemmas regarding the collision search algorithms described above. These lemmas are used in order to estimate the collision probability of special states that are calculated by our attacks and thus to bound their complexity. Lemmas 1, 2 and 5 can generally be considered as common knowledge in the field. Perhaps, the most interesting results in this section are lemmas 3 and 4. These lemmas show that the probability of our collision search algorithms to reach the same collision twice from different arbitrary starting points, is perhaps higher than one would expect. This phenomenon was already observed in previous works such as [22], but to the best of our knowledge, this is the first time that this phenomenon is formally proved.

**Lemma 1** Let $s \le l/2$ be a non-negative integer. Let $f_1, f_2, \dots, f_{2^s}$ be a sequence of random functions over the set of $2^l$ elements, and $g_i \triangleq f_i \circ \dots \circ f_{2^l} f_1$ (with the $f_i$ being either all identical, or completely independent). Then, the images of two arbitrary inputs to $g_{2^s}$ collide with probability of about $2^{s-l}$, i.e. $\text{Pr}_{x,y}[g_{2^s}(x) = g_{2^s}(y)] = \Theta(2^{s-l})$.

*Proof* Let $x$ and $y$ be two arbitrary points, $x_i = g_i(x)$ and $y_i = g_i(y)$ (or equivalently $x_0 = x$, $x_i = f_i(x_{i-1})$ and $y_0 = y$, $y_i = f_i(y_{i-1})$). We first deal with the case of independent functions $f_i$. As all $f_i$ are random functions, we have a pair of random points $(x_i, y_i)$ for each offset. The probability that none of the pairs collide is $(1 - 2^{-l})^{2^s}$. The event $g_{2^s}(x) = g_{2^s}(y)$ is equivalent to having (at least) one collision between the pairs, which occurs with probability $1 - (1 - 2^{-l})^{2^s} = \Theta(2^{s-l})$ (given $s \le l$).
When the functions $f_i$ are identical, the analysis is similar, but one also needs to consider dependencies between the sequences of points which are caused by collisions $x_i = y_j$ for $i \neq j$ (and also cycles of the form $x_i = x_j$). However, since $s \le l/2$, we are below (or at) the birthday bound and therefore such collisions occur with at most a (small) constant probability, and their asymptotic contribution to the value of $\text{Pr}_{x,y}[g_{2^s}(x) = g_{2^s}(y)]$ can be neglected. $\square$

**Lemma 2** Let $s \le l/2$ be a non-negative integer. Let $f$ be a random function, then with high probability the image size of the function $f^i$ is $O(2^l/i)$.

*Proof* We will show that the expected image size of $f^i$ is upper bounded by $2 \cdot 2^l/i$. Since the image size is positive, this upper bound proves the lemma, as for some $\alpha > 1$ the probability that the image size is more than $2\alpha \cdot 2^l/i$ is at most $1/\alpha$.

We calculate this expectation based on Theorem 2 of [9], which asserts that the expected image size of $f^i$ is $(1 - \tau_i) 2^l$, where $\tau_0 = 0$ and $\tau_{i+1} = e^{-1+\tau_i}$. We show by induction on $i \ge 1$ that $\tau_i > 1 - (2/i)$, which implies that the expected image size of $f^i$ is less than $2 \cdot 2^l/i$, as required. The base is $i=1$, for which indeed $\tau_1 = e^{-1} > -1$. Next, we need to prove that $\tau_{i+1} > 1 - (2/(i+1))$, or $e^{-1+\tau_i} > 1 - (2/(i+1))$. According to the assumption, it is sufficient to show that $e^{-2/i} > 1 - (2/(i+1))$, or equivalently $-2/i > \ln(1 - (2/(i+1)))$. This inequality can be deduced from the inequality $\ln(1+x) < x/(x/2+1)$ for $-1 < x < 0$ (see inequality (2) in [20]), by plugging in $x = -2/(i+1)$. $\square$

**Lemma 3** Let $\hat{x}$ and $\hat{y}$ be two random collisions (same-offset or free-offset) found by a collision search algorithm using $2^t$ chains of length $2^s$, with a fixed $\ell$-bit random function $f$ such that $2s + t \le \ell$. Then $\text{Pr}[\hat{x} = \hat{y}] = \Theta(2^{2s-\ell})$.

*Proof* First, we note that we generally have 4 cases to analyze, according to whether $\hat{x}$ and $\hat{y}$ were found using a free-offset, or a same-offset collision search algorithm. However, the number of cases can be reduced to 3, as we have 2 symmetric cases, where one collision is free-offset, and the other is same-offset. In this proof, we assume that $\hat{x}$ is a same-offset collision and $\hat{y}$ is a free-offset collision (this is the configuration used in our attacks). However, the proof can easily be adapted to the 2 other settings.

As previously noted, when $2s + t \le \ell$ each evaluated chain is not expected to collide with more than one different chain, and the pairs of chains can essentially be analyzed independently. Given a collision $\hat{x}$, We denote by $A$ the event that 2 new chains of length $2^s$, starting from arbitrary points $(y_0, y'_0)$, also collide on $\hat{x}$. Below, we show that $\text{Pr}[A] = \Theta(2^{2(2s-\ell)})$. Denote by $B$ the event that the chains starting from $(y_0, y'_0)$ collide (on $\hat{x}$ or any other point), then $\text{Pr}[B] = \Theta(2^{2s-\ell})$. We are interested in calculating the conditional probability $\text{Pr}[A|B] = \text{Pr}[\hat{x} = \hat{y}]$, and we have $\text{Pr}[A|B] = \text{Pr}[A \cap B]/\text{Pr}[B] = \text{Pr}[A]/\text{Pr}[B] = \Theta(2^{2(2s-\ell)-(2s-\ell)}) = \Theta(2^{2s-\ell})$, as required.

We are left to show that $\text{Pr}[A] = \Theta(2^{2(2s-\ell)})$. Denote the starting points of the chains which collide on $\hat{x}$ by $(x_0, x'_0)$, and the actual corresponding
colliding points of the chains by $(x_i, x'_i)$, so that $f(x_i) = f(x'_i) = \hat{x}$, with $x_i \neq x'_i$. Fixing $(x_0, x'_0)$, we now calculate $\Pr[A]$, namely the probability that 2 new chains of length $2^s$, starting from arbitrary points $(y_0, y'_0)$, also collide on $\hat{x}$. This occurs if $y_0, y_1, \dots, y_{2^s-i}$ collides with $x_0, x_1, \dots, x_i$, and $y'_0, y'_1, \dots, y'_{2^s-i}$ collides with $x'_0, x'_1, \dots, x'_i$ (or vise-versa). Clearly, $\Pr[A] = O(2^{2(2^s-\ell)})$, as all 4 chains are of length $O(2^s)$. Hence, to conclude the proof, we need to show that $\Pr[A] = \Omega(2^{2(2^s-\ell)})$.

In order to simplify the proof, we assume in the following that $0.25 \cdot 2^s \le i \le 0.75 \cdot 2^s$ and denote this event by $I$. We have $\Pr[I] \approx 1/2$ since the offset of the collision $\hat{x}$ is roughly uniformly distributed in the interval $[0, 2^s]$. This can be shown using Lemma 1, as increasing the length of the chains increases the collision probability (at a common offset) by the same multiplicative factor.

We have $\Pr[A|I] = \Theta(2^{2(2^s-\ell)})$, since when $0.25 \cdot 2^s \le i \le 0.75 \cdot 2^s$, all 4 chains $(y_0, y_1, \dots, y_{2^s-i}, x_0, x_1, \dots, x_i, y'_0, y'_1, \dots, y'_{2^s-i}, x'_0, x'_1, \dots, x'_i)$ are of length $\Theta(2^s)$. Therefore, $\Pr[A] = \Pr[A|I] \cdot \Pr[I] + \Pr[A \neg I] \cdot \Pr[\neg I] \ge \Pr[A|I] \cdot \Pr[I] = \Omega(2^{2(2^s-\ell)})$ as required. $\square$

**Lemma 4** Let $\hat{x}$ and $\hat{y}$ be two arbitrary same-offset collisions found, respectively, at offsets $i$ and $j$ by a collision search algorithm using $2^t$ chains of fixed length $2^s$, with independent $\ell$-bit random functions $f_i$, such that $s+t < \ell$. Then $\Pr[(\hat{x}, i) = (\hat{y}, j)] = \Theta(2^{s-\ell})$. Furthermore, when $i = j$, we have $\Pr[\hat{x} = \hat{y}] = \Theta(2^{2s-\ell})$.

*Proof* The proof follows essentially the same line of arguments as the proof of Lemma 3. We fix the collision $\hat{x}$ and denote by $A$ the event that chains starting from arbitrary points $(y_0, y'_0)$ collide on $\hat{x}$ at offset $i$, and by $B$ the event that the chains starting from $(y_0, y'_0)$ collide at an arbitrary offset $j$. We have $\Pr[B] = \Theta(2^{s-\ell})$ (see Lemma 1) and $\Pr[A] = \Theta(2^{2(s-\ell)})$.<fnref n="3" /> Thus, $\Pr[A|B] = \Pr[A \cap B]/\Pr[B] = \Pr[A]/\Pr[B] = \Theta(2^{s-\ell})$ as claimed.

When assuming that $i = j$, we need to change the definition of event $B$ such that the chains starting from $(y_0, y'_0)$ collide at the fixed offset $i$. This gives $\Pr[B] = \Theta(2^{-\ell})$ and $\Pr[A|B] = \Pr[A \cap B]/\Pr[B] = \Pr[A]/\Pr[B] = \Theta(2^{2s-\ell})$. $\square$

**Lemma 5** Let $\hat{x}$ be the entry point of an arbitrary cycle found by the cycle search algorithm for a fixed $\ell$-bit function $f$, using chains of fixed length $2^s$ such that $s \le \ell/2$. Let $y_0$ be an arbitrary point, and define the chain $y_{i+1} = f(y_i)$ for $i \in \{0, 1, \dots, 2^s - 1\}$. Then the probability that the chain $y_i$ finds the same cycle and entry point $\hat{x}$ is $\Theta(2^{2s-\ell})$, i.e. $\Pr[\exists i', j' \mid y_{i'} \neq y_{j'} \text{ and } y_{i'+1} = y_{j'+1} = \hat{x}] = \Theta(2^{2s-\ell})$.

*Proof* We denote the starting point of the chain found by the cycle search algorithm which collides (cycles) on $\hat{x}$ by $x_0$, and the corresponding collision by $(x_i, x_j)$, with $i < j$, $x_i \neq x_j$ and $f(x_i) = f(x_j) = \hat{x}$. In the following, we assume that $0.25 \cdot 2^s \le i, j \le 0.75 \cdot 2^s$, which occurs with constant

<footnote n="3">³ Once again, a lower bound on $\Pr[A]$ is easy to calculate assuming that $0.25 \cdot 2^s \le i \le 0.75 \cdot 2^s$ (which occurs with probability of about $1/2$).</footnote>
probability. The chain $\vec{y}$ will cycle with entry point $\hat{x}$ if $y_0, y_1, \ldots, y_{2^{s-j}}$ collides with $x_0, x_1, \ldots, x_i$. This occurs with probability of about $2^{2s-l}$ (when $0.25 \cdot 2^s \le i, j \le 0.75 \cdot 2^s$, the two chains are of length $\Theta(2^s)$), which proves that $\Pr[\exists i', j' \mid y_{i'} \ne y_{j'} \text{ and } y_{i'+1} = y_{j'+1} = \hat{x}] = \Omega(2^{2s-l})$. On the other hand, the probability that two chains of length at most $2^s$ collide is at most (roughly) $2^{2s-l}$, and therefore $\Pr[\exists i', j' \mid y_{i'} \ne y_{j'} \text{ and } y_{i'+1} = y_{j'+1} = \hat{x}] = \Theta(2^{2s-l})$. $\square$

# 4 Filters

We describe the two types of filters that we use in our attacks in order to match (known) states computed offline with unknown states computed online by the MAC oracle.

## 4.1 Collision filters

A simple collision filter was introduced in [19], and is also used in our work. A collision filter for an offline state $x$ is a pair of message blocks $(b, b')$, with $b \ne b'$, such that we obtain the same state after processing these blocks from $x$ (i.e. $h(x, b) = h(x, b')$). In order to build the filter, we find a collision in the underlying hash function by evaluating its compression function with state $x$, and about $2^{\ell/2}$ different messages blocks $b$. We apply the filter online on an unknown node $x'$ — obtained after processing a message $m'$ — by checking whether the tags of $m' \parallel b$ and $m' \parallel b'$ collide. If the state obtained after processing $m'$ is not $x$, the tags of $m' \parallel b$ and $m' \parallel b'$ collide with probability only $2^{-n} < 2^{-\ell}$; therefore the collision filter identifies the state $x$ with high probability.

The complexity of building a collision filter offline is $O(2^{\ell/2})$. Testing the filter online requires querying the MAC oracle with $m' \parallel b$ and $m' \parallel b'$; assuming that the length of $m'$ is $2^{s'}$, this requires $O(2^{s'})$ time.

## 4.2 Diamond filters

In order to build filters for $2^t$ nodes, we can build a collision filter for each one of them separately, requiring a total of $O(2^{t+\ell/2})$ time. However, this process can be optimized using the diamond structure, introduced by Kelsey and Kohno in the herding attack [15]. We now recall the details of this construction.

The diamond structure is built from a set of $2^t$ states $x_i$, constructing a set of messages $m_i$ of length $O(t)$, such that iterating the compression function from any state $x_i$ using message $m_i$ leads to a fixed final state $y$. The structure is built in $O(t)$ iterations, where each iteration processes a layer of nodes and outputs a smaller layer to be processed by the next iteration. This process terminates once the layer contains only one node, which is denoted by $y$.
Starting from the first layer with $2^t$ points, we evaluate the compression function from each point $x_i$ with about $2^{(\ell-t)/2}$ random message blocks. This gives a total of about $2^{(\ell+t)/2}$ random values, and we expect them to contain about $2^t$ collisions. Each collision allows matching two different values $x_i, x_j$ and to send them to a common value in the next layer, such that its size is reduced by a factor about 2. The message $m_i$ for a state $x_i$ is constructed by concatenating the $O(t)$ message blocks on its path leading to $y$. According to the detailed analysis of [17], the time complexity of building the structure is $\Theta(2^{(\ell+t)/2})$. Note that for a HAIFA hash function, the nodes of each layer in the structure must be built using the same function and therefore they must have the same offset.

<figure><img src="image_117.png" /></figure>

Once we finish building the diamond structure, we construct a standard collision filter for the final node $y$, using message blocks ($[b]$, $[b']$). Thus, building a diamond filter offline for $2^t$ states requires $O(2^{(\ell+t)/2})$ time, which is faster than the $O(2^{t+\ell/2})$ time required to build a collision filter for each node separately.

In order to test the filter for a state $x_i$ (in the first layer of the diamond structure) on the unknown node $x'$ obtained after processing a message $m'$ online, we simply check whether the tags of $m' \parallel m_i \parallel [b]$ and $m' \parallel m_i \parallel [b']$ collide. Assuming that the length of $m'$ is $2^{s'}$, then the online test requires $O(t + 2^{s'})$ time. Note that for a HAIFA hash function, the online and offline nodes tested for equality must have the same offset.

### 4.2.1 Online diamond filter

A novel observation that we use in this paper, is that in some attacks it is more efficient to build the diamond structure online by calling the MAC oracle. Namely, we construct a diamond structure for the set of $2^t$ states $x_i$, where (the unknown) $x_i$ is a result of querying the MAC oracle with a message $M_i$. Note that the online construction is indeed possible, as the construction algorithm does not explicitly require the value of $x_i$, but rather builds the corresponding $m_i$ by testing for collisions between the states (which can be detected according to collisions in the corresponding tags). However, testing for collisions online requires that all the messages $M_i$ for which we build the online diamond filter are of the same length (both for HAIFA and Merkle-Damgård hash functions). Assuming that the messages $M_i$ are of length $2^s$, building this construction requires $O(2^{s+(t+\ell)/2})$ calls to the compression function.

In order to test the filter for an unknown online state $x_i$ on a known state $x'$, we simply evaluate the compression function from $x'$ on $m_i \parallel [b]$ and $m_i \parallel [b']$,
and check whether the resulting two states are equal. Thus, the offline test requires $O(t)$ time.

<figure><img src="image_118.png" /></figure>

## 5 Internal State-recovery for HMAC with HAIFA

In this section, we describe the first internal state-recovery attack applicable to HAIFA. Our attack has a complexity of $\tilde{O}(2^{\ell-s})$ using messages of length $2^s$, but this only applies with $s \le \ell/5$; the lowest complexity we can reach is roughly $2^{4\ell/5}$. We note that attacks against HAIFA can also be used to attack a Merkle-Damgård hash function, giving more freedom in the queried messages by removing the requirement for long sequences of identical blocks as in [19].

In this attack, we fix a long sequence of “random” functions in order to reduce the entropy of the image states, based on Lemma 1. We then use an online diamond structure to match the states computed online with states that are compute offline. The detailed attack is as follows:

**Attack 1: State-recovery attack against HMAC with HAIFA**

Complexity $\tilde{O}(2^{\ell-s})$, with $s \le \ell/5$ (min: $2^{4\ell/5}$)

1. (online) Fix a message $C$ of length $2^s$. Query the oracle with $2^u$ messages $M_i = [i] \parallel C$. Build an online diamond filter for the set of unknown states $X$, obtained after $M_i$.

2. (offline) Starting from $2^t$ arbitrary starting points, iterate the compression function with the fixed message $C$.

3. (offline) Test each image point $x'$ obtained in Step 2 against each of the unknown states of $X$. If a match is found, then with high probability the state reached after the corresponding $M_i$ is $x'$.

<figure><img src="image_119.png" /></figure>

We detect a match between the grey points (●) using the diamond test built online.

*Complexity analysis.* In Step 3, we match the set $X$ of size $2^u$ (implicitly computed during Step 1), and a set of size $2^t$ (computed during Step 2). We compare $2^{t+u}$ pairs of points, and each pair collides with probability $2^{s-\ell}$
according to Lemma 1. Therefore, the attack is successful with high probability if $t+u \ge \ell-s$. We now assume that $t = \ell-s-u$, and evaluate the complexity of each step of the attack:

**Step 1:** $2^{s+u/2+\ell/2}$ **Step 2:** $2^{s+t} = 2^{\ell-u}$ **Step 3:** $2^{t+u} \cdot u = 2^{\ell-s} \cdot u$

The lowest complexity is reached when all the steps of the attack have the same complexity with $s = u = \ell/5$. More generally, we assume that $s \le \ell/5$ and set $u = s$ to balance steps 2 and 3. This gives an attack with complexity $\tilde{O}(2^{\ell-s})$ since $s+u/2 + \ell/2 = 3s/2 + \ell/2 \le 4\ell/5 \le \ell-s$.

# 6 New Tradeoffs for Merkle-Damgård

In this section, we revisit the results of [19], and give more flexible tradeoffs for various message lengths.

## 6.1 Tradeoff based on iteration chains

In this attack, we match special states obtained using collision based on Lemma 3. This attack extends the original tradeoff of [19] by using two improved techniques. First, while [19] used a same-offset offline collision search, we use a more general free-offset offline collision search which enables us to find collisions more efficiently. Secondly, while [19] used collision filters, we use a more efficient diamond filter.

## Attack 2: Chain-based tradeoff for HMAC with Merkle-Damgård

Complexity $O(2^{\ell-s})$, with $s \le \ell/3$ (min: $2^{2\ell/3}$)

1. (offline) Use free-offset collision search from $2^{\ell-2s}$ starting points with chains of length $2^s$, and find $2^c$ collisions (denoted by the set $\hat{X}$).

2. (offline) Build a diamond filter for the points in $\hat{X}$.

3. (online) Query the oracle with $2^t$ messages $M_i = [i] \parallel [0]^{2^s}$. Sort the tags, and locate 1 collision among the tags.

4. (online) Use a binary search to find the message prefix giving the unknown online collision state $\hat{y}$.

5. (online) Match the unknown online state $\hat{y}$ with each offline state in $\hat{X}$ using the diamond filter. If a match with $\hat{x} \in \hat{X}$ is found, then with very high probability $\hat{y} = \hat{x}$.
<figure><img src="image_120.png" /></figure>

We generate collisions offline using free-offset collision search, build a diamond filter for the collision points (♦), and recover the state of an online collision.

*Complexity analysis.* In Step 1, we use free-offset collision search with $2^{\ell-2s}$ starting points and chains of length $2^s$, and thus according to Section 3.1, we find $2^{\ell-2s}$ collisions (i.e. $c = \ell - 2s$). Furthermore, according to Lemma 3, $\hat{y} \in \hat{X}$ with high probability, in which case the attack succeeds.

In Step 3, we use same-offset collision search with $2^t$ starting points and chains of length $2^s$, and thus according to Section 3.1, we find $2^{2t+s-\ell}$ collisions. As we require one collision, we have $t = (\ell - s)/2$. We now compute the complexity of each step of the attack:

Step 1: $2^{\ell-s}$

Step 2: $2^{\ell/2+c/2} = 2^{\ell-s}$

Step 3: $2^{t+s} = 2^{(\ell+s)/2}$

Step 4: $s \cdot 2^s$

Step 5: $2^{c+s} = 2^{\ell-s}$

With $s \le \ell/3$, we have $(\ell + s)/2 \le 2/3 \cdot \ell \le \ell - s$, and the complexity of the attack is $O(2^{\ell-s})$.

## 6.2 Tradeoff based on cycles

We now generalize the cycle-based state-recovery attack of [19] which exploits the main cycle of approximate length $2^{\ell/2}$ in the graph of the random mapping in order to construct two colliding messages of the same length (thus having equal tags, which can be detected at the output). The attack of [19] uses messages of length $2^{\ell/2}$ and has a complexity of $2^{\ell/2}$.

Our attack uses the same idea of [19], but searches for (potentially) shorter cycles using (potentially) shorter messages of length $2^s$ for $s \le \ell/2$. The complexity of the attack $2^{2\ell-3s}$.

### Attack 3: Cycle-based tradeoff for HMAC with Merkle-Damgård

Complexity $O(2^{2\ell-3s})$, with $s \le \ell/2$ (min: $2^{\ell/2}$)

1. (offline) Search for a cycle in the functional graph of $f = h_{[0]}$, using the algorithm of Section 3.1 with chains of length $2^s$. Denote the length of the cycle by $L$, and its entry point by $\hat{x}$. Build a collision filter for $\hat{x}$.

2. (online) For different values of the message block $[b]$, query the MAC oracle with two messages $M = [b] \parallel [0]^{2^s} \parallel [1] \parallel [0]^{2^s+L}$ and $M' =$
$[b] \parallel [0]^{2^s+L} \parallel [1] \parallel [0]^{2^s}$ (both of length $1+2^s+1+2^s+L = 2+2^{s+1}+L$), until MAC($M$) = MAC($M'$).

3. (online) Define $M_i = [b] \parallel [0]^i \parallel [1] \parallel [0]^{2^s+L}$ and $M'_i = [b] \parallel [0]^{i+L} \parallel [1] \parallel [0]^{2^s}$, and use a binary search to find the minimum value of $i$ such that $M_i$ and $M'_i$ have the same MAC. Use the collision filter to test whether the state reached after $[b] \parallel [0]^i$ is equal to $\hat{x}$.

*Complexity analysis.* The intuition behind this attack is the same as the cycle-based attack from [19]. Step 2 will be successful if the message $M_0 = [b] \parallel [0]^{2^s} \parallel [1] \parallel [0]^{2^s}$ reaches the cycle of length $L$ twice: once after processing $[b] \parallel [0]^{2^s}$ and again after processing the full message $M'$. Indeed, if this is the case, then adding $L$ zero blocks in the first cycle (in message $M'$) or in the second cycle (in message $M$) does not change the state reached before the finalization function. In addition, $M$ and $M'$ have the same length $2+2^{s+1}+L$ which allows the collision to be propagated to the output (a simple attack that enters the cycle only once would not work because of the different lengths).

More formally, we need the two following conditions to be satisfied. First, the states obtained after evaluating the prefixes $[b] \parallel [0]^{2^s}$ and $[b] \parallel [0]^{2^s+L}$ must collide. This occurs if one of the states computed during the evaluation of $[b] \parallel [0]^{2^s}$ collides with $\hat{x}$ (and thus enters the cycle of length $L$), which has probability $\Theta(2^{2s-\ell})$ according to Lemma 5. Secondly, the states obtained after evaluating the suffixes $[1] \parallel [0]^{2^s+L}$ and $[1] \parallel [0]^{2^s}$ must also collide. Similarly to the previous case, this occurs if one of the states computed during the evaluation of $[1] \parallel [0]^{2^s}$ collides with $\hat{x}$. Again, this event occurs with probability $\Theta(2^{2s-\ell})$ according to Lemma 5. Thus, the success probability of Step 2 is $\Omega(2^{2(2s-\ell)})$ (if fact, it is $\Theta(2^{2(2s-\ell)})$), and we need to repeat it for $O(2^{2(\ell-2s)})$ different values of $[b]$ for the attack to succeed with high probability. Consequently, the time complexity of Step 2 is $O(2^{2(\ell-2s)+s}) = O(2^{2\ell-3s})$.

Step 3 will detect the minimum $i$ such that $M_i$ reaches the cycle, therefore the $i$-th state is the entry point of the cycle. Step 3 is expected to be run once for the correct pair, but each block value $b$ can lead to an internal collision (at a common offset) without reaching the cycle with probability about $2^{s-\ell}$, according to Lemma 1. Thus, Step 3 is run $2^{2(\ell-2s)+s-\ell} = 2^{\ell-3s}$ times with false positives.

The time complexity of all the steps is summarized below.

**Step 1:** $2^{\ell-2s+s} = 2^{\ell-s}$

**Step 2:** $2^{2(\ell-2s)+s} = 2^{2\ell-3s}$

**Step 3:** $2^s \cdot s \cdot (1 + 2^{\ell-3s}) = (2^s + 2^{\ell-2s}) \cdot s$

Since $s \le \ell/2$, the complexity of the attack is $O(2^{2\ell-3s})$.

## 7 Shorter Message Attacks

In this section, we describe more complex attacks that can reach a tradeoff of $2^{\ell-2s}$ for relatively small values of $s$. These attacks are useful in cases where the
message length of the underlying hash function is very restricted (e.g. the **SHA-2** family), and moreover they play an important role in the key-recovery attack on **HMAC** with the **GOST R 34.11-2012** hash function (described in Section 8). In order to reach a complexity of $2^{\ell-2s}$, we combine the idea of building filters in the online phase with the use of collisions as special states (using the results of Lemma 3 for Merkle-Damgård and Lemma 4 for HAIFA).

In the case of Merkle-Damgård with identical compression functions, we reach a complexity of $2^{\ell-2s}$ for $s \le \ell/8$, i.e. the optimal complexity of this attack is $2^{3/4 \cdot \ell}$. With the HAIFA mode of operation, we reach a complexity of $2^{\ell-2s}$ for $s \le \ell/10$ i.e. the optimal complexity of $2^{4/5 \cdot \ell}$, matching the optimal complexity of the attack of Section 5.

## 7.1 Merkle-Damgård

**Attack 4: Short message attack for HMAC with Merkle-Damgård**

Complexity $\tilde{O}(2^{\ell-2s})$, with $s \le \ell/8$ (min: $2^{3\ell/4}$)

1. (online) Query the oracle with $2^u$ messages $M_i = [i] \parallel [0]^{2^s}$, and locate $2^{c_1}$ collisions.

2. (online) For each collision $(i, j)$, use a binary search to find the distance (offset) $d_{ij}$ from the starting point to the collision, and denote the (unknown) state reached after $M_i$ (or $M_j$) by $y_{ij}$. Denote the set of all $y_{ij}$ (containing about $2^{c_1}$ states) by $Y$. Build an online diamond filter for all the states in $Y$.

3. (offline) Run a free-offset collision search algorithm from $2^t$ starting points with chains of length $2^s$, and locate $2^{c_2}$ collisions.

4. (offline) For each offline collision $\hat{x}$, match its iterates with all points $y_{ij} \in Y$: iterate the compression function with a zero message starting from $\hat{x}$ (up to $2^s$ times), and match iterate $2^s - d_{ij}$ (i.e., $f^{2^s - d_{ij}}(\hat{x})$) with $y_{ij}$ using the diamond filter. If a match is found, then with high probability $y_{ij} = f^{2^s - d_{ij}}(\hat{x})$.

<figure><img src="image_121.png" /></figure>

<figure><img src="image_122.png" /></figure>

We generate collisions, build an online diamond filter for their endpoints, and match them with iterates of collisions found offline.