Ron was wrong, Whit is right – Weak keys in the internet

Leave a reply

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.

The RSA cryptosystem

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 $latex l = 1024$ or $latex l = 2048$ bits), choose randomly two prime numbers p and q of of bitlength $latex l/2$. Choose a number $latex 1 < e < (p-1)*(q-1)$, that has no divisor in common with $latex (p-1)*(q-1)$. Many people choose $latex e = 2^{16+1}$ here for performance reasons, but other choices are valid as well. Now, the number $latex n = p*q$ and e form the public key, while $latex d = e^{-1} \bmod (p-1)*(q-1)$ 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 $latex c = m^e \bmod n$, and to decrypt a message, one computes $latex m = c^d \bmod n$. However, we don’t need that for the rest of this text can safely ignore that.

How random do these numbers need to be?

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.

What has been found out?

From my point of view, the paper contains two noteably results:

Many keys are shared by several certificates

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:

  • After a certificate has expired, another certificate is issued, that contains the same public key. From my point of view, there is nothing wrong with doing that.
  • A company changes their name or is taken over by another company. To reflect that change, a new certificate is issued, that contains another company name, but still uses the same key. I don’t see any problems here either.
  • A product comes with a pre-installed key, and the consumer has to request an certificate for that key. The same key is shipped to several customers. From my point of view, this is really a bad idea
  • Or there might be really a bad random number generator in some key generation routines, that two entities that are not related come up with the same RSA public (and private) key. This is a security nightmare.

Some keys share a common divisor

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.

What are the consequences?

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.

Which devices and vendors are affected?

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.

GMR-1 cipher specifications are now public

Leave a reply

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:

  • 4 Linear Feedback Shift registers in Fibonacci configuration.
  • 81 bits of state
  • Registers 1, 2, and 3 of length 19, 22, and 23 bits control the output
  • Register 4 of length 17 bits controls the clocking of registers 1, 2, and 3, and does not contribute to the output
  • Clocking control is a simple majority clocking, so that registers are clocked 0 or 1 times
  • The output combiner is a quadratic function

So in fact, this cipher looks like a A5/2 clone from GSM.

Don’t trust satellite phones – The GMR-1 and GMR-2 ciphers have been broken [UPDATE]

4 Replies

(cc) Iridium phone

Today, February 2nd 2012, Benedikt Driessen and Ralf Hund gave a very interesting talk at Ruhr Universität Bochum about their work on satellite phone security. In a nutshell, they were able to reverse engineer and to break the secret ciphers used in many satellite phone systems, namely the GMR-1 and the GMR-2 ciphers.

 

What are satellite phones?

We all know cell phones, also known as GSM, UMTS or 3G phones. These phones communicate with their network operators stations. Usual ranges are a few hundred meters in a city, or up to 40 kilometers in very sparsely populated areas. In many countries in Europe, there is like 99% coverage, so that it is hard to find a place outside with no network coverage. Of course, cell phones tend not to work in tunnels or basements, but outside, the network coverage is usually fine.

There are many countries in the world like the United States of America, Russia or China, with many underpopulated areas, without any network coverage. Also there is no network coverage on the oceans and in many third world countries. But there is a solution, phones communicating with a satellite instead of a ground station can be used there.

How do satellite phones differ?

All phones in Germany use a common standard, and phones can usually be used on different networks, like the O2, Vodafone, E-plus or T-Mobile network. In contrast to that, there are also many different providers in the United States, but they use different systems. For example AT&T and T-Mobile USA are running GSM networks, but Sprint uses a different system, so that you can’t use your T-Mobile phone on the Sprint network. Also for satellite phones, there are many different standards.

A very common standard made by ETSI is GMR-1, which is used by Thuraya and many more operators. The GMR-1 specifications, except for the encryption algorithms are public and available on http://www.etsi.org/. Like many systems maintained by ETSI, GMR-1 uses a proprietary stream cipher cipher, that is not available to the public. Another standard for satellite phones is GMR-2, which is used by Immarsat. Again, a proprietary stream cipher is used for encryption.

GMR-1 and GMR-2 ciphers have been reverse engineered

A few days ago, it was announced that the GMR-1 and GMR-2 ciphers have been reverse engineerd. From the announcement:

…The first main cont­ri­bu­ti­on is that we were able to completely re­ver­se en­gi­neer the en­cryp­ti­on al­go­rith­ms em­ploy­ed. Both ciph­ers had not been pu­bli­cly known pre­vious­ly. We de­scri­be the de­tails of the re­co­very of the two al­go­rith­ms from fre­e­ly avail­able DSP-firm­ware up­dates for sat­pho­nes, which in­clu­ded the de­ve­lop­ment of a cust­om di­sas­sem­bler and tools to ana­ly­ze the code, and ex­ten­ding prior work on bi­na­ry ana­ly­sis to ef­fi­ci­ent­ly iden­ti­fy cryp­to­gra­phic code. We note that these steps had to be re­pea­ted for both sys­tems, be­cau­se the avail­able bi­na­ries were from two en­t­i­re­ly dif­fe­rent DSP pro­ces­sors…

