Lucky Thirteen or RC4? Picking a TLS Cipher Order

If you run HTTPS servers, 2013 has already handed you attacks on both kinds of cipher that nearly every TLS connection uses. In February, Nadhem AlFardan and Kenny Paterson of Royal Holloway, University of London published Lucky Thirteen, a timing attack on CBC mode, tracked as CVE-2013-0169. Last Tuesday, results on RC4 came out in Dan Bernstein’s invited talk at FSE 2013, and on Wednesday the team (AlFardan, Bernstein, Paterson, Bertram Poettering and Jacob Schuldt) put up a page on the security of RC4 in TLS. NVD published it on Friday as CVE-2013-2566.

The RC4 page itself notes the awkward part: around half of all TLS traffic uses RC4, and it got popular because of earlier attacks on CBC mode. Running from one attack lands you on the other.

Lucky Thirteen goes after CBC padding

A CBC record in TLS is built by computing a MAC over the data, appending it, padding the result out to a full block, and encrypting. The padding isn’t covered by the MAC, so the receiver has to decrypt, check the padding and then check the MAC, and timing the difference between those failures is an old trick. RFC 5246, the TLS 1.2 spec, tells implementations to compute the MAC even when the padding is bad. It also admits this leaves a small timing channel, which it says isn’t believed to be large enough to exploit.

The paper shows it is. The MAC covers 13 bytes of header data (5 bytes of record header and an 8 byte sequence number), and with HMAC-SHA1 and carefully chosen message lengths, things line up so that a record with at least two bytes of valid padding gets processed slightly faster than one with bad padding or only one valid padding byte. The difference is about one hash compression function, a few hundred clock cycles on a modern processor. An attacker in the middle sends modified ciphertexts and times how long the TLS error message takes to show up.

The catch is that every bad record kills the session. The researchers needed about 2^23 TLS sessions to reliably recover one block of plaintext, with the attacker on the same LAN as the target and HMAC-SHA1 in use. If the target is base64, like a cookie, that drops to 2^19, and with BEAST-style malware in the victim’s browser opening sessions that each carry the cookie, they estimate 2^13 sessions per byte. They didn’t test across the internet and expect it to fail, or to need very large numbers of sessions, once the attacker is more than a couple of hops from the server, though they note a hostile network provider or a cloud environment could put an attacker close enough. DTLS is in worse shape, since the attacks there work in a single session.

Their own summary is that in its current form the attack isn’t a significant danger to ordinary users, with the usual reminder that attacks only get better.

The Lucky Thirteen fix is a library update

You don’t fix this in nginx or Apache config. The fix is making CBC decryption take the same time whether the padding is valid or not, and that happens in the TLS library. On February 5, OpenSSL released 1.0.1d, 1.0.0k and 0.9.8y, whose changelogs say they make decoding of SSLv3, TLS and DTLS CBC records constant time. The paper notes the OpenSSL patch took around 500 lines of new C. On February 11 came 1.0.1e, whose NEWS file lists a single change, a corrected fix for CVE-2013-0169, so on the 1.0.1 branch that’s the release you want. The paper lists fixed releases of NSS, GnuTLS, PolarSSL and others as well.

Most of us get OpenSSL from a distribution, and distributions backport fixes instead of bumping versions. Ubuntu’s USN-1732-1 from February 21 fixes CVE-2013-0169 in packages still versioned 1.0.1 on 12.04 LTS and 0.9.8k on 10.04 LTS. Red Hat’s RHSA-2013:0587 from March 4 does the same for RHEL 5 and 6, and says every service linked to OpenSSL has to be restarted, or the system rebooted, before the update takes effect. So check your distro’s advisory rather than the upstream version number, and restart the web server afterwards.

RC4’s problem is the keystream

RC4 is a stream cipher, so there’s no padding to time, which is why the Lucky Thirteen paper calls switching to RC4 the simplest countermeasure. It also warns that RC4’s first keystream bytes have small biases, and last week’s work turns that warning into an attack. The team identified the complete set of biases in the first 256 bytes of RC4 keystream. If the same plaintext, like a cookie, is encrypted at the same position across many sessions, those biases leak it through statistics. With SHA-1 as the MAC, the first 36 bytes are an unpredictable Finished message, so the attack goes after the next 220. Recovering them reliably takes around 2^30 sessions, though certain bytes come out reliably with only 2^24.

Unlike Lucky Thirteen, there’s no timing involved, and the attacker can be anywhere on the network path between client and server. The sessions come from the same places: an application that reconnects and resends a password or cookie, or BEAST-style malware in the browser.

