STATION ID - 7047/3.12

9x Datakit Network
FOR OFFICIAL USE ONLY

This is a 9x system, restricted to authorized persons and for
official 9x business only. Anyone using this system, network or data
is subject to being monitored at any time for system administration and
for identifying unauthorized users or system misuse. Anyone using this
system expressly consents to such monitoring and is advised that any
evidence of criminal activity revealed through such monitoring may be
provided to law enforcement for prosecution.





Understanding The GSM  (Part II of II)
by The Monty
e-mail me at: m0nty@hack.gr
check the http://www.hack.gr/users/m0nty


     Intro:
    ~~~~~~~~
   Ok here we are with the second part as i promised you. I was expecting to
 publish it a bit earlier but i couldn't. Anyway i remember i told you that
 we'll discuss here about inside of the MSC and the security of the GSM. I
 will say only a few things about the MSC and the structure of the OMC
 (Operating and Maintenance Center). Anyway here it goes..


     INTERFACES OF THE GSM
    ~~~~~~~~~~~~~~~~~~~~~~~
 Here are some acronyms that will be used above:

MSC = Mobile Servuces switching Center
AC  = Authentication Center
BS  = Base Station
BSC = Base Station Controler
EIR = Equipment Identification Register
HLR = Home Location Register
MAP = Mobile Application Part
OMC = Operating nad Maintenance Center
SIM = Subscriber Identity Module
TCE = Transcoding Equipment
VLR = Visitor Location Register
PSTN= Public Switched Telephone Network
   It should be known that the OMC is standar for all the mobile telephony 
 systems.



      The OMC
     ~~~~~~~~~

       OTHER MSCs               ______________         ____
           |             +------| _____      |---------|BS|
           |             |      | |TCE| & BSC|         ~~~~ ____ (Cordless)
           |             |      | ~~~~~      |--------------|BS|------+
          _|_________    |      ~~~~~~~~~~~~~~              ~~~~      |  ____ 
   +------|         |----+  _______                                   +->|MS|
 __|___   |  M S C  |-------|     |                                      ~~~~ 
 |PSTN|   |         |-------| TCE |-----+
 ~~~~~~   ~|~~~|~~~|~       |     |--+  |    _____   ____  (Cordless)    ____
           |   |   |        ~~~~~~~  |  |--->|BSC|---|BS|--------------->|MS|
           |   |   |                 |       ~~~~~   ~~~~                ~~~~
           | __|__ |                 |
           | |VLR| |                 |   _____            ____(Cordless) ____ 
        ___|_~~~~~ |                 +-->|BSC|------------|BS|---------->|MS|
        |EIR|    __|__   ______          ~~~~~            ~~~~           ~~~~
        ~~~~~    |HLR|---| AC |
                 ~~~~~   ~~~~~~
 
    
    This is a structure of a common OMC, at least a way that it could be. 
 As we can see in a MSC we can addapt besides the VLR, which is always there,
 a AC, HLR and a EIR. A MSC can also be in the same building with the BSC. 
 As i mentioned before the OMC has the same stracture for the whole network.
 Plus a MSC can use the EIR, AC, HLR from another MSC if it doesn't have them 
 installed.
 
   The MSC is connected with the PSTN (the telephone network) with CCS 7
 signalling and with other MSCs through the CCS 7 (MAP). Every MSC has
 installed a VLR. The VLR temporary saves the ID of a subscriber of another
 MSC in another location. The VLR takes data of a subscriber from the HLR.
 Plus the VLR informs the HLR whenever the MS is in the HLR's territory.
 The HLR has data of every subscriber that "belongs" to its area.
    
   The AC is something like the SIM card of the network. The AC works with
 the SIM card of a MS in order to fullfill some services (like authentication).
 The VLR uses the data that the AC purchaced from the SIM card to identify
 the MS. We'll say more in the security section about the "dialog" between
 the AC and the SIM.

   Every BTS has some RT (Radio Terminals). A RT transmits 8 channels in the
 same time, while one channel is used for the signalling. Depending on the 
 antenna type a BTS can cover one or more cells.

   A BSC is a part of the cordless transmission. It connects with the BS
 with the A-bis interface and controls the cordless channels of many BS.
 Further more a BSC uses TCE to transform the 13 kb/s cordless signall in
 a 64 kb/s for the PSTN. The BSC sends fault-signalls in the OMC and 
 executes the handover of a BS.

   The EIR has the "identity" (we'll see about that later on) of many MS
 and is used by the MSC to check if a MS is valid or not. A EIR is able 
 to isolate a MS from the network if it finds is invalid.
  


  SECURITY:
 ~~~~~~~~~~~

         The GSM satisfies the above security conditions:
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *   The system authenticates the identity of subscriber in order to charge
   the correct person's bill for the calls that are made. [SIB]

 *   The system checks the mobiles that access the network so that a stollen
   mobile couldn't connect to the network, even if the subscriber and the
   SIM (Subscriber Identity Module) card are legal. [Equipment Identity]

 *   The information (data/voice) that "travel" in the air from the mobile
   subscriber to the BS (Base Station) are secured (meaning that they are
   being encrypted).  [Ciphering]

 *   The system keeps the subscriber anonymous during his connection with
   the network so that noone can identify him. Subscriber Identity
   Confidentiality. [Anonymity]

  Closer look:
 ~~~~~~~~~~~~~~

         -o-     Subscriber Identity Authentication (SIB)     -o-

     In order for the system to charge the correct person each time a mobile
  subscriber wants to use the network the subscriber must identify himself.
  The authentication procedure of a subscriber takes place each time the
 subscriber connects/disconnects to the network and each time he/she wants
 to make a call. The mobile subscriber authenticates it self by sending the
 IMSI/TMSI to the network.

     The IMSI (International Mobile Subscriber Identity) is unique and
 defines the  mobile subscriber in the GSM network. The network gives this
 unique IMSI in each mobile without knowledge of his owner.

    The TMSI (Temporary Mobile Station Identity) has local purposes. The
 network also gives TMSI in each mobile and its use is to keep the anonymity
 of the subscriber. The TMSI structure is determined by the telecom.

    For the authentication of the subscriber the system uses the question-
 answer protocol between the network and the subscriber. The network issues
 a random challeng (a 128 bit random signal) RAND, this is the question. The
 mobile device estimates the answer - SRES (Singed Response) signal of 32
bit
 length - and applys the cryptographic algorithm A3 in the RAND signal and
 in the subscriber's secret recognition key ( Ki ). It then sends the SRES
 in the MSC. The MSC compares it's estimated SRES with the SRES that was
 received from the mobile device and authenticates the subscriber.

   The Ki and the A3 algorithm are kept in the SIM card for security reasons
 thus they can not be read or modified from a outsider. For every IMSI the
 AC (Authentication Center) pre-estimates the RAND/SRES/Kc triplets. These
 values are saved in the HLR's database. The Kc is the Ciphering Key which
 we'll be described later.


                -o-    Equipment Identity    -o-


   The network is able to check the mobile device that is used from a user
 to access the network. It checks if the device is stolen or technologicaly
 inappropriate so that it could prevent the device from connecting to the
 network. The equipment identity uses the international recognition number
 of the device (IMEI) and the database  EIR  (Equipment Identification
 Register) where all the IMEIs are kept.

   IMEI (International Mobile Equipment Identity) is a unique number for
 every mobile device of the GSM network. It is usually written in BAR code
 in the place where you adapt the battery of the device. With the IMEI the
 network can check if the device is allowed to connect to it.

   In the EIR the devices are kept in three categories:
    [i]    The white list for the devices that can freely connect to the
          netwoork.

    [ii]   The grey list for the questionable devices.

    [iii]  The black list for the devices that the connection in the network
            is not allowed. A device will be in the black list after its
            reported stollen to the company by their legal subscriber.

 So the connection to the network is allowed only after the IMEI's check
 from the EIR database.

     -o-  User Data & Signaling Protection - Security [Ciphering]  -o-

   In order to secure the cordless communication from the MS(Mobile Station)
 to the BS (Base Station) the network encrypts the signal using the A5
 Ciphering Algorithm. The needed for the encryption key (Encipher/Decipher key)
 Kc is taken after the applying of the A8 algorithm to the RAND signal and
 the Ki (the subscriber's secret recognition key). The Kc changes in every new
 connection to the network.

   The Kc key is being generated seperatly in the SIM card and in the AC.
 The generation of the Kc key in only one point (let's say in the AC) and
 then its sending in the mobile subscribe would be dangerous cause there
 would be no encryption during the cordless communication.

Ciphering of the cordless communication part Schematic:

  ______   [Ki]       _______    [Kc]    ______        _________
  | MS |----------->  |  A8 |----------->| A5 |------->| Speach|
  ~~~~~~  [RAND]      ~~~~~~~            ~~~~~~~       ~~~~~~~~~
     |                                                     |
     |                                                     |
     | (Authentication)                                    |
     |                                                     |
     |                                                     |
  ___|______   [Ki]     ______   [Kc]      ______       ___|_____
  |  GSM   |----------> | A8 |------------>| A5 |------>| Speach|
  | Network|  [RAND]    ~~~~~~             ~~~~~~       ~~~~~~~~~
  ~~~~~~~~~~


                -o-    Anonymity    -o-

   While the subscriber turns his mobile device on he uses the IMSI for his
 connection to the network. This is the only time where the subscriber uses
 his real identity. After that the network gives the subscriber a temporary
 id called TMSI. This temporary id is valid only for a specific area, if the
 subscriber moves to another area the network gives him a different TMSI.

   This anonymity while the subscriber is connected to the network holds the
 subscriber's location and his identity hidden, while he originates calls or
 updates his location etc..



         The GSM hack
        ~~~~~~~~~~~~~~
   There have been too many articles in magazines and on the net so i won't
 say much about this. There are many interesting sites that you should visit.
 First of all I want to clear out that the attack on the GSM was made while
 the attackers had physical access to the SIM card. Which means that if you
 don't have the card you don't have anything to clone (duh). Second there
 has NOT been an attack over the air, meaning noone hacked GSM via Um (Air
 Interface). The attackers where from University of California at Berkeley.

   The attacker's mathematical analysis of the SIM card proved to them that
 the cryptographic codes it used weren't that strong. So To exploit this
 vulnerability, an individual would interact with the SIM repeatedly, with
 enough queries, the attacker can use some mathematical techniques to learn
 the supposedly-secret key.


   Some technical details of the attack taken from ISAAC as they publish it:

    We showed how to break the COMP128 authentication algorithm, an
   instantiation of A3/A8 widely used by providers. Our attack is a
   chosen-challenge attack. We form a number of specially-chosen
   challenges and query the SIM for each one; the SIM applies COMP128 to
   its secret key and our chosen challenge, returning a response to us.
   By analyzing the responses, we are able to determine the value of the
   secret key.

    Mounting this attack requires physical access to the target SIM, an
   off-the-shelf smartcard reader, and a computer to direct the
   operation. The attack requires one to query the smartcard about
   150,000 times; our smartcard reader can issue 6.25 queries per second,
   so the whole attack takes 8 hours. Very little extra computation is
   required to analyze the responses.

    Though the COMP128 algorithm is supposed to be a secret, we pieced
   together information on its internal details from public documents,
   leaked information, and several SIMs we had access to. After a
   theoretical analysis uncovered a potential vulnerability in the
   algorithm, we confirmed that our reconstruction of the COMP128
   algorithm was correct by comparing a software implementation to
   responses computed by a SIM known to implement COMP128.


  Information for cryptographers

   The attack exploits a lack of diffusion: there's a narrow 'Pipe'
   inside COMP128. In particular, bytes i,i+8,i+16,i+24 at the output of
   the second round depend only on bytes i,i+8,i+16,i+24 of the input to
   COMP128. (By `Round'', I refer to one layer of `Butterflies'' and
   S-boxes; there are a total of 5*8 rounds in COMP128.) Bytes i,i+8 of
   the COMP128 input are bytes i,i+8 of the key, and bytes i+16,i+24 of
   the COMP128 input are bytes i,i+8 of the challenge input.

   Now we `Probe'' the narrow pipe, by varying bytes i+16,i+24 of the
   COMP128 input (i.e. bytes i,i+8 of the challenge) and holding the rest
   of the COMP128 input constant. Since the rounds are non-bijective, you
   can hope for a collision in bytes i,i+8,i+16,i+24 of the output after
   two rounds. The birthday paradox guarantees that collisions will occur
   pretty rapidly (since the pipe is only 4 bytes wide); collisions in
   the narrow pipe can be recognized, since they will cause a collision
   in the output of COMP128 (i.e. the two authentication responses will
   be the same); and each collision can be used to learn the two key
   bytes i,i+8 with a bit of analysis of the first two rounds (i.e.
   perform a R attack'', in the terminology of differential
   cryptanalysis).

   As stated, this would require 2^{4*7/2 + 0.5} = 2^{14.5} chosen-input
   queries to COMP128 to learn two key bytes (since each of the four
   bytes of output after the second round are actually only 7-bit
   values), and thus would require 8 * 2^{14.5} = 2^{17.5} queries to
   recover the whole 128-bit key Ki. However, we have some optimizations
   to get this number down a bit.

   Note that there is a significant amount of literature on the design of
   cryptographic hash functions out of a FFT-like structure (as COMP128
   is designed). For instance, Serge Vaudenay's work on a theory of
   black-box cryptanalysis (as well as his other work, e.g. FFT-Hash II
   is not yet secure'') is more than sufficient to uncover this weakness
   in COMP128. In other words, our attack techniques are not particularly
   novel.



      Closing:
    ~~~~~~~~~~~
   Well that was it.. About the algorithms i'm thinking, and propably will,
 publish a file showing proposal algorithms. The French algorithm, the
 Swedish and the UK algorithm. Cya ppl.

         9x -= Spreading HP in the new millenium 
