Security and Privacy in RFID Systems

This PhD thesis is concerned with authentication protocols using portable lightweight devices such as RFID tags. these devices have lately gained a significant attention for the diversity of the applications that could benefit form their features, ranging from inventory systems and building access control, to medical devices. However, the emergence of this technology has raised concerns about the possible loss of privacy carrying such tags induce in allowing tracing persons or unveiling the contents of a hidden package. this fear led to the appearance of several organizations which goal is to stop the spread of RFID tags. We take a cryptographic viewpoint on the issue and study the extent of security and privacy that RFID-based solutions can offer. In the first part of this thesis, we concentrate on analyzing two original primitives that were proposed to ensure security for RFID tags. the first one, HB#, is a dedicated authentication protocol that exclusively uses very simple arithmetic operations: bitwise AND and XOR. HB# was proven to be secure against a certain class of man-in-the-middle attacks and conjectured secure against more general ones. We show that the latter conjecture does not hold by describing a practical attack that allows an attacker to recover the tag's secret key. Moreover, we show that to be immune against our attack, HB#'s secret key size has to be increased to be more than 15 000 bits. this is an unpractical value for the considered applications. We then turn to SQUASH, a message authentication code built around a public-key encryption scheme, namely Rabin's scheme. By mounting a practical key recovery attack on the earlier version of SQUASH, we show that the security of all versions of SQUASH is unrelated to the security of Rabin encryption function. The second part of the thesis is dedicated to the privacy aspects related to the RFID technology. We first emphasize the importance of establishing a framework that correctly captures the intuition that a privacy-preserving protocol does not leak any information about its participants. For that, we show how several protocols that were supported by simple arguments, in contrast to a formal analysis, fail to ensure privacy. Namely, we target ProbIP, MARP, Auth2, YA-TRAP, YA-TRAP+, O-TRAP, RIPP-FS, and the Lim-Kwon protocol. We also illustrate the shortcomings of other privacy models such as the LBdM model. The rest of the dissertation is then dedicated to our privacy model. Contrarily to most RFID privacy models that limit privacy protection to the inability of linking the identity of two participants in two different protocol instances, we introduce a privacy model for RFID tags that proves to be the exact formalization of the intuition that a private protocol should not leak any information to the adversary. the model we introduce is a refinement of Vaudenay's one that invalidates a number of its limitations. Within these settings, we are able to show that the strongest notion of privacy, namely privacy against adversaries that have a prior knowledge of all the tags' secrets, is realizable. To instantiate an authentication protocol that achieves this level of privacy, we use plaintext-aware encryption schemes. We then extend our model to the case of mutual authentication where, in addition to a tag authenticating to the reader, the reverse operation is also required.

Implications of Position in Cryptography

Handan Kilinç Alper

In our daily lives, people or devices frequently need to learn their location for many reasons as some services depend on the absolute location or the proximity. The outcomes of positioning systems can have critical effects e.g., on military, emergency. Thus, the security of these systems is quite important. In this thesis, we concentrate on many security aspects of position in cryptography. The first part of this thesis focuses on the theory of distance bounding. A distance bounding protocol is a two-party authentication protocol between a prover and a verifier which considers the distance of the prover as a part of his/her credential. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. In this direction, we first study the optimal security bounds that a distance bounding protocol can achieve. We consider the optimal security bounds when we add some random delays in the distance computation and let the prover involve distance computation. Then, we focus on solving the efficiency problem of public-key distance bounding because the public-key cryptography requires much more computations than the symmetric-key cryptography. We construct two generic protocols (one without privacy, one with) which require fewer computations on the prover side compared to the existing protocols while keeping the highest security level. Then, we describe a new security model involving a tamper-resistant hardware. This model is called the secure hardware model (SHM). We define an all-in-one security model which covers all the threats of distance bounding and an appropriate privacy notion for SHM. The second part of this thesis is to fill the gap between the distance bounding and its real-world applications. We first consider contactless access control. We define an integrated security and privacy model for access control using distance bounding (DB) to defeat relay attacks. We show how a secure DB protocol can be converted to a secure contactless access control protocol. Regarding privacy (i.e., keeping anonymity in a strong sense to an active adversary), we show that the conversion does not always preserve privacy, but it is possible to study it on a case by case basis. Then, we consider contactless payment systems. We design an adversarial model and define formally the contactless payment security against malicious cards and malicious terminals. Accordingly, we design a contactless payment protocol and show its security in our security model. The last part of this thesis focuses on positioning. We consider two problems related to positioning systems: localization and proof of location. In localization, a user aims to find its position by using a wireless network. In proof of location, a user wants to prove his/her position e.g., to have access to a system or authorize itself. We first formally define the problem of localization and construct a formal security model. We describe algorithms and protocols for localization which are secure in our model. Proof of location has been considered formally by Chandran et al. in CRYPTO 2009 and it was proved that achieving security is not possible in the vanilla model. By integrating the localization and the secure hardware model, we obtain a model where we can achieve proof of location.

