- monthly subscription or
- one time payment
- cancelable any time
"Tell the chef, the beer is on me."
Today, Maxime Augier gave a great talk about the state of security of the internet PKI infrastructure. The corresponding paper written by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter was uploaded to eprint.iacr.org archive a few weeks ago. In a nutshell, they found out that some RSA keys, that is often used in the SSL/TLS protocol to secure internet traffic, are generated by bad pseudo random number generators and can be easily recovered, thous providing no security at all.
RSA is one of the oldest and most famous asymmetric encrytion schmes. The key generation for RSA can be summarized as follows:
For a given bitlength l (for example or bits), choose randomly two prime numbers p and q of of bitlength . Choose a number , that has no divisor in common with . Many people choose here for performance reasons, but other choices are valid as well. Now, the number and e form the public key, while is the private key. Sometimes, the numbers p and q are stored with the private key, because they can be used to accelerated decryption.
To encrypt a message m, one just computes , and to decrypt a message, one computes . However, we don’t need that for the rest of this text can safely ignore that.
When generating cartographic keys, we need to distinguish between just random numbers and cryptographically secure random numbers. Many computers cannot generate real random numbers, so they generate random numbers in software. For many applications like computer games and for example simmulations of experiments, we only need number that seem to be random. Functions like “rand()” from the standard c library provide such numbers and the generation of these numbers is often initialized from the current system time only.
For cryptographic applications, we need cryptographically secure random numbers. These are numbers that a generated in a way, that there is no efficient algorithm, that distinguish them from real random numbers. Generating such random numbers on a computer can be very hard. In fact, there have been a lot of breaches of devices and programs, that used a bad random number generator for cryptographic applications.
From my point of view, the paper contains two noteably results:
6 185 228 X.509 certificates have been collected by the researchers. About 4.3% of them contained an RSA public key, that was also used in another certificate. There could be several reasons for this:
This is definitely not supposed to happen. If two RSA keys are generated, that share a common divisor by the same or by different key generation routines, the private key for both public keys can be easily determined, and the key generation routine is deeply flawed.
For those, who use an RSA public key, that shares a modulus with another different RSA public key, their key provides no protection at all. All implementations, that generated these keys definitely need to be updated and the certificates using the weak keys need to be revoked.
Because disclosing the list of affected devices and vendors would compromise the security of these systems immediately, and allow everyone to recover their secret RSA keys, this has not been disclosed.
A reference implementation of the GMR-1 cipher has now been released. You can download the sourcecode from http://cgit.osmocom.org/cgit/osmo-gmr/tree/src/l1/a5.c.
Here are the most important facts in a nutshell:
So in fact, this cipher looks like a A5/2 clone from GSM.
"Tell the chef, the beer is on me."
"Basically the price of a night on the town!"
"I'd love to help kickstart continued development! And 0 EUR/month really does make fiscal sense too... maybe I'll even get a shirt?" (there will be limited edition shirts for two and other goodies for each supporter as soon as we sold the 200)