AbstractsComputer Science

RFID authentication and time-memory trade-offs

by Xavier Carpent

Institution: Université Catholique de Louvain
Department: Pôle en ingénierie informatique
Year: 2015
Keywords: Security; Privacy; Cryptography; Authentication
Record ID: 1077119
Full text PDF: http://hdl.handle.net/2078.1/157885


RFID is a technology that allows identification and authentication of objects or persons through the use of wireless communication between tags and readers. RFID Tags are small devices that are comprised of an antenna (for receiving/transmitting data) and a chip. Although exceptions exist (e.g. passports, etc.), tags are generally inexpensive and moderately powerful in terms of computation. Due to the high requirements (secure authentication, respect of privacy, speed of authentication, etc.) and specific constraints (asymetric system, inexpensive tags, wireless communication, etc.), there are many challenges in RFID security. Mostly two have been studied in this thesis: ultralightweight authentication (authentication protocols dedicated to extremely low-end tags where classical crypto is deemed too expensive) and the complexity/privacy tradeoff (protecting privacy makes the task of readers very time-consuming). In the former, our results are mostly cryptanalytic (almost all ultralightweight protocols are broken), and in the latter where, it seems, no perfect solution exists, our results are mainly analytical and comparative (the OSK/AO protocol in particular achieves good privacy protection with reasonnable complexity, and uses cryptanalytic time-memory tradeoffs that is the focus of the second part of the thesis). A cryptanalytic time-memory tradeoff is a tool to carry out brute force search for the pre-image of a one-way function efficiently. They are a compromise between the online exhaustive search (no precomputation, searching through all the possibilities) and the lookup table (all possibilities precomputed and stored, and then looking up when needed) approaches. In the former, no precomputation or memory is required, but the search is expensive, and in the latter, precomputation and storage is expensive, but the search is nearly instant. Time-memory tradeoffs are a compromise between these two solutions. In this thesis, ways to improve the performance of existing techniques have been explored, among which fingerprints (in which stored information is slightly different than in classical time-memory tradeoffs, which results in a speedup in the online phase), storage optimization (which reduce the storage of time-memory tradeoffs), and interleaving (which accelerates the search when there is a bias in the input probability distribution). (FSA - Sciences de l)  – UCL, 2015