Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN (2024)

Cryptographic protocols like TLS, SSH, IPsec, and OpenVPN commonly use block cipher algorithms, such as AES, Triple-DES, and Blowfish, to encrypt data between clients and servers. To use such algorithms, the data is broken into fixed-length chunks, called blocks, and each block is encrypted separately according to a mode of operation. Older block ciphers, such as Triple-DES and Blowfish use a block size of 64 bits, whereas AES uses a block size of 128 bits.

It is well-known in the cryptographic community that a short block size makes a block cipher vulnerable to birthday attacks, even if there are no cryptographic attacks against the block cipher itself. We observe that such attacks have now become practical for the common usage of 64-bit block ciphers in popular protocols like TLS and OpenVPN. Still, such ciphers are widely enabled on the Internet. Blowfish is currently the default cipher in OpenVPN, and Triple-DES is supported by nearly all HTTPS web servers, and currently used for roughly 1-2% of HTTPS connections between mainstream browsers and web servers.

We show that a network attacker who can monitor a long-lived Triple-DES HTTPS connection between a web browser and a website can recover secure HTTP cookies by capturing around 785GB of traffic. In our proof-of-concept demo, this attack currently takes less than two days, using malicious Javascript to generate traffic. Keeping a web connection alive for two days may not seem very practical, but it worked easily in the lab. In terms of computational complexity, this attack is comparable to the recent attacks on RC4. We also demonstrate a similar attack on VPNs that use 64-bit ciphers, such as OpenVPN, where long-lived Blowfish connections are the norm.

Countermeasures are currently being implemented by browser vendors, OpenSSL, and the OpenVPN team, and we advise users to update to the latest available versions.

Our results are described in the following technical paper, presented at ACM CCS 2016:

The security of a block cipher is often reduced to the key size k: thebest attack should be the exhaustive search of the key, with complexity2^k. However, the block size n is also an important securityparameter, defining the amount of data that can be encrypted under thesame key. This is particularly important when using common modes ofoperation: we require block ciphers to be secure with up to 2ⁿqueries, but most modes of operation (e.g. CBC, CTR, GCM,OCB, etc.) are unsafe with more than 2^n/2 blocks of message (thebirthday bound).

With a modern block cipher with 128-bit blocks such as AES, thebirthday bound corresponds to 256EB.However, for a block cipher with 64-bitblocks, the birthday bound corresponds to only 32GB, which is easily reached in practice. When the amount of dataencrypted under a fixed key approaches this limit, the security guaranteesof the mode of operation start to crumble. This problem iswell-known by cryptographers, who always require keys to bechanged well before 2^n/2 blocks. Howeverit is often minimized by practitionersbecause the attacks require known plaintext, and reveal only littleinformation.Indeed, standard bodies only recommend to change thekey just before 2^n/2 blocks, and many implementations don'tenforce any limit on the use of a key.

In particular, there are many uses of block ciphers with 64-bit blockswhere large amount of data are potentially encrypted under the same key, such as:

• 3G telephony (UMTS), encrypted with KASUMI;
• OpenVPN, which uses Blowfish as the default cipher;
• many Internet protocols, such as TLS, IPSec and SSH, support Triple-DES as a legacy cipher.

In all these scenarios, 32GB of data can be transferred in less than onehour with a fast connection.

In practice, block ciphers are used with a mode of operation in order todeal with messages of arbitrary length.The CBC mode is one of the oldest encryption modes, and still widelyused. The message M is divided into blocks m_i and isencrypted as: c_i = E_k(m_i ⊕ c_i-1),where c_-1 is an initializationvalue usually denoted as IV.We now explain the impact of collisions on the CBC mode.

CBC has been proven secure up to 2^n/2 ofmessages.On the other hand there is a simple birthday attack against CBC: after2^n/2 message blocks encrypted with the same key (in the samemessage or in different messages), a collision between two ciphertextblocks c_i = c_j is expected. Since E_k is apermutation, a collision in the output means that the inputs are thesame (m_i ⊕ c_i-1 = m_j ⊕ c_j-1)which reveals the xor of two plaintext blocks:m_i ⊕ m_j = c_i-1 ⊕ c_j-1.

