Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

Rainbow Tables for A5/1 by Mind Map: Rainbow Tables for A5/1
0.0 stars - reviews range from 0 to 5

Rainbow Tables for A5/1

Author Info

Map completed Sept 14, 2009 by Luke O'Connor

Link to my blog post based on this map

Main Source

HAR2009

At the recent Hacking at Random (HAR) conference, held from 13-16 August, Karsten Nohl detailed plans for cracking standard GSM cell phone encryption, known as A5/1, and making the results available for anyone to use. You can see a PDF of his presentation here.

announcement of a new project to attack the A5/1 GSM encryption

initiated by cryptography specialist Karsten Nohl

project page

Summary

Result

What, Security researcher Karsten Nohl is launching an open-source, distributed computing project designed to crack the encryption used on GSM phones and compile it into a code book that can be used to decode conversations and any data that gets sent to and from the phone.

How, With community assistance, he plans to pre-compute the secret keys and save them in a code book., He estimates that the project will need 80 people dedicating their hardware and processing resources for about three months before the PoC is ready. However, with 160 people, the time can drop to about six weeks., Each node will donate small portions of disk space, which will house part of the Rainbow Table that will be created and used to crack A5/1, and the fast GPUs will be used for the generation of, and lookup of, the nodes own table.

When, At the recent Hacking at Random (HAR) conference, held from 13-16 August, Karsten Nohl detailed plans for cracking standard GSM cell phone encryption, Nohl told The Tech Herald in an interview that the project expects to have a working proof-of-concept attack on A5/1, “…by the end of the year.”

Why, He hopes that by doing this it will spur cellular providers into improving the security of their services and fix a weakness that has been around for 15 years and affects about 3 billion mobile users., "Clearly we are making the attack more practical and much cheaper, and of course there's a moral question of whether we should do that," he said. "But more importantly, we are informing (people) about a longstanding vulnerability and hopefully preventing more systems from adopting this."

Sound bites

Security researcher Karsten Nohl is launching an open-source, distributed computing project designed to crack the encryption used on GSM phones and compile it into a code book that can be used to decode conversations and any data that gets sent to and from the phone.

Now Mobile Europe has been contacted by Cellcrypt, whose CEO Simon Bransfield-Garth, said, "Everybody has known for quite some time that a theoretical hack of GSM existed. This news means that the theoretical risk will become a very real one within the next six months. Governments have taken steps to manage the threat for years and now this is a very worrying prospect for anyone that discusses valuable or confidential information over their mobile phone.”

“In our soon to be published research, undertaken amongst corporate users in the USA, 79% of people discuss confidential issues by phone every few days with 64% making such calls daily.”

Theoretical compromise presented at the Black Hat conference “…requires the construction of a large look-up table of approximately 2 Terabytes – this is equivalent to the amount of data contained in a 20 kilometre high pile of books.”

Impact

As well as normal telephone conversations, this would also allow text messages to be read, not just by state agencies with specialist equipment (for whom it is already a matter of course), but by anyone with the right equipment, costing just 1,000 euros.

His project, which if successful, will allow anyone with some RF equipment, patience, and a $500 USD laptop, the ability to decode GSM-based conversations and data transmissions.

This would undermine the whole basis of the mobile banking security structure, which uses GSM to transfer mobile TANs for validating online transfers.

Reactions

The encryption problem is particularly serious for people doing online banking, where banks are using text messages as authentication tokens. Banks should instead offer RSA SecurID tokens or send one-time pass phrases through regular mail, Nohl said.

Assuming the project is a rousing success, isn’t he worried that the criminals will take advantage of the proof-of-concept?, Whenever there is Full Disclosure, the information disclosed will usually, “…put some users at risk, but make things better for everybody in the long run.”

“Some criminals already have this ability,” he explained. He gave is an example of code books available now for about $100,000 to $250,000 USD. “If you’re in the business of industrial espionage, then a quarter of a million dollars doesn’t sound like too high of a price,” he added.

GSM Alliance said that the research is a long way from being a practical attack on GSM.

Mitigation

In the meantime, people can use separate encryption products on the phone, like Cellcrypt, or handsets with their own encryption, Nohl said. Amnesty International and Greenpeace are using phones with stronger encryption, for example, but it only works if both parties to a conversation are using the same technology, he said.

3G is more secure, “AT&T has the ability to switch the iPhone to 3G on voice and data,” Nohl explained, but only for the iPhone 3G handsets. As things stand now, the iPhone 3G uses A5/3 (3G) for data transmission and A5/1 (GSM or 2G) for voice., The problem is that, before AT&T moves customers over to 3G to avoid the weakness in A5/1, they would need to admit that there is a problem on their 2G voice network, something Nohl notes is highly unlikely.

Lessons and Issues

