Algorithms in Motion: Security in GSM Systems

The Global System for Mobile Communications, or GSM, began in 1984 when Europe decided it needed a technology to unite the then-regionalized mobile phone systems. Since then, it has risen to claim dominance over cellular networks the world over. The GSM system, though it remains effective against common threats through a well-designed security barrier, after more than twenty years in service, is beginning to show its age.

The success of the GSM system ironically leads to its chief security concerns. The GSM is considered “the second generation (2G) mobile phone system and made mobile communications accessible for the mass market” (Gendrullis, 2008, p. 1). Despite its prevalence and commercial success, “[t]he GSM system has several security-related issues” (Bocan & Cretu, 2006, p. 19). The introduction of the mass market to the wireless communications industry led to many potential hackers gaining a predatory influence on it. With a user base over one billion strong, “GSM is a potential target for several kinds of attacks. The easiest to mount are the low tech attacks, such as call forwarding to premium numbers (depending on the network operator), bogus registration details, roaming fraud and terminal theft” (Bocan & Cretu, 2006, p. 19). The consumer is, of course, very interested in the security features of any wireless communications device “since users are likely to put personal, important or mission-critical data over an infrastructure that is not truly secure. The security weaknesses stem from both using multiple incompatible security schemes and design flaws in security protocols, which [are] inherent” (Bocan & Cretu, 2004, p. 18). The issue at the core of these inherent flaws in the security of wireless communication is the simple nature of radio communication. Bocan and Cretu write, “An attacker may never attempt to attack a strong cryptographic system instead will choose the weakest link in the telecommunication chain. That link is the radio domain” (2006, p. 18). As radio signals are ultimately at the mercy of their environment, this environment is usually where an attacker is likely to begin an attack.

Radio waves are a natural part of the electromagnetic spectrum and have been effectively harnessed for communication for more than a century. Radio communication begins with its own inherent set of risks in the possibility of interference. By the nature of the way radio waves interact with their environment, when a cellular device receives a message, the data “may have been exposed to a combination of various propagation phenomena such as free space attenuation, diffraction, reflection and other propagation effects before the mobile station receives it” (Halonen, Romero & Melero, 2004, p. 149). As a radio wave travels across space, it loses power, a phenomenon “caused by the fact that the signal is transmitted not only in a straight line but as a sphere, whose radius is the separation between the transmitter and the receiver. There is less power on the same piece of surface of a larger sphere than on a smaller sphere” (Halonen et al., 2004, p. 149) The signal can be perverted further as it travels, as “there are also losses in power due to reflection, diffraction around structures and refraction within them.” As a result of this loss of power, a cellular signal is weaker the farther away it is from an antenna, resulting in path loss. (Halonen et al., 2004, p. 149). Beyond the possibility of natural interference, the open and free nature of radio signals allows virtually anyone with the proper equipment to intercept data.

However, security in the GSM system has always been one of its chief selling points. To the end of preventing abuse of the system by unsubscribed users and pirate devices, “the security architecture of GSM was developed by the Security Expert Group (SEG) founded in 1984” (Gendrullis, 2008, p. 8). Working with the resources at hand, SEG had its work cut out for them with the issue innate to the radio medium. When dealing with the inherent issues of radio, “radio engineers are almost never security experts and the general tendency is to consider that security will be added later, if required. This is a very unhealthy way of thinking since security must be ‘blended’ together with the radio technology” (Bocan & Cretu, 2004, p. 1). If any degree of security is to be effectively created, “the security strategy must be applied end-to-end, i.e. from source to destination regardless of path. For example, WAP provides security using WTSL (Wireless Transport Security Layer), but this is not necessarily end-to-end security since encryption takes place only between the mobile device and the WAP gateway” (Bocan & Cretu, 2006, p. 19). The GSM system applies many methods to ensure the security of its users and operators. Upon its initial development, the GSM security system “was considered superior to other mobile communication systems... Another great enhancement over traditional mobile systems was the introduction of the SIM (Subscriber Indentifier Module) card which clearly separated the mobile device from the subscriber” (Bocan & Cretu, 2006, p. 19). When used domestically, the security system of the GSM architecture “proves far better than the analog cellular systems. The use of authentication, encryption and temporary identification numbers ensures the privacy and anonymity of users as well as preventing fraudulent use. Even GSM systems with the A5/2 encryption algorithm or with no encryption are inherently more secure than analog systems” (Bocan & Cretu, 2006, p. 20). When the mobile equipment sends a message, the data goes through “a multi-carrier, time-division multiple access and frequency division duplex, MC/TDMA/FDD” (Halonen et al., 2004, p. 144). This system of connections allows for a multiply-layered blanket of security, and has earned the confidence of consumers everywhere.

