I was requested to put together a small presentation about the old GSM system's security at my former employer.
As I really hate presentations without any real hands on experience, I wanted to actually show the internal mechanisms of the SIM and the mobile phone as well as the base station's communication in the presentation so I did a "quick" search (took two days) about the current situation of GSM related software and tools available to a simple person, that can be used to put together something interesting.
The results are a bit shocking... but in a good way :)
I will describe the mobile phone and the BTS emulation part later, since all of the information about them can be found on the Internet already.
To show the internal mechanisms of a SIM card as well as the communication between the SIM and the mobile phone, I found the following tools to be handy:
1. SimTrace
This little hardware is awesome!!! It sniffs the communication between the SIM and the telephone and integrates into Wireshark with a normal dissector for parsing the raw data, so you are able to see what goes on the wire on-the-fly.
2. A programmable SIM card
This programmable SIM can be used like a standard SIM but you can actually change the master key (Ki) used for key derivation. Also it can switch the used derivation algorithms (COMP128 v1/v2/v3), which is really handy.
And that's it for tools. For the next step to put this part of the presentation together I had to refresh my memory about how the authentication and encryption is carried out in GSM. Wikipedia and Google is here to help as always.
Security features in GSM in a nutshell:
1. Challenge-Response Authentication
2. Symmetric encryption (A5)
The common secret is a 16 byte number stored in the SIM card and also it's stored at the respective mobile operator, it is called "Ki". Since the SIM is a smartcard, it is considered secure and we all hope that our mobile operator is storing it in a real secure way also :).
(otherwise every call and data could be decrypted if it falls in the wrong hands)
GSM authentication
1. The base station sends a 16 byte random number RAND (I'm really curious if it's really random...)
2. The SIM card gets this RAND and uses the Ki (the secret number) to feed the A3A8 (other name is COMP128) algorithm. The output is a 12 byte long number, call it OUTPUT.
3. The OUTPUT is split into two parts, the upper 4 byte is called the SRES the lower 8 byte is the Kc.
4. The SRES will be sent back to the base station as the authentication response.
----
on the other end of the line, the mobile operator does that same algorithm, because he knows our key (Ki), he will calculate the SRES and the Kc. If the mobile operator's SRES matches the SRES we sent back, then we are authenticated on the network
-----
5. The Kc is sent to the mobile phone from the SIM card. It will be used as the encryption key for the A5 algorithm (not discussed here)
Key derivation
Using SIMTrace and Wireshark, we can see that the mobile phone sends only one command to the SIM card together with the RAND, and the card sends back the SRES+KC bytes. This can be observed in plain text :)
The big question remained, that how does exactly the COMP128 algorithm work?
After some searching I found that there are three versions of the COMP128, but only the first one could be found available for everyone.
--------------------
A little history: after version 1 of the COMP128 got published it turned out that from observing the input and the output of the algorithm for several inputs, one can easily recover the secret key Ki. This means SIM card cloning! And also means, that if someone previously "checked" your sim card before you obtained it from the shop or from your company, he will know the secret key so if he manages to sniff your calls over the air, he will be able to decrypt the communication without much effort. So far only version 1 is known to be weak against this birthday-paradox based attack,and this is why it's not used any more (discontinued in 2002).
Since version 2&3 have not been officially published (again I have not found any publication of it so far), excessive cryptanalysis probably have not been carried out on it (khmm.... just saying...)
--------------------
It seems that version 2 and 3 has not been published yet, or I was looking on the wrong Google?
So I kinda became frustrated that this presentation will be a bit incomplete, so I decided to dig a bit further. Luckily I "found" a test software used for SIM card compliance checks, which had the feature to check the version 2 & 3 of the algorithm also! Only one thing was left, reverse engineer the software to get to know the actual algorithm and then check against a valid implementation to be sure -remember the programmable SIM card I mentioned? :).
Using IDA I was able to recover the two algorithms from the software and implemented them to pure python. (Have I mentioned that I love Python?) It took some time, but I think it was a really good opportunity to learn a bit more about IDA :)
The testing part almost took the same time as the reverse engineering, because the command to change the algorithm of the programmable SIM was not working as described in the documentation -if we can call that poorly written nothing documentation- (I'll post the working command but right now I don't know where I have put it)
For this, I have written a small python script to load a key into the programmable SIM, generate 1024 random 16 byte long RAND number, then send it as the argument of the AUTH command, and store the response. (doing this to both v2 and v3 is like a little brute forcing huh?) Another script was responsible to cross check the results from the SIM with the result from the python script. No errors were found :) This however doesn't mean that my implementation of the COMP128v2 and v3 is perfect and completely following the standard (as this part of the standard is not published as far as I know), so please check it yourself and let me know the details.
Some words about the COMP128.
In v1 and v2 the last byte of the Kc was always 0x00, and the byte before the last was guessable -could only be 4 different value if I remember correctly, This means that the key used to encrypt your communication was weakened on purpose. In v3 this "limitation" was finally removed, but that doesn't help much to increase the security since the encryption algorithm used in GSM communication (A5) is officially broken. If you want security switch to 3G, the algorithms used for encryption and authentication there are public and so far there are not publicly known weakness in them (as far as I'm aware)
I hope by sharing this algorithm I help everyone who wants to know how the SIM card works to get a better understanding. I was thinking about implementing this algorithm into a Java card thus creating programmable SIMs, or using it as a software emulated SIM solution to test some weaknesses in the GSM network but so far I have a lot of work to do, If someone will do this please drop me a mail :)
Implementation and some test vectors -not a well defined test vector set I know-:
comp128.7z
Thank you for reading!
p.s.: this is my first blog ever, suggestions how to do it better are always welcome
