Karsten Nohl and Sylvain Munaut explained in their presentation called “GSM Sniffing” to the Chaos Computer Club Congress how you can find specific phones and eavesdrop on their communication.

Nohl cracked the 64-bit A5/1 GSM encryption code at the start of last year and made a set of encryption tables public. GSM, now over 20 years old, is used in most cell phones around the world — over 3 billion devices and 80 percent of phones including American Apple phones. When he published his results last year he said he wanted to embarrass operators into upgrading 2G calls to the more secure 128-bit A5/3 algorithm.

The GSM Association responded with skepticism. They emphasized strange things like the commercial aspects of hacking and the physical size of 2 Terabytes when converted into books. They also said eavesdropping was unlikely due to complexity of attacks as well as other controls such as broadcast frequency hops.

In 2007-8, a hacking group claimed to be building an attack on A5/1 by constructing a large look-up table1 of approximately 2 Terabytes — this is equivalent to the amount of data contained in a 20 kilometre high pile of books. […] All in all, we consider this research, which appears to be motivated in part by commercial considerations, to be a long way from being a practical attack on GSM. More broadly, A5/1 has proven to be a very effective and resilient privacy mechanism.

How tall is 2 Terabytes when measured in slices of humble pie?

Nohl, to prove the viability of a look-up table, released a set of open source hacking tools in mid-2010 called Kracken. So you might be tempted to conclude that he has been pushing on this very issue for a while. However, I see several news sources emphasize that it has taken a year for the CCC attack to be put together. It must comfort the Association to see reports of how long it takes but each step has been timed with a security conference — Nohl and Munaut have shown in this latest presentation that $100 in hardware is all that is necessary to perform the attack.

That has been their point all along.

So I think a more accurate description of this CCC presentation is that security experts have spent nearly two years trying to convince an Association of the need to improve security, and this is the latest “I told you so” presentation. Their first few slides include the August 2009 quote from the Association as a kind of problem statement:

“the GSM call has to be identified and recorded from the radio interface…we strongly suspect the team developing the intercept approach has underestimated its practical complexity. A hacker would need a radio receiver system and the signal processing software necessary to process the raw radio data.”

The GSM Association has a strong suspicion — faith-based security. Nohl and other security experts, in other words, are presenting facts to disprove a suspicion. He has now, for the third time in a year, publicly demonstrated the simplicity of an attack. Interestingly, although he had to show how to bypass frequency hops to prove his point he only showed an attack on A5/1 and not A5/3; this year he does not explicitly call for the stronger encryption algorithm.

That could be because the 128-bit A5/3 algorithm (aka KASUMI) was was also easily cracked by the Weizmann Institute of Science soon after his presentation in 2009.

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2^{ -14}$. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, $2^{26}$ data, $2^{30}$ bytes of memory, and $2^{32}$ time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the $2^{128}$ complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

Given that A5/3 also is broken, Nohl and Munaut conclude their presentation with the following “wish-list” and threat map for GSM Network security:

1. SMS home routing
2. Randomized padding
3. Rekeying before each call and SMS
4. Frequent TMSI changes
5. Frequency hopping

An interesting Telegraph story describes how a Civil War vignere cipher code message in a bottle has been decrypted.

A message in a bottle sent to a Confederate general during the Siege of Vicksburg, one of the key turning points of the American Civil War, has finally been deciphered [by the CIA] after 147 years.

See also the 2007 CIA publication “Intelligence in the Civil War” (PDF)