EPFL2018

Mutual Authentication in RFID: Security and Privacy

Radu-Ioan Paise, Serge Vaudenay

In RFID protocols, tags identify and authenticate themselves to readers. At Asiacrypt 2007, Vaudenay studied security and privacy models for these protocols. We extend this model to protocols which offer reader authentication to tags. Whenever corruption is allowed, we prove that secure protocols cannot protect privacy unless we assume tags have a temporary memory which vanishes by itself. Under this assumption, we study several protocols. We enrich a few basic protocols to get secure mutual authentication RFID protocols which achieve weak privacy based on pseudorandom functions only, narrow- destructive privacy based on random oracles, and narrow-strong and forward privacy based on public-key cryptography.

ACM Press2008

Secure communication using authenticated channels

Sylvain Pasini

Our main motivation is to design more user-friendly security protocols. Indeed, if the use of the protocol is tedious, most users will not behave correctly and, consequently, security issues occur. An example is the actual behavior of a user in front of an SSH certificate validation: while this task is of utmost importance, about 99% of SSH users accept the received certificate without checking it. Designing more user-friendly protocols may be difficult since the security should not decrease at the same time. Interestingly, insecure channels coexist with channels ensuring authentication. In practice, these latters may be used for a string comparison or a string copy, e.g., by voice over IP spelling. The shorter the authenticated string is, the less human interaction the protocol requires, and the more user-friendly the protocol is. This leads to the notion of SAS-based cryptography, where SAS stands for Short Authenticated String. In the first part of this thesis, we analyze and propose optimal SAS-based message authentication protocols. By using these protocols, we show how to construct optimal SAS-based authenticated key agreements. Such a protocol enables any group of users to agree on a shared secret key. SAS-based cryptography requires no pre-shared key, no trusted third party, and no public-key infrastructure. However, it requires the user to exchange a short SAS, e.g., five decimal digits. By using the just agreed secret key, the group can now achieve a secure communication based on symmetric cryptography. SAS-based authentication protocols are often used to authenticate the protocol messages of a key agreement. Hence, each new secure communication requires the interaction of the users to agree on the SAS. A solution to reduce the user interaction is to use digital signature schemes. Indeed, in a setup phase, the users can use a SAS-based authentication protocol to exchange long-term verification keys. Then, using digital signatures, users are able to run several key agreements and the authentication of protocol messages is done by digital signatures. In the case where no authenticated channel is available, but a public-key infrastructure is in place, the SAS-based setup phase is avoided since verification keys are already authenticated by the infrastructure. In the second part of this thesis, we also study two problems related to digital signatures: (1) the insecurity of digital signature schemes which use weak hash functions and (2) the privacy issues from signed documents. Digital signatures are often proven to be secure in the random oracle model. The role of random oracles is to model ideal hash functions. However, real hash functions deviate more and more from this idealization. Indeed, weaknesses on hash functions have already been discovered and we are expecting new ones. A question is how to fix the existing signature constructions based on these weak hash functions. In this thesis, we first try to find a better way to model weak hash function. Then, we propose a (randomized) pre-processing to the input message which transforms any weak signature implementation into a strong signature scheme. There remains one drawback due to the randomization. Indeed, the random coins must be sent and thus the signature enlarges. We also propose a method to avoid the increase in signature length by reusing signing coins. Digital signatures may also lead to privacy issues. Indeed, given a message and its signature, anyone can publish the pair which will confirm the authenticity of the message. In certain applications, like in electronic passports (e-passports), publishing the authenticated data leads to serious privacy issues. In this thesis, we define the required security properties in order to protect the data privacy, especially in the case of e-passport verification. The main idea consists for the e-passport to keep the signature secret. The e-passport should only prove that it knows a valid signature instead of revealing it. We propose a new primitive, called Offline Non-Transferable Authentication Protocol (ONTAP), as well as efficient implementations that are compatible with the e-passport standard signature schemes.