RC4 must die

Rivest Cipher 4 (RC4) is one of the most popular stream cipher and as per ICSI Certificate Notary project statistics, RC4 encrypted communication comprises of about 30 percent of SSL/TLS communication. In past few months, couple of attacks, or enhancement of previous known attacks against this widely used algorithm have been proposed and thus making future use of RC4 perilous and hopefully bringing curtains to 28 years of successful existence.

Before getting into the details of the attacks, firstly let us revisit what SSL/TLS is. Secure Socket Layer (SSL, a.k.a Transport Layer Security (TLS)), is the most widely used secure communication protocol on the Internet today. SSL/TLS is presently used for protecting various application level traffic, like in HTTPS to encrypt web browsing traffic, in IMAP and SMTP to cryptographically protect email traffic, to name a few. It is also extensively used with embedded systems, mobile devices, in point of sale payment devices etc. To learn more about SSL/TLS, please read my previous post.

An SSL session, to explain briefly, consists of two phases: SSL Handshaking Protocol and Record Protocol. The former consists of a client authenticating itself to the server and both establishing a cryptographic session keys, which will be used for protecting further communication. While, the latter phase comprises of using the established session key and symmetric key cryptography to build a secure channel of communication for application-layer data. The symmetric key cryptography algorithms come in two flavors based on their underlying design:

– Block Ciphers (CBC mode of operation, e.g: AES)
– Stream ciphers (e.g: RC4)

In the recent past, SSL/TLS has been in the limelight for various security flaws of varying severity  and discussed over here. Broadly, the flaws were either algorithmic weakness or implementation weakness. Heartbleed and OpenSSL CCS occurred because of improper implementation in OpenSSL library, a widely used SSL/TLS library. In contrast, POODLE involved algorithmic weakness. Implementation based security vulnerabilities are relatively easy to fix, as it involves patching the vulnerable part of the code, but vulnerabilities arising because of shortcomings in algorithm design requires change of components which are  vulnerable.

The two attacks are based on the inherent design flaws of RC4 and discussed below.

The first attack [1] is based on the fact that some of the pseudo-random bytes in RC4 used to encode messages are predictable. In 2013 researchers demonstrated that this lack of randomness can be exploited by seeing more than 17 billion (234) separate encryptions of the same data. At the time, this was considered to be impractical attack. Now researchers have further refined the attack and claim that now it takes a tad more than 67 million (226) encryptions of same data to recover the underlying plaintext with 50 percent success rate. It is successfully demonstrated that the enhanced attack can extract security tokens from both basic access authentication over HTTPS and IMAP protocol, used for retrieving and storing e-mail.

The second attack [2], dubbed “bar-mitzvah” attack, given the age of “invariance weakness” on which the attack is based. The attack is devised by researchers at Imperva, a security firm and was presented at Black Hat security conference in Singapore. “Invariance weakness” in RC4 was responsible for fatal exploits against Wired Equivalent Privacy (WEP) technology used to encrypt Wi-Fi networks in 2001. “Bar-mitzvah” attack requires sampling of one billion RC4 encryption to decrypt credit card number, password, or authentication cookie key. Though this attack has a very limited scope, as it is restricted to first 100 bytes of ciphertext generated by RC4. In spite of the limitation, it is significantly faster than performing exhaustive attack that guesses passwords, credit card numbers etc and thus should be considered a practical threat.

Historically, block ciphers also did not have a good past. AES-CBC has seen significant cryptanalysis attacks like BEAST, Lucky 13, POODLE to name a few. These attacks were based on design shortcomings of the algorithm. After series of attacks against block ciphers, RC4 (stream ciphers) was proposed as the recommended work around the attacks. Which also justifies the presence of huge chunk of RC4 encrypted traffic on the Internet. And now two new proposed attacks on RC4, pushes it towards the cliff.

Many argue that the above attacks against RC4 may not be easy to execute practically, but if anything is to be learned from BEAST, Lucky 13 and POODLE, is that – attacks only get better. FREAK vulnerability is a perfect example of implications of using old and archaic standards beyond a certain threshold may come back and bite us really hard. To further strengthen the case against the use RC4, as per RFC 7456 [4], use of RC4 with any TLS version is prohibited.

Various browser vendors are working on doing away with support of RC4 in their browsers  [7]. Mozilla Firefox [5] will stop supporting RC4 in Firefox 44 (expected in Jan 2016), while Google’s Chrome [6] and Microsoft’s Edge [8] browser will stop support by Feb 2016.

[1] http://www.isg.rhul.ac.uk/tls/RC4passwords.pdf
[2] https://www.blackhat.com/asia-15/briefings.html#bar-mitzva-attack-breaking-ssl-with-13-year-old-rc4-weakness
[3] http://arstechnica.com/security/2015/03/noose-around-internets-tls-system-tightens-with-2-new-decryption-attacks/
[4] https://tools.ietf.org/html/rfc7465
[5] https://blog.mozilla.org/security/2015/09/11/deprecating-the-rc4-cipher/
[6] https://googleonlinesecurity.blogspot.in/2015/09/disabling-sslv3-and-rc4.html
[7] http://www.infoworld.com/article/2979527/security/google-mozilla-microsoft-browsers-dump-rc4-encryption.html
[8] https://blogs.windows.com/msedgedev/2015/09/01/ending-support-for-the-rc4-cipher-in-microsoft-edge-and-internet-explorer-11/