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.

44 comments

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

    See subject: Since vidcards are used to crack these faster, WHY aren't they using them to optionally ALSO process their work they are intended to do in these encryption/decryption deciphering logic engines faster, not by making them algorithmically better even - but rather using hardware that's available & perhaps in this instance, under-utilized...

    (I've read too much on when they're intentionally slowed as I've seen w/ OpenSSL due to bulk OR by the NSA etc. - et al)

    This is ALL so that when you hit sites that use SSL variants, they work faster - because face it - it IS a speed-hit that's bad for performance as opposed to not using it @ all...

    * QUESTION:

    Does the math involved in processing encryption while it's actually working NOT "lend itself" to vidcards speeding them up?

    (... iirc, it's mainly linear algebra - "Yes, APK makes salute across & down" movement with hand - related work that lends itself to it)

    (Feel free to correct me where I am off, IF I am, as I can stand to learn as much as the next guy - AND - to learn something new + dispel any misconceptions I had - "disillusionment IS enlightenment").

    APK

    P.S.=> Thanks in advance for those commenting seriously (F-off to trolls) perhaps even teaching me something here -Oh & by the way (lol) IF I am right? Patent pending apk on this idea... apk

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

      It don't work that well ?.

      The problem is that if you have a heavilly threaded process wanting to do encryption, say a web server, all the threads are in a different state.

      So the data is different, different sizes, but also the connection state, some threads are waiting for input, some halfway through sending. To use a video card (which can run the same algorithm over different data efficiently) you'd have to synchronize the threads - costing you more performance than you'd gain.

      Attacking doesn't have that issue, same data, 6000 different keys, just do it.

    2. 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.

    3. 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.

    4. 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...

    5. Re:Answer me this... apk by Anonymous Coward · · Score: 0

      PCIe 3.0 has 126.032 Gbps of bandwidth available on an x16 bus. (Source: Wikipedia)

      It only takes 13 of those 10 Gbps connections to fully saturate PCIe 3.0 x16. That's what, $50? Psssh.

  2. Small self-edit addendum... apk by Anonymous Coward · · Score: -1

    "it's mainly linear algebra" - by Anonymous Coward on Thursday July 16, 2015 @10:34PM (#50125759)

    Add to that " matrix math at work in the hardware in FPGA" - games use the linear algebra to 'paint' with values - does encryption? Sounds it if the reverse is true for cracking it faster...

    * Here's where if I am off it's a big help to learn otherwise too.

    APK

    P.S.=> Addendum concluded... apk

  3. Ayoub Amine by Anonymous Coward · · Score: -1

    thank you for this article

    http://www.ibda3-net.com

  4. yesterday's news? by Anonymous Coward · · Score: 0

    did everyone got used to it so no one wants to comment? :)

  5. Ayoub by Anonymous Coward · · Score: -1

    thank you :)

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

    Bwuhahahahahahaha

  7. ALL My encryptions are rc4 by Anonymous Coward · · Score: 0

    what better encryption is the available???

    1. Re:ALL My encryptions are rc4 by Anonymous Coward · · Score: 1

      I'm not an expert... AES?

    2. Re:ALL My encryptions are rc4 by Anonymous Coward · · Score: 0

      The Caesar cipher. Although don't use the ROT13 variant - that's been broken.

    3. 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.

  8. 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 Anonymous Coward · · Score: 0

      If you want a fast stream cipher, you can use a modern one like Cha-Cha by DJB. There only reason to stick around with RC4 is backwards compatibility, and even that is dubious nowadays when IE6 is finally in the long process of being phased out. Please don't use RC4.

    4. 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
    5. Re:Is there any value in studying this? by Anonymous Coward · · Score: 0

      IE6 still has its uses.

    6. Re:Is there any value in studying this? by Anonymous Coward · · Score: 0

      Yes. As do antelope. That use has a name: "prey".

  9. 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.

  10. 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 Anonymous Coward · · Score: 0

      You shouldn't be implementing crypto algorithms, even well-known ones, you should be using a vetted library instead.

    4. 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
    5. 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.

    6. 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
    7. Re:Why are we still using RC4? by Anonymous Coward · · Score: 0

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

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

      Those devices are, by definition, upgradable; the question is wherever the corporation behind them wants to maintain them in favor of peddling a newer device all for the sake of more sales.

      This is already the case with consumer routers.

    8. Re:Why are we still using RC4? by Anonymous Coward · · Score: 0

      And smart phones.

  11. Second self-edit addendum... apk by Anonymous Coward · · Score: -1

    You ALL know that I keep goats so I can lick their sweaty rectums right? There is a special place in hell for people like me, and I can't wait to get there.

    Feel free to send me goat sex pics or coupons for astroglide. Because I'm literally jizzing my pants over having first post today.

    APK

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

    "All Your Biases Are Belong To Us"

    FTFY

    --
    Set your phasers on "funky"!
    1. Re:Meme fail by Anonymous Coward · · Score: 0

      Blame the researchers -- their title misses the "Are"

    2. Re:Meme fail by Anonymous Coward · · Score: 0

      Aye matey. All your bases arrr belong to Davey Jones' locker.

  13. 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 Anonymous Coward · · Score: 0

      I keep an open WiFi at home for passersby, but nobody else seems to be doing that for me.

      Probably because of the state of fear over someone like a pedophile using their internet and it being traced back to them and not the pedophile?

    2. 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.

  14. Impersonating me?... apk by Anonymous Coward · · Score: 0

    See subject: Grow up idiot, stop impersonating me.

    APK

    P.S.=> Get a life & get over your obsession with me too please... apk

  15. Parallelization's key then (thanks)... apk by Anonymous Coward · · Score: 0

    "GPUs are good at doing the same thing many times in parallel, which is what breaking encryption requires, but not regular usage." - by marcansoft (727665) on Thursday July 16, 2015 @11:11PM (#50125895) Homepage

    See subject & that quote from you (says it all) - it's key & perfect for my understanding of this & WHY vidcards aren't used over CPUs (others noted how that's built into CPUs now too which also helps explain the 'why' of them NOT being used for actual valid encryption processing speedups).

    * This I understand from normal programming using threads, & it makes sense, ala

    This not gaining (due to C having to wait out the results of A first - thus, no point in using diff. threads of execution on A, B, & C):

    A = B+C
    B = 1
    C = A + B

    Perhaps not the best example here, but it helps make my points with an illustration... this sounds ALMOST that way regarding encryption and the rest of WHAT A GPU DOES (doing same thing many times in parallel) does the rest...

    APK

    P.S.=> Thanks - as I said, I learned something here today & "it's not a wasted day when you learn a new thing"... apk

    1. Re:Parallelization's key then (thanks)... apk by Anonymous Coward · · Score: 0

      A GPU array gives you a lot of cpu's that don't talk to each other much.
      It seems like if you are searching a large key-space (or bias-space?), then you could divide up the space across the GPU's and see which one gets lucky.
      (This assumes that the array can search faster than the CPU with any special hardware like an AES functional unit.)

      Is there something about this particular RC4 weakness which prevents this?

      Assuming this is a real deal:
      A really interesting question here is how long has this been known, and by who, and was that a good idea.
      One would like to think the NSA has known about this for years, but has had the restraint not to use it for more than a handful of domestic issues.
      Hopefully a Congress-critter will quietly verify this as a reality check to see if they are worth their salt.

  16. That's a good idea but... apk by Anonymous Coward · · Score: 0

    See subject: For me to invest time in a new tech (for me), I have to have an idea to apply it to 1st - to keep me interested basically by having an "end goal" in place that's practical for solving a problem for myself, FIRST, & then possibly, others also.

    * I had no idea HOW fpga's or vidcards work really, but NOW I do (doing the same thing many times in parallel from what others stated)... that alone, helps me loads.

    (Understanding of the mechanics of their processing is key of course, first - this turned out worth asking to me, since I learned some new principles at least...)

    APK

    P.S.=> Still, see subject - nothing like "hands on" for that as you said... apk

  17. 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.