As previously stated, the radio domain is the greatest weak spot of any current wireless communication system. The GSM is not an exception, and the system is inherently vulnerable “to denial of service attacks as scarce resources such as signaling channels are blindly granted to anyone who requests them. Flooding the signaling channels with rogue or legitimate requests essentially means that the traffic channel is paralyzed. The flood on the signaling channel may be caused by a misbehaving mobile station or by genuine requests” (Bocan & Cretu, 2006, p. 21). There are several forms of denial of service attacks, “of which the most common are causing the network not to transmit messages it should be sending in order to provide a service to legitimate clients or causing the network to send messages it should not” (Bocan & Cretu, 2006, p. 23). The very nature of the security system between the SIM card and the tower is that the latter must always interact with the former before authentication, and “the network commits valuable resources to not-yet-authenticated clients. As such, the network cannot distinguish legitimate traffic from the rogue traffic and there isn’t much that can be done” (Bocan & Cretu, 2006, p. 23). Cellular service providers counter this through actively monitoring the system’s activity. Bocan and Cretu write, “Fraud management systems monitor a variety of indicators, such as multiple calls at the same time, large variations in revenue paid to other parties, large variations in duration of calls (very short or very long), changes in customer usage (indicating that a mobile has been stolen or is being abused) and closely monitoring customer during a probationary period” (2006, p. 19). By these means, the cellular provider is able to identify and eliminate devices that are simply being used to harass and interfere with the functioning of proper and legitimate equipment working within the GSM system.

But beyond denial of service attacks are attacks through which hackers gain an active influence within the system rather than just negating the system’s potential for use. An early line of defense against pirate devices gaining access to the system takes the form of “a simple challenge-response algorithm... The GSM Authentication Center (AuC) generates a random 128-bit number and sends it to the mobile station via radio link. This number and the subscriber key (Ki) are fed to the A3 algorithm which produces a signed response (SRES) which is in turn sent back to the AuC” (Bocan & Cretu, 2006, p. 19). This is the exchange of data that allows previously-described denial of service attacks, by exploiting the initial, unauthenticated phase, to seriously disrupt the functioning of a network’s access point. The protocol effectively negates the influence of pirate devices as follows: “If a subscriber wants to be authenticated by an operator he first has to identify himself with the help of his IMSI. Afterwards, the operator sends him a 128 bit random number RAND (i.e., the challenge) which he has to respond to with a 32 bit signed response SRES” (Gendrullis, 2008, p. 9-10). By the time the message reaches the AuC, “AuC has already computed its own SRES based on the same inputs and it is now capable of deciding whether the mobile station is who it says it is” (Bocan & Cretu, 2006, p. 19). The response received from the device (SRES) “is then compared to the expected response XRES already known by the operator. If the two values match the subscriber is authenticated” (Gendrullis, 2008, p. 9-10). It is through this exchange of numeric keys that false devices are denied entry into the system and perhaps future service. The system that regulates and polices access to the GSM as a whole is the “equipment identity register (EIR) in which known international mobile equipment identity (IMEI) numbers are stored. If a mobile radio station is reported to be stolen its IMEI number can be added to a black list in the EIR and, thus, the equipment will be suspended” (Gendrullis, 2008, p. 8). The interdependent layering of the system allows the system to catch and neutralize devices.

