Breaking the GSM A5/1 cryptography algorithm with rainbow tables and high-end FPGAS
- 1 August 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1946147X,p. 747-753
Abstract
A5 is the basic cryptographic algorithm used in GSM cell-phones to ensure that the user communication is protected against illicit acts. The A5/1 version was developed in 1987 and has since been under attack. The most recent attack on A5/1 is the “A51 security project”, led by Karsten Nohl that consists of the creation of rainbow tables that map the internal state of the algorithm with the keystream. Rainbow tables are efficient structures that allow the tradeoff between run-time (computations performed to crack a conversation) and space (memory to hold pre-computed information). In this paper we describe a very effective parallel architecture for the creation of the A5/1 rainbow tables in reconfigurable hardware. Rainbow table creation is the most expensive portion of cracking a particular encrypted information exchange. Our approach achieves almost 3000× speedup over a single processor, and 2.5× speedup compared to GPUs. This performance is achieved with less than 5 Watt power consumption, achieving an energy efficiency in the order of 150x better that the GPU approach.Keywords
This publication has 7 references indexed in Scilit:
- Characterization and Improvement of Time-Memory Trade-Off Based on Perfect TablesACM Transactions on Information and System Security, 2008
- Cryptanalysis with COPACOBANAIEEE Transactions on Computers, 2008
- A Real-World Attack Breaking A5/1 within HoursLecture Notes in Computer Science, 2007
- Making a Faster Cryptanalytic Time-Memory Trade-Off2003
- Cryptanalysis of the A5/1 GSM Stream Cipher2000
- Cryptanalysis of Alleged A5 Stream Cipher1997
- A cryptanalytic time-memory trade-offIEEE Transactions on Information Theory, 1980