Slashdot Mirror
New RC4 Encryption Attacks Reduces Plaintext Recovery Time
msm1267 writes: Two Belgian security researchers from the University of Leuven have driven new nails into the coffin of the RC4 encryption algorithm. A published paper, expected to be delivered at the upcoming USENIX Security Symposium next month in Washington, D.C., describes new attacks against RC4 that allow an attacker to capture a victim's cookie and decrypt it in a much shorter amount of time than was previously possible. The paper "All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS," written by Mathy Vanhoef and Frank Piessens, explains the discovery of new biases in the algorithm that led to attacks breaking encryption on websites running TLS with RC4, as well as the WPA-TKIP, the Wi-Fi Protected Access Temporal Key Integrity Protocol.
The answer is that it varies - GPUs are anywhere from mediocre to useless at "normal" crypto.
It depends on whether the particular encryption algorithm/mode in use is parallelizable or not. For example, CBC is not parallelizable - you have to encrypt each block of data serially. GPUs are useless at CBC mode encryption. More modern modes like GCM and XTS are parallelizable to an extent, as you can encrypt multiple blocks at once, but there is still a serial dependency in the process (there is no real way of completely getting rid of all dependencies while keeping the algorithm usefully secure), so you still need to do some pre or post-processing of the data in a serial fashion. And even then, you're limited by bandwidth in/out of the GPU.
Public-key crypto (RSA, DSA, and ECDSA) isn't really parallelizable either as it only deals with small data sizes. And typical hash algorithms like SHA-1 and SHA-256 are also not parallelizable in their construction.
Thing is, CPUs these days have hardware AES encryption acceleration, making this mostly a moot point. GPUs are good at doing the same thing many times in parallel, which is what breaking encryption requires, but not regular usage.
The techniques used for this attack may be useful attacking other things, so it's good to make it known so new algorithms can be tested for susceptibility to this.
All known issues with RC4 have to do with statistical biases in the first bytes of the key stream, in particular the first 256 bytes (this paper also mentions a significant bias at byte 258). As far as we know, all issues with RC4 are avoided in protocols that simply discard the first kilobyte of key stream before starting to apply the key stream on the plaintext. SSH does this (discarding the first 1.5 kiB IIRC). For WPA I can imagine that this workaround would have an unacceptable performance penalty on small data packets. For some reason, this approach was never implemented for TLS/HTTPS or WPA.
So why would one be interested in RC4? It's significantly faster than AES when run on processors that do not have hardware AES support. If I use scp and rsync-over-ssh to copy files to devices like a Raspberry Pi or my home server which runs on a low-power VIA processor, it's a big difference (aes versus arcfour), something like 4 MB/s versus 8 MB/s. Here are some benchmarks: openSSH cipher benchmarks.
I keep my eyes open for papers like this, in particular I check whether they make statements on weaknesses after the first kilobyte of key stream.
Avantslash: low-bandwidth mobile slashdot.
"All Your Biases Are Belong To Us"
FTFY
Set your phasers on "funky"!