The elusive key to the whole system lies in a series of algorithms entrusted to process and encrypt data sent through the wireless network with the intention of rendering it illegible to any that might intercept the message without the proper means to decode it. When GSM is processing a conversation, the conversation is “sent as a sequence of frames ever 4.6 millisecond. Each frame contains 114 bits representing the digitized A to B communication, and 114 bits representing the digitized B to A communication” (Biryukov, Shamir, & Wagner, 2000, p. 2). Every frame must be encrypted to protect the system from infiltration. Bocan and Cretu write, “The A3 (authentication) and A8 (key generation) algorithms are operator specific and they are best kept secrets. It is well known the fact that a secret authentication or encryption algorithm may be vulnerable since it does not benefit from the experience of the cryptanalytic community who may try to uncover flaws and errors in design” (2006, 19). Despite a lack of community input, the system is still used. When an engineer is designing or applying cryptographic algorithms, the “natural question that comes is how long should the key be” (Bocan & Cretu, 2006, p. 20)? The designers of the GSM system based the security architecture “on symmetric cryptography with a long-term secret. Most precisely, the long-term secret is a 128 bit secret key (Ki) which is uniquely determined for each subscriber. Only the subscriber and his home operator are in possession of this secret” (Gendrullis, 2008, p. 9). This secret resides in the user’s SIM card safely tucked away into his or her wireless device. Gendrullis writes, “Ki is stored in the SIM used in an MS on the subscriber side and only in the AuC of the home operator on the provider side. It is then used in a challenge/response protocol to authenticate the subscriber” (2008, p. 9-10). The barrier between the message and its potential interceptor is the A5 algorithm. The A5 algorithm serves to encrypt data transmitted between a mobile device and the tower. The algorithm codes the information at “two frames at a time (2 x 114 bits), one for uplink and the other one for downlink. In the initial design (called A5/1), the session key K is mixed with the frame counter to initialize a set of 3 registers that will produce the 228 bit output by XORing the LFSR with the plaintext” (Bocan & Cretu, 2006, p. 20). Despite long years of faithful service, the A5 algorithm is still vulnerable to attack.

Cyberattacks come in many forms, but in order to crack an encryption, one must have the cipher. If one seeks to crack a cipher, it comes through time, effort, frequent guesswork, and the right equipment. The two main types of computers cryptanalysts use to cut through an encryption are “generic all-purposes workstations, and specialized hardware devices” (Pornin & Stern, 2000, p. 318). When it comes to the A5 encryption, if an observer were to “consider the key length as the only cybersecurity factor, it is interesting to see how long it would take to decrypt a message with a given key length, assuming a cracking machine capable of 1 million encryptions per second. The time required to break a 128 key is extremely large” (Bocan & Cretu, 2004, p. 3). The machine would require 10.8 x 10^24 years of guesswork for such a machine to crack the algorithm (Bocan & Cretu, 2004, p. 4) In such time, the natural processes of entropy would surely destroy the cracking machine before it could come close to a conclusion, rendering the device utterly useless on its own in cracking the A5 encryption. The A5/1 can so confound the device because it “uses a very small amount of silicium when implemented in hardware. It includes three LFSR, with a clocking sequence depending on the internal state of the three registers. It outputs a stream of bits that is combined (by mean of an exclusive or) with the data to encipher” (Pornin & Stern, 2000, p. 319). The data then goes through series of processes to mask the data. Pornin and Stern continue, “The three LFSR are of length 19, 22 and 23 bits. At each clock cycle, a majority bit is calculated, from the three middle bits of the registers; those registers which middle bit agrees with the majority are shifted. Then the output bit is the exclusive or of the three final bits of the registers” (2000, p. 319). After this step, the cipher is applied, effectively encrypting the data. The final step commences, during which “[t]he internal state is loaded with a 64-bit session key and a 22-bit known counter; the cipher is then ran for 100 cycles and the corresponding output bits discarded, and then 228 bits are produced for enciphering the data. Then the cipher is reset, with the same key and the next counter value” (Pornin & Stern, 2000, p. 319-320). Thusly progresses the A5/1 algorithm, impervious to countless eons of mechanical code analysis.

The algorithm is by no means foolproof, however. When one considers human agency in the process of data infiltration, “[t]he key can easily be recovered from the internal state at any moment with a critical branching process… therefore, once one internal state of A5/1 has been revealed the cryptanalysis is considered complete, since the same session key is used throughout the entire phone conversation” (Pornin & Stern, 2000, p. 319-320). When scientists reverse engineered the ciphers, they “started cryptanalyzing them and found several cryptographic weaknesses. Despite this fact, both ciphers are still used for encrypting GSM traffic and, thus, to provide confidentiality” (Gendrullis, 2008, p. 1). Cryptanalysis of the algorithm began in the nineties. An early cryptanalysis of A5/1 was “informally presented by Ross Anderson, who published in 1994 an alleged description of A5/1 (which turned out to be mostly correct, except for the position of bits for clocking and linear feedback)” (Pornin & Stern, 2000, p. 320).