Just that a cipher has been reverse engineered and is now public is not an indication for any kind of weakness of the cipher. Many popular encryption systems, like SSL/TLS that is used for online banking use cryptographic algorithms that are known to the public and have never been designed as closed source systems. In fact, one of the golden rules in cryptography, known as “Kerckhoffs’s principle” states that the security of a system should never be based on keeping the system private. Instead it should just be based on keeping the secret keys used in the system private.

The reverse engineering of GMR-1 has been done by disassembling firmware updates for the Thuraya SO-2510 phone. Most modern phones consist of 2-3 different processors. A main CPU for all the applications and the graphics and the user interface. Another CPU (DSP) is mostly responsible for signal processing and speech coding, and some very low level parts are implemented in dedicated hardware. Because the market for satellite phones is quiet small compared the GSM market, it is usually cheaper to implement these stream ciphers in software on the DSP, instead of hardware, so that standard chips with a custom firmware can be used, instead of a more expensive custom chip design. If a firmware can be extracted from the chip, or is available as a firmware update, this also eases the reverse engineering of these encryption algorithms. For the for the Thuraya SO-2510, the stream cipher has been found inside the DSP code, but not on the ARM host code. Here, a Texas Instruments C55x DSP was used.

Because one may assume, that these stream ciphers are similar to the GSM ciphers, they decided to search through the dissembled DSP code, and look for functions using a lot of XOR and shift operations. These two instructions are mainly used for bit manipulations when implementing linear feedback shift registers in software, but are not so common in none crypto code.

To reverse GMR-2, a Immarsat IsaPhonePro was used. Again, the firmware was analyzed, and the code for a Blackfin DSP was extracted. Surprisingly, the reverse engineered GMR-2 cipher is very different from GMR-1, and also very different from any cipher used in GSM or DECT. Instead of bits, the cipher operates on 8 bit registers (byte-registers). Also surprisingly, two S-Boxes from DES are used in this cipher.

Attacks on GMR-1 and GMR-2 are possible

The GMR-1 cipher is very similar to A5/2, 4 LFSRs are used, but the clocking is only controlled by a single register R4. As a result, one can even use ciphertext only attacks against GMR-1, which means only valid cipher texts are required for the attack. This type of attack is much more powerful than just a known plaintext attack, because it works with any kind of ciphertext, even without knowing the plaintext. This is possible, because there are parity checks inside the plaintext, that reveal the structure of the encrypted plaintext. The attack is similar to the attack described in http://cryptome.org/gsm-crack-bbk.pdf. The whole attack can be executed in less than 30 minutes on a standard PC.

For GMR-2, a known-plaintext attack is possible. In a nutshell, with a certain probability, some bits of the keystream will only be generated from Bytes 0 and 4 of the key. One can observe many keystreams and come up with a highly likely hypothesis for these two bytes of the key, and do a brute force search on the remaining key bytes. In total, keystreams from 5-6 frames (50-65 bytes of the keystream) are required to come up with a good hypothesis. After this, they key can be recovered within a second on a standard PC. However, so far it is unknown how difficult it is, to recover plaintexts.

UPDATE: The full paper is now available: http://gmr.crypto.rub.de/paper/paper-1.pdf

Sovereign Keys – A proposal for fixing attacks on CAs and DNSSEC

Leave a reply

The EFF presented their proposal how to improve the security of SSL/TLS and the internet PKI infrastructure. To understand their proposal, one needs to understand how PKI in the internet works today:

Public Key Cryptography

In cryptography, you can usually encrypt and decrypt  data. In the past, encryption and decryption used the same key. Starting from the 70s, a new class of encryption/decryption algorithms was invented, the public key encryption algorithm. Instead of using the same key for en- and decryption, these algorithms use different keys for en- and decryption. During key generation, two keys are generated: A public key, that is used to encrypt data, and can be given out to everybody in the word, and a corresponding secret key, that must be kept hidden by the owner. Everybody who has access to the public key can encrypt data, but only the owner of the secret key is able to decrypt it.

There are many algorithms, for example RSA and ElGamal are the most famous public key encryption algorithms, while other algorithms like McEliece and Rabin are less well known.

Besides encryption, there are also digital signature algorithms. Again, a public and a private key is generated. The private key can be used to generate a digital signature on a document. The public key can then be used to verify the signature on the document. A signature on a document should guarantee that the document was really signed by the holder of the private key, and was not altered afterwards.

PKI

