There has been speculation that the well known RC4 cypher can be broken by state agencies. Now we have a new result which indicates that it is possible to crack in 75 hours, which make it a practical method in some cases. 

RC4 is a stream cypher which means that you use a key to generate what looks like a random stream of bits which you exclusive or with the data. The receiver of the encrypted bit stream simply exclusive ors the encrypted stream with the same random bit stream to decrypt the data. The receiver can decrypt the bit stream in this way because they also have the key which allows them to generate the same pseudo random bit stream. 

RC4 is used in WPA-TKIP WiFi security and some HTTPS connections, estimated to be about a third of all encrypted connections. 

The RC4 cypher is fast but it has a long history of revealing small, but important, imperfections. In 2013 an attack was devised, but it took 2000 hours to guess the characters in an authentication cookie. The approach used "biases" - the correlations that exist between particular bytes of the cyphertext and the key. Now, with some additional biases that have been detected, Mathy Vanhoef and Frank Piessens have managed to reduce the time to  75 hours for TLS and only an hour against WPA-TKIP. 

The reason it takes so long is that they still need a lot of data.

For theTLS attack they needed about 9*2²⁷ encryptions of the cookie. They can get this number of samples by some clever interception and man-in-the-middle techniques.

See the following video for a general outline:

Vanhoef and Piessens manage to get 4450 requests per second on average and clearly one way to hinder the attack is to reduce the service rate. The method uses additional biases to the ones found originally and the researchers are still looking for more using statistical testing. Hence the title of the paper - All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS. 

At the moment the time to decrypt is too long to be really useful, but as the researchers say in their blog:

"Our work significantly reduces the execution time of performing an attack, and we consider this improvement very worrisome. Considering there are still biases which are unused, that more efficient algorithms can be implemented, and better traffic generation techniques can be explored, we expect further improvements in the future."

The attack is not limited to decrypting cookies - any repeatedly encrypted data can be recovered in the same way. 

The use of RC4 is declining because of calls by Microsoft and Mozilla not to use it, but these requests were based on a general feeling that state agencies had cracked it. This now looks increasingly possible given the new results. 

In many ways, if you know how the RC4 algorithm works, it is surprising that such a simple approach has worked so well for so long and indeed its current state hardly constitues an open door. You have to do quite a bit of work to decrypt even a cookie in RC4 and this only works for data you can repeatedly sample in encrypted form. 

In case you were worried, no data or cats were hurt in the attack as the researchers created a dummy site that would probably become very popular if they decided to actually launch it.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info