Design and Implementation of Efficient and Secure Lightweight Cryptosystems

In recent years there has been a wide-spread deployment of battery-powered and passive devices such as RFID tags, systems with very strong limitations on area, cost and power budgets. Deploying cryptographic solutions for these systems is both important, because it could unlock several security-critical applications, and challenging, due to the stringent budgets: the overheads of even the smallest block ciphers are often one or more orders of magnitude too high. Because of this reason there is a growing interest in lightweight cryptography, a discipline that tries to develop cryptographic solutions for systems with very tight cost, area and power constraints. The importance of lightweight cryptography is forecasted to continue growing in the future, with lightweight systems becoming more ubiquitous and more common in sensitive applications.In this work we analyse and solve several problems related to light weight cryptography. We first study efficient implementations of feedback shift registers (FSR)-based cryptosystems, such as stream ciphers and hash functions, that are especically designed for highly-constrained environments. The core of our solution is to apply a Fibonacci-to-Galois transformation that changes the structure of an FSR to minimise its critical path. Along with this transformation we apply several hardware optimization techniques, such as pipelining and double-frequency clock generators, that are necessary to obtain through-put benefits. Our results show impressive throughput improvements (100% for some cryptographic systems) without any area and power penalties. In a second part, we show how to protect FSR-based stream ciphers from power analysis attacks, a type of attack that exploits the information content in the power trace of a system. It is well known that, due to their very simple hardware structure, FSR-based stream ciphers are very vulnerable to this type of attacks. We introduce two different countermeasures against power analysis attacks: one at the architectural level (masking the switching activity of the FSRs) and the other one at the physical level ( flattening the power curve to one among two power levels). Both solutions exploit the properties of FSR-based stream ciphers with the specic goal to minimise their area and power overheads. We demonstrate them on the FSR-based stream cipher Grain by performing Differential Power Analysis (DPA) and Mutual Information Analysis (MIA) attacks at SPICE level. However, the techniques we introduce are general and can potentially be applied to any FSR-based stream ciphers. In a third part, we focus on Ring Oscillator Physical Unclonable Functions (RO-PUFs), a type of digital fingerprint used for chip identication that is well-suited for lightweight cryptography. We suggest solutions to two well-known problems related to this type of PUF: how to generate a secure and large challenge-response database and how to increase PUF reliability in presence of temperature variations. We validate our solutions at SPICE level by modelling the random variations introduced during manufacturing.QC 20140224