“The idea is to guess the two first registers, and half of the third register, which is basically enough to know the clocking sequence and deduce the second half of the third register by solving a system of linear equations. This attack is applicable to the real A5/1, with a workload of about 2^52 guesses (each implying the resolution of a system of a dozen linear equations)” (Pornin & Stern, 2000, p. 320). After this defeat, further humiliation came when “[t]he simple design of A5/1 eventually proved insecure and it was broken around April 1998 by Ian Goldberg and David Wagner who also succeeded to break the A5/2 algorithm in as few as 5 clock cycles. This is very uncomfortable for anyone who uses the GSM infrastructure for private communication” (Bocan & Cretu, 2006, p. 20). Though the GSM remains effective against a low-tech attack, a party of sufficient resources and skill is capable of hacking through its defense algorithm.

Despite its flaws, the mechanisms of the GSM system are very complex. The burden of security provided by an older standard system in an evolving world make “Cryptographic and authentication mechanisms… very difficult to upgrade” (Bocan & Cretu, 2006, p. 19). On top of this, there are design flaws to be exploited by the adventurous hacker. Despite its defenses against false subscribers, “GSM intrastructure does not address active attacks, such as identity cashing, camping on a false BTS, eavesdropping, etc.” (Bocan & Cretu, 2006, p. 19). There is also a security issue whenever GMS connects to a fixed network. By the nature of a fixed network, “[c]ommunication and signaling traffic are not protected when connected to fixed networks, therefore the GSM network is only as secure as the fixed network to which it connects” (Bocan & Cretu, 2006, p. 19). To add to an eroding security base, the user of a mobile device has no indication of how secure her connection is before she sends data (Bocan & Cretu, 2006, p. 19). The GSM system has existed for more than two decades, a long time in terms of modern technology, and is perhaps nearing the end of its lifecycle.

Despite the GMS’ long and faithful service continues to provide cellular reception across the world, the nature of technological advancement has perhaps outpaced the power of old technology. Its encryptions can be effectively cryptanalyzed, and it remains vulnerable to a variety of breaches of security. As the technological world advances, the time to abandon this faithful courier of data will certainly come.

References

Biryukov, A., Shamir, A., & Wagner, D. (2000). Real Time Cryptanalysis of A5/1 on a PC. Fast Software Encryption, (2001) New York: 7th Internation Workshop, 1-18. Retrieved from http://link.springer.com/chapter/10.1007/3-540-44706-7_1

Bocan, V. & Cretu, V. (2004). Security and Denial of Service Threats in GSM Networks. Periodica Politechnica, (2004), Vol. 49, 1-6. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.690&rep=rep1&type=pdf

Bocan, V. & Cretu, V. (2006). Threats and Countermeasures in GSM Networks. Journal of Networks, (2006) N.p. Retrieved from http://ojs.academypublisher.com/index.php/jnw/article/view/010618/655

Gendrullis, T. (2008). Hardware-Based Cryptanalysis of the GSM A5/1 Encryption Algorithm. N.p. Retrieved from http://www.emsec.rub.de/media/crypto/attachments/files/2010/04/da_gendrullis.pdf

Halonen, T., Melero, J., Romero, J., Wigard, J. (Eds). (2004). Basics of GSM Radio Communication and Spectral Efficiency. GSM, GPRS and EDGE Performance. West Sussex, England: John Wiley & Sons Ltd. Retrieved from http://books.google.com/books?id=cgAroFIOyZIC&printsec=frontcover&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false

Pornin, T., & Stern, J. (2000). Software-Hardware Trade-Offs: Application to A5/1 Cryptanalysis. Cryptographic Hardware and Embedded Systems – CHES 2000, (2000) Worcester: Second International Workshop, 318-327. Retrieved from http://link.springer.com/chapter/10.1007/3-540-44499-8_25