Cryptographic puzzles and distance-bounding protocols: Practical tools for RFID security

Widespread adoption of RFID technology is being slowed down because of increasing public concerns about associated security threats. This paper shows that it is possible to enhance the security of RFID systems by requiring readers to perform a computational effort test. Readers must solve a cryptographic puzzle - one of the components of the Weakly Secret Bit Commitment (WSBC) sent by tags - to obtain the static identifier of the interrogated tag. The method we present is based on a simple concept already used in security applications such as anti-spam or TCP SYN flooding protection, yet original in the RFID context until now. The scheme provides privacy protection while being an effective countermeasure against the indiscriminate disclosure of the whole contents of a large number of tags. Then, we scrutinize the combined use of cryptographic puzzles and distance-bounding protocols. First, a classical and relatively straight-forward solution is presented. Secondly, we introduce a protocol named Noent, that follows a new approach that reduces drawbacks associated with WSBC such as key delegation, whilst gaining all the advantages of employing distance-bounding protocols such as the certainty on the distance between a tag and reader.