These ideas sound simple at the first look, but in practice, getting a public key of a person or company is not that easy. Just publishing your public key in some kind of web forum or on your facebook page is not enough. Everybody would be able to create a facebook page for another person, and then posting a fake public key on that page, or under that persons name on a web forum. So we need a way to establish a binding between a public key and a person or identity (a company name, a domain name or an email address). One solution would be to meet everybody in person who you want to communicate with, but it doesn’t scale well, and not everybody wants to fly to San Jose, California, just to get the public key for paypal.com.

For these job, Public Key Infrastructue (PKI) and X.509 Certificates have been invented. A Certification Authority (CA) is an organization, that verifies the identity of a person, and that this person is in possession of a private key. After this has been confirmed, the CA issues a X.509 certificate. That certificate contains the corresponding public key of that person, and it’s identity, and this information is signed using the CAs private key. Everybody who thinks that this CA does a good job in verifying the identity of persons, and is in possession of that CAs public key can verify that signature. As from now on, one only needs to trust a CA. One can simply give away the certificate issued by a CA, and everybody can get the public key from the certificate, and verify that it really belongs to that person, by verifying the signature of the CA. Today, there are hundreds of CAs active on the internet, and every web browser comes with a pre-installed list of trustworthy CAs and their public keys.

SSL/TLS

To encrypt HTTP traffic and to prove the autenticity of a website, the SSL/TLS protocol was created. When a session to a web server is established, the web server usually provides a digital certificate containing the public key of that web server. The web browser verifies the signature on that certificate, and that the identity in that certificate matches with the servers name it want’s to connect to. If everything is fine, the public key in that certificate is used to establish a secure session with that web server using some kind of key derivation scheme. (I won’t go into detail here)

The current state of PKI in the internet

At the first look, this sounds like a perfect solution. Whenever I want to talk privately with paypal, I just point my web browser to https://www.paypal.com/, it automatically connects to the server, gets a certificate, verifies that is has been correctly signed by a trustworthy CA, and the identidy in the certificate matches the expected servers hostname.

Attack vectors

However, there are multiple problems with that system. Just to mention one example: There are hundred of CAs active in the internet, and your web browser trusts every single one of them. Every CA is allowed to issue a certificate for every domain name in the internet. For example the national Chinese stat CA is allowed to issue a certificate for http://www.defense.gov/, which is the website of the ministry of defense of the united states of america. Also, the verification done by most CAs is minimal. For many CAs, it is sufficient if you can receive a mail for hostmaster@domain.tld, to get a certificate for domain.tld. There are multiple ways how you can attack this:

CAs

First of all, you may find a bug in the CAs website or email server, that allows you to get access to the certificate issuing software, bypassing these checks.

DNS

Also, you might be able to attack a DNS server serving the zone-file for domain.tld, that allows you to reroute mail for hostmaster@domain.tld on the DNS level. This allows you to get a certificate for domain.tld too.

Routers

Routers, especially those using BGB or a similar protocol might be tricked into rerouting the traffic for the mail server of domain.tld to your network. This way, you can intercept the mail and get your certificate too.

Crypto

Besides that, weak cryptography  algorithms like MD5 have been used by some CAs, and this has been used to generate a rouge certificate too.

The EFF solution

To improve the security of PKI, the EFF has presented a proposal: Sovereign Keys

Sovereign Keys should make it harder for an attacker to generate a new certificate for an HTTPS website, without the cooperation of the legitimate site operator. The main building block of Sovereign Keys are so called timeline servers. These timeline servers are append-only databases, meaning that one can only add entries to the database, but never modify or delete them. These timeline servers could be operated by different entities like the EFF itself, or Mozilla, Google or Microsoft.

To use Sovereign Keys, the side administrator obtains an X.509 certificate as usual. Then he generates a new key, the so called sovereign key. He uploads the key with the certificate to a timeline server. The server operator checks, if that certificate is really issued by a valid CA and no other sovereign key has been added previously, and adds the sovereign key with the hostname of the certificate to the database.

When a client connects to the website, he also requests all database entries belonging to that hostname from a timeline server. In parallel to that, a SSL/TLS connection is established. The Server delivers the server certificate to the client, with an additional signature created with the sovereign key. The client can then check, if this signature can be verified with the sovereign key retrieved from the timeline server.

More details

The full protocol is a little bit more complex, because it needs to deal with revocation, privacy, mirroring and load balancing the timeline servers and many more things. It has not yet been finalized, but a draft of the protocol can be downloaded from: https://git.eff.org/?p=sovereign-keys.git;a=blob_plain;f=sovereign-key-design.txt;hb=master

Summary

For me, this looks like one of two solutions you need to improve the general security of SSL/TLS. Sovereign keys is a great solution for website operators that care about the security of their users. It will not help a user, if the website he connects to does not use it. For these cases, a different solution should be used, like checking if multiple computers in the internet get the same certificate from the server.