2G technology

Cellular radio
The reason for the name is that coverage is obtained by dividing the coverage area into cells, smaller regions with lower coverage so that frequency resources can be reused in cells further away. The diameter of a cell is determined by the transmitters power, typically low in handsets, and also determined by the number of users in the area. A densely populated area will typically have smaller cells. Typically a frequency is reserved for 2-3 times the length of the cell and high quality bad pass filters must be used. Some channels on a typical radio network is reserved for signalling (administration). Antennas of base stations are constructed so that signal is sent into sectors, like this illustration:

History
Cellular radio communication began in Bell laboratories in the 1970s and the first commercial versions were seen in the 1980s in the United Kingdom and in Scandinavia. Countries developed their own systems in the beginning, and led to a limited marked. The first generation of mobile phones, 1984 to 1996 were analogue systems. AMPS in the U.S. at 800 MHz (30 KHz channels) and NMT in the Nordic countries around 453-467 MHz. United Kingdom and Japan had a variant called TACS. They were based on access based on frequency division.

AMPS = Advanced Mobile Phone System (U.S/Asia)
NMT = Nordic Mobile Telephone (Europe/Asia)
TACS = Total Access Communication System (Japan)

The second generation of cellular communication, from about 1992 to 2000, were based on time division or code division (multiple) access where subscribers were assigned time slots within a period for their communication or access to a spread spectrum coded waveform. The communication link seemed constantly available in the same sense movies looks like they are animating. An initial systems were cdmaOne (Interim Standard 95) followed by GSM and PDC. GSM uses time division (TDMA) and frequency hopping at 900 MHz and 1800 MHz. PDC is a Japanese variant using 800 MHz and 1500 MHz.

GSM = Global System Mobile_communication (Europe/Asia)
PDC = Personal Digital Cellular (Japan)

Waiting for the third generation, we have something called 2.5G from around 2001 to 2003, allowing sending of data using the GSM technology. HSCSD and GPRS. HSCSD allowed 38kbps while GPRS allowed 144kbps using up to 8 GSM channels combined. Then came EDGE allowing even more bandwidth up to 384kbps.

HSCSD = High Speed Circuit Switched Data
GPRS = General Packet Radio Service
EDGE = Enhanced Data for Global Evolution!

Multiple access
In order for subscribers to share limited frequency resources, three multiple access techniques are typically used (alone or in combination).

• Frequency division (FDMA): A channel or frequency is allocated to a user for the duration of the call. Like having a separate room for each communication. Like the original analogue switched fixed line phone networks. Easy to build, but uses the capacity poorly.
  
• Time division (TDMA): Subscribers talk in one at a time in an orderly predefined manner, like a token ring network or multiplexing. It is more efficient since time slots can be allocated on demand, but it also requires synchronization and guard times so not to step on each others feet.
  
• Code division (CDMA): This is a technique using spread spectrum (DSSS and FHSS) where a low cross-correlated modulation code determines the waveform. Everything except the correct signal will look like noise for the receiver. This is like talking different languages in a shared room.
  

GSM
GSM is the most widespread technique, used by more than 3 billion people around the world. It supports varying cell sizes ranging from the biggest called "macro" covering up to 35 Km, down via "micro", "pico", down to "femto" covering indoor rooms. Special kinds of base stations are used in tunnels and areas in the "shadow" of the main base stations. This is an overview of the GSM components:

3 of the 4 GSM elements are visible: The user equipment MS, the BSS which is the radio and logic at the base stations and the NSS "core" network equipment keeping track of registered users, routing between cellular base stations and external networks. The 4th is Operation and Support Subsystem (OSS).

The MS "mobile station" consists of a phone and a removable SIM-card where the subscriber-related details lie on. It has a secret key used for authentication with the GSM system and it also keeps track of current cell tower it is connected to. The phone has a Mobile Equipment Identity (IMEI) number that is unique for the device. It it not registered to a user, but instead used for reporting stolen phones for blacklisting (optional).

The base station contains a controller that decides channel allocation for up to hundreds of base transceiver stations (BTS). It also handles handover between connected BTS. The BTS directly controlling up to 16 transceivers (radio receiver and transmitter).

The NSS subsystem is the glue connecting mobile subscribers to other providers and land line based phone systems. It keeps information about the registered users, keeps track of usage for billing, authenticates the users and handles roaming on at greater distances that the BSS cannot handle themselves. The MSC keeps track of where the users are to be found in order to route an incoming call to the correct tower. The HLR and VLR are registers of users, the home for own subscribers and visitor for customers of other providers when roaming. Both have the "real" number in addition to international mobile subscriber identities (IMSI) and MSISDN numbers, and the current location and any restrictions are also stored here. The EIR (equipment register) is for storing stolen phone ID's and for tracking suspicious phones. The authentication center calculates data for authentication sent to the base station. It is designed primarily for avoiding use of the system that can not be billed.

The OSS subsystem is for traffic management, configuration, monitoring and fault handling.

Burst of data

