Slashdot Mirror

← Back to Stories (view on slashdot.org)

New RC4 Encryption Attacks Reduces Plaintext Recovery Time

Posted by samzenpus on from the protect-ya-neck dept.

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.

21 of 44 comments (clear)

  1. Re:Answer me this... apk by marcansoft · · Score: 5, Informative

    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.

  2. I'll have CmdrTaco's WiFi password within the hour by Anonymous Coward · · Score: 1

    Bwuhahahahahahaha

  3. Is there any value in studying this? by thegarbz · · Score: 3, Insightful

    Is there any further value in studying an encryption scheme that is widely considered completely and irreparably broken? At this point isn't it like discovering a house with a completely open front door can be broken into by smashing a window?

    RC4 is already not recommended as a cypher for many applications.

    1. Re:Is there any value in studying this? by suutar · · Score: 4, Informative

      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.

    2. Re:Is there any value in studying this? by hankwang · · Score: 5, Informative

      studying an encryption scheme that is widely considered completely and irreparably broken?

      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.
    3. Re:Is there any value in studying this? by DarkOx · · Score: 2

      Yes because there are many many situations where the only mutually supported cipher between two end points is RC4 be it used for SSL/TLS or any other protocol. RC4 is also much faster when you are working with something that does not have hardware accelerated crypto. It does not matter much if we are talking some big SSL offload device but can matter a great deal when its some tiny MIPS or ARM chip in your industrial controller.

      Studying the possible attacks on RC4 make sense because there are lots of people who may be faced with a decision requiring large investments of time and money replacing hardware or software that is otherwise still meeting their needs. You need to have some understanding of just how risky RC4 might be to make that decision. Its easy in a security role to just say "RC4 == bad must fix", but that isn't providing great service. Understanding the value of what you are protecting and the potential consequences if the encryption is broken are critical the next part is understanding how easy it is to break.

      If a successful attack requires 10's of thousands of known plain texts that you can't imagine the likely attackers have any way of getting, and will take months of key space searching with 100's of GPUs and special purpose build software, vs some guy with a couple Radeons and a stock copy of Kali can do it in hour with handfull of plain texts it might change the decision.

      --
      Repeal the 17th Amendment TODAY! Also Please Read http://www.gnu.org/philosophy/right-to-read.html
  4. Why still bothering with RC4? by wvmarle · · Score: 2

    It's old, it's pretty much done for, and preceded by many better protocols (some of which have also been seriously damaged since, like RC5). It starts to sound a bit like kicking a dead horse.

  5. Why are we still using RC4? by jonwil · · Score: 2

    Why would any sane admin use RC4 for SSL/TLS instead of using a more secure algorithm like AES?

    1. Re:Why are we still using RC4? by nullchar · · Score: 5, Interesting

      Because it's in firmware that can't be [easily] upgraded?

      Hooray the Internet of Things! Billions of devices that will never be upgraded.

    2. Re:Why are we still using RC4? by OrangeTide · · Score: 1

      RC4 and TEA are the only algorithms I have memorized, everything else I have to look up because they are so complicated. For being trivial to implement (at least in software), RC4 lasted quite a while.

      --
      “Common sense is not so common.” — Voltaire
    3. Re:Why are we still using RC4? by OrangeTide · · Score: 2

      I shouldn't be writing compilers either, but I do that too.

      --
      “Common sense is not so common.” — Voltaire
    4. Re:Why are we still using RC4? by dave420 · · Score: 3, Interesting

      We already have billions of devices which will never be updated, so I fail to see why an attack on the Internet of Things is at all pertinent.

    5. Re:Why are we still using RC4? by jp10558 · · Score: 2

      I'd say it's somewhat relevant - it's saying that 'we have a problem now - here's how the "internet of things" will make that problem worse. Maybe figure out mitigations before you buy into the "internet of things"' . . .

      However, here it's likely preaching to the choir. But for general consumption / random google search results, it seems like it's a good idea to point out that this could be an issue.

      --
      Opera, Proxomitron-Grypen,GPG 0x0A1C6EE3
  6. Re:ALL My encryptions are rc4 by Anonymous Coward · · Score: 1

    I'm not an expert... AES?

  7. Re:Answer me this... apk by Anonymous Coward · · Score: 1

    GPUs can do a subset of the formulas for encryption, as well as do some operations that aren't related to the normal encryption process but are related to attacking weaknesses in the encryption algorithm or even factoring for primes.

    There is a bit of bit shuffling and different rounds that are required for more encryption algorithms. A GPU can do these, but not really any faster than a CPU. As the order of operations matters a great deal and it is not easily parallelized. If it were, then it would be even easier to break.

    You should check out OpenCL or CUDA programming for a bit, now that relatively inexpensive graphics cards are capable of using it, of course the more money you spend the faster it goes, but for learning you can go cheap on this. The only cost is your own time.

  8. Re:Answer me this... apk by Anonymous Coward · · Score: 1

    And even then, you're limited by bandwidth in/out of the GPU.

    Heh, if that's the thing limiting your ability to handle encrypted data, I envy your internet connection. I've been fortunate enough to get to play with direct-to-Internet 10Gbps before but DAMN, son. 10Gbps is an ant fart compared to PCIe gen 3 x16...

    I still can't quite believe that today, with four K80s per U, you could get 100TFs of double precision and half a petaflop of float (~25u), AND a 100Gbps network (4u?), AND 200TB of raid-1'ed backing store (8u) into a single cabinet. The power cable would be the size of a bodybuider's forearm and you'd have to install it in a wind tunnel, but even so...

  9. Meme fail by srussia · · Score: 3, Informative

    "All Your Biases Are Belong To Us"

    FTFY

    --
    Set your phasers on "funky"!
  10. Will it help cracking WiFi? by rduke15 · · Score: 1, Interesting

    That's all I'm really interested in. Will it make cracking the neighbor's WiFi practical again? Nobody uses WEP anymore, and almost all the routers with WPS seem to have been upgraded to prevent the very nice Reaver attack which was so cool a few years ago.

    I used to get Internet access anywhere by simply cracking some nearby WiFi. Nowadays, I usually need to use my phone's data connection, which is painfully slow and not usable in other countries because of roaming charges. I keep an open WiFi at home for passersby, but nobody else seems to be doing that for me.

    1. Re:Will it help cracking WiFi? by phoenix_V · · Score: 2

      It's not good for random areas you are passing through, but AT&T DLS routers with WiFi use a 10 digit passcode which is a nice short key space to search if your using pyrit (https://code.google.com/p/pyrit/)

      Comcast defaults to I think a 12 character passcode, but even though it's alpha-numeric they inexplicably used all uppercase, way to screw up the better security decision and needlessly limit your key space as well...

      The short of the above is most people seem to leave the default settings, so grab a few modern GPU's and have a party, backup wifi will be yours in no time. Just be sure to have a good disk on the server storing all the results, they can get large.

  11. Re: ALL My encryptions are rc4 by gmiller123456 · · Score: 1

    I swichted to double rot13 years ago. I've heard of some people using tripple rot13, but that just seems like overkill.

  12. Google setup by manu0601 · · Score: 1

    Oddly, Google still uses RC4, according to Qualys test. They also still allow SSLv3 and have not yet moved to SHA2 signed certificates.