It's everywhere in the news, and I couldn't resist trying to figure out how it works. I think I roughly found out but we'll have to wait for Karsten Nohl's presentation at BlackHat to see if I was right :)
Mobile phones are capable of receiving OTA (Over The Air) commands ('update', 'get status'...) in the form of SMS messages sent by their service provider. Fortunately, those messages support encryption and integrity checks.
More specifically, the secure packet header specifies the algorithm and key set identifier to use for ciphering (KIc) and the algorithms and key set identifier to use (KID) for packet's integrity. The keys are pre-shared secrets known by both entities (SIM card and provider), and the key set identifier is like an index in the table of keys attached to the relevant SIM.
Figure 1. OTA commands sent by SMS. Trustworthy entities share secrets with the SIM cards, but an attacker can craft an OTA SMS to retrieve the keys
An attacker can intentionally craft a corrupted command packet whose integrity fields are corrupted. The problem lies in the response of the SIM card. Some implementations talk a bit too much and their response contains the error code (this is normal) but also valid integrity fields for the packet (usually, it is better to simply drop error messages or provide a minimal response). Thus, the attacker knows the plaintext (an error response) and the ciphertext. Doing what cryptanalysts call a known-plaintext attack, the attacker can recover the key (KID). This is particularly easy to do when the algorithm is weak, such as DES. As a matter of fact, Mr Nohl claims he recovers the integrity key in 2 minutes using rainbow tables.
Unfortunately, it seems that several SIM cards (not all though), still use DES. The specs I read mentioned the use of DES-CBC or DES-ECB (even worse!), 3DES2-CBC or 3DES3-CBC for KIc, and DES-CBC, 3DES2-CBC or 3DES3-CBC for KID.
Figure 2. Coding of KID as specified in 3GPP TS 23.048 V5.9.0
The attacker's got the key. So what?
With the correct OTA integrity key, the attacker can craft correctly signed OTA SMS messages, and use those for instance to install Java applets on the SIM card. As Mr Nohl points out, the applets can do plenty of nasty things (send SMS, query phone location etc), especially when the implementations of Java sandbox are flawed.
That's not all. Actually, OTA SMS messages can also be used to install ELF binaries on the SIM card. See 3GPP TS 31.131. There's an impressive API (CatSendShortMessage, CatSetupCall, CatLaunchBrowser), and so plenty of opportunities for an attacker - without even needing to abuse Java sandboxing.
As recent SIMs have up to 1 GB of storage capacity, there's far enough space on the SIM to install malicious programs. A trojan downloader would be particularly convenient for an attacker.
Is my SIM card affected?
Actually, it is somewhat difficult to check what algorithm our SIM card is using.
One possibility consists in sniffing the SMS packet and inspecting the fields KIc and KID to make sure 3DES is mentioned (3DES, unlike DES, is not easy to brute force). However, using 3DES once does not mean 'single' DES is not used in other cases, because a SIM can carry both DES and 3DES key sets. So we'd actually need to check all OTA SMS messages and make sure none ever uses DES...
Another possibility consists in inspecting the SIM card itself and checking that all possible OTA key sets (there are up to 15) have keys whose length is greater or equal than 128 bits, which means Triple DES is being used (let's hope however that OTA won't ever use the first 64 bits of a 3DES key as a DES key if the OTA command header specifies use of DES!).
But where are those keys stored? SIM cards store data using a special file system. See 3GPP TS 51.011. Each information corresponds to an Elementary File (EF) located in a tree-like architecture. The top node is named 'Master File' (MF). Then, there are typically the GSM and the Telecom subnodes etc.
According to the document below, the OTA key KID should be located in MF (3f00) - EF 2fe6. Unfortunately, the SIM cards I tried out had nothing in that field :(
Figure 3. Location of KID elementary file in the SIM card
I used a small Linux utility named simdump to read the contents of my SIM card.
sudo ./dump phoenix:/dev/ttyUSB0 ATR: 3b 16 94 d0 00 13 00 30 00 probably USIM - aborting 3f00 MF (MF) 3 DFs 3 EFs 7f10 DF_TELECOM (DF) 0 DFs 10 EFs 7f20 DF_GSM (DF) 0 DFs 22 EFs 7f21 DF_DCS1800 (DF) 0 DFs 22 EFs 7f45 ??? (DF) 0 DFs 35 EFs read ofs 0 len 19 9804 read ofs 0 len 13 9804 read ofs 0 len 114 9804 ... 6f20 EF_KC (EF) transp status 01 size 9 rec_len 0 0000: ce ns ur ed va lu ef or kc
In that dump, note that Kc (8 bytes + a trailing 1-byte key sequenece number), the SIM's session cipher key, is not the key we are looking for. I'll let you know if I find out...
To conclude, Karsten Nohl's finding is more about exploiting a flaw in OTA SMS messages, and then using that to install malicious native or Java code on the SIM... which basically results in 0wning the SIM card.
-- the Crypto Girl