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 sessions. If only a single byte needs to be recovered, about 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 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.

(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

I’m in Leuven attending FSE 2009 and the The First SHA-3 Candidate Conference. I’ve decided to tweet updates on the interesting bits. You can follow these updates for FSE by subscribing to the #fse2009 twitter feed.

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

• EUROCRYPT 2009
• FSE 2009 (PDF)
• CT-RSA 2009

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.

Alex Biryukov was so kind as to organize a public mirror of Wiki of ESC 2008 which took place in Echternach, Luxembourg from January 7th to 11th, 2008. I found this workshop extremely interesting and had quite a blast there. Lots of interesting slides for you on the mirror of the Wiki; not all of the talks were on symmetric-key cryptography. I’ve been meaning to write about some of the talks here, but due to my limited time available for such things at the moment I have kept postponing it thus far; there is something in my drafts folder though.

MiFare’s CRYPTO1 stream cipher has captured my attention for a while. However, hardware reverse-engineering is not a field I actively engage in. So I was very happy when Karsten Nohl (University of Virginia), Starbug and Henryk Plötz gave a talk at the 24C3 [the 24th Congress of the Chaos Computer Club taking place in Berlin at this very moment] yesterday evening showing that they have reverse-engineered most parts of this cipher. CRYPTO1 uses a 48-bit LFSR-based filter generator to generate key stream.

The filter function – if I understood correctly – uses 24 20 taps (this was not mentioned in the talk, I asked Karsten privately about this) however the degree of the boolean function implementing the filter , thus it remains to be seen whether algebraic attacks can be applied. Even if no algebraic attacks are applied, a BSW sampling TMTO will break CRYPTO1 completely. This was pretty obvious before they gave their talk, but now vendors actually have to worry about this being out in the wild once the feedback and the filter function have been revealed.

My colleague Erik took photos of the slides which I put up on Zooomr. A video recording of the talk should be available shortly and will be linked here.

Update 2008-01-02: A recording of the talk now is available (MPEG4, iPod compatible).

LASH, the lattice-based hash function designed by Kamel Bentahar, Dan Page, Markku-Juhani O. Saarinen and Nigel Smart has been broken into tiny little pieces. A septumvirate of authors (Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling, and Huaxiong Wang) have submitted the following devastating analysis of LASH-x to FSE 2008:

• Preimages for LASH-x in about 2^0.36x hash evaluations (and memory).
• Collisions for LASH-x in about 2^0.57x work (and storage). LASH-160′s maximum security level thus effectively is about 58 bits, for LASH-256 we get 93 bits.
• Long-message attacks using lattice reduction techniques
• LASH is not a pseudo-random function (control 1 byte of input and distinguish the output from random with probability 2^{-8})
• A TMTO attack on the final compression function working in about O(x2^x/4) time and memory
• Heuristics for a CVP attack against LASH-160 (using NTL‘s BKZ implementation)

The pre-image and collision attacks presented in the paper exploit the specific fact that LASH uses an all-zero IV, however the authors also demonstrate that tweaking the hash function by changing the IV will not help much. An extended version of the article is available on the IACR’s ePrint server.
Update 2007-12-03: as correctly pointed out in a comment by random, this paper has only been submitted to FSE 2008. It is not clear yet whether it is accepted or not, since notifications of acceptance will only be sent out on December, 10th, 2007. Sorry for the confusion!
Update 2007-12-18: The list of accepted papers for the FSE 2008 is public. The LASH paper has been accepted.

Michael Vielhaber presents an interesting result against a reduced version of the eSTREAM submitted cipher Trivium in a paper on the IACR ePrint archive. By reducing the key setup from 4 full rounds (1152 clock cycles) to two cycles (576 cycles) he is able to mount a chosen IV algebraic attack using a total of 2^6 chosen IV resyncs. This reduced version is called ONE.FIVIUM by him. The impact of the attack against ONE.FIVIUM that 47 of the 80 key bits are claimed to be determined with probability 1 by this attack. The write up needs polishing but most of the results indeed mostly check out. Unfortunately the method by which he arrived at these results is (in my opinion, at least) only superficially described. I strongly suspect this paper is intended to mark a claim. Further results against a clock setup with more cycles are to be expected. Trivium is living dangerously.If you want to check out Michael Vielhaber’s results yourself, I have written Python code for just that. My colleague Andrey Pyshkin initially confirmed the 6 out of the first 7 approximations listed in the table, aidatest.py checks all of them. Below is the output of 256 runs.

approx. for key bits [1] was correct 256 out of 256 times
approx. for key bits [2, 65] was correct 256 out of 256 times
approx. for key bits [3, 66] was correct 0 out of 256 times
approx. for key bits [4] was correct 256 out of 256 times
approx. for key bits [5] was correct 256 out of 256 times
approx. for key bits [6] was correct 256 out of 256 times
approx. for key bits [8] was correct 256 out of 256 times
approx. for key bits [9] was correct 256 out of 256 times
approx. for key bits [11] was correct 256 out of 256 times
approx. for key bits [14] was correct 256 out of 256 times
approx. for key bits [16] was correct 256 out of 256 times
approx. for key bits [17] was correct 256 out of 256 times
approx. for key bits [19] was correct 256 out of 256 times
approx. for key bits [25] was correct 256 out of 256 times
approx. for key bits [26] was correct 256 out of 256 times
approx. for key bits [27] was correct 256 out of 256 times
approx. for key bits [36] was correct 256 out of 256 times
approx. for key bits [38] was correct 256 out of 256 times
approx. for key bits [39] was correct 256 out of 256 times
approx. for key bits [55] was correct 256 out of 256 times
approx. for key bits [56] was correct 256 out of 256 times
approx. for key bits [57, 63] was correct 256 out of 256 times
approx. for key bits [59, 65] was correct 256 out of 256 times
approx. for key bits [60, 66] was correct 256 out of 256 times
approx. for key bits [61] was correct 256 out of 256 times
approx. for key bits [62] was correct 256 out of 256 times
approx. for key bits [63] was correct 256 out of 256 times
approx. for key bits [64] was correct 256 out of 256 times
approx. for key bits [65] was correct 256 out of 256 times
approx. for key bits [66] was correct 256 out of 256 times
approx. for key bits [67] was correct 0 out of 256 times
approx. for key bits [68] was correct 0 out of 256 times
approx. for key bits [15] was correct 256 out of 256 times
approx. for key bits [18] was correct 256 out of 256 times
approx. for key bits [20] was correct 256 out of 256 times
approx. for key bits [23] was correct 256 out of 256 times
approx. for key bits [30] was correct 256 out of 256 times
approx. for key bits [32] was correct 256 out of 256 times
approx. for key bits [33] was correct 256 out of 256 times
approx. for key bits [35] was correct 256 out of 256 times
approx. for key bits [58] was correct 166 out of 256 times
approx. for key bits [21] was correct 256 out of 256 times
approx. for key bits [22] was correct 256 out of 256 times
approx. for key bits [10] was correct 115 out of 256 times
approx. for key bits [12] was correct 141 out of 256 times
approx. for key bits [58] was correct 256 out of 256 times
approx. for key bits [69] was correct 256 out of 256 times

The list of accepted papers for the Fast Software Encryption Workshop 2007 in Luxembourg has been posted. FSE 2007 is taking place from March 26th-28th, 2007 in Luxembourg and is hosted by Alex Biryukov (Program Chair) and Jean-Claude Asselborn (General Chair).