ALaRI Hang Glider

Search form

Education and Innovation in Embedded Systems Design

USI Università della Svizzera italiana, USI Faculty of Informatics, Advanced Learning and Research Institute USI Università della Svizzera italiana USI Faculty of Informatics USI Advanced Learning and Research Institute

Seminar: Application of FPGA Design: Design Challenges for Implementing Realtime A5/1 Attack with Precomputation Tables

Friday, July 11, 2008

Speaker: Martin Novotny 


GSM communication is encrypted with A5/1 stream cipher. Many attack scenarios against GSM have been proposed, however none of them was fully implemented. The first real-world attack appears to be the smart brute-force attack recently developed and implemented in Chair for Embedded Security, Ruhr-University Bochum. When using COPACOBANA machine, the cipher can be broken in less than 6 hours on average. Another approach is to use precomputed time-memory trade-off (TMTO) tables. This method allows for very fast attack, e.g. A5/1 cipher might be broken in a couple of minutes. However, precomputation of TMTO tables demands extensive computation power and hence it may last from several weeks up to several thousands of years, depending on both the cipher and the computation platform.

In our talk

  1. we will introduce COPACOBANA, the cluster of 120 low-cost FPGAs. COPACOBANA is well-suited for highly-parallelizable tasks of cryptanalysis, bioinformatics, and others.
  2. we will discuss variants of TMTO methods, their advantages and drawbacks with respect to the actual cipher and with respect to efficient hardware implementation.
  3. we will present a hardware engine calculating TMTO tables for A5/1. The engine was designed and implemented for COPACOBANA machine. We will discuss how we utilized certain properties of Xilinx FPGAs and what design choices we made to gain high performance of the machine


This was a joint work with Andy Rupp of Ruhr University Bochum

Short Bio
Martin Novotny received his master's degree in electrical engineering from the Czech Technical University in Prague in 1992. Currently, he is a Ph.D. student at the Czech Technical University in Prague and at the Ruhr-University Bochum. His research interests include embedded systems, digital design, arithmetic units, cryptanalytical hardware and efficient hardware implementation of cryptographic algorithms.