Category Archives: symmetric

Symmetric Key Cryptanalysis

SSL/TLS broken again – A weakness in the RC4 stream cipher

A few days ago, a new attack against SSL/TLS has been published by Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering and Jacob Schuldt. Many attacks on SSL/TLS in the past relied on the protocol design itself, broken implementations leaking side channels, or the X.509 certificate system and improper issuing of certificates. In contrast to these, the new attack is focused on the RC4 stream cipher, that can be used against SSL/TLS.

RC4 usage in SSL/TLS

SSL/TLS doesn’t rely on a single cryptographic primitive. Instead when a new SSL/TLS session is established, both parties negotiate a ciphersuite. A ciphersuite consists of a key exchange algorithm, an encryption method and an integrity protection method. To agree on a common ciphersuite, the SSL/TLS client sends a list of all ciphersuites it supports, and the server choses one of the methods from the list, usually the first one which is also supported by the server. The RC4 stream cipher is one of the possible choices for the encryption method, and also wildly supported and used. Compared to many other encryption methods, RC4 is very fast in software, very easy to implement, and also very efficient because it doesn’t require any padding as many encryption methods based on block ciphers do.

What makes RC4 a bad stream cipher

So what would be expect from a (secure) stream cipher? A stream cipher should take a key, and transform this key into a (pseudo-) random sequence of bytes, chosen from a uniform distribution. However, RC4 has also serious weaknesses. For example, RC4 is also used in the famous WEP protocol, to protect WiFi networks. Here, many similar RC4 keys are used that differ only in the first 3 bytes. These 3 bytes of the key are used as an initialization vector for the cipher, and are transmitted in clear with the encrypted packet. The remaining bytes of the key are shared among all packets, but should only be known to the operator of the network. What has been shown for WEP is, that an attacker, who knows the first 3 bytes of the key, and also has access to some bytes of the key stream can predict the next bytes of the key. The probability for predicting a single byte correct is only slightly above a random guess, but repeating the procedure for many packets (like 10.000) will reveal the secret key that protects the network with almost 100% probability. In a nutshell, if you know a part of an RC4 key, and some bytes of the keystream, then you can predict parts of the remaining key better than just guessing.

How can this be applied to SSL/TLS

But for SSL/TLS, the situation is entirely different. Here, a new key is chosen almost randomly for every new connection and no parts of the key are shown to an attacker. As a result, the methods used to attack RC4 in WEP cannot be applied for SSL/TLS connections. But there are more problems in RC4:  Even if a key for RC4 is randomly chosen, the keystream bytes of RC4 have some biases. For example the second by of output will be 0 with a probability of more than 1/256. What recently has been discovered is, that much more of such biases exist. If a plaintext is transmitted over SSL/TLS, one gets a small hint about the plaintext. If the same plaintext is transmitted over and over again using TLS with RC4 encryption, one can recover the first bytes of the plaintext using these biases in the keystream generated by RC4. No assumptions about other plaintext or keystream bytes must be made, and no knowledge of parts of the key is required. Also this works independant of the implementation used, because it doesn’t require any timings or similar side channels from the implementation.

Consequences of the attack

The number of sessions required depends on how much is known about the plaintext, and what should be recovered. A full plaintext can be recovered using $latex 2^{30}$ sessions. If only a single byte needs to be recovered, about $latex 2^{24}$ sessions might be sufficient, depending on the position of the byte in the plaintext. If one only wants to distinguish two plaintexts only, then less than $latex 2^{24}$ sessions might be enough.

Countermeasures

One may ask now how to counter the attack. One of the best solutions would be to just simply disable RC4 support on a client or on a server. As long as a client and a server still share another common ciphersuite, they will still operate properly. Alternatively, both the server and the client can be patched to send empty application layer records, until the first 256 or 512 bytes of output of RC4 have been used. Currently, the attack works best with the first bytes of output of RC4, but less well with the following bytes.

Final remarks

I have also previously been active in research on RC4 and WEP attacks.

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

(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

Accepted papers for EUROCRYPT 2009, FSE 2009 and CT-RSA 2009

The lists of accepted papers for the following conferences have become available in the last couple of days:

Interesting cryptanalysis papers will be presented at all of the above conferences. It is a bit of a hassle to have CT-RSA and EUROCRYPT back to back on two different continents though.