home *** CD-ROM | disk | FTP | other *** search
/ TAP YIPL / TAP_and_YIPL_Collection_CD.iso / PHREAK / CELLULAR / GSMSEC.TXT < prev    next >
Encoding:
Text File  |  2000-02-28  |  31.8 KB  |  631 lines

  1.                         GSM Security and Encryption
  2.  
  3.                  by David Margrave, George Mason University
  4.  
  5. 1.0 Introduction
  6.  
  7. The motivations for security in cellular telecommunications systems are to
  8. secure conversations and signaling data from interception as well as to
  9. prevent cellular telephone fraud. With the older analog-based cellular
  10. telephone systems such as the Advanced Mobile Phone System (AMPS) and the
  11. Total Access Communication System (TACS), it is a relatively simple matter
  12. for the radio hobbyist to intercept cellular telephone conversations with a
  13. police scanner. A well-publicized case involved a potentially embarrassing
  14. cellular telephone conversation with a member of the British royal family
  15. being recorded and released to the media. Another security consideration
  16. with cellular telecommunications systems involves identification
  17. credentials such as the Electronic Serial Number (ESN), which are
  18. transmitted "in the clear" in analog systems. With more complicated
  19. equipment, it is possible to receive the ESN and use it to commit cellular
  20. telephone fraud by "cloning" another cellular phone and placing calls with
  21. it. Estimates for cellular fraud in the U.S. in 1993 are as high as $500
  22. million. The procedure wherein the Mobile Station (MS) registers its
  23. location with the system is also vulnerable to interception and permits the
  24. subscriberÆs location to be monitored even when a call is not in progress,
  25. as evidenced by the recent highly-publicized police pursuit of a famous
  26. U.S. athlete.
  27.  
  28. The security and authentication mechanisms incorporated in GSM make it the
  29. most secure mobile communication standard currently available, particularly
  30. in comparison to the analog systems described above. Part of the enhanced
  31. security of GSM is due to the fact that it is a digital system utilizing a
  32. speech coding algorithm, Gaussian Minimum Shift Keying (GMSK) digital
  33. modulation, slow frequency hopping, and Time Division Multiple Access
  34. (TDMA) time slot architecture. To intercept and reconstruct this signal
  35. would require more highly specialized and expensive equipment than a police
  36. scanner to perform the reception, synchronization, and decoding of the
  37. signal. In addition, the authentication and encryption capabilities
  38. discussed in this paper ensure the security of GSM cellular telephone
  39. conversations and subscriber identification credentials against even the
  40. determined eavesdropper.
  41.  
  42. 2.0 Overview of GSM
  43.  
  44. GSM (group special mobile or general system for mobile communications) is
  45. the Pan-European standard for digital cellular communications. The Group
  46. Special Mobile was established in 1982 within the European Conference of
  47. Post and Telecommunication Administrations (CEPT). A Further important step
  48. in the history of GSM as a standard for a digital mobile cellular
  49. communications was the signing of a GSM Memorandum of Understanding (MoU)
  50. in 1987 in which 18 nations committed themselves to implement cellular
  51. networks based on the GSM specifications. In 1991 the first GSM based
  52. networks commenced operations. GSM provides enhanced features over older
  53. analog-based systems, which are summarized below:
  54.  
  55.    * Total Mobility: The subscriber has the advantage of a Pan-European
  56.      system allowing him to communicate from everywhere and to be called in
  57.      any area served by a GSM cellular network using the same assigned
  58.      telephone number, even outside his home location. The calling party
  59.      does not need to be informed about the called person's location
  60.      because the GSM networks are responsible for the location tasks. With
  61.      his personal chipcard he can use a telephone in a rental car, for
  62.      example, even outside his home location. This mobility feature is
  63.      preferred by many business people who constantly need to be in touch
  64.      with their headquarters.
  65.  
  66.    * High Capacity and Optimal Spectrum Allocation: The former analog-based
  67.      cellular networks had to combat capacity problems, particularly in
  68.      metropolitan areas. Through a more efficient utilization of the
  69.      assigned frequency bandwidth and smaller cell sizes, the GSM System is
  70.      capable of serving a greater number of subscribers. The optimal use of
  71.      the available spectrum is achieved through the application Frequency
  72.      Division Multiple Access (FDMA), Time Division Multiple Access (TDMA),
  73.      efficient half-rate and full-rate speech coding, and the Gaussian
  74.      Minimum Shift Keying (GMSK) modulation scheme.
  75.  
  76.    * Security: The security methods standardized for the GSM System make it
  77.      the most secure cellular telecommunications standard currently
  78.      available. Although the confidentiality of a call and anonymity of the
  79.      GSM subscriber is only guaranteed on the radio channel, this is a
  80.      major step in achieving end-to- end security. The subscriberÆs
  81.      anonymity is ensured through the use of temporary identification
  82.      numbers. The confidentiality of the communication itself on the radio
  83.      link is performed by the application of encryption algorithms and
  84.      frequency hopping which could only be realized using digital systems
  85.      and signaling.
  86.  
  87.    * Services: The list of services available to GSM subscribers typically
  88.      includes the following: voice communication, facsimile, voice mail,
  89.      short message transmission, data transmission and supplemental
  90.      services such as call forwarding.
  91.  
  92. 2.1 GSM Radio Channel
  93.  
  94. The GSM standard specifies the frequency bands of 890 to 915 MHz for the
  95. uplink band, and 935 to 960 MHz for the downlink band, with each band
  96. divided up into 200 kHz channels. Other features of the radio channel
  97. interface include adaptive time alignment, GMSK modulation, discontinuous
  98. transmission and reception, and slow frequency hopping. Adaptive time
  99. alignment enables the MS to correct its transmit timeslot for propagation
  100. delay. GMSK modulation provides the spectral efficiency and low out-of-band
  101. interference required in the GSM system. Discontinuous transmission and
  102. reception refers to the MS powering down during idle periods and serves the
  103. dual purpose of reducing co-channel interference and extending the portable
  104. unit's battery life. Slow frequency hopping is an additional feature of the
  105. GSM radio channel interface which helps to counter the effects of Rayleigh
  106. fading and co-channel interference.
  107.  
  108. 2.2 TDMA Frame Structures, Channel Types, and Burst Types
  109.  
  110. The 200 kHz channels in each band are further subdivided into 577 ms
  111. timeslots, with 8 timeslots comprising a TDMA frame of 4.6 ms. Either 26 or
  112. 51 TDMA frames are grouped into multiframes (120 or 235 ms), depending on
  113. whether the channel is for traffic or control data. Either 51 or 26 of the
  114. multiframes (again depending on the channel type) make up one superframe
  115. (6.12 s). A hyperframe is composed of 2048 superframes, for a total
  116. duration of 3 hours, 28 minutes, 53 seconds, and 760 ms. The TDMA frame
  117. structure has an associated 22-bit sequence number which uniquely
  118. identifies a TDMA frame within a given hyperframe. Figure 1 illustrates the
  119. various TDMA frame structures.
  120.  
  121.                                   [Image]
  122.  
  123.                        Figure 1 TDMA Frame Structures
  124.  
  125. The various logical channels which are mapped onto the TDMA frame structure
  126. may be grouped into traffic channels (TCHs) used to carry voice or user
  127. data, and control channels (CCHs) used to carry signaling and
  128. synchronization data. Control channels are further divided into broadcast
  129. control channels, common control channels, and dedicated control channels.
  130.  
  131. Each timeslot within a TDMA frame contains modulated data referred to as a
  132. "burst". There are five burst types (normal, frequency correction,
  133. synchronization, dummy, and access bursts), with the normal burst being
  134. discussed in detail here. The bit rate of the radio channel is 270.833
  135. kbit/sec, which corresponds to a timeslot duration of 156.25 bits. The
  136. normal burst is composed of a 3-bit start sequence, 116 bits of payload, a
  137. 26-bit training sequence used to help counter the effects of multipath
  138. interference, a 3-bit stop sequence required by the channel coder, and a
  139. guard period (8.25 bit durations) which is a "cushion" to allow for
  140. different arrival times of bursts in adjacent timeslots from geographically
  141. disperse MSs. Two bits from the 116-bit payload are used by the Fast
  142. Associated Control Channel (FACCH) to signal that a given burst has been
  143. borrowed, leaving a total of 114 bits of payload. Figure 2 illustrates the
  144. structure of the normal burst.
  145.  
  146.                                   [Image]
  147.  
  148.                       Figure 2 Normal Burst Structure
  149.  
  150. 2.3 Speech Coding, Channel Coding, and Interleaving
  151.  
  152. The speech coding algorithm used in GSM is based on a rectangular pulse
  153. excited linear predictive coder with long-term prediction (RPE-LTP). The
  154. speech coder produces samples at 20 ms intervals at a 13 kbps bit rate,
  155. producing 260 bits per sample or frame. These 260 bits are divided into 182
  156. class 1 and 78 class 2 bits based on a subjective evaluation of their
  157. sensitivity to bit errors, with the class 1 bits being the most sensitive.
  158. Channel coding involves the addition of parity check bits and half-rate
  159. convolutional coding of the 260-bit output of the speech coder. The output
  160. of the channel coder is a 456-bit frame, which is divided into eight 57-bit
  161. components and interleaved over eight consecutive 114-bit TDMA frames. Each
  162. TDMA frame correspondingly consists of two sets of 57 bits from two
  163. separate 456-bit channel coder frames. The result of channel coding and
  164. interleaving is to counter the effects of fading channel interference and
  165. other sources of bit errors.
  166.  
  167. 3.0 Overview of Cryptography
  168.  
  169. This section provides a brief overview of cryptography, with an emphasis on
  170. the features that appear in the GSM system.
  171.  
  172. 3.1 Symmetric Algorithms
  173.  
  174. Symmetric algorithms are algorithms in which the encryption and decryption
  175. use the same key. For example, if the plaintext is denoted by the variable
  176. P, the ciphertext by C, the encryption with key x by the function Ex( ),
  177. and the decryption with key x by Dx( ), then the symmetric algorithms are
  178. functionally described as follows:
  179.  
  180.   C=Ex(P)
  181.   P=Dx(C)
  182.   P=Dx(Ex(P))
  183.  
  184. For a good encryption algorithm, the security of the data rests with the
  185. security of the key, which introduces the problem of key management for
  186. symmetric algorithms. The most widely-known example of a symmetric
  187. algorithm is the Data Encryption Standard (DES). Symmetric encryption
  188. algorithms may be further divided into block ciphers and stream ciphers.
  189.  
  190. 3.1.1 Block Ciphers
  191.  
  192. As the name suggests, block ciphers encrypt or decrypt data in blocks or
  193. groups of bits. DES uses a 56-bit key and processes data in 64- bit blocks,
  194. producing 64-bits of encrypted data for 64-bits of input, and vice-versa.
  195. Block algorithms are further characterized by their mode of operation, such
  196. as electronic code book (ECB), cipher block chaining (CBC) and cipher
  197. feedback (CFB). CBC and CFB are examples of modes of operation where the
  198. encryption of successive blocks is dependent on the output of one or more
  199. previous encryptions. These modes are desirable because they break up the
  200. one-to-one correspondence between ciphertext blocks and plaintext blocks
  201. (as in ECB mode). Block ciphers may even be implemented as a component of a
  202. stream cipher.
  203.  
  204. 3.1.2 Stream Ciphers
  205.  
  206. Stream ciphers operate on a bit-by-bit basis, producing a single encrypted
  207. bit for a single plaintext bit. Stream ciphers are commonly implemented as
  208. the exclusive-or (XOR) of the data stream with the keystream. The security
  209. of a stream cipher is determined by the properties of the keystream. A
  210. completely random keystream would effectively implement an unbreakable
  211. one-time pad encryption, and a deterministic keystream with a short period
  212. would provide very little security.
  213.  
  214. Linear Feedback Shift Registers (LFSRs) are a key component of many stream
  215. ciphers. LFSRs are implemented as a shift register where the vacant bit
  216. created by the shifting is a function of the previous states. With the
  217. correct choice of feedback taps, LFSRs can function as pseudo-random number
  218. generators. The statistical properties of LFSRs, such as the
  219. autocorrelation function and power spectral density, make them useful for
  220. other applications such as pseudo-noise (PN) sequence generators in direct
  221. sequence spread spectrum communications, and for distance measurement in
  222. systems such as the Global Positioning System (GPS). LFSRs have the
  223. additional advantage of being easily implemented in hardware.
  224.  
  225. The maximal length sequence (or m-sequence) is equal to 2n-1 where n is the
  226. degree of the shift register. An example of a maximal length LFSR is shown
  227. below in Figure 3. This LFSR will generate the periodic m-sequence
  228. consisting of the following states (1111, 0111, 1011, 0101, 1010, 1101,
  229. 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110).
  230.  
  231.                                   [Image]
  232.  
  233.              Figure 3 Four-Stage Linear Feedback Shift Register
  234.  
  235. In order to form an m-sequence, the feedback taps of an LFSR must
  236. correspond to a primitive polynomial modulo 2 of degree n. A number of
  237. stream cipher designs consist of multiple LFSRs with various
  238. interconnections and clocking schemes. The GSM A5 algorithm, used to
  239. encrypt voice and signaling data in GSM is a stream cipher based on three
  240. clock-controlled LFSRs.
  241.  
  242. 3.2 Public Key Algorithms
  243.  
  244. Public key algorithms are characterized by two keys, a public and private
  245. key, which perform complementary functions. Public and private keys exist
  246. in pairs and ideally have the property that the private key may not be
  247. deduced from the public key, which allows the public key to be openly
  248. distributed. Data encrypted with a given public key may only be decrypted
  249. with the corresponding private key, and vice versa. This is functionally
  250. expressed as follows:
  251.  
  252.   C=Epub(P), P=Dpriv(C)
  253.   C=Epriv(P), P=Dpub(C)
  254.  
  255. Public key cryptography simplifies the problem of key management in that
  256. two parties may exchange encrypted data without having exchanged any
  257. sensitive key information. Digital Signatures also make use of public key
  258. cryptography, and commonly consist of the output of a one-way hash function
  259. for a message (discussed in Section 3.3) with a private key. This enables
  260. security features such as authentication and non- repudiation. The most
  261. common example of a public key algorithm is RSA, named after its inventors
  262. Rivest, Shamir, and Adleman. The security features of GSM, however, do not
  263. make use of any type of public key cryptography.
  264.  
  265. 3.3 One-Way Hash Functions
  266.  
  267. Generally, one-way hash functions produce a fixed-length output given an
  268. arbitrary input. Secure one-way hash functions are designed such that it is
  269. computationally unfeasible to determine the input given the hash value, or
  270. to determine two unique inputs that hash to the same value. Examples of
  271. one-way hash functions include MD5 developed by Ron Rivest, which produces
  272. a 128-bit hash value, and the Secure Hash Algorithm (SHA) developed by the
  273. National Institutes of Standards and Technology (NIST), which produces a
  274. 160-bit output.
  275.  
  276. A typical application of a one-way hash function is to compute a "message
  277. digest" which enables the receiver to verify the authenticity of the data
  278. by duplicating the computation and comparing the results. A hash function
  279. output encrypted with a public key algorithm forms the basis for digital
  280. signatures, such as NIST's Digital Signature Algorithm (DSA).
  281.  
  282. A key-dependent one-way hash function requires a key to compute and verify
  283. the hash value. This is useful for authentication purposes, where a sender
  284. and receiver may use a key-dependent hash function in a challenge-response
  285. scheme. A key-dependent one-way hash function may be implemented by simply
  286. appending the key to the message and computing the hash value. Another
  287. approach is to use a block cipher in cipher feedback (CFB) mode, with the
  288. output being the last encrypted block (recall that in CFB mode a given
  289. block's output is dependent on the output of previous blocks). The A3 and
  290. A8 algorithms of GSM are key- dependent one-way hash functions. The GSM A3
  291. and A8 algorithms are similar in functionality and are commonly implemented
  292. as a single algorithm called COMP128.
  293.  
  294. 4.0 Description of GSM Security Features
  295.  
  296. The security aspects of GSM are detailed in GSM Recommendations 02.09,
  297. "Security Aspects," 02.17, "Subscriber Identity Modules," 03.20, "Security
  298. Related Network Functions," and 03.21, "Security Related Algorithms".
  299. Security in GSM consists of the following aspects: subscriber identity
  300. authentication, subscriber identity confidentiality, signaling data
  301. confidentiality, and user data confidentiality. The subscriber is uniquely
  302. identified by the International Mobile Subscriber Identity (IMSI). This
  303. information, along with the individual subscriber authentication key (Ki),
  304. constitutes sensitive identification credentials analogous to the
  305. Electronic Serial Number (ESN) in analog systems such as AMPS and TACS. The
  306. design of the GSM authentication and encryption schemes is such that this
  307. sensitive information is never transmitted over the radio channel. Rather,
  308. a challenge-response mechanism is used to perform authentication. The
  309. actual conversations are encrypted using a temporary, randomly generated
  310. ciphering key (Kc). The MS identifies itself by means of the Temporary
  311. Mobile Subscriber Identity (TMSI), which is issued by the network and may
  312. be changed periodically (i.e. during hand-offs) for additional security.
  313.  
  314. The security mechanisms of GSM are implemented in three different system
  315. elements; the Subscriber Identity Module (SIM), the GSM handset or MS, and
  316. the GSM network. The SIM contains the IMSI, the individual subscriber
  317. authentication key (Ki), the ciphering key generating algorithm (A8), the
  318. authentication algorithm (A3), as well as a Personal Identification Number
  319. (PIN). The GSM handset contains the ciphering algorithm (A5). The
  320. encryption algorithms (A3, A5, A8) are present in the GSM network as well.
  321. The Authentication Center (AUC), part of the Operation and Maintenance
  322. Subsystem (OMS) of the GSM network, consists of a database of
  323. identification and authentication information for subscribers. This
  324. information consists of the IMSI, the TMSI, the Location Area Identity
  325. (LAI), and the individual subscriber authentication key (Ki) for each user.
  326. In order for the authentication and security mechanisms to function, all
  327. three elements (SIM, handset, and GSM network) are required. This
  328. distribution of security credentials and encryption algorithms provides an
  329. additional measure of security both in ensuring the privacy of cellular
  330. telephone conversations and in the prevention of cellular telephone fraud.
  331.  
  332. Figure 4 demonstrates the distribution of security information among the
  333. three system elements, the SIM, the MS, and the GSM network. Within the GSM
  334. network, the security information is further distributed among the
  335. authentication center (AUC), the home location register (HLR) and the
  336. visitor location register (VLR). The AUC is responsible for generating the
  337. sets of RAND, SRES, and Kc which are stored in the HLR and VLR for
  338. subsequent use in the authentication and encryption processes.
  339.  
  340.                                   [Image]
  341.  
  342.        Figure 4 Distribution of Security Features in the GSM Network
  343.  
  344. 4.1 Authentication
  345.  
  346. The GSM network authenticates the identity of the subscriber through the
  347. use of a challenge-response mechanism. A 128-bit random number (RAND) is
  348. sent to the MS. The MS computes the 32-bit signed response (SRES) based on
  349. the encryption of the random number (RAND) with the authentication
  350. algorithm (A3) using the individual subscriber authentication key (Ki).
  351. Upon receiving the signed response (SRES) from the subscriber, the GSM
  352. network repeats the calculation to verify the identity of the subscriber.
  353. Note that the individual subscriber authentication key (Ki) is never
  354. transmitted over the radio channel. It is present in the subscriber's SIM,
  355. as well as the AUC, HLR, and VLR databases as previously described. If the
  356. received SRES agrees with the calculated value, the MS has been
  357. successfully authenticated and may continue. If the values do not match,
  358. the connection is terminated and an authentication failure indicated to the
  359. MS. Figure 5 shown below illustrates the authentication mechanism.
  360.  
  361.                                   [Image]
  362.  
  363.                    Figure 5 GSM Authentication Mechanism
  364.  
  365. The calculation of the signed response is processed within the SIM. This
  366. provides enhanced security, because the confidential subscriber information
  367. such as the IMSI or the individual subscriber authentication key (Ki) is
  368. never released from the SIM during the authentication process.
  369.  
  370. 4.2 Signaling and Data Confidentiality
  371.  
  372. The SIM contains the ciphering key generating algorithm (A8) which is used
  373. to produce the 64-bit ciphering key (Kc). The ciphering key is computed by
  374. applying the same random number (RAND) used in the authentication process
  375. to the ciphering key generating algorithm (A8) with the individual
  376. subscriber authentication key (Ki). As will be shown in later sections, the
  377. ciphering key (Kc) is used to encrypt and decrypt the data between the MS
  378. and BS. An additional level of security is provided by having the means to
  379. change the ciphering key, making the system more resistant to
  380. eavesdropping. The ciphering key may be changed at regular intervals as
  381. required by network design and security considerations. Figure 6 below
  382. shows the calculation of the ciphering key (Kc).
  383.  
  384.                                   [Image]
  385.  
  386.                 Figure 6 Ciphering Key Generation Mechanism
  387.  
  388. In a similar manner to the authentication process, the computation of the
  389. ciphering key (Kc) takes place internally within the SIM. Therefore
  390. sensitive information such as the individual subscriber authentication key
  391. (Ki) is never revealed by the SIM.
  392.  
  393. Encrypted voice and data communications between the MS and the network is
  394. accomplished through use of the ciphering algorithm A5. Encrypted
  395. communication is initiated by a ciphering mode request command from the GSM
  396. network. Upon receipt of this command, the mobile station begins encryption
  397. and decryption of data using the ciphering algorithm (A5) and the ciphering
  398. key (Kc). Figure 7 below demonstrates the encryption mechanism.
  399.  
  400.                                   [Image]
  401.  
  402.                 Figure 7 Ciphering Mode Initiation Mechanism
  403.  
  404. 4.3 Subscriber Identity Confidentiality
  405.  
  406. To ensure subscriber identity confidentiality, the Temporary Mobile
  407. Subscriber Identity (TMSI) is used. The TMSI is sent to the mobile station
  408. after the authentication and encryption procedures have taken place. The
  409. mobile station responds by confirming reception of the TMSI. The TMSI is
  410. valid in the location area in which it was issued. For communications
  411. outside the location area, the Location Area Identification (LAI) is
  412. necessary in addition to the TMSI. The TMSI allocation/reallocation process
  413. is shown in Figure 8 below.
  414.  
  415.                                   [Image]
  416.  
  417.                     Figure 8 TMSK Reallocation Mechanism
  418.  
  419. 5.0 Discussion
  420.  
  421. This section evaluates and expands on the information presented in previous
  422. sections. Additional considerations such as export controls on crypography
  423. are discussed as well.
  424.  
  425. 5.1 GSM Encryption Algorithms
  426.  
  427. A partial source code implementation of the GSM A5 algorithm was leaked to
  428. the Internet in June, 1994. More recently there have been rumors that this
  429. implementation was an early design and bears little resemblance to the A5
  430. algorithm currently deployed. Nevertheless, insight into the underlying
  431. design theory can be gained by analyzing the available information. The
  432. details of this implementation, as well as some documented facts about A5,
  433. are summarized below:
  434.  
  435.    * A5 is a stream cipher consisting of three clock-controlled LFSRs of
  436.      degree 19, 22, and 23.
  437.    * The clock control is a threshold function of the middle bits of each
  438.      of the three shift registers.
  439.    * The sum of the degrees of the three shift registers is 64. The 64-bit
  440.      session key is used to initialize the contents of the shift registers.
  441.    * The 22-bit TDMA frame number is fed into the shift registers.
  442.    * Two 114-bit keystreams are produced for each TDMA frame, which are
  443.      XOR-ed with the uplink and downlink traffic channels.
  444.    * It is rumored that the A5 algorithm has an "effective" key length of
  445.      40 bits.
  446.  
  447. 5.2 Key Length
  448.  
  449. This section focuses on key length as a figure of merit of an encryption
  450. algorithm. Assuming a brute-force search of every possible key is the most
  451. efficient method of cracking an encrypted message (a big assumption), Table
  452. 1 shown below summarizes how long it would take to decrypt a message with a
  453. given key length, assuming a cracking machine capable of one million
  454. encryptions per second.
  455.  
  456.          Table 1 Brute-force key search times for various key sizes
  457.  
  458.  Key length in bits   32        40      56        64          128
  459.    Time required to
  460.   test all possible   1.19      12.7    2,291     584,542     10.8 x 10^24
  461.         keys          hours     days    years     years       years
  462.  
  463. The time required for a 128-bit key is extremely large; as a basis for
  464. comparison the age of the Universe is believed to be 1.6x10^10 years. An
  465. example of an algorithm with a 128-bit key is the International Data
  466. Encryption Algorithm (IDEA). The key length may alternately be examined by
  467. determining the number of hypothetical cracking machines required to
  468. decrypt a message in a given period of time.
  469.  
  470.             Table 2 Number of machines required to search a key
  471.                            space in a given time
  472.  
  473.            Key length in bits    1 day     1 week      1 year
  474.                    40          13         2          -
  475.                    56          836,788    119,132    2,291
  476.                    64          2.14x10^8  3.04x10^6  584,542
  477.                    128         3.9x10^27  5.6x10^26  10.8x10^24
  478.  
  479. A machine capable of testing one million keys per second is possible by
  480. todayÆs standards. In considering the strength of an encryption algorithm,
  481. the value of the information being protected should be taken into account.
  482. It is generally accepted that DES with its 56-bit key will have reached the
  483. end of its useful lifetime by the turn of the century for protecting data
  484. such as banking transactions. Assuming that the A5 algorithm has an
  485. effective key length of 40 bits (instead of 64), it currently provides
  486. adequate protection for information with a short lifetime. A common
  487. observation is that the "tactical lifetime" of cellular telephone
  488. conversations is on the order of weeks.
  489.  
  490. 5.3 Export Restrictions on Encryption Technology
  491.  
  492. The goal of the GSM recommendations is to provide a pan- European standard
  493. for digital cellular telecommunications. A consequence of this is that
  494. export restrictions and other legal restrictions on encryption have come
  495. into play. This is a hotly debated, highly political issue which involves
  496. the privacy rights of the individual, the ability of law enforcement
  497. agencies to conduct surveillance, and the business interests of
  498. corporations manufacturing cellular hardware for export.
  499.  
  500. The technical details of the encryption algorithms used in GSM are closely
  501. held secrets. The algorithms were developed in Britain, and cellular
  502. telephone manufacturers desiring to implement the encryption technology
  503. must agree to non-disclosure and obtain special licenses from the British
  504. government. Law enforcement and Intelligence agencies from the U.S.,
  505. Britain, France, the Netherlands, and other nations are very concerned
  506. about the export of encryption technology because of the potential for
  507. military application by hostile nations. An additional concern is that the
  508. widespread use of encryption technology for cellular telephone
  509. communications will interfere with the ability of law enforcement agencies
  510. to conduct surveillance on terrorists or organized criminal activity.
  511.  
  512. A disagreement between cellular telephone manufacturers and the British
  513. government centering around export permits for the encryption technology in
  514. GSM was settled by a compromise in 1993. Western European nations and a few
  515. other specialized markets such as Hong Kong would be allowed to have the
  516. GSM encryption technology, in particular the A5/1 algorithm. A weaker
  517. version of the algorithm (A5/2) was approved for export to most other
  518. countries, including central and eastern European nations. Under the
  519. agreement, designated countries such as Russia would not be allowed to
  520. receive any functional encryption technology in their GSM systems. Future
  521. developments will likely lead to some relaxation of the export
  522. restrictions, allowing countries who currently have no GSM cryptographic
  523. technology to receive the A5/2 algorithm.
  524.  
  525. 6.0 Conclusion
  526.  
  527. The security mechanisms specified in the GSM standard make it the most
  528. secure cellular telecommunications system available. The use of
  529. authentication, encryption, and temporary identification numbers ensures
  530. the privacy and anonymity of the system's users, as well as safeguarding
  531. the system against fraudulent use. Even GSM systems with the A5/2
  532. encryption algorithm, or even with no encryption are inherently more secure
  533. than analog systems due to their use of speech coding, digital modulation,
  534. and TDMA channel access.
  535.  
  536. 7.0 Acronyms
  537.  
  538. A3
  539.      Authentication Algorithm
  540. A5
  541.      Ciphering Algorithm
  542. A8
  543.      Ciphering Key Generating Algorithm
  544. AMPS
  545.      Advanced Mobile Phone System
  546. AUC
  547.      Authentication Center
  548. BS
  549.      Base Station
  550. CBC
  551.      Cipher Block Chaining
  552. CEPT
  553.      European Conference of Post and Telecommunication Administrations
  554. CFB
  555.      Cipher Feedback
  556. CKSN
  557.      Ciphering Key Sequence Number
  558. DES
  559.      Data Encryption Standard
  560. DSA
  561.      Digital Signature Algorithm
  562. ECB
  563.      Electronic Code Book
  564. ETSI
  565.      European Telecommunications Standards Institute
  566. GMSK
  567.      Gaussian Minimum Shift Keying
  568. GSM
  569.      Group Special Mobile
  570. HLR
  571.      Home Location Register
  572. IMSI
  573.      International Mobile Subscriber Identity
  574. Kc
  575.      Ciphering Key
  576. Ki
  577.      Individual Subscriber Authentication Key
  578. LAI
  579.      Location Area Identity
  580. LFSR
  581.      Linear Feedback Shift Register
  582. MoU
  583.      Memorandum of Understanding
  584. MS
  585.      Mobile Station
  586. MSC
  587.      Mobile Switching Center
  588. NIST
  589.      National Institute of Standards and Technology1
  590. OMS
  591.      Operation and Maintenance Subsystem
  592. RAND
  593.      Random Number
  594. RSA
  595.      Rivest, Shamir, Adleman
  596. SHA
  597.      Secure Hash Algorithm
  598. SRES
  599.      Signed Response
  600. TACS
  601.      Total Access Communications System
  602. TMSI
  603.      Temporary Mobile Subscriber Identity
  604. VLR
  605.      Visitor Location Register
  606.  
  607. References
  608.  
  609.   1. Van der Arend, P. J. C., "Security Aspects and the Implementation in
  610.      the GSM System," Proceedings of the Digital Cellular Radio Conference,
  611.      Hagen, Westphalia, Germany, October, 1988.
  612.   2. Biala, J., "Mobilfunk und Intelligente Netze," Friedr., Vieweg & Sohn
  613.      Verlagsgesellschaft, 1994.
  614.   3. Cooke, J.C.; Brewster, R.L., "Cyptographic Security Techniques for
  615.      Digital Mobile Telephones," Proceedings of the IEEE International
  616.      Conference on Selected Topics in Wireless Communications, Vancouver,
  617.      B.C., Canada, 1992.
  618.   4. European Telecommunications Standards Institute, Recommendation GSM
  619.      02.09, "Security Aspects".
  620.   5. European Telecommunications Standards Institute, Recommendation GSM
  621.      02.17, "Subscriber Identity Module".
  622.   6. European Telecommunications Standards Institute, Recommendation GSM
  623.      03.20, "Security Related Network Functions".
  624.   7. Hodges, M.R.L., "The GSM Radio Interface," British Telecom Technology
  625.      Journal, Vol. 8, No. 1, January 1990, pp. 31-43.
  626.   8. Hudson, R.L., "Snooping versus Secrecy," Wall Street Journal, February
  627.      11, 1994, p. R14
  628.   9. Schneier, B., "Applied Cryptography," J. Wiley & Sons, 1994.
  629.  10. Williamson, J., "GSM Bids for Global Recognition in a Crowded Cellular
  630.      World," Telephony, vol. 333, no. 14, April 1992, pp. 36-40.
  631.