Informatics Seminar on Friday, July 11 at 10.30 - Martin Novotny

Decanato - Facoltà di scienze informatiche

Data d'inizio: 11 Luglio 2008

Data di fine: 12 Luglio 2008

The Faculty of Informatics is pleased to announce a seminar given by Martin Novotny


TITLE: Application of FPGA Design: Design Challenges for Implementing Realtime

A5/1 Attack with Precomputation Tables


SPEAKER: Martin Novotny

DATE: Friday, July 11th, 2008

PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)

TIME: 10.30



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



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.