Lightweight cryptography on ultra-constrained RFID devices

Hamann, Matthias

Vorschau

PDF
dissertation-hamann-2018.pdf - Veröffentlichte Version
Download (7MB)

URL:	https://madoc.bib.uni-mannheim.de/45091
URN:	urn:nbn:de:bsz:180-madoc-450910
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2018
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Krause, Matthias
Datum der mündl. Prüfung:	22 Mai 2018
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	Kryptologie , RFID , Authentifikation , Stromchiffre
Freie Schlagwörter (Englisch):	Lightweight Cryptography, Ultra-Constrained RFIDs, Lightweight Authentication, Lightweight Stream Ciphers, Small-State Stream Ciphers, LIZARD, Provable Security, Time-Memory-Data Tradeoff Attacks, BDD Attacks
Abstract:	Devices of extremely small computational power like RFID tags are used in practice to a rapidly growing extent, a trend commonly referred to as ubiquitous computing. Despite their severely constrained resources, the security burden which these devices have to carry is often enormous, as their fields of application range from everyday access control to human-implantable chips providing sensitive medical information about a person. Unfortunately, established cryptographic primitives such as AES are way to 'heavy' (e.g., in terms of circuit size or power consumption) to be used in corresponding RFID systems, calling for new solutions and thus initiating the research area of lightweight cryptography. In this thesis, we focus on the currently most restricted form of such devices and will refer to them as ultra-constrained RFIDs. To fill this notion with life and in order to create a profound basis for our subsequent cryptographic development, we start this work by providing a comprehensive summary of conditions that should be met by lightweight cryptographic schemes targeting ultra-constrained RFID devices. Building on these insights, we then turn towards the two main topics of this thesis: lightweight authentication and lightweight stream ciphers. To this end, we first provide a general introduction to the broad field of authentication and study existing (allegedly) lightweight approaches. Drawing on this, with the (n,k,L)^<80>-protocol, we suggest our own lightweight authentication scheme and, on the basis of corresponding hardware implementations for FPGAs and ASICs, demonstrate its suitability for ultra-constrained RFIDs. Subsequently, we leave the path of searching for dedicated authentication protocols and turn towards stream cipher design, where we first revisit some prominent classical examples and, in particular, analyze their state initialization algorithms. Following this, we investigate the rather young area of small-state stream ciphers, which try to overcome the limit imposed by time-memory-data tradeoff (TMD-TO) attacks on the security of classical stream ciphers. Here, we present some new attacks, but also corresponding design ideas how to counter these. Paving the way for our own small-state stream cipher, we then propose and analyze the LIZARD-construction, which combines the explicit use of packet mode with a new type of state initialization algorithm. For corresponding keystream generator-based designs of inner state length n, we prove a tight (2n/3)-bound on the security against TMD-TO key recovery attacks. Building on these theoretical results, we finally present LIZARD, our new lightweight stream cipher for ultra-constrained RFIDs. Its hardware efficiency and security result from combining a Grain-like design with the LIZARD-construction. Most notably, besides lower area requirements, the estimated power consumption of LIZARD is also about 16 percent below that of Grain v1, making it particularly suitable for passive RFID tags, which obtain their energy exclusively through an electromagnetic field radiated by the reading device. The thesis is concluded by an extensive 'Future Research Directions' chapter, introducing various new ideas and thus showing that the search for lightweight cryptographic solutions is far from being completed.