And there’s no library update coming. The page considers discarding the first keystream bytes, but every client and server would have to do it the same way, TLS has no way to negotiate it, and the team calls it not practically deployable. Their verdict on danger to ordinary users matches Lucky Thirteen’s, except they say they anticipate significant further improvements.

Two imperfect options

Put the two pages side by side and each one points at the other. The Lucky Thirteen page says switching to RC4 should only be a temporary measure. The RC4 page says switching to CBC suites is fine provided BEAST and Lucky Thirteen have been patched, and that many TLS 1.0 and 1.1 implementations now have those patches. Both give the same long-term answer, AEAD suites like AES-GCM from TLS 1.2, and both say TLS 1.2 isn’t widely supported yet.

The official server docs still read like 2011. nginx’s Configuring HTTPS servers guide warns that CBC ciphers may be vulnerable to BEAST (CVE-2011-3389) and shows ssl_ciphers RC4:HIGH:!aNULL:!MD5; with ssl_prefer_server_ciphers on; to prefer RC4-SHA. Apache’s 2.4 SSL how-to has a speed-optimized example that puts RC4-SHA:AES128-SHA first with SSLHonorCipherOrder on. As of this writing, neither page mentions this year’s attacks.

BEAST works against the chained IVs of CBC mode in SSL and TLS 1.0, so it’s the older clients where you actually have to choose. CBC means Lucky Thirteen is handled by your patched library while BEAST protection depends on the client’s own TLS stack. RC4 means nothing is patched anywhere, but the attack needs somewhere between 16 million and a billion sessions.

Give TLS 1.2 clients AES-GCM

Whatever you pick for older clients, anything that can speak TLS 1.2 should get GCM. RFC 5288 defines the AES-GCM suites on top of TLS 1.2’s AEAD support and says they must not be negotiated in older versions. That means OpenSSL 1.0.1 on the server, the first release with TLS 1.1 and 1.2, so check which branch your distro ships: Red Hat’s advisory above updates OpenSSL 1.0.0 packages on RHEL 6, while Ubuntu 12.04 is on 1.0.1. nginx has included TLSv1.1 and TLSv1.2 in its default ssl_protocols since 1.1.13 and 1.0.12, given OpenSSL 1.0.1. On Apache, SSLProtocol all covers them with OpenSSL 1.0.1 on 2.4, and 2.2 gained them in 2.2.23.

Keep expectations modest on the client side. The Lucky Thirteen paper says most major browsers don’t support TLS 1.2 yet, and cites SSL Pulse finding it on only 11.4% of 200,000 surveyed sites in January.

OpenSSL 1.0.1e skips TLS 1.2-only suites on older connections, so listing AES-GCM first costs TLS 1.0 clients nothing; they fall through to the next match. The reverse isn’t true. With server preference on, the nginx guide’s RC4:HIGH string hands RC4 to TLS 1.2 clients too, because the RC4 suites sit ahead of every GCM suite.

Here’s one way to write that in nginx, keeping RC4 as the fallback:

ssl_ciphers AESGCM:RC4:HIGH:!aNULL:!MD5;
ssl_prefer_server_ciphers on;

And in Apache, where -SSLv2 matters on 2.2 because all still includes SSLv2 there:

SSLProtocol all -SSLv2
SSLCipherSuite AESGCM:RC4:HIGH:!aNULL:!MD5
SSLHonorCipherOrder on

If RC4 worries you more than unpatched TLS 1.0 clients, drop RC4: from the string. That leaves AES-GCM followed by nginx’s default HIGH:!aNULL:!MD5 set, which contains no RC4. These strings are my own reading of the two research pages plus the directive syntax in the nginx and Apache docs, not something either project or research team has published. AESGCM is an OpenSSL 1.0.1 alias, and the cipher parsers in 0.9.8y and 1.0.0k skip names they don’t recognize.

Checking the result

Run your string through the same OpenSSL your server links against to see the order, then connect once per version with an OpenSSL 1.0.1 client:

openssl ciphers -v 'AESGCM:RC4:HIGH:!aNULL:!MD5'
openssl s_client -connect example.com:443 -tls1_2
openssl s_client -connect example.com:443 -tls1

The Cipher is line should show a GCM suite for the first connection and your chosen fallback for the second.

The takeaway

Lucky Thirteen is a patch and a restart: 1.0.1e, 1.0.0k, 0.9.8y or your distro’s backport. RC4 is a judgment call with no patch behind it. Put AES-GCM first so TLS 1.2 clients skip the argument entirely, then decide with open eyes what older clients fall back to. Both research teams say the real exit is the AEAD suites in TLS 1.2, and until browsers get there, that fallback is the part worth thinking about.