With 2^d blocks of data the expected number of collisionsis roughly 2^2d-n-1 (following the birthday paradox).

Practical impact

In many contexts, recovering only the xor betweentwo plaintext blocks is not sufficient for an attack with apractical impact. However, an attack can be mounted when the followingconditions are fulfilled:

• a fixed secret is sent repeatedly;
• some fraction of the plaintext is known.

In this case, there is a chance that acollision leaks the xor between the fixed secret and the knownplaintext; this would immediately reveal the secret. More precisely,this attack is expected to succeed with high probability as soon as2^s copies of the secret and 2^t known blocks are encrypted,with s+t ≥ n.

In particular, this is applicable to the security of encrypted HTTPconnections, when an authentication token is send with every request.A man-in-the-browser attacker can generate a largenumber of requests, and recover the authentication token, using the factthat most headers in the request are predictable or even controlled bythe attacker.

Many of the most influential Internet security protocols, such as TLS,SSH, and IPsec were standardized at a time when 64-bit block ciphers,such as Triple-DES and Blowfish, were still consideredstrong.For example, in TLS 1.0 and 1.1, Triple-DES is the mandatory encryptionalgorithm, so all TLS libraries implement it and a vast majority ofweb servers support it. In addition, until we disclosed theattacks in this paper, OpenSSL included Triple-DES ciphersuites in itsHIGH-security list (it has now been moved to MEDIUM).

Triple-DES and Blowfish usage in VPNs.

IPSec Most IPSec-based VPN clients supportTriple-DES for interoperability. In particular, some versions ofMicrosoft's L2TP VPN clientuse Triple-DESby default.

OpenVPN OpenVPN is a popular open-source VPN solutionoriginally written by James Yonan. The default encryption for thetransport protocol of OpenVPN is Blowfish – a 64-bit cipher – with theCBC mode. OpenVPN supports two different modes to generate session keysto encrypt the messages:

• In pre-shared-key mode, static keys are used for all the traffic. In particular, there is no limit to the lifetime of those keys.
• In TLS mode, session keys are generated with a TLS handshake, using certificates to authenticate the peers. The session keys are updated periodically, with limits on the number of packets, the number of bytes, or a session time. The default configuration rekeys the tunnel every hour.

Triple-DES usage in HTTPS.

Triple-DES is the second most widely supported cipher (after AES) in HTTPSservers, with about 87% of servers supportingit.Furthermore, all popular web browsers support Triple-DES. The cipher thatis actually negotiated for a TLS connection is chosen by the server,based on its local preference order and on the order in which theclient advertises its ciphersuites. Since most modern browsers and serversprefer AES over Triple-DES one may expect only a negligible number of connectionsto negotiate Triple-DES. However, we find evidence that 1-2% ofall TLS connections likely use Triple-DES in CBC mode, as described below.

Firefox TelemetryTelemetry data from Mozilla Firefoxshow that Triple-DES is used for close to 1% of HTTPS connections fromFirefox browsers (0.76% with beta 49). The use of Triple-DES with Firefox is slowly decreasing, and peaked with the removal of RC4 fromthe list of supported ciphers in version 36. Indeed a number of serversare configured to use, in order of preference, first RC4, then Triple-DES,and now use Triple-DES with Firefox. Since all modern browsers havedeprecated RC4 between 2013 and 2015 (followingRFC 7465), they will also usea Triple-DES ciphersuite in this situation.

Scanning the Top 1M WebsitesWe performed a scan of the top 1 million servers as listed byAlexa using the cipherscantool. Wefound that 86% of the servers that support TLS include Triple-DES as oneof the supported ciphers. Moreover, 1.2% of these servers are configuredin such a way that they will actually pick aTriple-DES based ciphersuite with a modern browser, even though better alternatives are available.(In particular many of these servers support AES-based ciphersuites, but use Triple-DES or RC4 preferentially.)

