Why is Google using RC4 for their HTTPS/SSL?
$ openssl s_client -connect www.google.com:443 | grep "Cipher is" New, TLSv1/SSLv3, Cipher is RC4-SHA
Isn't RC4 unsafe to use?
Academically speaking, RC4 is terrible; it has easy distinguishers ("easy" means "can really be demonstrated in lab conditions"). It is also hard to use properly. However, SSL/TLS uses RC4 correctly, and in practice the shortcomings of RC4 have no real importance.
The power-that-be at Google decided to switch to RC4 by default because of the recent "BEAST" attack, which demonstrates (again, in lab conditions) a compromise of a Paypal cookie. There is no such dramatic demonstration for an attack on RC4 as used in SSL, so it was estimated that using AES-CBC with SSL/TLS 1.0 was "more risky" than using RC4.
The academically "right thing" to do would be to use AES-CBC with TLS 1.1 (or any ulterior version), which has no problem with BEAST and none of the RC4-related weaknesses either. However, Google makes money in the real world, and, as such, they cannot enforce a configuration which would prevent a third of their user base from connecting.
Wikipedia has a decent writeup on the known attacks on RC4. Most of them are from biases of the output. To give you an idea of the severity of the attacks see the following quotes from the Wikipedia page:
There is also this:
The following bias in RC4 was used to attack WEP:
As far as I know, however, SSL/TLS does not use a long-term key with a nonce. It establishes a new key every connection (and even refreshes the key after some period of time).
The take away point is, RC4 has shown some weaknesses that have actually been exploited to attack real-world system under certain configurations. But, no one has shown if/how these weaknesses affect SSL/TLS. If you are worried about it, however, I believe SSL/TLS has a cipher negotiation phase, so there is probably a way to force connections to not be able to use RC4. This could open you up to other attacks though.
Like often in cryptography things are easier to misuse than to use ;-)
I do think that in the fullness of time the choice to forcibly migrate people to RC4 will be considered a folly.
We recently had a PCI auditor command that we use RC4 to avoid the BEAST attack. We had no option but to comply or face losing our PCI certification. Across the industry, people are fleeing from AES-CBC in response to this attack. Yet in my opinion using RC4 in TLS is much, much worse than incorrectly using CBC.
Why you ask?
Let's say that Alice and Bob disagree about the security of RC4. Alice thinks RC4 is completely fine for TLS, Bob disagrees.
They decide to set up a little game. In each round of the game, Bob will submit two messages to Alice, m0 and m1. Alice will then choose an RC4 key at random, encrypt one of the messages and send it back to Bob. She always chooses the same message to encrypt for all the rounds in a specific game: either she always encrypts m0 or she always encrypts m1. Bob can have as many rounds as he likes, but at the end his goal is to tell which of the two messages he is getting back in each round.
Now for any secure cipher, Bob wouldn't be able to do this with a probability greater than 50%. However, for RC4 he can do this trivially by requesting the encryption of pairs of two byte messages.
Here's how it works. He sets M0 to 0xFFFF and he sets M1 to 0x0000. The second byte of an RC4 key stream as about twice the likelihood of being zero as it should do: $2\over256$. His strategy is to just submit these messages again and again and again and again. He then records how often he sees 0xFF in the second byte versus how often he see 0x00. He can use this to distinguish whether he's getting M0s or M1s.
This isn't some academic attack either, you can actually implement it in a few lines of Python and it runs in a handful of seconds. See here for some working code I've knocked together that demonstrates this attack. I've set the default number of trials to 2000. It occasional gets it wrong on this setting but most of the time the challenger and attacker agree.
Worse, this game isn't all that academic either. It is often the case that with TLS that same payload is encrypted under multiple keys.
Suppose we use TLS to secure POP or IMAP sessions. The initial phase of the protocol are identical for all users. Worse, it often the case the actual user passwords are transmitted over the TLS.
An attacker might be able to use the biases in the first few hundred bytes of RC4 to significantly reduce an exhaustive search of a user password. He just sits there waiting for the user to connect to their POP server and records each session's bytes. People often configure their e-mail client to do this every few minutes. We're not expecting the user to do anything out of the ordinary!
He then analyses these bytes with respect to already known biases to prioritise a brute-force search of the password space.
I don't even think any new cryptanalysis is required to mount this attack. It simply a question of developing a clever heuristic algorithm that uses the biases already known to significantly reduce the search space. It's just a matter of time until someone does this!
In summary, I think RC4 is as close to broken as you can get without being able to recover arbitrary plaintext. It should be retired urgently and nobody should be using it. Least of all Google.
It's not very practical yet (at least 224 ciphertexts), but attacks can only get better, not worse. Remember how it was with WEP cracking.
Note that the above discussion may be out of date after the Snowden revelations. For example, see the "Hardening Internet Infrastructure" panel at IETF88 where Schneier speculates that the NSA expects to be able to break RC4 and is recruiting staff to do so.
A major problem we still face is fazing out old encryption standards with vulnerabilities, without breaking web access to many sites and services for machines or networks running older software like WinXP and IE8, or that may have a high upgrade cost. I think we should just start forcing the issue however by announcing a timeline in which any vulnerable standards should be removed.
In the leaked Snowden documents released so far there are references to the NSA already using very powerful super computers to try and exploit crypto as large as 2048-bit RSA keys as well as targeting others like AES. Comments alluded to such enormous breakthroughs that only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it
From Bruce Shneier's blog
He later published a new public key of length 4096.