/================================================================================\
---------------------------------[ PLAYHACK.net ]---------------------------------
\================================================================================/


-[ INFOS ]-----------------------------------------------------------------------
Title: "GSM Demystified"
Author: emdel
Website: http://www.playhack.net
Date: 2008-01-02 (ISO 8601)
---------------------------------------------------------------------------------


-[ SUMMARY ]---------------------------------------------------------------------
0x01: Security Introduction
0x02: Weaknesses
0x03: How to exploit these weaknesses
0x04: The future
0x05: Conclusions
0x06: References
---------------------------------------------------------------------------------



---[ 0x01: Security Introduction ]
In this section I give you a general idea about gsm security.

Twenty years ago in Denmark, thirteen operators give life to the Global System for
Mobile Communications, well-known as GSM. This is a foundamental step in our
history and in this paper will see some reasons.
The born of GSM has a lot of meanings such as the end of analogic communication and
the beginning of digital age or the awareness of the importance of security in the
fild of mobile. With the 2g there is a new sort of sensibility and there is a new
task: the wireless systems must be safe like the wireline and gsm try to reach that
goal. Gsm's strength is based on three its features:

(i) Authentication
(ii) Time trick :)
(iii) Cryptology

This time I've only listed these GSM aspects and I hope then I can explain you :D
I and You, my reader, aren't normal dudes, we want to understand and analyze everything
and we love looking for some flaws and with this spirit we can underline some our
thougthts. We can attack the network, we can create e fake base station and so on then
we know the ciphering is weak, in fact the keys are exchanged without protection.
Conceptually we can think to brute-force the key used during the ciphreing process and try
other kinds of attacks. At the end the gsm is not so safe at all.
Now it's time to understand the three features above:

(i) Authentication. We know what a cellular is and everyday we send a sms or we call
our friends and so we use our sim.
Maybe someone doesn't know the sim's role and beacause it's a necessary component of
our phone. Inside the sim (Subscriver Idenity Module) there is a permanent secret
key called Ki. This important key has two houses: the first is inside our sim and
the second is in a beautiful place called Authentication Center. Now it is easy to
understand what are the steps during a authentication session. We must check if
our ki is the same of the ki stored in the authentication center, this is the main idea.
This check isn't so easy, now we try to see it:

|----------bs1
|house1| ------ |----------bs2 ------> |house2| ( my dashed lines are waves )
|----------bsn

This figure shows you the authentication session in general. House1 is our cellular,
House2 is the authentication center.
Now we can see in depth what the checking do. The idea is wonderful, look at it:
we have a secret key, well so we can use it to
compute something. To reach the correct result we must have the true key :).
This is the main idea. To our cellular is sent a random string, its length is 128 bit,
then, at this time, the sim plays its role with the A3 function. We can see A3 with this
coding point of view: int A3( int Ki, int random_string ). So we pass to this function
the ki and the random string and the function returns a int in our example called SRES,
its length is 32 bit, this number is sent back to the sender of the famous random number
and only at this point there is the checking process. This is the basic idea of the
authenitcation process.

(ii) Time trick. After the authentication there are other steps, keep in mind the time is
our path and we follow it. To improve our security a temporary key is generated by a new
function called A8. The prototype of A8's function is the same of A3, in fact we can see
something as int A8( int Ki, int random_string). At the end A3 and A8 have the same
parameters. Now it's time to the questions. What is the role of A8?
This is a possible answer: "A8 must encrypt our phone calls on the air". What is the
output of this function? "The output is a temporary key called Kc and it is used to encrypt
our calls". I tell more times the same thing because it is important to understand
these features to exploit these services, remember it! So the time trick is based on the
clever idea of a temporary key.


(iii) cryptology. Lines above I've written "wireless system must be safe like
the wireline".
Gsm reaches this goal using cryptology. At this point we can write a brief summary.
We have a secret key used during the authentication. With Kc we can encrypt our calls
between our phone and the base station. Keep in mind we use this key until a new
authentication process. To encrypt our calls we use a famous algorithm called A5 but
unluckily its features aren't public.
I think the figure below can help you to really understand these actions:

Ki Ki
[*] ==========> BS =========> |_|
<...rand..................
----sres----------------->

