Deka - an OpenCL A5/1 cracker
Deka is a fast, free and portable A5/1 (that's the cipher used in mobile phones) cracker written in OpenCL. Thanks to efficient use of vector instructions and hard-drive NCQ, the Kc key on a real-world GSM network can usually be recovered in 5-60 seconds with 2 minutes RTT (i.e., cracking many keys in parallel) depending on network security, signal quality etc. (test machine is a high-end desktop: 8 core AMD FX-8150, 32 GB RAM, 3x ATI HD 7970, 4x ADATA SX900)
Deka started as an attempt to port Kraken, the first A5/1 cracker available, to AMD GCN architecture, and resulted in a complete rewrite. Deka is binary compatible with Kraken, allowing easy evaluation and seamless switch.
- Deka is portable. It runs on every platform where Python, GCC and OpenCL work.
- Deka is fast. The kernel is fully vectorized, including the final challenge lookup, and we ship kernels for architectures supporting 128- and 256-bit vectors. The table lookup is using NCQ and stripping unnecessary syscalls to minimize computing overhead.
- Deka is clusterable. Work is distributed over TCP. You can run more nodes to speed cracking up.
- Deka is modular. You can, for example, write A5/1 chain generator in VHDL, load it to a FPGA, and you just need to change a few lines of code to make it work with deka.
- Deka is, we hope, easier to understand. For example you can enjoy comments in the source code :)
To be honest, there are some.
- Deka is more difficult to set up than Kraken, as there is no automated tool to configure tables (yet).
- Deka is still dependent on Kraken (with Kraken's unclear licensing terms), as we do not have our own table converter and A5/1 backclocker.
- Deka is burst-oriented, which worsens round-trip-time for real-time cracking by approximately a factor of two.
Nice to have features:
- “cancel” command to cancel processing of a given burst. This is useful when the key is successfully recovered and so there is no use to continue computing.
- delta.py does not use barriers/conditional variables, but busy waiting
- paplon.py leaks memory – reportqs are not freed when the client disconnects
Attack in a nutshell
TL;DR You can go through the A5/1 keyspace and save some “distinguished points”. When you want to recover the key, you reconstruct the keyspace from the nearest distinguished point. (I want to know more!)
Deka listens on a TCP socket, waits for a keystream and once you submit one, it finds a secret state that resulted in this keystream. Hence you need some GSM sniffer, keystream guesser, TCP client and secret state processor. gsmtk implements exactly that.
We need to do an equivalent of 5 billion A5/1 encryptions and read 200k pseudorandom 4KiB blocks from disk to crack a key on an insecure network (multiply with 10 on secure network).
- Computer running a recent Linux distribution (Deka has been developed on Debian Jessie with HD7970 cards, but definitely should work on other distributions and probably on other UNIX systems too), 64bit (we need a 64bit system as we allocate lots of memory)
- CPU power which depends on the rest of the system. For example an AMD FX-8150 can process 120 kfrag/s.
- 8 or better 16 GB RAM to fit the table index, track bursts and have some space for block cache
- OpenCL capable card, or several of them
- Deka has been tested on AMD HD7970 and nVidia GTX 610M (which is of course slow).
- 1.7TB of fast storage - SSDs at best. And probably some SATA controller that does not have problems with lots of random reads.
- A5/1 TMTO attack description - a theoretical overview of the attack
- Attack implementation - an efficient practical implementation on real hardware
- Architecture overview - architecture overview, protocol and data structures
- Installing deka - getting deka to work on your computer
- deka-test - test vectors to test your setup works correctly
- Ability to read the installation manual and comments in configuration files.
- Understanding the concept of “files”, “directories”, “devices” and “addresses”.
- Understanding the concepts of “Makefile”, “compiler” and “JIT”.
Please don't take this as some meanness, I just started getting tons of emails from people who obviously don't follow. If you have found a real bug, have some improvement, or are just interested in technical discussion, you are welcome.
- Řehoř Gölöncséryi (niekt0) and Tomash (sysop) for introducing me to GSM security and the GSMstack toolkit and advice regarding how wrong it is and what should I do better.
- Kraken team, as there is very few documentation available - reading their sources was a great help in understanding the attack.
- blanket (cz)
- a method of torture particularly popular among soldiers in former Czechoslovakia
Vankúš is Slovak for a small rodent gopher; the userspace OpenCL library called oclvankus may resemble another cracker, oclhashcat.
Paplón is Slovak for goose.