This weakness in the encryption used on the phones, A5/1, has been known about for years. There are at least four commercial tools that allow for decrypting GSM communications that range in price from $100,000 to $250,000 depending on how fast you want the software to work

General Sources

cnet

their summary, Security researcher Karsten Nohl is launching an open-source, distributed computing project designed to crack the encryption used on GSM phones and compile it into a code book that can be used to decode conversations and any data that gets sent to and from the phone.

why he's doing it, "We're not creating a vulnerability but publicizing a flaw that's already being exploited very widely," he said in a phone interview Monday., "Clearly we are making the attack more practical and much cheaper, and of course there's a moral question of whether we should do that," he said. "But more importantly, we are informing (people) about a longstanding vulnerability and hopefully preventing more systems from adopting this."

what it means, Using the code book, anyone could get the encryption key for any GSM call, SMS message, or other communication encrypted with A5/1 and listen to the call or read the data in the clear., Once the look-up table is created it would be available for anyone to use., Carriers should upgrade the encryption or move voice services to 3G, which has much stronger encryption, Nohl said., The encryption problem is particularly serious for people doing online banking, where banks are using text messages as authentication tokens. Banks should instead offer RSA SecurID tokens or send one-time pass phrases through regular mail, Nohl said., In the meantime, people can use separate encryption products on the phone, like Cellcrypt, or handsets with their own encryption, Nohl said. Amnesty International and Greenpeace are using phones with stronger encryption, for example, but it only works if both parties to a conversation are using the same technology, he said.

how, If 160 people donate their computing resources to the project, it should only take one and a half months to complete, he said., Participants download the software and three months later they share the files created with others, via BitTorrent, for instance, Nohl said. "We have no connection to them," he added., By distributing the effort among participants and not having it centralized, the new effort will be less vulnerable to outside interference, he said.

legality, Nohl wasn't certain of the legal ramifications of the project but said it's likely that using such a look-up table is illegal but possession is legal because of the companies that openly advertise their tables for sale.

other efforts, This weakness in the encryption used on the phones, A5/1, has been known about for years. There are at least four commercial tools that allow for decrypting GSM communications that range in price from $100,000 to $250,000 depending on how fast you want the software to work, A few years ago a similar GSM cracking project was embarked upon but was halted before it was completed after researchers were intimidated, possibly by a cellular provider, Nohl said.

mobile europe

from theory to practice, Now Mobile Europe has been contacted by Cellcrypt, whose CEO Simon Bransfield-Garth, said, "Everybody has known for quite some time that a theoretical hack of GSM existed. This news means that the theoretical risk will become a very real one within the next six months. Governments have taken steps to manage the threat for years and now this is a very worrying prospect for anyone that discusses valuable or confidential information over their mobile phone.”

private conversations, “In our soon to be published research, undertaken amongst corporate users in the USA, 79% of people discuss confidential issues by phone every few days with 64% making such calls daily.”, cellcrypt

bit silly, And Stuart Quick, risk management specialist at Henderson Risk Limited, commented, “The recent attention given to the hacking A5/1 is no surprise. It remains a Holy Grail amongst the hacking community and is intriguing because of the associated conspiracy theories. It is believed that the cipher has had weaknesses engineered in to it in order to make it easier for the security services to snoop on calls and that mobile communications providers are therefore misleading or incorrectly advertising their product’s level of security.”

heise sec

impact, As well as normal telephone conversations, this would also allow text messages to be read, not just by state agencies with specialist equipment (for whom it is already a matter of course), but by anyone with the right equipment, costing just 1,000 euros., This would undermine the whole basis of the mobile banking security structure, which uses GSM to transfer mobile TANs for validating online transfers., Should the project prove successful and the tables be distributed via, for example, BitTorrent, mobile phone operators will probably find themselves forced to move to more secure encryption standards., This would, however, require that all mobile phones support the new standard, something which usually necessitates a firmware update, and is therefore likely to be a big issue for many users.

why, intended to make the wider public aware of the vulnerabilities in A5/1, which are already old hat in specialist circles.

how, With community assistance, he plans to pre-compute the secret keys and save them in a code book., Since, even with the relatively non-secure A5/1 standard, this would take 100,000 years on a normal PC and would require 128 petabytes of storage capacity, Nohl’s software uses a number of tricks., Nohl is calling on the community to participate in the project in order to compute the tables in the shortest possible time., A little under 200 PCs should be enough to achieve this within a few months., Nohl's idea is nothing new – hacker group THC started to pre-compute key tables for A5/1 back in 2008, and is reported to have completed the task with the aid of FPGAs., However, apparently due to legal issues, the tables have never been published. Nohl's project is largely based on the earlier work carried out by THC, but adds a number of enhancements.

what, It uses the latest graphics cards with CUDA support to carry out the computation,, distributes the task over large numbers of computers connected over the web, compresses the code book/tables using specific procedures so that they take up less space.

tech herald

summary

