Researchers take another crack at SSL

Filed Under: Data loss, Featured, Privacy

SSL, or Secure Sockets Layer, is the "great enabler" of online commerce.

It's the S in HTTPS, and it's the padlock in the address bar of your browser.

It's the underlying protocol which stops the cybercrooks enjoying a complete free-for-all when you spend money or read your email online.

Together, SSL and its big brotherTransport Layer Security (TLS, which is SSL with a beard and in grown-up clothes) provide a ubiquitous cryptographic mechanism by which two people on the internet, including people who have never met or done business with each other before, can exchange information with secrecy, authenticity and integrity.

Loosely speaking, that means they can verify that they really are talking to each other, not to an impostor; that no-one else is eavesdropping; and that no-one can tamper with the content of their conversation.

But SSL has recently been in the news for all the wrong reasons. For example, we've had the BEAST, Diginotar, Verisign, Stuxnet and, most recently, Trustwave.

In sequence, these SSL-related disaster stories involve: the prevalent server-side implementation of SSL/TLS in a cryptographically weak way; a corporate break-in allowing an Iranian hacker to mint himself fake online SSL IDs; an admission by a certificate authority that it had been hacked in 2010 but forgot to tell anyone; stolen SSL certificates used by a virus writer; and a certificate authority that got caught out creating an eavesdropping SSL certificate for a customer.

It gets worse. Not one but two research papers have just surfaced, digging into the mechanics of actually building the bits-and-bytes of SSL certificates. The results aren't catastrophic, but they are, to say the least, interesting.

Most SSL certificates rely on a public key encryption algorithm called RSA for their authentication component. The idea is that I create a pair of keys: one public; the other private. So if I sign something with my private key, you can use my public key to verify that only I could have signed it. And if you encrypt something with my public key, you can be sure than only I can unlock it.

Provided, of course, that my private key really is private.

Assuming no-one steals my key, or pays a certificate authority to issue a fake key in my name, just how unique [*] is is my private key? Is there a chance that someone else, without any malice aforethought, might unexpectedly end up with a key pair that is identical or at least dangerously similar to mine?

"Yes," according to this latest research.

The problem comes in key generation. Greatly oversimplified, RSA requires you to generate a unique pair of prime numbers, p and q, and to publish, amongst other things, their product, n. You can't be mathematically certain that your p and q are unique, but if they are generated genuinely randomly, the chance that someone else chose them already ought to be vanishingly small.

If you could split n back into p and q, you would have cracked the key. So the security of the system depends on the difficulty of taking that public value n and converting it back into its prime factors p and q.

Prime numbers are only divisible by themselves. So the product of two prime numbers is divisible only by itself and those two primes. Factoring small primes is easy. 15, for example is 5 x 3. You can do this in your head. But factoring ever-larger prime products is ever harder. Try doing the 10-digit product 9326222179 [**] in your head, and then bear in mind that the smallest prime products recommended for current use in RSA keys are over 300 digits long (1024 bits).

So, if someone else has a key with the same n as yours, you know their p and q, because each n factors in only one way. Alternatively, if they choose one of p or q non-randomly, you have a better-than-average chance of guessing it. Since q = n/p and p = n/q, guessing one prime factor gives you the other one on a plate.

And the recent research found a small but worrying number of public keys which shared the same value of n, or which used prime factors from an obviously non-random source.

I'm not going to repeat the papers' findings here - the authors deserve that you read the actual results by clicking through to their own articles, here and here - but both sets of researchers found duplicated ns (prime products), and ns which could be factored easily.

At least some of these problems are explained by poor (or just plain wrong) random number generation, leading to one or both of p and q being guessable, thus breaking the privacy of the resulting private key.

As the famous mathematician and computer scientist John von Neumann is supposed to have said:

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number. There are only methods to produce random numbers, and a strict arithmetic procedure ... is not such a method.

If you're a coder, don't cut corners on randomness. And never, ever try to roll your own pseudo-random number generator, unless you're a world-class cryptographer.


[*] Prescriptive linguists would say that 'unique' is binary. There aren't degrees of uniqueness. They are right. I am attempting a literary manoeuvre here. Please run with it.

[**] 9326222179 = 104729 x 89051

, , , , , , , , , , , , ,

You might like

12 Responses to Researchers take another crack at SSL

  1. John · 1331 days ago

    What? Someone still recommending 1024 bit RSA keys? Probably the same types who insist on the use of 256 bit AES (equivalent to 3072 bit RSA)...

    • Paul Ducklin · 1331 days ago

      Your satire is hard to grok, Sir! (I got a bit confused between your less-thans and greater-thans.)

      But 1024-bit RSA moduli are kinda hard to factor. (If you have purchased an SSL key which expires in the next year, for example, then I think that you would have to agree that a 1024-bit RSA prime product "is enough".)

      Nevertheless, folks, this comment should remind you that key sizes for RSA-type public-key crypto and AES-type symmetric crypto cannot directly be compared.

      An RSA-type key of X bits means "the complexity of cracking it is, we hope, linearly related to the effort of factoring an X-bit-sized product of two primes".

      An AES-type key of Y bits means "the complexity of cracking it is, we hope, linearly related to the complexity of trying out 2-to-the-power-Y decryption keys."

      Calculating the computational complexity ratio between RSA-X and AES-Y is left as an exercise for the reader :-)

  2. Clim · 1331 days ago

    "Since q = p/n and p = q/n..." Is it correct? ))

    • Paul Ducklin · 1331 days ago

      Errr, of course not. Just, ahhhh, testing :-)

      (Corrected in the article. Thanks for noticing!)

  3. john shale · 1331 days ago

    There must be a limited number of these pqn combinations.
    With the computer memory now available, would it be necessary to crack a key, when a look up table could probably check out possible matches to a given public key, quite quickly?

    • Paul Ducklin · 1330 days ago

      You can't short-circuit the factoring with a table: the number of primes available is simply enormous. The Prime Number Theorem says that about 1 in every ln(n) numbers (ln is logarithm-to-the-base-e) in the vicinity of n is prime. We're looking for primes in the vicinity of 2^512, and the ln of that number is about 355, so our primes have an average gap between them less than 2^9. That still leaves us more than 2^503 possible primes to choose from.

      That means that if every keyholder chooses genuinely randomly from the available stash of primes, the probability of collisions is irrelevantly small. And the list of available primes is far, far too large to enumerate in advance. You'd need a flash drive bigger than the universe to store them all :-)

  4. James Nelson · 1330 days ago

    Any competent hacker should be able to generate a table of large prime numbers, and therefore generate a table of possible products. They could then just try them all one after the other.

  5. Curious · 1330 days ago

    Why can't someone use a lookup table to find what p and q are? Surely since p and q are both primes, then there is only a "limited" subset of results possible ?

  6. Curious · 1330 days ago

    And you are not looking up looking through the whole subset - just the last digit to agree, then second to last digit to narrow down the list, then 3rd to last digit - etc

  7. Dan Kaminsky · 1329 days ago

    None of the RSA keys in question were attached to valid certificates. Not one.

  8. Mike Curry · 1329 days ago

    Prime numbers are divisible, not only by themselves, but also 1. (just being critical)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

About the author

Paul Ducklin is a passionate security proselytiser. (That's like an evangelist, but more so!) He lives and breathes computer security, and would be happy for you to do so, too. Paul won the inaugural AusCERT Director's Award for Individual Excellence in Computer Security in 2009. Follow him on Twitter: @duckblog