Was pulled in to a fun customer issue last Friday around disabling RC4 in Active Directory. What happened was, as you can imagine, not good: RC4 was disabled and half their environment promptly started having a Very Bad Day.
— Steve Syfuhs (@SteveSyfuhs) March 1, 2021
Twitter warning: Like all good things this is mostly correct, with a few details fuzzier than others for reasons: a) details are hard on twitter; b) details are fudged for greater clarity; c) maybe I'm just dumb.
RC4 is a stream cipher. A stream cipher is kinda sorta like a one time pad (note: kinda, and sorta). A one-time pad is a cryptographic operation that takes one value and XORs it against a random value. A^B = C. A is your data, B is random noise. C is your encrypted cipher.
They're incredibly useful because the XOR operation is only reversible when you know A or B, and if B is suitably random that means you have to guess for all combinations of B. In other words you have to brute force it. As far as cryptography goes that's nearly perfection.
However, the trick with one-time pads is that you need as many random bits as you have data. If you have 10 data you need 10 random. If you 10k data you need 10k random. You cannot repeat the random, lest you introduce a pattern and code breakers just love patterns.
So a stream cipher could take a one-time pad and cut the key down to a fixed length, manipulating the key every operation. Let's say you have 100 data and 10 random. The first 10 data get XOR'ed to the 10 random, then the 10 random get XOR'ed to something else. Repeat 10 times.
This turns out to be incredibly simple to code and is incredibly fast relative to other crypto algorithms. However, the cost is that you're now doing key scheduling which means if you can predict the schedule you've broken the cipher.
RC4 fits the bill here. It's painfully simple to implement. Here it is in entirety. But it's also irreparably broken.
The thing with RC4 is that if you have enough data transformed by a single key you can eventually predict what the original plaintext is. This became a semi-practical attack in 2013 when some smart folks figured out how to apply this to TLS. https://isg.rhul.ac.uk/tls/
... continue reading