Windows XP Clients and Windows 2003 ServersThe Windows Server 2003 operating system does not support AES-basedciphersuites in its default configuration, although support for AES canbe added with an optional hotfix. The Windows XP operating system withsecurity update MS10-049 supportsAES-based ciphersuites.If AES-based ciphersuites have not been added, these operating systems support onlyRC4, Triple-DES, DES, and RC2-40. While they are not supportedanymore by Microsoft, they still have some users, and this createssituations where the best available cipher is Triple-DES.

Long-lived HTTPS connection

An important requirement for the attack is to send a large number ofrequests in the same TLS connection. Therefore, we need to find client andservers that not only negotiate the use of Triple-DES, but also exchange alarge number of HTTP request in the same TLS connection (withoutrekeying). This is possible using a persistent HTTP connection, asdefined in HTTP/1.1 (Keep-Alive).On the client side, all browsersthat we tested (Firefox, Chrome, Opera) will reuse a TLS connection aslong as the server keeps it open.

On the server side,we found that a number of HTTP servers will close the TLS connectioneven when it is still active. In particular, Apache and Nginxlimit the number of requests sent in the same connection, with a maximumof 100 in the default configuration. On the other hand, IIS does notseem to have such a limit. In practice, many high profile serversaccept a very large number of requests in a single TLS connection.

Vulnerable WebsitesFor a better estimate of the number of vulnerable servers, we testedservers from Alexa's top 10k that negotiate Triple-DES with a modernclient. We identified 11483 different HTTPS servers, and found that 226 of them (1.9%) negotiate Triple-DESwith a modern client. Moreover, 72 of these (0.6% of the total) alsoaccept to keep a connection open for at least 800k requests.Consequently, the duration of the attack is not unrealistic, at leastfrom the viewpoint of browsers and servers, and we estimate that atleast 0.6% of HTTPS connections are vulnerable to our attacks.

For advice about how to check a website'sconfiguration and configure it properly, see the FAQ.

We now demonstrate concrete attacks against authenticated HTTP sessions evenwhen they are secured by TLS or OpenVPN. First, we identify a few examples of secret authentication credentialsthat are repeatedly sent by the browser on every request. We then show how we can recover these secrets using block cipher collisions.

HTTP Bearer Tokens

Cookie-based SessionsModern HTTPS websites use a variety of methods to manage authenticatedsessions with their clients. The most popular mechanism is securecookies as specified in RFC6265. Once a user has logged in, theserver sets a cookie containing a secret value on the user'sbrowser. The browser will then send the cookie on all subsequentrequests to the website, implicitly authenticating the user.

Cookies are sensitive, because an attacker who obtains a session cookiecan then log in as the user from a different browser. The cookie actsas a bearer token that carries the user's delegated credential.

A cookie for a website is normally included in all requests to thatwebsite whether that request was initiated by the user, or a script onthe website, or even by a different website. Browsers sometimes imposestricter rules for this last category of requests, called cross-originor cross-domain requests. For example, XmlHttpRequests sent from onedomain to another may not have cookies attached. However, cross-domainrequests for images or iframes will still send cookies.

HTTP BasicAuthApart from cookies, there are other mechanisms for a website toauthenticate the user. In the HTTP Basic Authentication mechanismspecified in RFC7617, the browser asks the user to enter a usernameand password into a special dialog and then sends this information (inplaintext) as an HTTP header of the form:

Authorization: Basic dGVzdDoxMjPCow=

Once a user has entered his login information once, the browser will typicallycache this information and use it on all subsequent requests to the server.Notably, even if a different website creates a cross-domain request to theauthenticated server, the BasicAuth credentials will be automatically sentby the browser.BasicAuth credentials contain the user's password and are hence security-critical.One should only use this authentication mechanism over HTTPS but a number ofcorporate websites use BasicAuth over HTTP, under the assumption that theirusers can only access the website over a VPN or some other secure connection.

The Beastly Attack Scenario

