Turns out that TLS with RC4 (which was supposed to protect us against the BEAST and the CRIME attacks) is not so secure after all:

The attacks arise from statistical flaws in the keystream generated by the RC4 algorithm which become apparent in TLS ciphertexts when the same plaintext is repeatedly encrypted at a fixed location across many TLS sessions.

That sounds familiar... A few months ago, I read a very similar statement in a paragraph on attacks on RC4 in RFC4345 (Improved Arcfour Modes for SSH):

[...] A consequence of this is that encrypting the same data (for instance,a password) sufficiently many times in separate Arcfour keystreams can be sufficient to leak information about it to an adversary.

Intrigued by that, I posted a question on Stackexchange Cryptography, asking if the same problem wouldn't also apply to TLS, with pretty bad implications for password/cookie authentication. I got a very interesting response by a user named poncho, who claimed that he was able to successfully recover a password from 8 billion RC4 encrypted messages.

8 billion seems like too much for a practical attack even when the attacker is able to provoke repated retransmissions of the secret, but if there were a way to optimize that attack, TLS with RC4 would be in serious trouble. And this seems to be exactly what happened just now.

Matthew Green has published a very nice summary of the new attack and the implications on his blog, and I completely agree with his conclusion – we need to stop using RC4.