Yes - I concur that the "cryptanalytic breakthrough" GCHQ talked about the NSA having a few years ago was most probably some kind of a practical RC4 break, from

Yes - I concur that the "cryptanalytic breakthrough" GCHQ talked about the NSA having a few years ago was most probably some kind of a practical RC4 break, from context. (Schneier thought this one of the likely possibilities too.) It's used enough in TLS (especially at the time these documents were penned, as some advising on BEAST countermeasures actually encouraged people to use it, instead of switching to TLSv1.2 to use the strong AEAD ciphers - awfully convenient for them!) that if they have, say a known-plaintext-prefix attack of reasonable complexity that can be hardware-accelerated, that would be widely leveragable into very real breaks to them - and the structure of such a thing would look remarkably like what we see here. RC4 is about as good as such a simple crypter can be, but it really is too simple and not good enough now, and I strongly suspect it is already toast and way too late to safely phase out - which is why the IETF are hopefully about to publish an RFC strongly recommending it MUST NOT be used in TLS, at all. (Worse, even if RC4 isn't toast to everyone right now, an attacker who can put your data on ice for a few years - like just about every Nation State Adversary does - may very well make toast with it down the line and read all your data.) We don't have any second-preimages in MD5, yet; what's demonstrated are techniques for efficient collisons. They might, but collisions are easily enough for practical problems as many have publicly demonstrated. SHA-1 hasn't been publicly demonstrated with a collision yet, but it has all the same underlying problems as MD5 (and the original SHA), just to a lesser extent - I suspect that NSA can produce SHA-1 collisions with enough effort. Don't expect them to spend more effort than they need, however, to save money and avoid revealing capabilities where possible. Several attackers have happily leveraged simpler shortcuts - there's a piece of (probably South Korean) malware that has signing keys co-opted from hapless developers who've somehow been derping around with 512-bit RSA keys. I could break those, so that's completely ridiculous! By the way - do be on the look out for PGP signatures with 1024-bit DSA signing keys. There's a lot of them. Upgrade to at least 3072-bit RSA, I suggest (or Ed25519).