Sunday, 21 April 2013

Secrets of the SIM

First project that I would like to share is regarding the SIM card's "secret" key derivation algorithm, the COMP128.

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

23 comments:

  1. Hi
    in the file is only comp128v2 could you make the comp128v3 and comp128v1 to compare a sim card that i have.
    i want to try something
    thanks

    ReplyDelete
    Replies
    1. Sorry for the late reply.
      If you look carefully you will find that version 3 is also included in the script :)
      Version 1 is all over the internet, it has been published in 1998. But here is a link:
      http://cgit.osmocom.org/osmocom-bb/plain/src/shared/libosmocore/src/comp128.c?h=prom/dietlibc

      Delete
  2. hi m working over a project OPEN BTS IN GSM and so i want to kno how to work for obtaining imsi of a sim or should i use programmable sim...if so then how can i program it

    ReplyDelete
    Replies
    1. Hello. The easiest way is to sniff the data between the SIM card and the mobile phone while you turning it on.
      You can use this : http://bb.osmocom.org/trac/wiki/SIMtrace/Hardware

      You will have to use a programmable sim card eventually for testing.

      Delete
  3. Hi
    May I know how to find out the type of encryption algorithm which is used in SIM cards

    ReplyDelete
    Replies
    1. It will not be hundred percent true, but something like this:
      1. COMP128v1 is not used anymore, so you will probably never encounter it. 2. COMP128v2 generated Kc last byte always 0x00 3. COMP128v3 the last byte can by anything.
      After 1 or 2 challgenge-response requests you will be able to tell the version.

      Delete
  4. Dear H.P.,
    Your article is really interesting, and your skills and commitment to understand SIM technology is impressive.
    Although I would like to discuss this (or other) theme with you, I pretty much an ignorant in these matters.
    Nevertheless, congratulations.

    ReplyDelete
  5. it's very interesting.. anyway, I don't understand a thing :
    The sim card that contain algorithm v2 or next, the input for authentication on the sim card is the same?
    in other words
    step 1. sendToSim("AUTH",RAND)
    step 2. receveFromSim(SREQ,Kc)

    ReplyDelete
    Replies
    1. Yes, it's the same on all three versions of COMP128

      Delete
  6. Excellent work.

    I hope you don't mind, but i've done a C port of your algorithm and Comp128-1. They're available here:
    https://github.com/FreeRADIUS/freeradius-server/blob/master/src/modules/rlm_eap/libeap/comp128.c

    This now allows FreeRADIUS to act as an AuC for EAP-SIM authentication which is pretty neat.

    I couldn't see a license attached to your original code. It'd help us (the FreeRADIUS project), if you released your code under something like GPLv2 so there are no legal issues later down the road.

    Of course if you don't want your code redistributed in the form (above), i'll remove it from our repository.

    I've credited your website (hackingprojects.net) as being the original author. If you'd like your real name and email address listed there instead, don't hesitate to contact me (just send me a message on Google+).

    If you happen to have a document which describes Comp128-4, that'd also be very useful as it'd allow us to implement support for that also.

    Anyway, thanks again for this excellent work.

    ReplyDelete
    Replies
    1. I have posted the code for anyone to use. I'm happy for it to have landed in a project such as yours :) I believe COMP128-4 is still under development, therefore nothing to hack on it so far.

      Delete
    2. Also, I give up on Google+... can we discuss things in mail?

      Delete
    3. Sure a.cudbardb@freeradius.org

      Delete
  7. Great article. You mention in it that you worked out the command sequence to get the sysmocom grcard working. Is there any chance you can post that info? I know it would same many of us a lot of time since the documentation sysmocom has available is pretty thin.

    Thanks in advance.

    ReplyDelete
    Replies
    1. If it's still an open issue, drop me a mail. I wanted to create a new post on the technical howto, but I did not have time for that :( I still have the Python scripts somewhere...

      Delete
  8. thanks for the Article its very useful

    ReplyDelete
  9. Hello,very nice article,congratulations,can I email you?

    ReplyDelete
    Replies
    1. Sure, hackingprojectsblog at gmail.com

      Delete
  10. Is it possible to make this into an application that could be used with a card reader? I have an old card reader lying around and was hoping to put it to use.

    ReplyDelete
    Replies
    1. I don't understand the question. This algorithm should be generating the responses.
      For communicating with the sim card, a generic card reader can be used.

      Delete
  11. Great stuff. I would like to use it in my pyprotosim tool (see http://sourceforge.net/projects/pyprotosim/?source=directory)
    You will be credited and your site linked.

    ReplyDelete
    Replies
    1. Sure, go ahead. For creadits, please drop me a mail at hackingprojectsblog at gmail.com

      Delete