Tuesday, 28 April 2015

GSM WTF BBQ Pt1

Passive GSM interception Part 1

This blog post will cover passive GSM interception of phone calls and text messages. It will include some of the history of GSM and how it was broken, the newer tools and attack methods and finally a guide on how to set up a test bed for interception using TWILIGHT VEGETABLE a suite of tools designed to make cracking GSM as easy as possible.

Part 1 of this guide will cover the requirements and setting up the environment, part 2 will cover traffic capture and decryption.

GSM

Global System for Mobile Communications (GSM for short) is a suite of protocols designed for second generation (2G) mobile phone communication, put simply it's used extensively around the world for making calls on your mobile.

GSM comes with various security features to authenticate users on the network, it uses the SIM of the caller to authenticate the mobile device with the base station using a pre-shared key and challenge/response, once authenticated the calls are encrypted with a stream-cipher typically A5/1 for America and most of Europe, you can read more about A5/1 here.

History of breaking A5/1

A5/1 has a long history of attacks, the Snowden leaks showed that the NSA can easily decrypt calls, there's also rumors that the strength of the standard when it was first introduced into Europe was deliberately limited with an encryption key length of only 56bits, this made interception by government agencies easier. The security work carried out on GSM has largely been kept private and out of the public domain, there has been many white papers and theoretical attacks but few projects have ever released easy to use tools until very recently.

Weaknesses in a5/1 were known as far back as 1994, however attacks on A5/1 as used in GSM didn't occur until 2003 where downgrade attacks forcing phones on to the much weak A5/2 stream cipher were possible. In 2007 COPACOBANA was developed as an FPGA hardware solution for attacks on A5/1 and DES, this was the first commercially available attack tool. In 2008 a group called The Hackers Choice started a project to break GSM using rainbow tables, a time memory trade off attack, however the tables were never released in to the public domain.

It wasn't until 2009 that Karsten Nohl and Sascha Kri├čler announced The A5/1 cracking project at Blackhat, you can find the talk on YouTube, part 1 is here. This project is similar to prior attacks and uses a mix of time memory trade off and distinguished point chains to create 2Tb of rainbow tables, a tool for using these tables called Kraken was also released, this allowed anyone to discover a5/1 keys for encrypted portions of GSM traffic.

Use of these tools was deliberately left difficult to help stop widespread use, this is where TWILIGHT VEGETABLE steps in. TWILIGHT VEGETABLE is one of many projects that are being developed by hackers working on the NSA Playset, it's essentially a custom distribution of Kali Linux with all the tools necessary to automate GSM sniffing pre-installed. The project was introduced at DefCon 22, you can see the presentation here. The project is aimed at making cracking of GSM as easy as possible.

TWILIGHT VEGETABLE

While the project aims to make the process of decryption as easy as possible, it is still no trivial task setting up the tools, like most security work on GSM the documentation seems to be lacking and help is hard to find. Because of this I've written the following guide which will walk you through all the steps for setting up all the tools.

Requirements 

Here is everything you need in order to crack A5/1 using TWILIGHT VEGETABLE, note that while the rainbow tables are about 2Tb you'll need 4Tb of disk space total.

Hardware:
  • 2Tb USB external hard drive
  • 2Tb of additional storage
  • 16Gb USB flash drive
  • A USB SDR dongle based off the RTL chipset - example here
  • A laptop
Software:
  • Something that can uncompress .bz2 files, for windows I recommend 7zip from here.
  • The 7Gb compressed Twilight Vegetable image from here.
  • Something to write images to the USB drive, I recommend Win32 Disk Imager from here.
  • The 1.6Tb of Kraken GSM Rainbow tables, the torrents can be found here.


Step 1 - Create a TWILIGHT VEGETABLE bootable USB

The first step is to create a bootable USB flash drive with a install of TWILIGHT VEGETABLE. First you'll need to download the TWILIGHTVEGETABLE image from the link above, you'll also need some software to extract the image from the compressed bz2 file, on windows you can use a compression tool called 7zip, linked above. Once 7zip is installed, select the file "TWILIGHTVEGETABLE-1.0.img.bz2" file and extract the image, you'll need approximately 15.2Gb of space.

Plug in your 16Gb USB flash, make sure it doesn't contain any files you want to keep, as the following steps will erase everything on the drive. 

Download and install Win32 Disk Imager from the link above. Make sure you right click the applications and "run as administrator". Open the file browser and select your TWILIGHTVEGETABLE-1.0.img file. Use the device drop down menu and select the drive letter of your USB flash drive - it's important to get the drive letter right!

