An Experimental Security Analysis of Two Satphone Standards

An Experimental Security Analysis of Two Satphone Standards
Ikkita Satfon standartlarining eksperimental xavfsizlik tahlili
General purpose communication systems such as GSM and UMTS have been in the focus of security
researchers for over a decade now. Recently also technologies that are only used under more specific circum- stances have come into the spotlight of academic research and the hacker scene alike. A striking example of this is recent work [Driessen et al. 2012] that analyzed the security of the over-the-air encryption in the two existing ETSI satphone standards GMR-1 and GMR-2. The firmware of handheld devices was reverse- engineered and the previously unknown stream ciphers A5-GMR-1 and A5-GMR-2 were recovered. In a second step, both ciphers were cryptanalized, resulting in a ciphertext-only attack on A5-GMR-1 and a known-plaintext attack on A5-GMR-2.
Системы связи общего назначения, такие как GSM и UMTS, находятся в центре внимания безопасности.
исследователей уже более десяти лет. В последнее время в центре внимания как академических исследований, так и хакерской сцены оказались технологии, которые используются только при более специфических обстоятельствах. Ярким примером этого является недавняя работа [Driessen et al. 2012], в котором анализировалась безопасность беспроводного шифрования в двух существующих стандартах спутниковых телефонов ETSI GMR-1 и GMR-2. Прошивка портативных устройств была реконструирована, и были восстановлены ранее неизвестные потоковые шифры A5-GMR-1 и A5-GMR-2. На втором этапе оба шифра были криптоанализированы, что привело к атаке только зашифрованным текстом на A5-GMR-1 и атаке с известным открытым текстом на A5-GMR-2.
GSM va UMTS kabi umumiy maqsadli aloqa tizimlari xavfsizlikning diqqat markazida bo'ldi
o'n yildan ortiq tadqiqotchilar. Yaqinda, shuningdek, faqat aniqroq sharoitlarda qo'llaniladigan texnologiyalar akademik tadqiqotlar va xakerlar sahnasining diqqat markazida bo'ldi. Buning yorqin misoli so'nggi ishdir [Driessen va boshqalar. 2012] mavjud ikkita ETSI satphone standartlari GMR-1 va GMR-2da havodan shifrlash xavfsizligini tahlil qildi. Portativ qurilmalarning dasturiy ta'minoti teskari muhandislikdan o'tkazildi va ilgari noma'lum bo'lgan A5-GMR-1 va A5-GMR-2 oqim shifrlari qayta tiklandi. Ikkinchi bosqichda ikkala shifr ham kriptotanallashtirildi, natijada A5-GMR-1-ga faqat shifrlangan matn hujumi va A5-GMR-2-ga ma'lum ochiq matnli hujum sodir bo'ldi.
In this work, we extend the afore-mentioned results in the following ways: First, we improve the proposed attack on A5-GMR-1 and reduce its average case complexity from 232 to 221 steps. Second, we implement a practical attack to successfully record communications in the Thuraya network and show that it can be done with moderate effort for approx. $5 000. We describe the implementation of our modified attack and the crucial aspects to make it practical. Using our eavesdropping setup, we recorded 30 seconds of our own satellite-to-satphone communication and show that we are able to recover Thuraya session keys in half an hour (on average). We supplement these results with experiments designed to highlight the feasibility of also eavesdropping on the satphone’s emanations.
Ushbu ishda biz yuqorida aytib o'tilgan natijalarni quyidagi yo'llar bilan kengaytiramiz: Birinchidan, biz A5-GMR-1 ga taklif qilingan hujumni yaxshilaymiz va uning o'rtacha ish murakkabligini 232 dan 221 bosqichga qisqartiramiz. Ikkinchidan, biz Thuraya tarmog'ida kommunikatsiyalarni muvaffaqiyatli qayd etish uchun amaliy hujumni amalga oshiramiz va uni taxminan o'rtacha harakat bilan amalga oshirish mumkinligini ko'rsatamiz. $5 000. Biz o'zgartirilgan hujumimizni amalga oshirish va uni amaliy qilish uchun muhim jihatlarni tasvirlaymiz. Tinglash sozlamalarimizdan foydalanib, biz o'zimizning sun'iy yo'ldoshdan sun'iy yo'ldoshga 30 soniyalik aloqani yozib oldik va biz Thuraya seans kalitlarini yarim soat ichida (o'rtacha) qayta tiklashimiz mumkinligini ko'rsatdik. Biz ushbu natijalarni satfonning emanatsiyalarini tinglash imkoniyatini ta'kidlash uchun mo'ljallangan tajribalar bilan to'ldiramiz.
The purpose of this paper is threefold: Develop and demonstrate more practical attacks on A5-GMR-1, summarize current research results in the field of GMR-1 and GMR-2 security, and shed light on the amount of work and expertise it takes from setting out to analyze a complex system to actually break it in the real world.
Ushbu maqolaning maqsadi uchtadir: A5-GMR-1 ga ko'proq amaliy hujumlarni ishlab chiqish va namoyish qilish, GMR-1 va GMR-2 xavfsizligi sohasidagi joriy tadqiqot natijalarini umumlashtirish va unga kerak bo'lgan ish va tajriba miqdorini yoritish. murakkab tizimni haqiqiy dunyoda sindirish uchun tahlil qilishni boshlashdan.
Additional Key Words and Phrases: Mobile Security; Satellite Phone Systems; Cryptanalysis; Binary Anal- ysis; Real-world Attack; Stream Cipher
Qo'shimcha kalit so'zlar va iboralar: Mobil xavfsizlik; Sun'iy yo'ldosh telefon tizimlari; Kriptanaliz; Ikkilik tahlil; Haqiqiy dunyo hujumi; Oqim shifrlash
ACM Reference Format:
Driessen, B., Hund, R., Willems, R., Paar, C., Holz, T.. 2012. An Experimental Security Analysis of Two Satphone Standards. ACM Trans. Info. Syst. Sec. 16, 3, Article 10 (November 2013), 30 pages.
DOI = 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000

1. 
   INTRODUCTION
   

1.KIRISH
Mobile communication systems have revolutionized the way we interact with each other. Instead of depending on landline connections with fixed locations, we can talk to other people wherever we are and also transmit data from (almost) arbitrary locations.
Системы мобильной связи произвели революцию в том, как мы взаимодействуем друг с другом. Вместо того, чтобы зависеть от стационарных соединений с фиксированными местоположениями, мы можем разговаривать с другими людьми, где бы мы ни находились, а также передавать данные из (почти) произвольных мест.
Mobil aloqa tizimlari bizning bir-birimiz bilan o'zaro munosabatlarimizni inqilob qildi. Ruxsat etilgan joylar bilan statsionar aloqalarga bog'liq bo'lish o'rniga, biz qayerda bo'lishimizdan qat'iy nazar, boshqa odamlar bilan gaplashishimiz va (deyarli) o'zboshimchalik bilan ma'lumotlarni uzatishimiz mumkin.
Especially the Global System for Mobile Communications (GSM) has evolved into an
extremely large-scale system; with more than four billion subscribers in 2011, it is the
most widely deployed standard for cellular networks. Many other cellular network
standards like Universal Mobile Telecommunications System (UMTS), CDMA2000 (also known as IMT Multi-Carrier (IMT-MC)), or 3GPP Long Term Evolution (LTE)
exist and are continuously enhanced to meet growing customer demands.
В частности, Глобальная система мобильной связи (GSM) превратилась в
чрезвычайно масштабная система; с более чем четырьмя миллиардами подписчиков в 2011 году, это наиболее широко распространенный стандарт для сотовых сетей. Многие другие сотовые сети
такие стандарты, как Универсальная система мобильной связи (UMTS), CDMA2000 (также известная как IMT Multi-Carrier (IMT-MC)) или 3GPP Long Term Evolution (LTE)
существуют и постоянно совершенствуются для удовлетворения растущих потребностей клиентов.
Ayniqsa, Mobil Aloqa uchun Global Tizim (GSM) ga aylandi
juda keng ko'lamli tizim; 2011 yilda to'rt milliarddan ortiq obunachilarga ega
uyali tarmoqlar uchun eng keng tarqalgan standart. Boshqa ko'plab uyali aloqa tarmoqlari
Universal Mobile Telecommunications System (UMTS), CDMA2000 (shuningdek, IMT Multi-Carrier (IMT-MC) deb nomlanuvchi) yoki 3GPP Long Term Evolution (LTE) kabi standartlar
mavjud va mijozlarning ortib borayotgan talablarini qondirish uchun doimiy ravishda takomillashtirilmoqda.
Cellular mobile networks require a so-called cell site to create a cell within the net- work. The cell site provides all the infrastructure necessary for exchanging radio sig- nals between mobile handsets and the provider network. For example, a typical cell site contains one or more sets of transmitters/receivers, antennas, digital signal pro- cessors to perform all computations, a GPS receiver for timing and other control elec- tronics. The cells within a network have only a limited operating distance and, thus, a certain proximity to a cell site is always necessary to establish a connection to the mobile network.
In practice, however, it is not always possible to be close to a cell site and there are many use cases in which no coverage is provided. Workers on an oil rig or on board of a ship, researchers on a field trip in a desert or near the poles, aid workers in remote areas or areas that are affected by a natural disaster, journalists working in politically unstable areas, or certain military and governmental undertakings are a few of many uses cases where terrestrial cellular networks are not available. To overcome this lim- itation, satellite systems were introduced that provide telephony and data services based on telecommunications satellites. In such systems, the mobile handset (typically called satphone) communicates directly with satellites in orbit. Thus, coverage can be provided without the need of a highly interconnected infrastructure on the Earth’s surface.
There are two major satphone protocol families, standardized by the European Telecommunications Standards Institute (ETSI), that were both developed in the past few years:
— Geostationary Earth Orbit (GEO) Mobile Radio Interface (better known as GMR-1)
is a family of ETSI standards that were derived from the terrestrial cellular stan- dard GSM. In fact, the specifications of GMR are an extension of the GSM stan- dard, where certain aspects of the specification are adjusted for satphone settings.
This protocol family is supported by several providers (e.g., Thuraya, SkyTerra, TerreStar) and has continuously undergone several revisions to support a broader range of services. — The GMR-2 family is even closer to GSM. It deviates from the GMR-1 specifications in numerous ways, most notably the network architecture is different.
The specification documents of GMR-1 and GMR-2 are available online, but do not provide any information about implementation details of security aspects. More pre- cisely, it was not publicly known which encryption algorithms are actually used to secure the communication channels between a satphone and a satellite. Since an at- tacker can easily eavesdrop on the radio signals between satphone and satellite, even at some distance, it is obvious that weak encryption would be a serious threat to confi- dentiality. At this point, it was thus unclear what effort would be needed by an attacker to actually intercept telephony and data services for common satphone systems.
In this paper, we build on our previous work [Driessen et al. 2012], which reverse- engineered the stream ciphers A5-GMR-1 and A5-GMR-2, used in the respective stan- dards. In contrast to the original publication, we focus less on the process of reverse- engineering itself, but rather collect all relevant information regarding security and configuration aspects of the system: We describe the network architecture of satellite telecommunication systems and, to some degree, how they operate on the physical and protocol level. We describe the architecture of the satphones themselves, the ciphers we found for GMR-1 and GMR-2 and our results of cryptanalyzing them. We improvethe complexity of attacking A5-GMR-1 by a factor of 211 due to targeting a different channel and exploiting the fact that frame numbers and initial states in A5-GMR-1 are linearly related. Latter property allows us to mount an attack that uses multi- ple speech data frames (instead of only one control channel frame), which leads to less guessing when the attack is performed. This considerable improvement enables us to mount an attack on the Thuraya network, for which we proceed to describe the hardware and software requirements for an actual attack. We discuss crucial aspects when implementing and executing an eavesdropping attack, experimentally establish the feasibility of direct uplink interception and ultimately show that GMR-1 privacy is practically non-existent.
Effectively, we thus demonstrate that current satphone systems are vulnerable to eavesdropping attacks; the results of this paper can be used to build an interceptor for satellite telecommunication systems.
2. BACKGROUND AND RELATED WORK
We now introduce the background information necessary to understand the basics of satellite telephone systems (with a focus on GMR-1), their security mechanisms and the architecture of the mobile handsets. More information about these topics can be found in the literature [Wright 1995; Matolak et al. 2002; ETSI 2001a; Maral and Bousquet 2009; Jim Geovedi and Raoul Chiesa 2011]. Furthermore, we discuss related work in this area.
2.1. Network Layout
Thuraya implements the GMR-1 standard and provides satellite telephony for most of Europe, the Middle East, North, Central and East Africa, Asia and Australia. To achieve this coverage, the network consists of two overlapping regions, each handled by a different satellite. Thuraya satellites are operating in Geosynchronous Orbit (GSO), where they do not stay on a position but follow a fixed movement pattern, typically an analemma. Currently, there are two operational1 satellites named Thuraya-2 and Thuraya-3. The former is relevant here, since it is centered on the Middle East and supplies most of Europe as well as a large portion of the African continent with con- nectivity, see
Figure 1.
Thuraya offers a diverse range of products for fixed installations, handhelds (i.e., satphones) and even solutions for the maritime environment. With the help of Thu- raya, voice, fax and IP-based data can be transmitted where “traditional” infrastruc- tures (e.g., GSM, UMTS, WLAN, etc.) are not available. In addition to the satellites, a set of terrestrial gateways and one primary gateway (located in Sharjah, United Arab Emirates) handle the entire network as depicted in Figure 2. Gateway stations pro- vide the connectivity to tethered networks, e.g., telephone calls to a landline are for- warded to the Public Switched Telephone Network (PSTN) and enable maintenance and configuration purposes. For this so-called ground segment, conventional wave- length (3.400 − 3.625 GHz and 6.425 − 6.725 GHz) signals are used. The user segment operates on L-band carriers assigned to spotbeams, which are Thuraya’s equivalent to cells in GSM (albeit covering far more area). In the L-band, the frequency band from 1.525 to 1.559 GHz is assigned for downlink (space-to-earth) communication while the uplink (earth-to-space transmissions) operates between 1.6265 and 1.6605 GHz. Up- link and downlink are divided into 1087 paired carrier frequencies with a spacing of 31.25 KHz.
Fig. 1. Network coverage of the Thuraya-2 satellite, [Peter 2013]

2.2. Channels

Just like in GSM, the Time Division Multiple Access (TDMA) time slot architecture is employed which partitions a carrier frequency into disjunct timeslots of a fixed length. Figure 3 shows how a TDMA frame (middle) is split into 24 timeslots (bot- tom) of 5/3 ms each. 16 TDMA frames are grouped together into one multiframe (top), which is 640 ms long. Furthermore, multiframes are consolidated into a superframe, of which 4 496 comprise a hyperframe. It should be noted that each TDMA frame has a
19-bit TDMA frame number; numbering starts at 0, the number is incremented with each new frame.
Several logical channels (called channels from now on) can share a carrier frequency by being mapped on different timeslots. Due to this architecture, a channel is uniquely determined by a frequency and a sequence of Timeslot Numbers (TN). There are dif- ferent types of channels, but all are either Traffic Channels (TCH) for voice, fax or IP- based data, or Control Channels (CCH). Data is sent over these channels in the form of frames (i.e., blocks of consecutive bits), that are encoded (cf. Section 2.3) by adding redundancy to protect against transmission failures. Frames are enumerated by their respective TDMA frame numbers, which we simply call frame numbers from now on.
For some channels, the encoded data is subsequently encrypted, see Section 2.3. The encoded (and encrypted) data is finally modulated before it is transmitted via the phone’s antenna. The encoding scheme differs from channel to channel and is depen- dent on the respective reliability requirements as defined in the various documents of the standard.
An Experimental Security Analysis of Two Satphone Standards

Fig. 2. Layout of the Thuraya network

Fig. 3. TDMA architecture of GMR-1 networks
Specific channels relevant for our attack are the Frequency Correction Channel (FCCH), the Common Control Channel (CCCH) and the Traffic Channel-3 (TCH3).
The FCCH is initially (e.g., after power up) used by the satphone to determine its rel- ative time and frequency error in order to synchronize with the satellite. The CCCH is used to send information to the phone when a new channel (e.g., TCH3) needs to beestablished2. These assignment messages contain an Absolute Radio-Frequency Chan- nel Number (ARFCN) and a TN, which is, as explained above, all that is required to use the channel. After TCH3 has been set up on the uplink and downlink, it can be used to transmit speech data.
In Section 5.1 we will go more into the process of translating ARFCNs into frequen- cies and how we can actually tune to the TCH3 channel.
2.3. Encoding and Encryption
As mentioned before, all data has to be encoded before it is sent to travel the distance of around 36 000 Km between ground and satellite.

Fig. 4. Generic encoding (and encryption) scheme for information in the GMR-1 system
Encoding always increases the size of the encoded data, thus adding redundancy which allows error detection and possibly correction. Figure 4 shows the multiple en- coding steps of which not all are always applied to data, depending on the channel it is sent on. The general encoding procedure is as follows:
Each channel uses the following sequence and order of operations:
— The information bits are encoded with a systematic block code, i.e., CRC, building words of information and parity bits;
— these information and parity bits are encoded with a convolutional code, building the coded bits;
— the coded bits are reordered and potentially interleaved over multi- ple bursts;
— the interleaved bits are scrambled and, in some cases, multiplexed with other bits (before or after encryption);
To protect against eavesdropping of data sent over the air, the encoded bits are en- crypted with a proprietary cipher. However, doing it the way it is done in GMR-1 leads to a property we exploit for our real-world attack (cf. Section 4.5).
Encryption in GMR-1 is enabled on a per-session basis, i.e., for the duration of one call a session key Kc is established (see Figure 5 for a sketch of the respective proto- col). This key is derived from a challenge RAND sent by the network and a long-term key Ki, known only to the satphone and network. In the specifications, the key deriva- tion algorithm is denoted as A8, which serves the same3 role as the A8 function in GSM. On the handheld side it is implemented on the phone’s SIM card, where also the corresponding long-term key is stored.
With the help of the session key, data can be encrypted with an algorithm denoted as A5 (shorthand for A5-GMR-1). This algorithm is a stream cipher that encrypts data

Fig. 5. Protocol for establishing a session key Kc between satphone and provider network
2.4. Satellite Telephone Architecture
We now briefly introduce the general architectural structure of satellite phones and the hardware typically found in such devices. In a later section, we provide more details on the specific phones we studied during our analysis, including a discussion of the actual hardware.
In general, the architecture of satellite phones is similar to the architecture of cel- lular phones [Welte 2010]. Both types of handsets have to perform a lot of processing of speech and signal data, thus they typically ship with a dedicated digital signal pro- cessor. Consequently, the afore mentioned, computationally intensive operations are done by the DSP. More relevant for our purpose are the facts that DSPs are also suit- able for executing cryptographic algorithms and that encryption is part of the encoding process, which makes DSP code a prime candidate for holding GMR cipher code.
Nevertheless, the core of a satphone is a standard microprocessor (usually an ARM- based CPU) that serves as the central control unit within the system. This CPU ini- tializes the DSP during the boot process. Furthermore, both processors share parts of the main memory or other peripheral devices to implement inter-processor communi- cation. To understand the flow of code and data on a phone, we thus needed to analyze the communication between the two processors.
The operating system running on the main CPU is typically a highly specialized system that is designed with respect to the special requirements of a phone system (e.g., limited resources, reliability, real-time constraints, etc.). All of the software is de- ployed as one large, statically linked firmware binary which typically contains ARM code mixed with DSP code. For our analysis, we were especially interested in the inter- processor communication functionality provided by the operating system as well as the DSP initialization routine. This is due to the fact that we needed to extract and trans- form the DSP code, as it is found in the firmware, into the format actually executed by the DSP.
2.5. Related Work
Satellite telecommunication systems are related to terrestrial cellular systems since the GMR standards are derived from the GSM standard. We can thus leverage work on the analysis of cellular systems for our security analysis as discussed in the fol- lowing. Briceno et al. published in 1999 an implementation of the GSM A5/1 and A5/2 algorithms, which they apparently obtained by reverse engineering a GSM hand- set [Briceno et al. 1999]. However, no details about the analysis process were ever published and it remains unclear how the algorithms were actually derived. Our anal- ysis is also based on actual implementations of the ciphers; we discuss the general approach in Section 3 and provide analysis details in later sections.
There has been much work on the security analysis of the ciphers used within GSM, e.g., [Golic 1997; Biham and Dunkelman 2000; Biryukov et al. 2000; Ekdahl and Jo- hansson 2003; Bogdanov et al. 2007; Nohl and Paget 2009; Dunkelman et al. 2010].
The cipher used in GMR-1 is related to the A5/2 algorithm, but the configuration of the cipher is different. Our attack on this algorithm builds on existing ideas for A5/2 [Petrovic and Fuster-Sabater 2000; Barkan et al. 2008], which we extended to enable a time-ciphertext trade-off.
3. GENERAL APPROACH
In this section, we outline the general methodology we used for identifying and ex- tracting encryption algorithms from satellite phones. Furthermore, we also discuss the assumptions that helped us during the reverse engineering phase.
We analyzed two representative phones that operate according the two different standards we are interested in. More precisely, we analyzed the firmwares of the fol- lowing two phones: — the Thuraya SO-2510 satphone that implements the GMR-1 specification — the Inmarsat IsatPhone Pro satphone that implements the GMR-2 specification The starting point of our analysis was the publicly available firmware upgrade of each of these two devices. The entire analysis was performed purely statically since we initially did not have a real satellite phone at our disposal that we could instrument to perform a dynamic analysis. Furthermore, we did not have access to a whole device simulator that enables debugging of arbitrary firmware image, thus we had to develop our own set of analysis tools. However, the ARM code for the main microprocessor (used by both phones) can be partially executed and debugged in a CPU emulator such as QEMU.
The approach we followed to analyze both satphones can be separated into the fol- lowing five phases: (1) Obtain the firmware update package and the respective update program (usually a Windows executable). (2) Extract the firmware image from the package. (3) Reconstruct the correct memory mappings of the code and data sections in the firmware image. (4) Identify the DSP initialization procedure in order to extract the DSP code/mapping. (5) Search for the encryption algorithms in the DSP code using specific heuristics as well as control and data flow analysis techniques.
Several steps can be automated, but some manual analysis is nevertheless required.
We successfully applied this method to the two phones we analyzed. In addition, we speculate that also other kinds of satphones can be analyzed in this way.
These basic assumptions helped us to find the relevant pieces of code in a shorter amount of time: (1) The length of the session key is known. (2) The length of the keystream, as generated by the cipher, is equal to the length of the encrypted frame. (3) Since the GMR standards are derived from GSM, the ciphers bear at least some resemblance to the well-known, LFSR-based A5 algorithms.
Actual lengths for first two assumptions can be derived from the publicly available parts of the GMR specifications [ETSI 2001b; 2001c]. These assumptions enabled us to decrease the search space of potential code. The last assumption is rather speculative, but helped us in finding one of the two algorithms (but did not hold for the second cipher).
4. SECURITY ANALYSIS OF GMR-1
We used the Thuraya SO-2510 phone as an example for a handset that operates ac- cording to the GMR-1 standard. This decision was solely driven by the fact that the firmware of this satphone is publicly available from the vendor’s website. In fact, we did not analyze any other GMR-1 satellite phone, but since the protocol is standardized we are confident that our analysis results apply to all other GMR-1 phones as well.
4.1. Hardware Architecture
The Thuraya SO-2510 runs on a Texas Instruments OMAP1510 platform. The core of the platform is an ARM-925 CPU along with a TI TMS320C5000 signal processor.
This information can be deduced from corresponding strings in the binary and from pictures of the actual components soldered on the circuit board [OsmocomGMR 2012].
Figure 6 provides a high-level overview of the architecture.
Both processors can communicate with each other using a special shared peripherals bus. Furthermore, they share the same RAM and can access additional memory (e.g., SRAM or Flash) on equal terms. Initially, DSP code or data has to be loaded by the ARM CPU into the specific memory regions of the DSP. The DSP code can be located in either the on-chip SARAM (which holds 96 Kb of memory) or in the SRAM, which is accessed through the memory interface controller (MIC). Writes to the SARAM re- gion of the DSP are especially interesting for extracting the corresponding DSP code.
The official OMAP1510 documents suggest pre-defined memory regions to be used by the ARM-MMU for mapping this memory area [Texas Instruments 2012]. During our analysis, we could confirm that the firmware uses exactly the same mappings.
4.2. Finding the Cipher
We were able to find the cipher A5-GMR-1 in the firmware of a Thuraya SO-2510 phone with the help of IDA Pro by ranking functions in the DSP code according to their percentage of XOR and SHIFT operations. The four topmost functions in this ranking turned out to implement the different linear feedback shift registers (LFSR) of the cipher . The interested reader is referred to the original publication [Driessen et al. 2012] for more details.
4.3. Structure of the Cipher
The cipher used in GMR-1 is a typical stream cipher. Its design is a modification of the A5/2 cipher [Petrovic and Fuster-Sabater 2000; Barkan et al. 2008], which is used


Fig. 6. The OMAP1510 platform [Texas Instruments 2012]
in GSM networks. Similar to A5/2, the cipher uses four LFSRs which are clocked ir- regularly. We call these LFSRs R1, R2, R3 and R4, see Figure 7 for a schematic of the structure.
Fig. 7. The A5-GMR-1 cipher

Comparing A5/2 and A5-GMR-1, we see that for most registers the feedback poly- nomials and also the selection of input taps for the non-linear majority-function M

Table I. Configuration of LFSRs in A5-GMR-1 and A5/2



with
M : {0, 1}3 7→ {0, 1}
(x2, x1, x0)2 7→ x2x1 ⊕ x2x0 ⊕ x0x1
were changed. Also, the positions of the bits that are XORed with the respective out- puts of the majority functions are different. All feedback-polynomials have five mono- mials, which is not the case for A5/2, as shown in Table I.
4.4. Mode of Operation
Next we focus on the mode of operation. Clocking a single LFSR means evaluating its respective feedback polynomial and using the resulting bit to overwrite the leftmost position of the LFSR, after shifting its current state by one bit to the right. When the cipher is clocked for the l-th time with irregular clocking active, the following happens: (1) The irregular clocking component C evaluates all taps of R4, the remaining registers are clocked accordingly, i.e., (a) Iff M(R4,1, R4,6, R4,15) = R4,15, register R1 is clocked. (b) Iff M(R4,1, R4,6, R4,15) = R4,6, register R2 is clocked. (c) Iff M(R4,1, R4,6, R4,15) = R4,1, register R3 is clocked. (2) The taps of R1, R2 and R3 are evaluated and one bit of keystream is output accord- ingly, i.e.,
zl =M(R1,1, R1,6, R1,15) ⊕ M(R2,3, R2,8, R2,14)⊕ M(R3,4, R4,15, R3,19) ⊕ R1,11 ⊕ R2,1 ⊕ R3,0
is generated. (3) R4 is clocked.
The cipher is operated in two modes, initialization and generation mode. Running the cipher in former mode includes setting the initial state of the cipher, which is done in the following way: (1) All four registers are set to zero. (2) A 64-bit initialization vector α = (α0, ..., α63) is computed by XORing the bits of the 19-bit frame number N and 64-bit session key K, i.e.,
α = F(K,N) = (K₀,K₁,K₂,K₃ ⊕ N₆,K₄ ⊕ N₇,
K₅ ⊕ N_8,K₆ ⊕ N₉,K₇ ⊕ N₁₀,
K₈ ⊕ N₁₁,K₉ ⊕ N₁₂,K₁₀ ⊕ N₁₃,
K₁₁ ⊕ N₁₄, K₁₂ ⊕ N₁₅,
K₁₃ ⊕ N₁₆, K₁₄ ⊕ N₁₇, K₁₅ ⊕ N₁₈,
K₁₆, K₁₇, ..., K₂₁, K₂₂ ⊕ N₄,
K₂₃ ⊕ N₅, K₂₄, ..., K₅₉, K₆₀ ⊕ N₀,
K₆₁ ⊕ N₁,K₆₂ ⊕ N₂,K₆₃ ⊕ N₃)
(3) The bits of α are re-ordered to α0 with
α₀ = (α₁₅, α₁₄, ..., α₀, α₃₁, α₃₀, ..., α₁₆, α₄₇, ..., α₃₂, α₆₃, ..., α₄₈)₂
and clocked into all four registers in this order. To clock one bit of α0 into R1, its feedback polynomial is evaluated and the resulting bit then clocked into R1, after XORing it with the α0 bit. The same bit of α0 is also clocked into R2, R3 and R4.
Then, the second bit of α0 is clocked into all four registers in this manner and so on.
While doing this, irregular clocking is deactivated, i.e., all registers are clocked for each bit of α’.
(4) The least-significant bits of all four registers are set to 1, i.e., R1,0 = R2,0 = R3,0 =
R4,0 = 1.
We denote the whole initialization process by

where β is a 81-bit string, comprised of the consecutive bits of the four initialized registers. After all registers are initialized, irregular clocking is activated and the cipher is clocked 250 times. The resulting output bits are discarded.
Now the cipher is switched into generation mode and clocked for 2 · m times, generating one bit of keystream at a time. Here, m is the length of an encrypted frame.
Depending on the direction 4 bit, either the first half or the second half of the 2 m keystream bits is used for encryption/decryption. We denote the l-th keystream bit by z_l^(N), where 0 ≤ l < 2 m is the number of irregular clockings (after warm-up) and N the frame number that was used for initialization. Since our cryptanalysis will focus on the downlink, we denote the continuous keystream for frames N, N + 1, ... (as decrypted by the phone) by z, where

is the concatenation of the first halves of z^(N), z^(N+1), … respectively. The choice of m depends on the type of channel for which data is encrypted or decrypted. For the TCH3 channel, each frame has a length of m = 208 bits.
4.5. Cryptanalysis
The attack we present in the following is a variant of the ciphertext-only attack orig- inally presented in [Driessen et al. 2012], which itself was inspired by previous at- tacks [Petrovic and Fuster-Sabater 2000; Barkan et al. 2003] on A5/2. Please note that we treat bit strings as column vectors and vice versa. We now briefly review the pro- posed attack that exploits several weaknesses which are either due to the design of the cipher or due to the use of the cipher in GMR-1: (1) Given R4, the clocking behavior of A5-GMR-1 is uniquely determined. (2) Since the inputs to each majority-component are only from one register, one bit of keystream can always be expressed as an easy to linearize quadratic equation over
GF(2).
(3) In GMR-1, encryption is applied after encoding (which is entirely linear in GF(2)) and scrambling5. (4) For each two keystreams generated by the same session key but different frame numbers, the respective initial states are linearly related by the XOR-differences of the frame numbers.
Due to the first and second observation and given enough keystream bits for a partic- ular frame N we can guess R4, clock the entire cipher for several times and generate a linearized system of equations over GF(2), i.e.,

describing keystream bits as linear combinations of terms which either are individual bits or products of two bits from the initial state of R1, R2 and R3. If we guess R4 correctly and A has full rank, solving the equation system gives the correct initial state which can easily be used to obtain the session key. Please note that, even if the session key is fixed, for different frame numbers not only the keystream but also the initial state and the matrix describing its relation to the keystream will be different. The required number of linearly independent equations, and hence the minimum6 number of known keystream bits, is denoted as v with

Here, the numbers 18, 21 and 22 are due to the sizes of registers R1, R2 and R3 respectively (one bit is subtracted due to the fixed 1 per LFSR, cf. Subsection 4.4). By k₁, k₂ and k₃ we denote the number of bits we may additionally guess for each of these LFSRs. Fixing variables helps to decrease the size of the equation systems and the number of required keystream bits, but also increases the average amount of bits to guess for the whole attack to 2^15+k1+k2+k3.
We now use the principle we have outlined above (and the fact that encryption is applied to encoded data) for a ciphertext-only attack which explicitly targets the TCH3 channel in GMR-1. Encoding, scrambling and encrypting a 160-bit speech-frame d(N) with frame number N can be expressed as


where Gt is the transpose of the 160×208 generator matrix G of the code, s is a 208-bit pseudo-random scrambling sequence, z^(N) the keystream generated for this frame and c^(N) the resulting 208-bit codeword. G and s can be derived from the specification of TCH3 (cf. Subsection 5.2), additionally a parity-check matrix H can be derived from G with H_c = 0 iff c = G^td. Due to this property, if we invert scrambling for a codeword c^(N), we get


Given a syndrome (i.e., a bit vector indicating whether decoding was completed without errors, potentially enabling error correction) vector r^(N) = H(c^(N) ⊕ s), we can, again, set up an equation system in variables x₀, x₁, ..., x_v−1 of the initial state by guessing R₄, clocking the cipher 250 times (to account for the warm-up phase) and another 208 times, i.e.,

Here, A is the 208 × v matrix that describes the linear relation between x and the bits z₀^(N), z₁^(N)…, z₂₀₀₇^(N)

generated by the cipher. Please note that H is a 48 × 208 matrix and subsequently S is a 48 × v matrix which implies that for v > 48 this system is not uniquely solvable. In order to obtain an equation system where S has full rank, we need to generate and collect equations from several encrypted frames for consecutive frame numbers N, N +1, .... For a fixed session key, the initial states for different frame numbers are linearly related by the XOR-differences of the frame numbers. Taking these differences into account when generating equations allows to build a uniquely solvable equation systems and solving this equation system gives a potential initial state which could have generated z^(N).
Now we describe the actual steps of our attack for which we assume that we are in possession of n 48-bit syndromes

which correspond to TCH3 downlink data encrypted under the same session key.

Our attack is parameterized by n, k₁, k₂, k₃ and N₀ and recovers the initial state β = G(K, N₀). Before we proceed, we need to introduce the helper-function V(·) which can be applied to extract certain bits of the 81-bit state of A5-GMR-1. Depending on the configuration of the attack, V(·) will extract a bitstring which corresponds to these positions of the overall state whose bits we have guessed (i.e., R₄ and parts of the other registers). (1) Systematically guess the bitstring γ which has 20 + k₁ + k₂ + k₃ bits (also incorpo- rating the fixed bit per LFSR). For each syndrome 0 ≤ i < n do the following: (a) Compute the
81-bit difference δ = G(0, N₀) ⊕ G(0, N_i) in the initialization state for frame number N₀ and N_i.
(b) Modify γ by XORing it with the corresponding positions of δ, i.e., γ0 = γ ⊕ V(δ).
(c) Based on γ’ and δ generate a linearized 458×v matrix B (and vector y for the one constant per equation) which describes the linear relation between the initial state for N₀ and the 458 keystream bits generated for r^(Ni). (d) Take the warm-up phase into account by discarding the first 250 rows of B to obtain a 208 × v matrix B’ and also discarding the first 250 elements of y to obtain y’.
(e) Compute the 48 × v matrix S’ and vector r’ such that

and add those rows of S’ (and the corresponding bits from r’) to the equation system S_x = r, which are linearly independent from all previously existing rows of S.

(f) Abort if S has full rank.
(2) Solve the equation system by computing x = S⁻¹r and combine the guessed bits and x appropriately to obtain the 81-bit initialization state candidate β.
(3) Initialize A5-GMR-1 with β and clock it to obtain 208 bits of keystream z’ ^(N0) for frame number N₀ and test whether

If this equation holds, applying the obtained keystream produced a valid codeword.

This implies we have produced the correct keystream and therefore (most likely) the correct initial state.
Once we have β = G(K, N₀), we can set up another equation system

where L describes the process of clocking α into all four LFSRs (and setting the lowest bit per LFSR to 1 which is expressed by э). Solving the equation system resolves the initialization vector α from which we can easily derive the session key K = F(α, N₀).