Our attack scenario, is similar to the setup used in recent attacks on RC4.The attacker wants to steal some bearer token that is being repeatedlysent by a browser to a website secured with HTTPS, or an HTTP websiteaccessed through a VPN. We assume that the attacker cancontrol some JavaScript on a web page loaded by the user's browser,either by actively tampering with an HTTP response on the wire, or byhosting a malicious website that the user is fooled into visiting. Wealso assume that the attacker can observe all the encrypted traffic between thetarget browser and the secure website.

We further assume that the data is encrypted with a 64-bit block cipherin CBC mode (either an HTTPS connection where the client and server havenegotiated Triple-DES, or an HTTP connection though a VPN encrypted with Blowfish or Triple-DES). Suppose the victim is already logged in to awebsite and has a session cookie. The attacker runs maliciousJavaScript code on the victim's browser that repeatedly sends HTTPqueries to the target website server, each containing the sessioncookie. If he sends close to 2³² queries, a collision isexpected between a ciphertext block corresponding to the cookie(c_i), and a known block (c_j), containing a known part of thequery. The collision attack against CBC reveals the session cookie:p_i = p_j ⊕ c_i-1 ⊕ c_j-1.

Note that most of the traffic generated by the attacker is known orpredictable. The requested URL is chosen by the attacker, and all theheaders excepted the cookie are predictable and can be observed in anyHTTP traffic.

<html> <body> <script> var W = new Array; for (var i=0; i<8; i++) { var x = new Worker("worker.js"); W.push(x); } </script> </body></html>

var url = "https://10.0.0.1/index.html";var xhr = new XMLHttpRequest;// Expand URL to ~4kB using a query string// Alternatively, force a large cookieurl += "?";var x = 10000000;for (var i=0; i<=500; i++) { url += x++;}while(true) { xhr.open("HEAD", url, false); xhr.withCredentials = true; xhr.send(); xhr.abort();}

Proof-of-Concept Attack Demo

The attacker code consists of two parts: a JavaScript program that sends a large number of HTTP requests, and a networkadversary who processes the resulting ciphertext to recovers a 16-byte secret.

Man-in-the-browser code The attacker code isshown on the right: it uses Web workers toissue XmlHttpRequests, usingthe withCredentials property to make sure that cookies aresend in the cross-origin request.We experimented with several browsers, and we obtained the bestresults with Firefox Developer Edition 47.0a2.

Recovering collisionsWe captured the encrypted packets with tcpdump and used aC++ program to extract the ciphertext blocks (using libpcap).In both the HTTPS attack and the OpenVPN attack, each HTTP query is sent in aseparate encrypted record, which contain the plaintext at a fixedposition, as well as some extra information (packet number, padding,MAC, ...). Therefore, it is easy to know to which plaintext blockcorresponds each ciphertext block, and to align the cookie to a block limit.After capturing all the traffic, the C++ program sorts the ciphertextblocks in order to locate collisions. Since the amount of data is quitelarge (hundreds of gigabytes), we use the external sort implementation of thestxxl library. With a NAS storage, sorting the data tookaround four hours.

Attacking Basic Auth over OpenVPN

To demonstrate the attack against OpenVPN, we use a pre-shared-keytunnel between two physical machines running Linux, with FirefoxDeveloper Edition 47.0a2 on one side, and an nginx server on the otherside. Access to the server is protected by BasicAuth, and the userhas entered his credentials. Using the default OpenVPN settings, thetunnel is encrypted with Blowfish in CBC mode.

We use the Javascript code described in the previous section to send alarge number of requests to the server though the tunnel. We foundthat increasing the size of the request to 4~kB does not significantlyreduce the query rate, but reduces the number of queries required forthe attack. In our setting, the browser generates about 2900 requestsper second, using several web Worker running in parallel. We expectthe first collision after roughly2^32.3 blocks (40GB), i.e. one hour.In practice, we detected the first collisionearly, after only 30 minutes (2^31.3 blocks); as expected, thepredicted xor difference was correct. The full attack needs about2^36.6 blocks (785GB) to recover a two-block secret out of 4kBmessages; this should take about 19 hours in this setting. In ourdemo, it took 18.6 hours and 705GB, and we successfullyrecovered the 16-byte authentication token.