where: [*] is our cellular, Bs == base station, |_| == authentication center
Now we briefly analyze the structure of GSM cipher. There are two main kinds of A5's
algorithm one is stronger than other. A5/1, it is used in Europe, and the "weak" A5/2.
Some papers underline how to attack with 2^x steps where x is a number between 40
and 50. This complexity turns away people like hackers or phreakers, so, at the end,
only a powerful hardware can really attack the GSM cipher. During a conversation
through the radio channel we send frames, their length is 114 bits. Kc is used
with the frame counter (fn), kc size is 64 bits while fn 22 bits. These are
the inputs of the A5 keystream generator, at the end we have 114 bits of data and then
they will be xored and we have the ciphertext. These are the steps in the our mobile
station. In the base station it changes a bit however we still have our 228 bits
and then we xor the ciphertext in order to have our data. Now we have talked
about the main aspects of A5, but the cryptology and its strength is present
everywhere in the mobile communication. I've briefly analyzed this algorithm
because it is very important, it is the knight of our privacy in these world of
eavesdropers.
Lines above I talked about other functions called A3 and A8. They use a key-hash
function called COMP128. We must remember it because the first hack of GSM was
on its weakness, in the 1998. In these years a lot of countries focus their
attention on security so a new better functions exists and its name is A5/3
but it will be used on 3gpp and it is based on the famous Kasumi algorithm.

Now we have analyze the main features of gsm security.
We are ready to find out new things :)
-----------------------------------------------------------------------------[/]



---[ 0x02: Weaknesses ]
GSM is not secure at all. The main problems are phone cloning and all related
frauds and the security of conversation, in fact someone can intercept our phone
call and so he can eavesdrop our "secret" words. The main problem of gsm security
is the strategy of "security by obscurity" in fact the consortium developed all
algorithms in secret way and it disclosed only to the operators and to all related
factories. They believe in this strategy, if nobody knows the algorithm nobody can
crack it! We know history and we know that all these strategies are going to fail,
in fact at the features of algorithms leaked out and so the underground community
studied them carefully.
There are a lot of kinds of attacks against the algorithms of gsm. A vulnerable
point is based on air waves. During a call we can intercept these waves:

) /|\
))) / | \
[*] )))))) ^_* / | \==> BTS
| ))) | / | \
our phone ) attacker
|
waves

This is a possible scenario. If an attacker intercept our waves and at the end
our frames he try to crack them, using modern hardware this action is not so
impossible. Our privacy is related to the time in fact It is impossible to decrypt in
real time our data but at the end after some hours he can understand all frames.
Keep in mind this flaw of GSM system.
So at the end GSM security layer ensures us the privacy of our conversation in real time.
Nothing could eavesdropping our voice during our conversation.
However there are other weaknesses and now we focus our attention on the sim card
and the so-called social engineering.
Social engineering can seem stupid but it's possible. Everyone can pretend to
be an employer of our telephone company.
Then he'll come in in our house and install a good wire tap to eavesdropping
our secret conversation. In this situation we hasn't to have a blind trust and we
must distrust about everyone.
Now we analyze the flaws of our sim card. We know something about it and it's time
to understand how it really works.
Sim card is the cradle of our secret Ki. If someone obtains it he can listen our
conversation, he can dial while we are paying. This aspect isn't so important in this
paper because we focus our attention on listening the calls. There are attacks to obtain
the secret Ki. Lines above i've talked about an algorithm called COMP128, it isn't so
strong.
There are two kinds of attack: on air and with a real access to the phone. They both
have the same idea. We can deduce the Ki from the sres response, with the verb deduce
i mean through a cryptanalysis action. It isn't so difficult, we must have a smartcard
reader, have patience and time ^_*. On the air we must challenge the phone in a
place where the bts signal is weak, this place can be a subway for instance and
even this time we need time and patience. These kinds of attack are called sim-cloning
and the goal can be multiple: cloning, interception, etc.
There are other attacks. They are based on the well-known signaling network.
In the whole GSM security system there is a general flaw, it is the transmission
after the bts, it is unencrypted, so if someone accesses to the signaling network
he can read our data. SS7 system is weak and an attacker can obtain our ki, rand,
sres etc.

/|\ |
))) / | \ no man's land [|]
[*] )))))) secure zone / | \==> BTS ^_* [|] => bsc
| ))) protected by / | \ |_attacker [|]
phone |_ waves A5

In the figure above we can see how the whole system works and where is its major
weakness.
I've talked about the general weaknesses of the gsm system.
Now it's time to exploit them!
-----------------------------------------------------------------------------[/]



---[ 0x03: How to exploit these weakness ]
Now we try to analyze in depth sim card, its function and its role. I give you some
definitions in order to understand how the sim card works and what it is. A sim card
is simply a smart card and so it has chip in which there is a sort of os, a small
filesystem and some applications and to warrant a security layer there is a PIN.
To have idea about the sim structure you can see the figure above:
__________
| 1 2| \ ===> the zone inside the sim is the famous chip. The numbers represent:
|_3____4| | 1 : eeprom
|__________| 2 : cpu --> I/0
3 : ram
4 : rom