Downlink and uplink bands are separated by 20 MHz and there are 374 channels of 200 KHz for each of them. 8 users can share a channel as they are assigned time slots. A transmission in a time slot is called a burst. Every MS (phone + SIM) get upling and downling separated by 45 or 95 MHz depending on usage of 900 MHz or 1800 MHz GSM type for interference protection and they never transmit earlier than 3 slots after the BTS (tower).

A time slot is 577 micro seconds but only 546.5 of them are actually sent on. Two parts of 57 bits (114) and the rest is overhead (totaling 148 bit). This overhead can be "stolen" frames used for critical signalling. Other formats exists for synchronization and call setup. 8 of these time slots are collected and called a frame. 26 frames is a multiframe. 51 multiframes is a superframe and when you then take 2048 superframes you get a hyperframe. They last 3h and almost 29 minutes. This knowledge is probably not useful for most people.

2G Security (GSM and GPRS)

Goals
Basically, equivalent security to the land line based phone system. Authentication was important to ensure billing and encryption while in the air. Anonymity has also been important.

Authentication
The SIM contains a key Ki (up to 128bit) and is also found in the AuC component of the NSS. The encryption key Kc (64bit) is derived from Ki and a random nonce. The algorithm used is called COMP128 and is consists of A3 (authentication) and A8 (encryption key generator). A3, A5 and A8 are not published, but they have partly leaked and are now reverse engineered.

As we can see from this illustration, Ki is present at both the user SIM card and at the authentication center. The AuC generates a random 128 bit number and gives it to the subscriber. Both generate a SRES (32 bit) verification code and they are compared at the AuC. Both also generate a key for over the air encryption using the same data. Before any of this can happen, the ID of the subscriber must be sent to the AuC, the IMSI (international mobile subscriber identity) a 15 digit number. After the first successful authentication a temporary MSI (TMSI) will be generated and assigned to the user and stored in the SIM together with a new LAI (location area identifier). The pair LAI and TMSI are then used in further authentication requests so that the user stays anonymous from now on to potential eavesdroppers.

A3 and A8 are both hash functions (COMP128) and are a german design from 1988. The last 10 bits of Kc is set to all 0, and this weakens the security by design. A5 is a stream cipher and has 4 "modes".

• A5/0 is "off"
  
• A5/1 is the normal strength algorithm
  
• A5/2 is a weakened algorithm
  
• A5/3 is a replacement for A5/1 using KASUMI (feistel-network using output block mode and is also used in UMTS)
  

We remember a burst of data is 114 bit so this is the block length used when encrypting and decrypting. The frame number (22 bit) is used as an initialization vector (IV). The key will hopefully be replaced by the time this one ticks over. Because the output of A5 needs to cover both down and uplink, it actually produces 228 bit for every frame number. The A5/1 consists of 3 LFSR with stop-and-go-clocking. The initialization of the LFSR's for every frame consists of the 22 bits of the frame number being feed into the LFSR's and clocked 100 times without output.

The A5/2 uses 4 LFSR's where one of the registers is driving the stop-and-go-clocking. When initializing, some positions of the 3 primary LFSR's are set to one, and thus once again made more insecure by design.

A5/3 uses a common module called KGCORE and is used here and also the GEA3 algorithm of GPRS and f8 for UMTS. Since the KASUMI is a 64 bit block cipher, we simply disregard the bits in the last block when we don't need more bits. The KGCORE looks like this:

GPRS security
The difference in GPRS is that confidentiality is provided through the whole network and the TMSI (temporary ID) is replaced by P-TMSI (Packet TMSI) and IP-addresses are assigned. Two new nodes at the NSS is added:

SGSN = Serving GPRS Support Node (tunneling mode for encryption between these - IPSec)
GGSN = Gateway GPRS Support Node

The CA, CB, CC etc have a different definition as seen in the illustration.

Weaknesses
Different weaknesses are known of the COMP128 (generation of authorization and encryption keys): A weakness (1998) in the 2nd round of compression function, requires 6 hours of SIM card traffic to get the secret key. Results in broken SIM card. A build on this one in 2004 requires only 1 hour of queries. A side channel attack can perform the attack in 3 minutes or less. The result is the possibility of cloning a SIM card and thus allows for calling on somebody else's bill.

Weaknesses in the A5/1 (strongest) algorithm (1997) uses the 10 0-bits using 64TB of disk space. Reduced to 140GB in year 2000. Primarily because of too few bits. In 2003 more vulnerabilities were found attacking the stop-and-go mechanism.

The A5/2 has a way too short R4 register (17 bits), can be guessed fast. Known plain text attacks are known (1999). Creating an over defined system of equations can break the system without getting the key. Error correlation can also be used.

No protection against impersonation is in the system, which means the GSM system authenticates the user, but not the other way around. It is thus simple to set up a rouge access point. Criminals and the police has been known to do this.

Attacks on the other components of the GSM system is also possible, including the home location register, number of people with access to the authentication centers, availability concern if the MSC is attacked or damaged somehow.