Attacking Secure Cookies over HTTPS

The attack against HTTPS connection is very similar to the attackagainst OpenVPN, as long as we have a client and server that negotiateTriple-DES, and that keep a connection open for a long time.

Vulnerable Websites As detailed above, about 0.6% of the top Alexa 100Kwebsites support Triple-DES and allow long-lived HTTPS connections. Thislist contains many high-profile e-commerce and banking websites.

We use the Javascript code described above,but we note that with several Workers running inparallel, modern browsers open a few parallel connections tothe server and split the requests over these connections.For our attack, we need to maximize the throughput over a singleconnection. This can be achieved by disturbing some of the connectionsso that most of request are send in a single. In our setup, we usediptables rules to limit the rate of all connections except one.In a real attack, this would be done by an active man-in-the-middle, buta passive man-in-the-middle can also mount the attack -- it will justtake more time to collect the data.

Proof-of-Concept Attack DemoIn our setup we use Firefox Developer Edition 47.0a2 runningon Linux and an IIS 6.0 serverin a Windows Server 2003 R2 SP2 Virtual machine. The default configuration ofIIS 6.0 with all recommended updates offers only RC4 and Triple-DES ciphers,and will use Triple-DES with Firefox and other recent browsers where RC4 isdisabled. Moreover, IIS 6.0 supports HTTP/1.1 and keeps an active connection openfor an arbitrary long time.

On Firefox Developer Edition 47.0a2, with a few dozenWorkers running in parallel, we can send up to 2000 requestsper second in a single TLS connection.In our experiment, we were lucky to detect the first collision afteronly 25 minutes (2^20.1 requests), and we verified that thecollision revealed the xor of two plaintexts blocks. As seenpreviously, the full attack should require 2^36.6 blocks (785GB) torecover a two-block cookie, which should take 38 hours in our setting.Experimentally, we have recovered a two-block cookie from an HTTPS trace of only 610GB, captured in 30.5 hours.

We have demonstrated the first concrete attacks on mainstream Internetprotocols that exploit block cipher collisions. Our attacks canrecover valuable secrets such as HTTP cookies and passwords in under40 hours. Our attacks impact a majority of OpenVPN connections and anestimated 0.6% of HTTPS connections to popular websites. We expectthat our attacks also impact a number of SSH and IPsec connections,but we do not have concrete measurements for these protocols. Likemany recent attacks on TLS, such a BEAST and RC4 NOMORE, theunderlying principles behind our attacks were well known tocryptographers. Our goal is to raise awareness among practitionersabout the vulnerabilities of short block ciphers and on safe ways ofusing them.

Comparison with RC4 attacks

Our attack scenario is very similar to the setup of the recentattacks on the use of RC4 in HTTPS. We usethe same man-in-the-browser setting to generate a large number of HTTPrequests, and the data complexity of the attack is comparable.Our attack requires only 2^29.1 short queries of 512bytes(280GB in total), whichcan be reduced to 2^27.6 longer queries of 4kB(785GB in total). However, these numbers are for thecase when all the data is encrypted within the same session. Even ifthe amount of data sent on a single connection is limited, as long asthe limit is close enough to the birthday bound, we can still mountour attacks across multiple parallel and sequential sessions, albeitwith a higher data and time complexity.

Mitigation

The obvious way to avoid these attacks is to stop using legacy 64-bitblock ciphers. Alternatively, the attack can be mitigated by rekeyingthe session frequently.

Concretely, we recommend the following measures to preventour attack:

• Web servers and VPNs should be configured to prefer 128-bit ciphers. According to our scans, about 1.1% of the top 100k web server from Alexa, and 0.5% of the top 1 million, support AES but prefer to use 3DES.
• Web browsers should offer 3DES as a fallback-only cipher, to avoid using it with servers that support AES but prefer 3DES.
• TLS libraries and applications should limit the length of TLS sessions with a 64-bit cipher. This could be done with TLS renegotiation, or in some cases by closing the connection and starting a new one (i.e. limiting HTTP/1.1 Keep-Alive, SPDY, and HTTP/2 with 3DES ciphersuites).
• OpenVPN users can change the cipher from the default Blowfish to AES, using for instance cipher AES-128-CBC on the client and server configuration. If they don't control the server configuration, they can mitigate the attack by forcing frequent rekeying with reneg-bytes 64000000.

Responsible disclosure

We have communicated our results and concerns to the OpenVPN team, andto various website owners, browser vendors, and TLS libraries. They allacknowledged theissue, and are working on implementing countermeasures. The TLSvulnerability received CVE number CVE-2016-2183, and the OpenVPNvulnerability is tracked as CVE-2016-6329.

NIST is working ondeprecationof 3DES. They plan to limit the use of 3DES to2²⁰ blocks with a given key, and to disallow 3DES in TLS,IPsec, and possibly other protocols.

OpenVPN 2.3.12 will display awarning to users who choose to use 64-bit ciphers and encourage themto transition to AES (ciphernegotiation is also being implemented in the 2.4 branch). It will alsoimplement a defaultrenegotiation limit of 64MB when used in TLS mode in a future version. A wiki entry provides further details.

OpenSSL has moved 3DES ciphersuites from theHIGH category toMEDIUM in the 1.0.1 and 1.0.2 branches, and will disable it by default inthe upcoming 1.1.0 release.They have a blog entry with further details.

Akamai will offer an option for web serveradministrators to drop 3DESfrom the offered ciphers.

Apple has disabled 3DES on icloud.com and isrecommending thatall its customers disable 3DES on their websites.

Currently, most browsers see about 1% of their connections using3DES, and vendors consider this number too high to simply disable3DES on the client side, since too many websites would be broken.So, they are instead considering implementing data limits perconnection to force rekeying, or offering 3DES ciphersuites only in afallback negotiation if no AES ciphersuite is acceptable to theserver.

Mozilla is implementing data limits for allciphersuites. This has been integrated into NSS 3.27, which should be used in Firefox 51.

Microsoft has removed 3DES from the False Startwhitelist.

More details about implemented countermeasureswill be added to this webpage as they becomeavailable.

On the Web

The attack has been mentionned onThreatpost, Ars Technica, Matthew Green's blog, Tom's hardware, Softpedia, Naked Security, The Register, inira.fr, andZDnet.fr, among others....

Why is 3DES still used with a modern browser?

Because more than 1% of the web servers are poorly configured, and prefer using 3DES rather than AES.

How can I check if my server is well configured?

You can use the scanning tool form Qualys SSL Labs. In the "Handshake Simulation" section, you should see 3DES or RC4 only with browsers that don't support stronger ciphersuites, like IE6/XP and IE8/XP. If you have 3DES ciphersuites at the bottom of the "Cipher Suites" section, you can try to remove them, but it's not an immediate security issue. Removing 3DES will protect you against potential downgrade attack, but it will also break connections from older clients.

How can I fix my server's configuration

You can follow the advice from Mozilla, and their Configuration generator.

I'm using Blowfish-256, is it safe?

No, the attack is independent of the key length. It work on Blowfish with any key length, and Triple-DES with 3 independent keys (168 bits in total).

Why Sweet32?

It's a stupid pun, based on the sweet sixteen birthday celebration. Our attack is a birthday attack (taking its name from the birthday paradox) with complexity 2³². You could also say that 2³² is the sweet spot where attacks become practical.

Can I use your logo to talk about the attack?

Yes, you can. To the extent possible under law, Gaëtan Leurent has waived all copyright and related or neighboring rights to the Sweet32 logo.

We are a pair of researchers from INRIA, the French national research institute for computer science. You can contact us at our email addresses: [FirstName].[LastName]@inria.fr (use our names without any accents.)

• Karthikeyan Bhargavan
• Gaëtan Leurent