Now you have a idea about sim and its anatomy. We know the importance of ki and with
it someone can clone our poor sim.
A normal cryptographic attack is based on the analysis of the inputs and outputs and
then the attacker try to understand how the system works:

input ==> system ==> outputs

In our situation we want to understand how COMP128 works. Once we have understood
it we can clone a sim card, it isn't easy due to security by obscurity but
fortunately Marc Briceno and his friends manage to their goal. Today we know how COMP128
works and the conclusion is ... any ideas? ^_*. I am not going to analyze how to break
COMP128 i'll link it at the end of the paper.
Now we try to understand some attacks vs A5 in particular the Biased Birthday's
one and Shamir & c.'s one. Let's go!
Biased Birthday. To understand this attack we need some information: in primis
we must define a set of states called X, X is our input, the we compute our outputs.
Now we have a outputs and we must define Y, Y is another set in which there are the
unknow states. The main idea of this attack is to look for some same states.
Now we take a eye in depth.
To really understand how it works we need math. X intersection Y is not equal 0.
Every chosen state has a odds. P(X)
is the probability of a state to be chosen from X and P(Y) from Y. We must keep in
mind that the intersection isn't empty only if:
sum[P(X)P(Y)] = 1
If this formula is correct the attack is possible. Then we must choose the states
from X and Y and use a indipendent distribution in which there is a sort of correlation
between X and Y. This attack is possible beacuse A5/1 uses randomization to each frame
with a different frame counter and so we can analyze it using distributions.
There is a complexity roughly 2^48 but there are some ways to reduce it :).
Now it's time to understand Shamir and c. attack. This attack is wonderful, in fact
it requires only two minutes of conversation. Then it can find out the key in
few seconds. It is based on the thing i call "theory of states". We have again X and Y
with the same meaning, but this time the idea is different. We must find the same state
in X intersection Y and then we must run the algorithm in the opposite direction :D.
Here the complexity is roughly 2^64. We need 5 bytes per state and so if we compute
the needed memory we can find something as 73 Gigabyte. I don't explain how to reverse
A5 or the three of steps, anyway at the end of paper i give you some links.
Here i've briefly analyzed two famous attacks and how they work.
-----------------------------------------------------------------------------[/]



---[ 0x04: The future ]
Gsm is 2g and now we know that the future is 3g. 3g technology tries to harden
the weak 2g and it tries to improve the services and to raise the speed on the net.
The future maybe has a name, UMTS. The future has a new radio technology WCDMA
while the past uses a mix of TDMA and FDMA. The future has a new kind of sim
called USIM. The future knows the history, the stupid paradigm "security by
obscurity" is dead. The companies are happy and this time they've developed new
algorithms maybe the end, this time, is different.
However the future must live with its past and so umts must be interworked with
the the old gsm or the gprs. The secret cradle of a5 is given first to gea3
( the algorithm for gprs encryption) and then it was light with the new cyclop
called Kasumi algorithm. Maybe Kasumi is the solution to the next twenty years
as the people of 3gpp think, Kasumi is really strong and it derives from another
algorithm called Misty developed by Mitsubishi Electric Corporation. Kasumi passes
avalanche effect and another test vs renondance input.
Other tests studied some important algorithms related with Kasumi, f8 the so
called confidentiality algorithm and it is important because it's the keystream
generator, and f9 the so called data integrity algorithm and it is
important because the mac ( mac means Message Authentication Code :P ) is based on it.
Maybe the security goal will be reached.
The future is designed for multimedia communication, everyone will use
high-quality images and video. 3gpp people are working about two new standarts
to reach the their goal, these standarts are hspa ( High Speed Downlink Packet Access )
and a new radio system called lte ( Long Term Evolution ). Only with these
kinds of technology we can reach 2Mbps of high bit rates.
At the end the future isn't so dark ;).
-----------------------------------------------------------------------------[/]



---[ 0x05: Conclusion ]
We have seen that gsm is weak in some levels. Its algorithms are broken and the
politics "security by obscurity" has lost its initial strength. Gsm is better than
1g but it isn't enough. Let's conclude this short paper saying that now you are
aware of the mobile communication problems and you must pay attention on it.
I hope you consider useful this paper. This is only a point of departure. I wanna
thank nexus omni, god and null and my friends of eop Sarosoft and germano ^_^
-----------------------------------------------------------------------------[/]



---[ 0x06: References ]
http://en.wikipedia.org/wiki/GSM
http://www.gsmworld.com
http://jya.com/crack-a5.htm
http://ftp.ccc.de/gsm/a512.c
-----------------------------------------------------------------------------[/]


\======================================[EOF]=====================================/