Click the "Write" button to write the contents of the img to the USB key, once this is finished you will have a bootable USB flash drive with all the tools you need.

Step 2 - Prepare your external 2Tb HDD

This next step is to create DRIZZLECHAIR by writing the rainbow tables into a partition on the external drive, they cannot simply be copied on to the drive, they're inserted inside a partition using a special tool, this is why you need an additional 2Tb of space on top of the 2Tb external drive.

Turn off the computer you want to use for copying the tables and insert your TWILIGHT VEGETABLE USB drive, then boot the machine from the USB key, in some cases this will happen automatically, otherwise you'll need to enter into your BIOS settings and set the boot order to boot from USB first, if you need to do this consult your motherboard manual for BIOS instructions. Once you've booted off the USB drive, select persistent mode to load Kali.

First you need to identify which mount name your 2Tb drive has, this step is crucial because if you get this wrong you'll delete the partitions on the wrong drive and if you accidentally delete the rainbow tables you'll be extremely mad. For the rest of this tutorial I'm going to use the mount name "sdz" you need to replace all instances of "sdz" in the instructions with your mount point name for the external drive, this will be different depending on your system. I am not responsible for any data loss if you do these steps incorrectly!

Open a terminal window and enter the following commands one at a time, remembering to replace ALL instances of sdz with your mount name.

umount /dev/sdz1
parted /dev/sdz rm 1
parted /dev/sdz mkpart primary 0g 5g
parted /dev/sdz mkpart primary 5g 100%
partprobe /dev/sdz
mkfs.ext3 -L DRIZZLECHAIR /dev/sdz1
e2label /dev/sdz1 DRIZZLECHAIR
partprobe /dev/sdz

These commands will mount the drive, remove any existing partitions, then it will create a 5Gb partition at the start of the drive (sdz1) where you can store the tools if you wish, and then create a 2nd partition (sdz2) which fills the rest of the drive which is where the rainbow tables will live, finally we format sdz1 with a file system and give it the label DRIZZLECHAIR. The drive is now prepared.


Step 3 - (OPTIONAL)

This step is optional depending on where you store your rainbow tables, if they're on a local disk attached to the computer you're booting off then skip straight to step 4.

For me the tables are shared on a file server on my network since my laptop doesn't have 2Tb of internal disk space, this step covers connecting Kali to a network share so you can copy files across the network. Beware this method is much slower than copying from an internal drive, an internal drive copy speed will take approximately 10 hours but across a wireless network it took about 3 days.

To connect to a windows share I installed cifs because I had trouble getting smb working, to install cifs make sure you have internet access, open a terminal window and type:

sudo apt-get install cifs-utils

Now create the mount point you want to use, you first need to create a new folder which I made at /mnt/gsm

cd /mnt/
mkdir gsm

Then you can mount your network share with the following command, replace "###.###.###.###" with the IP address of your network share, and "sharename" with the name of the shared folder. The 2nd path is where the share will be mounted to.

mount -t cifs //###.###.###.###/sharename /mnt/gsm

Double check you can browse this directory, if you get a permissions error make sure to set the shared folder settings to allow guest/anonymous access.


Step 4 - Preparing tools for use

The tool to insert the tables on to the drive is called TableConvert it's not actually compiled into the binaries so we need to do that first. Open a terminal window and browse to the TableConvert directory with:

cd /root/kraken/TableConvert

then compile the binaries by typing:

make TableConvert

We're not going to use this tool directly, we're going to use a wrapper called Behemoth.py which is a python tool already on the system in the /root/kraken/indexes directory. However the version that comes with the current version of TWILIGHT VEGETABLE is out of date and requires some extra work sym linking directories before use, it's just easier to download the latest copy of Behemoth.py with this already fixed. You can download this on github here, make sure to place it in the index directory and overwrite the current one.

Next we need to set up the config file which will point TableConvert to the right partition to insert the tables into. You need to make a copy of the sample conf file, in your terminal window type:

cp tables.conf.sample tables.conf

Now open this new tables.conf file for editing and remove the list of example devices and replace them with your drive and partition, the partition number will be 2, remember to replace sdz with your drive name. It should look something like this:

#Devices: dev/node max_tables
Device: /dev/sdz2 40
#Tables: dev id(advance) offset

The max tables value is set at 40 because there's 40 individual tables and we want them all on the same drive. Make sure to save changes to this file.

