Martin Novotný (#466)
Topic of his/her doctorate.
Time-Area Efficient Hardware Architectures for Cryptography and Cryptanalysis
Public Key Cryptography, Elliptic Curve Cryptography, Arithmetic Unit, Binary Finite Fields GF(2^m), Normal Basis, Multiplication, Inversion, Cryptanalysis, Brute-Force Attack, TMDTO Attack, A5/1, COPACOBANA, FPGA
Year of completion
In the first part of the thesis we focus on scalable arithmetic units operating over the binary finite field GF(2^m) with a normal basis representation of the field elements. The scalability is crucial in applications of different kind - small, low power embedded devices as opposed to high-throughput backbone applications.
Although scaling by digit-serialization is a well-known method, its application to normal-basis multipliers brings problems with irregularities. Little has been done for the case when the digit width does not divide the degree of the field, although this situation is unavoidable in cryptographic applications.
In this thesis we present four architectures of the digit-serial normal basis multiplier that we developed. We demonstrate digit-serialization on the pipelined multiplier by Agnew et al., however, these methods are also applicable to other multiplier structures, e.g. the multiplier by Kwon et al. All architectures can be implemented for any digit width. Our evaluation shows that their advantages are complementary with respect to the digit width.
Based on the scalable multiplier design, we extended our work to build an entire scalable arithmetic unit. Only a shifter has to be added to support inversion. It is scaled by the number of shifts implemented in hardware. This is a special case of another little-studied problem: scaling a sub-unit in the presence of another one, dominating the design in area and time. We present an optimization method applicable to such cases.
In the second part of the thesis we focus on cryptanalysis of GSM communication, which is encrypted with A5/1 cipher. We present two attacks against A5/1 cipher. Both attacks are supported by an existing low-cost special-purpose hardware device COPACOBANA. They represent the first real-world implementations of attacks against A5/1 reported in open literature.
The first attack is a guess-and-determine attack revealing the internal state of A5/1 in about 6 hours on average (and about 12 hours at the worst-case). To mount the attack only 64 consecutive bits of a known keystream are required and we do not need any precomputed data. We also propose an optimized version of the attack. Both plain and optimized version of the attack have been fully implemented and tested on our target platform.
The second attack is a time-memory-data trade-off attack revealing the internal state of A5/1 with certain probability in a matter of minutes. COPACOBANA is used in both the precomputation phase and the online phase of the attack. When designing the precomputation engine, we have utilized the features of underlying FPGA architecture to gain the maximum performance. Here proposed design approach can be reused when designing similar attacks against other stream ciphers.
novotnym (at) fit.cvut.cz