RFID technology can potentially be applied almost everywhere. A typical RFID system involves a reader and a number of tags, which may range from the battery-powered ones with Wi-Fi capabilities, to the low-cost ones that are constrained in resources with even no internal power. Keeping RFID systems secure is important, because they are vulnerable to a number of malicious attacks. As for low-cost RFID systems, security problems become much more challenging, as many traditional security mechanisms are inefficient or even impossible due to resource constraints. Some existing solutions utilize traditional cryptographic primitives such as hash or encryption functions, which are often too expensive in hardware to be implemented on low-cost RFID tags. Furthermore, some other lightweight solutions have been reported to be broken, revealing their keys and ID numbers to the attackers.

In this thesis, we propose lightweight solutions to Mutual Authentication and Ownership Transfer for RFID systems. Mutual Authentication mitigates the issues of eavesdropping and cloning of tags. Only authenticated readers and tags will successfully communicate with each other. Furthermore, we adapt our Mutual Authentication scheme to secure the Ownership Transfer of RFID tags, which is a pertinent issue in the scope of RFID. When an item passes from one owner to another, it is undesirable for the old owner to be able to access the tag or read data from it. The new user must therefore update the access-granting information without revealing this to the old owner. Tag search is another important functionality that a RFID system should provide. In this thesis, we study how to secure tag search with a focus on low-cost RFID systems for which existing solution is not efficient.

These protocols are all realized by utilizing minimalistic cryptography such as Physically Unclonable Functions (PUF) and Linear Feedback Shift Registers (LFSR). PUFs and LFSRs are very efficient in hardware, and provide the low-cost RFID tags with unique characteristics that prevent a multitude of attacks. Compared to existing solutions built on top of hash functions that require 8000 - 10000 gates, our experimental results show that the schemes we propose demand only between 650 - 1400 gates for 64 bit variables and can be easily accommodated by the cheapest RFID tags with only 2000 gates available for security functions.