The Rise and Fall of RC4
By Itsik Mantin, Director of Security Research at Imperva
In the last couple of years we’ve seen quite a lot of interest concentrated around the RC4 cipher.
Following the BEAST attack on SSL in 2011, many security experts had suggested a preference for RC4 as the SSL cipher on the AES-CBC.
Trying not to be very blunt, I would say that I was surprised by this recommendation, probably along with most of the cryptographic community.
This recommendation could have been reasonable back in the 1990’s, when RC4 details leaked out, and everyone (including myself as M. Sc. student in the course “Method in Cryptanalysis”) was amazed by how simple a secure cipher could be.
However, like the year 2004 for MD5, the year 2001 was very bad for RC4, with sequence of flaws being discovered, shaking, or should I say breaking, the trust of the cryptography community in this cipher.
It started with brilliant research by Fluhrer and McGrew that discovered severe statistical flaws in the RC4 pseudo-random generator.
It continued with my discovery with Adi Shamir of huge statistical flaws in the initialization mechanisms of RC4, and with a joint effort of both groups in the Fluhrer-Mantin-Shamir research, showing two severe ways that the initialization mechanism of RC4 is severely flawed, causing a total break of the WEP protocol, which used RC4 to protect Wi-Fi communication.
The next step was a flood of ever-improving attacks on the initialization mechanisms of RC4, which lasted for more than a decade now and is still continuing.
But let’s go back to 2011.
The BEAST attack required a fixed key, used for the encryption of large amounts of data.
Unluckily for AES, it was strong enough to be used with the same key to encrypt gigs of data without compromising security.
As a stream cipher RC4 mandates a different key for every new encryption, rendering the BEAST attack useless and bringing this so-odd situation.
It took about a year – a moment in academic research terms – for the cryptographic community to translate this shock into an actual attack on RC4 when used in SSL in the Royal-Holloway attack.
Interestingly, this attack was based on the old research by Fluhrer and Mcgrew from 2000.
The Bar-Mitzvah attack from 2015, which relied on a the Invariance Weakness that was presented in the 2001 FMS paper, and the recent attack, based on my work from 2005, continued this trend of cleaning the dust from old crypto flaws and designing security flaws from them.
For many this sequence of attacks on RC4 usage in real-world systems is frustrating, or even frightening.
However, let me lead you to a more optimistic perspective.
The reason for the ongoing usage of RC4 was a gap. A huge gap, spreading between the academy and the industry.
Brilliant researchers in the universities had discovered security flaws, but this knowledge didn’t span this gap, and never reached the consciousness of real-world practitioners.
The good thing is that this gap is getting closed, partially thanks to departments of practical security research in the academy, and partially thanks to research units in the industry.
The RC4 case is an excellent case.
I don’t have the statistics of RC4 usage in the post-BEAST era, but it is likely that a majority of the SSL traffic was protected using RC4.
Following the academy-originated Royal-Holloway attack, and the industry-originated Bar-Mitzvah attack, this number had dropped to less than 20%.
An interesting comparison of the RC4 usage statistics snapshot I took from ssl-pulse on March 9, 2015, before the publication of the Bar-Mitzvah attack, to the same statistics from a couple of days ago (before the recent attack), shows that the number of web servers that choose RC4 for secure communication with modern browsers had fallen from 23.3% to 16.2%, a fall of one third.
figure 1: July 15, 2015
figure 2: March 9, 2015
With the recent attack, this downfall is likely to continue.