how, Namely, his project uses graphics cards with GPU capability, and seeks to build a distributed infrastructure of nodes., Namely, his project uses graphics cards with GPU capability, and seeks to build a distributed infrastructure of nodes., Each node will donate small portions of disk space, which will house part of the Rainbow Table that will be created and used to crack A5/1, and the fast GPUs will be used for the generation of, and lookup of, the nodes own table., Nohl told The Tech Herald in an interview that the project expects to have a working proof-of-concept attack on A5/1, “…by the end of the year.”, He estimates that the project will need 80 people dedicating their hardware and processing resources for about three months before the PoC is ready. However, with 160 people, the time can drop to about six weeks., anonymous, The project is anonymous, and the hope is that as users finish their part of the process, they will upload their completed tables to anonymous repositories and share them with BitTorrent.

impact, After the work is complete, the code book produced will be given out freely, and can be used to listen in on GSM-based phone conversations, capture SMS messages sent over the GSM network, or both at the same time., Wouldn’t this mean the criminals could get access to GSM networks and compromise subscriber privacy and security? Why would Nohl even consider this?, 3G is more secure, “AT&T has the ability to switch the iPhone to 3G on voice and data,” Nohl explained, but only for the iPhone 3G handsets. As things stand now, the iPhone 3G uses A5/3 (3G) for data transmission and A5/1 (GSM or 2G) for voice., The problem is that, before AT&T moves customers over to 3G to avoid the weakness in A5/1, they would need to admit that there is a problem on their 2G voice network, something Nohl notes is highly unlikely.

why, “We thought that everyone that is using cell phones should be aware of the security risks,” Nohl explained to us. “Our most sincere and primary goal was to raise awareness about this problem.”, Adding to this he said that the projects aim is to raise awareness about the widespread use of GSM, and by proxy A5/1, which amounts for just over 80-percent of the mobile phone market, used in 200 countries the world over by almost 3 billion people, starting a public debate over the present insecurity and how to make GSM more secure to a “…level where people are comfortable using cellular phones.”

moral, full disclosure, What about the risks? Full Disclosure, which is exactly what he has done with the project's announcement, means that end users are being placed in the line of fire., Assuming the project is a rousing success, isn’t he worried that the criminals will take advantage of the proof-of-concept?, “Some criminals already have this ability,” he explained. He gave is an example of code books available now for about $100,000 to $250,000 USD. “If you’re in the business of industrial espionage, then a quarter of a million dollars doesn’t sound like too high of a price,” he added., Whenever there is Full Disclosure, the information disclosed will usually, “…put some users at risk, but make things better for everybody in the long run.”

GSMA

summary, GSM Alliance said that the research is a long way from being a practical attack on GSM., Moreover, the GSMA feels that there were commercial considerations behind the projects goals

unlikely, storage, heoretical compromise presented at the Black Hat conference “…requires the construction of a large look-up table of approximately 2 Terabytes – this is equivalent to the amount of data contained in a 20 kilometre high pile of books.”, interception, “However, before a practical attack could be attempted, the GSM call has to be identified and recorded from the radio interface., So far, this aspect of the methodology has not been explained in any detail and we strongly suspect the team developing the intercept approach has underestimated its practical complexity,” the GSMA statement says., “The GSMA should take the hacker community and its current interest in GSM technology more serious.”, hinted that the team developing the A5/1 intercept approach underestimated its practical complexity

how, As the project members finish their part of the process, the hope is that they will upload their completed tables to anonymous repositories and share them with BitTorrent.

better encryption, At the same time, there is work to improve the security of GSM-based networks. “The GSMA has been working to further enhance privacy protection on GSM networks and has developed a new high-strength algorithm, A5/3… This new privacy algorithm is being phased in to replace A5/1.”, The use of A5/3 is already spreading across the mobile footprint here in the US., A5/3 is used predominately in 3G networks, but in the case of carriers like AT&T, 3G is only partially implemented., AT&T carries the voice side of their network on GSM, and the data side of things is 3G. This means they are using both A5/1 and A5/3.

HAR2009

Subverting the security base of GSM, not a friendly title

repeatedly broken but no public exploit

GSM is global, omnipresent and insecure, 80% of mobile phone market 200+ countries 3 billion users!, since 1987

should not be used for new apps as insecure

need public decrypt PoC, nice timechart slide 5

groundwork done and open, fast A5/1 implementation, table paremeterization, just generation remains

direct lookup table, An A5/1 code book is 128 Petabyte and takes 100,000+ years to be computed on a PC, he calls it a code book

need to be smarter, Time on single threaded CPU: 100,000+ years, 3 months on 80 CUDA nodes, parallel, alg tweaks

tables, rainbow + DP, don't follow size discussion

distributed, For efficiency, tables distributed over many nodes are preferred, More importantly, no single point of failure should exist on the critical path to the GSM decode PoC