Design and Analysis of Security Schemes for Low-cost RFID Systems (2012)

With the remarkable progress in microelectronics and low-power semiconductor technologies, Radio Frequency IDentification technology (RFID) has moved from obscurity into mainstream applications, which essentially provides an indispensable foundation to realize ubiquitous computing and machine perception. However, the catching and exclusive characteristics of RFID systems introduce growing security and privacy concerns. To address these issues are particularly challenging for low-cost RFID systems, where tags are extremely constrained in resources, power and cost. The primary reasons are: (1) the security requirements of low-cost RFID systems are even more rigorous due to large operation range and mass deployment; and (2) the passive tags' modest capabilities and the necessity to keep their prices low present a novel problem that goes beyond the well-studied problems of traditional cryptography. This thesis presents our research results on the design and the analysis of security schemes for low-cost RFID systems.&#13;\n&#13;\nMotivated by the recent attention on exploiting physical layer resources in the design of security schemes, we investigate how to solve the eavesdropping, modification and one particular type of relay attacks toward the tag-to-reader communication in passive RFID systems without requiring lightweight ciphers. To this end, we propose a novel physical layer scheme, called Backscatter modulation- and Uncoordinated frequency hopping-assisted Physical Layer Enhancement (BUPLE). The idea behind it is to use the amplitude of the carrier to transmit messages as normal, while to utilize its periodically varied frequency to hide the transmission from the eavesdropper/relayer and to exploit a random sequence modulated to the carrier's phase to defeat malicious modifications. We further improve its eavesdropping resistance through the coding in the physical layer, since BUPLE ensures that the tag-to-eavesdropper channel is strictly noisier than the tag-to-reader channel. Three practical Wiretap Channel Codes (WCCs) for passive tags are then proposed: two of them are constructed from linear error correcting codes, and the other one is constructed from a resilient vector Boolean function. The security and usability of BUPLE in conjunction with WCCs are further confirmed by our proof-of-concept implementation and testing.&#13;\n&#13;\nEavesdropping the communication between a legitimate reader and a victim tag to obtain raw data is a basic tool for the adversary. However, given the fundamentality of eavesdropping attacks, there are limited prior work investigating its intension and extension for passive RFID systems. To this end, we firstly identified a brand-new attack, working at physical layer, against backscattered RFID communications, called unidirectional active eavesdropping, which defeats the customary impression that eavesdropping is a ``passive" attack. To launch this attack, the adversary transmits an un-modulated carrier (called blank carrier) at a certain frequency while a valid reader and a tag interacts at another frequency channel. Once the tag modulates the amplitude of reader's signal, it causes fluctuations on the blank carrier as well. By carefully examining the amplitude of the backscattered versions of the blank carrier and the reader's carrier, the adversary could intercept the ongoing reader-tag communication with either significantly lower bit error rate or from a significantly greater distance away. Our concept is demonstrated and empirically analyzed towards a popular low-cost RFID system, i.e., EPC Gen2. Although active eavesdropping in general is not trivial to be prohibited, for a particular type of active eavesdropper, namely a greedy proactive eavesdropper, we propose a simple countermeasure without introducing extra cost to current RFID systems.&#13;\n&#13;\nThe needs of cryptographic primitives on constraint devices keep increasing with the growing pervasiveness of these devices. One recent design of the lightweight block cipher is Hummingbird-2. We study its cryptographic strength under a novel technique we developed, called Differential Sequence Attack (DSA), and present the first cryptanalytic result on this cipher. In particular, our full attack can be divided into two phases: preparation phase and key recovery phase. During the key recovery phase, we exploit the fact that the differential sequence for the last round of Hummingbird-2 can be retrieved by querying the full cipher, due to which, the search space of the secret key can be significantly reduced. Thus, by attacking the encryption (decryption resp.) of Hummingbird-2, our algorithm recovers 36-bit (another 28-bit resp.) out of 128-bit key with $2^{68}$ ($2^{60}$ resp.) time complexity if particular differential conditions of the internal states and of the keys at one round can be imposed. Additionally, the rest 64-bit of the key can be exhaustively searched and the overall time complexity is dominated by $2^{68}$. During the preparation phase, by investing $2^{81}$ effort in time, the adversary is able to create the differential conditions required in the key recovery phase with at least 0.5 probability.&#13;\n&#13;\nAs an additional effort, we examine the cryptanalytic strength of another lightweight candidate known as A2U2, which is the most lightweight cryptographic primitive proposed so far for low-cost tags. Our chosen-plaintext-attack fully breaks this cipher by recovering its secret key with only querying the encryption twice on the victim tag and solving 32 sparse systems of linear equations (where each system has 56 unknowns and around 28 unknowns can be directly obtained without computation) in the worst case, which takes around 0.16 second on a Thinkpad T410 laptop.