December 11, 2001
CS 574
By May, 2001, more than half a billion people were using GSM mobile phones – or 70% of digital wireless users worldwide.1 One might surmise that if 500 million people have subscribed to this “GSM” service, then it must be well established. It must provide the services the users want, the prices must be affordable, and it must be somewhat secure – secure in the sense that the service is reliable, bills are accurate, and the system ensures some kind of privacy. These assumptions may be true today, but this was not always the case. From its birth, GSM technology has seen its security implementation go from cutting-edge, to hacker-friendly, and finally to the strong and resilient system it is today.
Brief Background
Wireless technology became popular in Europe in the early 1980’s. Users flocked to the analog cellular telephone system and each country responded by developing its own protocols for cellular communication. Although this allowed users in each country to partake in wireless technology, this system also suffered from two major disadvantages – the equipment could only be used inside a nations borders and the market was severely limited for the specific equipment needed. These national systems were not compatible with systems from other countries – which meant cell phones stopped working as soon as one of the many national boundaries in Europe was crossed. In addition, a limited market created a less than desirable situation for businesses in each country. Europeans, realizing that a new system was needed, met at the Conference of European Posts and Telegraphs in 1982. The group, also known as CEPT, formed a study group named Groupe Spécial Mobile, or GSM. The goals of this GSM group were sixfold in nature:
In 1989 the responsibility of the GSM specifications was transferred to the European Telecommunications Standards, or ETSI, and Phase I of the GSM Standard was published in 1990. In 1991, commercial service started and end users witnessed the birth of what we today call GSM, or the Global System for Mobile communications.
Decisions, Decisions, Decisions
In order to achieve the six goals mentioned above, the designers of GSM chose to use digital technology. This was a rather significant decision at the time, since almost all other cellular networks were analog. Although yet unproven, the potential of a digital system was too much to overlook. As cell phones rapidly gained popularity in the 1980’s, analog systems were unable to cope with the higher demand. The addition of new frequency ranges would have been necessary for analog systems to meet this new demand – a solution many European countries were unwilling to agree upon. Digital systems offered ways of coping with a higher demand without expanding out of the allocated frequency ranges.
Digital systems also offered better voice quality. In analog systems, physical disturbances in the wireless system are passed directly to the receiver. Conditions such as multipath reception, interference, or fading signals can cause noticeable degradation in the quality of the voice heard over the speaker. In digital systems, these disturbances can be avoided by transforming the data into bits. This transformation combined with techniques like digital coding can greatly improve the quality of the transmission.
Digital systems also offered compatibility with ISDN networks. Since the telecommunications industry had converted to digital networks during the GSM developmental phase, an analog system would have required an additional conversion factor to be involved. A digital network would make this problem simply disappear.
So, What Does This Have to do With Security?!
GSM was designed to be a telephone network – just without the wires. Thus, the goals of GSM security were to be analogous. Charles Brookson, Chairman of the Security Group of GSM MoU (Memorandum of Understanding), succinctly summarized this simple goal by stating that the “objective of security for [the] GSM system is to make the system as secure as the public switched telephone network.” 3 So, in order to keep pace with its wired older brother, GSM needed to meet the following requirements:
Unfortunately, these two goals proved to be, for the most part, unattainable. First of all, the very design of a wireless cellular telephone system is quite vulnerable to eavesdropping. Encrypted wireless data leaves the mobile unit and travels to a base station, where it enters the wired network. This is where the vulnerability occurs. Once the encrypted data reaches the base station, it is unencrypted – leaving it entirely up to the carrier to ensure security. This unencrypted data at the base station is vulnerable to law enforcement officers with a warrant, service provider employees, etc. A wireless system is by no means a secure user-to-user link. In fact, Brookson commented that the “greatest threat is from simpler attacks such as disclosure of the encryption keys, insecure billing systems or corruption!” 3 It is attacks such as these that provide the weak link in the big picture, user-to-user wireless system. Although this is not a fallacy of the protocol technology in question (e.g. GSM, CDMA, TDMA, etc), it is a fallacy in the security of the entire system.
The designers knew of the security vulnerability mentioned above and had no choice but to leave this particular issue in the hands of the service providers. The GSM specifications would not apply to data once it had reached the ground, and they made no attempt to extend the standards to do so. Security was obviously not a top priority. Their top goals were to get a new digital, wireless standard approved across many nations – and playing politics with individual nations on encryption issues would only serve to delay the project longer.
However, the system wide fallacy was no excuse to ignore security in the standard. If GSM were to be accepted, it would need to provide the measures to meet the two goals outlined above in over-the-air transmissions. In order to do so, the designers chose to use two separate encryption algorithms. One would be used for authentication, or the guarantee that the user is in fact who the user claims to be, and one to provide some privacy to the over-the-air traffic. The designers decided on the A5 algorithms for voice and data encryption – or, more precisely, A5/1 and A5/2. During the development of GSM, security theory centered around the "security by obscurity" approach. 11 In other words, the algorithms were developed in secret and never revealed to the public. The idea here was to provide any possible intruder with as little information as possible – in the hope that keeping the algorithm secret would prevent any weaknesses from being discovered. The GSM designers, being faithful to this "security by obscurity" ideology, chose the unpublished A5/1 and A5/2 algorithms for voice encryption. The A5/1 algorithm is the stronger of the two and was allocated for use by countries that are members of CEPT. A5/2 is a weaker algorithm and was to be used by all other countries. These A5 algorithms are stream ciphers with 64 bit keys – chosen for the quick speed of transformation and low error propagation. 12 However, secrecy does not imply flawlessness, and defects were later discovered in the A5 algorithms. One such uncovered flaw was ten zeroes introduced into the key, effectively creating a 54 bit key. And, in what was the most devastating blow, in 1999, Adi Shamir and Alex Biryukov showed that the A5/1 algorithm could be broken on a home PC in less than one second. 11 This “cracking” of the A5/1 algorithm was not a deathblow to GSM – Shamir and Biryukov’s method required sophisticated radio scanning equipment and a full two minutes of voice encrypted data to succeed. 9 However, technology only improves with time, and GSM was on the brink of losing the public’s trust.
In addition to GSM’s virtual inability to guarantee privacy, their method of authentication also fell under attack in 1998. Authentication in GSM is accomplished by the Challenge Response method. Each mobile unit is assigned a secret key – known only by the mobile unit and an Authentication Center (accessible by the base station). The base station sends a random string to the mobile unit, which then uses its secret key to generate a response. The base station uses the secret key provided by the Authentication Center to determine if the mobile unit’s response is correct. The original shared algorithm was known as A3 and was kept secret, much like A5/1 and A5/2. In 1998, the Berkeley Group published their analysis of COMP128 (the carrier algorithm used to implement A3). The analysis classified the algorithm to be extremely weak – in fact, they summarized that it would take approximately 219 queries to the mobile unit to determine the secret key. This translates to roughly eight hours of airtime. These 480 minutes are not very much – especially when one considers that carrier providers sell monthly plans that contain up to thousands of minutes. In other words, the A3 “algorithm is cryptographically weak, and it is not difficult to break the algorithm and clone GSM digital phones.” 4
The real question here is, “What went wrong?” The designers put together a standard that is by far the most widely used wireless standard in the world. So, how did the security aspect of GSM become so bad? Once again, the answer to these questions can be traced back down to the security theory accepted at the time. Much like digital technology, secret algorithms were the wave of the future – and this is what the GSM designers had accepted. However, digital technology was an overwhelming success while security theory became gutted and revamped. The digital aspects of GSM – the service and functionality of the network – are still boasting 70% of wireless users worldwide. At the same time, the “security by obscurity” theory has become completely discredited. GSM was becoming the security laughing stock of the wireless industry and it was time to get an upgrade.
KASUMI and MILENAGE
After the Shamir
and Biryukov experiment, GSM finally received the security updates it so
desperately needed. Gone were the days
of "security by obscurity” and a new era of open discussion was born. Encryption algorithms were often published
and then scrutinized by the academic community with the hope that any fallacies
would be discovered before the algorithms were put to use. The 3rd Generation Partnership
Project (3GPP) was founded in 1998 for this purpose. In fact, the new algorithms GSM has adopted are a direct result
of the 3GPP.
The KASUMI algorithm was chosen to be the replacement for A5. KASUMI is a block ciphering algorithm that uses a 128 bit key and generates a 64 bit output stream from a 64 bit input stream. 10 KASUMI is essentially a Feistel Cipher with eight rounds. The 3GPP performed extensive analysis on KASUMI, including linear cryptanalysis, differential cryptanalysis, higher order differential cryptanalysis, and weak key searches. The 3GPP Report on KASUMI states that no weak keys were discovered and no practical attacks could be found that can break KASUMI at its full eight round implementation. 10 As for the foreseeable future in computer technology, it will be quite some time before a desktop PC will doom KASUMI to share A5’s fate.
With the advent of 3GPP, and GSM’s adoption of the KASUMI algorithm for voice encryption, the A3 algorithm for authentication has also been updated. Today, GSM uses the 3GPP algorithm known as MILENAGE – which is a variant of AES, or Rijndael. MILENAGE was chosen for its time-tested strength, its ability to run very fast on the chipsets present in cell phones, and its low memory usage. 10 MILENAGE is also public and can be downloaded from many websites across the net (i.e., www.securityfocus.com). Thanks to MILENAGE, cloning GSM phones has now been relinquished to the past – an incredibly important step in reclaiming the public’s trust.
Wrap Up
In retrospect, one of the main weaknesses of GSM was the security aspect. For a standard being used by millions of customers around the world, an update to the encryption algorithms being used was crucial. Since GSM is now utilizing an improved security ideology – published encryption algorithms with a basis is solid security theory – GSM has reinforced its position as the most widely used digital wireless standard in the world today.
[1] http://www.wirelessweek.com/index.asp?layout=story&doc_id=26255&verticalID=2
[2] Threats and Countermeasures in Wireless Networking by Sean Wang, December 20, 2000.
[3] http://www.brookson.com/gsm/gsmdoc.htm
[4] http://www.isaac.cs.berkeley.edu/isaac/gsm.html
[5] http://ccnga.uwaterloo.ca/~jscouria/GSM/gsmreport.html
[6] http://news.zdnet.co.uk/story/0,,t269-s2075699,00.html
[7] http://www.usatoday.com/life/cyber/tech/ctg848.htm
[8] http://cryptome.org/a51-bsw.htm
[9] http://www.counterpane.com/crypto-gram-9912.html
[10] http://www.research.att.com/~janos/3gpp.html
[11] http://www.iol.ie/~kooltek/gsmpaper.html
[12] Security in Computing, Charles P. Pfleeger, Prentice Hall, 2000