The last step is to copy all of the files from the /root/kraken folder in to the 5Gb partition at the start of the drive, when the tables are inserted into the external drive during the next step, index files are generated in the /indexes/ folder which are about 3.2Gb total, if you only have a 16Gb flash drive then you'll run out of space.

Mount the first partition of your DRIZZLECHAIR drive somewhere so you can get access via the terminal, I created a new directory in the /mnt/ folder called drizzlechair first,

cd /mnt/
mkdir drizzlechair

Then in a terminal type the following, remember to replace sdz with your drive name.

sudo mount -t ext3 /dev/sdz1 /mnt/drizzlechair

Copy the entire kraken folder to the DRIZLLECHAIR drive

cd /root/kraken
cp -R * /mnt/drizzlechair/kraken


Step 5 - Inserting the rainbow tables into the partition

Now to start the copy, make sure if you're using a laptop the power cord is in and nothing will interrupt the copy process, this step takes a long time. In a terminal window type:

cd /mnt/drizzlechair/kraken/indexes

Now type the following replacing "/mnt/gsm" with the directory you've stored the rainbow tables.

sudo python Behemoth.py /mnt/gsm

Sit back and relax, you'll get info pop up on the screen to tell you what table is currently being copied, you have a 10 hour wait from an internal drive or a something closer to 72 hours across a network.


Step 6 - The you dun goof'd step (OPTIONAL)

If for any reason the process is interrupted you can resume it, you'll first need to make note of the last table name that was being written to the drive. Simply trying to resume it by running Behemoth again will it will skip all the tables, you need to remove entries from the tables.conf file 

Open the tables.conf file for editing and you'll see this file now has an entry for all the tables, one per line, simply delete the lines of the tables that have not been written including the the last partially written one, save changes to the file. Now delete any index (.idx) files in the indexes directory for any tables that weren't written, they're given the same name as the table number.

Then run Behemoth again, it will skip all the other tables with entries in tables.conf and resume where it ended.


Step 7 - Testing

Lastly we test Kraken, switch to the kraken directory

cd /mnt/drizzlechair/kraken/Kraken

Run Kraken and give it the directory where the indexes are stored

./kraken /mnt/drizzlechair/kraken/indexes

Now run the test command

test

It should run a test string of binary, a reasonable speed from an external drive is about 160 seconds on average, I get about 180-185 seconds but it depends on your hardware, USB version, drive speed etc.

Next time on FrostyHacks

In part 2 of this guide I will cover capturing GSM traffic with a USB RTL-SDR device and the steps to extract the keys to submit to Kraken. It will be available as soon as I've got everything working myself!

I appreciate any comments and feedback both positive and negative, especially if there's any mistakes that need correcting. You can also contact me on Skype for help or if you're willing to assist with the SDR steps. SkypeID: frostyhacks

11 comments:

  1. Cant wait for part 2. Finally somebody exaplined it.

    ReplyDelete
  2. Waiting for part 2 , mail me when its ready

    Mohit123q@gmail.com

    ReplyDelete
  3. is there a mirror for the TWILIGHT VEGETABLE image? looks like it was taken down

    ReplyDelete
  4. Hi,

    I can upload it someplace but it has to be at least 8Gb free storage

    ReplyDelete
  5. hi
    This is a great tutorial, can you help me with Kraken ? I have it all set up right but for some reason it only gives me the line :
    crack #0 took 128689 msec

    and not the

    Found .....

    ReplyDelete
  6. Wondering if there's a different procedure if I ordered my Tables from Hacker Warehuose? Seems like there's already DRIZZLECHAIR folder on the drive they sent along with the tables. I have a 2nd 2 TB drive that's I've formated and made ready for tables.

    ReplyDelete
  7. Hi, what about part 2? I hope it will be available soon. Thumbs up for this tutorials.

    ReplyDelete
  8. Old post but ...


    this omits the 2006 attack described here
    http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf
    "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted
    Communication"

    Far easier, takes less cpu, faster than Kraken, less disk space, and older than the rainbow table project. And completely omitted from the history of A5 attacks. This is NOT the 2003 downgrade attack. The 2003 downgrade attack can be found here http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2003/CS/CS-2003-05.pdf whch has the same title as the 2006 paper.

    ReplyDelete
    Replies
    1. How much timeit takes for decryption? I mean one key in how many seconds?

      Delete
    2. Hello there, i was inquisitive, about the practical implementation of the "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted". Can you provide me some description (such as source code) for the A5/1 decryption.

      Delete