We are the 99.8%: Premature report of RSA demise

If you haven’t read the paper itself [PDF], you've probably seen the NY Times article. A group of researchers led by Arjen Lenstra analyzed a few million RSA public keys and found that some 0.2% of these keys share at least one prime factor with another public key and can thus be factorized. This is due to a random number generation flaw in the process used to choose primes during the generation of these public keys.

I don’t know if their analysis technique is novel, but it’s definitely interesting. Instead of identifying some weakness in a specific key generation library, or analyzing each key separately, the team analyzed pairs of keys to see if they share a common factor. This is done by finding the GCD (Greatest Common denominator) of each pair. If a pair of keys doesn't share a prime they will have a GCD of 1. By working with a very large number of keys the researchers were able to identify a large number of faulty keys.

So is this a big deal? Not as big as you might think from reading the NY Times article.

Obligatory PHD comic

DigiNotar: When is a secure network not secure?

The Dutch government report (PDF) on the DigiNotar hack has confirmed what I suspected:

The separation of critical components was not functioning or was not in place. We have strong indications that the CA-servers, although physically very securely placed in a tempest proof environment, were accessible over the network from the management LAN.

These guys at DigiNotar are living in the nineties. These days the most important attack vector by far is through the network and not physical access. DigiNotar, like many others, invested more effort in defending against the less important attack.

But don't mock them. If you use a disk encryption technology like PointSec or PGP Disk and think it gives you any signficant protection, you may be making the same mistake - assuming an attack involving physical access. It's quite likely hackers already have control of your computer even though it's physically in your possession. You should do what you can to prevent network-based attacks (firewall, anti-virus), but even then you must not assume you're 100% secure. If you have anything that is truly secret just don't put it on a computer you connect to the Internet.

There's been a paradigm shift in the world of corporate security. Instead of traveling and trying to physically access the information of a single company, hackers can use technologies like Remote Access Trojans to attempt attacks on hundreds of companies from the comfort of their own home and with less risk of getting caught by law enforcement. Too many security teams, not just RSA and DigiNotar, haven't yet fully adjusted to this situation.

BTW, the full paragraph in the report begins with another sentence:

The most critical servers contain malicious software that can normally be detected by anti-virus software. The separation of critical components was not functioning or was not in place. We have strong indications that the CA-servers, although physically very securely placed in a tempest proof environment, were accessible over the network from the management LAN.

Which reminds me yet again of this XKCD classic:

DigiNotar: Intruder issued fake certificates

Dutch certificate authority DigiNotar revealed that the fake Google certificates signed by them were due to an intrusion into their system. The didn't give any details on how this was done.

I would assume the attacker didn't physically enter DigiNotar's facilities but instead accessed their network through the Internet. If so, this is yet another case of a security system being breached because the owner did not keep highly sensitive assets properly segregated from computers with access to the open internet.  RSA are not alone.

Or as Randall Munroe of XKCD puts it:

The RSA SecurID debacle: Why it happened

The RSA SecurID saga was one of the more interesting security stories of 2011. Analyzing the background of this story can give some insight as to how security decisions are taken and why security systems fail.