30 November 2009--If you're still using a cellphone based on early digital standards, you better be careful what you say. The encryption technology used to prevent eavesdropping in GSM (Global System for Mobile communications), the world's most widely used cellphone system, has more security holes than Swiss cheese, according to an expert who plans to poke a big hole of his own.
Karsten Nohl, chief research scientist with H4RDW4RE, a Sunnyvale, Calif.-based security research firm, is mounting what could be the most ambitious attempt yet to compromise the GSM phone system, which is used by over 3 billion people around the world. Others have cracked the A5/1 encryption technology used in GSM before, but their results have remained secret. However, Nohl, who earned a Ph.D. in computer science at the University of Virginia and is a member of Germany's Chaos Computer Club (CCC), intends to go one big step further: By the end of the year, he plans to make the keys available to everyone on the Internet.
Each GSM phone has its own secret key, which is known by the network. Every time a call is initiated, a new session key for that particular call is derived from the secret key and used to encrypt the call. Nohl aims to crack the session key.
The engineer has designed an open-source software program that participants in his A5/1 cracking project can install on their PCs and use to share the task of computing the lookup tables that make up the cryptography system. The final codebook with the computed tables will be shared across a peer-to-peer network. Therefore, no one computer contains all the files, making it difficult, if not impossible, to remove the cracking tool entirely from the Internet.
The aim of the project, he says, is not to "break anything" but rather to create an awareness of "a long-standing vulnerability" in GSM encryption technology and, ultimately, to push mobile phone operators still delivering calls over GSM networks either to phase in the more advanced voice and text-messaging encryption technology, A5/3, or upgrade to a newer-generation digital phone system.
Technically, Nohl's approach is based on the same techniques used in a GSM crack carried out in 2008 by security group The Hacker's Choice (THC). But Nohl's effort has a few twists.
The A5/1 cracking project aims to compress the 128-petabyte A5/1 codebook -- which would require more than 100 000 years of computing by a single PC to crack--to around 2 or 3 terabytes of data, and a computing time of around three months, with the help of about 80 computers. To speed up computing time, the project relies on some components not always found in your standard PC, such as Nvidia Corp.'s CUDA (Compute Unified Device Architecture) graphics cards and Xilinx Virtex field-programmable gate arrays (FPGAs).
"Graphics cards aren't necessarily faster than CPUs, but they are for a few specific applications, and computing the A5/1 cipher is one of them," Nohl says. While admitting that expensive Virtex chips aren't common in PCs, he says several groups with Virtex clusters have joined the project.
To reduce storage requirements, the A5/1 cracking project compresses data with "rainbow tables." These are a type of lookup table that can be used to create a codebook to defeat encryption. Because rainbow tables tend to be large and can take many days or months to compute, depending on processor speed, a common approach to generating them is "time memory trade-off" (TMTO). As its name implies, the approach forces a trade-off: either lower memory usage and slower program execution or higher memory usage and shorter computation time. Although rainbow tables can take a long time to create, once made, they can be used to recover passwords or in the case of GSM, to list session keys and eavesdrop on calls.
GSM cracking has a long history, which began in the late 1990s in academic circles and has since sprouted a handful of commercial businesses. Today, these companies legally sell GSM call-interception solutions--which are relatively expensive--mostly to government intelligence agencies. In general, supplying and using this software is illegal in the wider market, but no one can say for certain how many groups have illegally gained access to the technology.
That's the point Nohl hopes to drive home: The A5/1 algorithm is a broken 64-bit encryption technology, a relic of the Cold War era, when laws prohibited the export of strong encryption technology from the United States. It needs to be replaced--ideally by the much stronger, 128-bit A5/3 system, which is already being used in newer-generation digital cellular systems, such as Universal Mobile Telecommunications System (UMTS). "If you go from the 64 bits of the A5/1 cipher to the 128 bits of A5/3," says Nohl, cracking requires an amount of memory storage that is beyond what "is available on earth."
A big problem with plugging the GSM encryption hole, according to the security expert, is that operators are unwilling to admit that a problem even exists. Many want to avoid spending additional money on upgrading aging and amortized GSM infrastructure, he says. The GSM Association, which represents the interests of GSM mobile operators around the world, says only that it is aware of various eavesdropping projects. In the same breath, it points to the complexities of identifying and recording calls from RF signals.
Some experts see Nohl's approach as unique. "The issue is not whether GSM can be cracked--we know it can. It's the scale and effort required to do so, and the accessibility of technology," says Simon Bransfield-Garth, CEO of Cellcrypt, in London, which specializes in encryption technology for mobile phones. He believes Nohl's project will succeed in providing "a viable way of creating the codebook in a practical amount of time and disk space" and, equally important, in making "the software to create the codebook publicly available." Bransfield-Garth adds that once the codebook is available on the Internet, the hacker community will create call-interception tools that even people with "little specialist knowledge" will be able to use.
Those tools, however, will also require hardware to intercept GSM radio signals, and additional software to connect the radio interceptor to the A5/1 cracking project's distributed codebook. While admitting that the task of intercepting mobile phone calls in the air is "not trivial," Nohl points to the GNU Radio project, a free software tool kit for building and deploying software-defined-radio systems, and to the availability of relatively inexpensive Universal Software Radio Peripheral high-speed computer boards for making software radios.
Too much fuss over a security hole in an aging system? Security vulnerabilities are always an issue for programmers and engineers when improving running systems and developing new ones. And even though newer digital mobile phone network technologies promise to be airtight, the vast majority of mobile phone users in the world are still using GSM systems, and many will continue to do so for years to come. They're paying customers, and they have a right to privacy, says Nohl.
About the Author
John Blau writes about technology from Düsseldorf, Germany. In July 2009 he wrote about the resurgence of efforts to make synthetic skin.