1 Introduction

Radio Frequency IDentification (RFID) has become one of the most emerging wireless technologies used in order to identify and authenticate objects, animals and people in recent years. RFID is also one of the most likely technologies to promote the Internet of Things (IoT) paradigm and is proliferated in many real-life applications such as access control, supply chain, hospital care system, automatic toll collection, payment systems, e-passport, vicinity/proximity cards, etc. It is considered that near-field communication (NFC) technology in smart phones is a new up-to-the-minute opportunity for RFID technology and we are on the doorstep of a new RFID era [1, 2].

A simple RFID system consists of a tag (transponder), a reader (interrogator) and a back-end server. A tag basically has a microchip which stores data and an antenna used to transmit and receive messages through electromagnetic waves. Generally, it is considered that a back-end server is separated from an RFID reader and it acts as a mediator between the tags and the server for the communication. A back-end server keeps all the information (secret keys, data, etc.) about tags. Furthermore, RFID tags can be categorized into active, passive and semi-passive tags. Passive tags do not have their own power source and energize their integrated circuit (IC) by using the waves transmitted by the reader. Moreover, tags can also divided into four groups with respect to their operating frequency that usually depends on the availability of frequency bands and regulations: Low frequency (LF, 125–134.2 kHz and 140–148.5 kHz), high frequency (HF, ISM band at 13.56 MHz), ultra high frequency (UHF, 860–960 MHz) and microwave (> 2.45 GHz) [2]. Passive low-cost RFID tags of smaller sizes are highly preferred in many applications and this desire introduces some computation, energy and size restrictions on the tag. The production price of the tags is usually around $0.05–$0.10 and the cost pressure is quite dominant on hardware capabilities [3].

Security and privacy concerns arise since a tag communicates with a reader over an insecure wireless channel. Tag impersonating, tracking (forward and backward tracing), eavesdropping, replay, man-in-the-middle and denial of service (DoS) attacks can be performed by an attacker using the messages transmitted in the air [4]. Implementing heavy cryptographic algorithms to overcome these issues is a challenging task due to the limited capabilities of low-cost RFID tags [2, 3, 5,6,7]. For protocol designers, such constraints enforce a trade-off between security and practicality. Furthermore, over the past few years, numerous lightweight authentication protocols have been proposed so as to mitigate security and privacy concerns for RFID systems [8]. Most of new protocols claimed that they were impregnable against every type of attack, providing different RFID system features such as scalable identification, tag ownership transfer, mutual authentication, robustness against noisy environments, reader corruption resiliency, etc. Unfortunately, many of them failed to satisfy the claimed security and privacy properties [8,9,10,11].

On the other hand, privacy models have been presented to systematically analyze the security and privacy of proposed authentication protocols. Such an evaluation is theoretically accomplished based on the privacy models to examine the security, anonymity and untraceability properties before using an RFID protocol in real-life systems. Recently, several models have been proposed to formalize security and privacy in the context of RFID systems [12,13,14,15,16,17,18,19,20]. A privacy model should be detailed, attentive and flexible not to overlook the realities of practical RFID systems. Although it has been considered that Vaudenay’s model [14] is one of the most evolved and well-defined privacy models, some papers have been published to ameliorate his model [16, 19,20,21]. These results, to the best of our knowledge, have claimed that their improvements fulfill the missing parts of the model but the privacy model has still fractures. In our opinion, the design of a new, appropriate, complete, and flexible security and privacy model considering the various abilities of an adversary is an essential need. Most importantly, we have noticed that Vaudenay’s model has not taken the misuse of random number generators into consideration and this is a new and different adversary ability especially for real-word scenarios introduced in this paper.

Designers generally build the security and privacy of their protocols on the utilization of a random number generator (RNG) which is one of the most common primitive cryptographic functions. Eventhough designers regard RNGs as secure, their improper deployment might cause serious weaknesses in a protocol scheme. More importantly, many proposed RNGs that are asserted secure today, might be broken or become weaker in the near future. In the literature, presented RNG attacks [22,23,24,25] show that protocol designers should put care into the deployment of RNGs in order not to encounter security and privacy issues in their protocols.

2 Overview

2.1 Related Work

Privacy models are proposed as a base for analyzing the security and privacy of authentication protocols in a methodological manner. For this purpose, the privacy models formally define some properties such as RFID schemes, security and privacy prerequisites of the schemes and abilities of an adversary. In this context, Avoine et al. [26] has published a framework to formalize privacy in RFID protocols in 2005. Avoine also extended the previous model in his thesis [12]. Then, Juels and Weis [13] modified Avoine’s model by adding a side channel information attribute. Furthermore, different model definitions were provided in [27, 28]. Although, there were several other attempts to design useful, proper and complete privacy model to represent and analyze RFID systems, the models did not consider all, or miss some important adversary properties (corruption, using side channel information, etc.) and they did not appropriately model an RFID scheme in terms of authentication, identification, protocol execution, etc. However, Vaudenay [14] has proposed a well-designed and relatively complete privacy model that has been quite popular among many protocol designers. In time, several researchers have improved Vaudenay’s model [16, 19,20,21] for which more detail is provided below.

Avoine et al. [16] introduced the notion of time and formalized it by modifying Vaudenay’s model with a new privacy class called TIMEFUL privacy. They show that an adversary can trace an RFID tag by only following the time that a reader has taken to authenticate the tag. According to their model, an adversary can call timer oracle to learn the spent time for its overall computations during authentication and can distinguish the tag. They stated that if an RFID protocol is TIMEFUL-private, an adversary cannot obtain anything about the tag identity using time information.

Akgün and Çaǧlayan [19] defined the notion of forward untraceability by extending Vaudenay’s model. In their model, they emphasized the relay of valuable information on each communication round of the protocol and they claim that Vaudenay’s model does not represent real-world settings because an adversary can miss some communication rounds due to some reason such as low signal to noise ratio. They applied their revised model to analyze some existing RFID protocols and showed that the schemes are not resistant to forward untraceability and server impersonation as claimed.

Kardaş et al. [20] improved Vaudenay’s model by claiming that an adversary has capability to corrupt a tag at most k times. Hence, they introduced k-strong privacy that is an extension of the privacy classes of Vaudenay’s model and is positioned between strong privacy and destructive privacy.

Hermans et al. [21] modified Vaudenay’s model by introducing insider privacy notion based on the insider attack that is first discussed for RFID schemes by van Deursen and Radomirović [29]. They analyzed some existing RFID protocols to show the applicability of their model. Moreover, they propose a new RFID authentication protocol that provides wide-forward-insider privacy.

2.2 Contributions of The Paper

In this paper, we show that RNGs could be the weakest point in RFID authentication protocols and misusing them can cause severe security and privacy issues. From this point of view, we first revisit and extend Vaudenay’s privacy model [14] by introducing the notion of RNGs based on their improper usage. To do so, we formalize a new privacy level called RANDOMEYE privacy that is integrated into Vaudenay’s model.

We also claim that Vaudenay’s model is not sufficient for some real-world scenarios. For instance, consider the following case that is not covered by Vaudenay’s model: An adversary obtains some random numbers in a scheme and predicts the outputs of the RNG or the RNG loses its randomness because of some reasons such as aging, environmental effects, etc. (see Sect. 3.2 for further some explanations and existing attacks about RNGs). Motivated by this need, we introduce a novel adversary class what we called RANDOMEYE and define a new random oracle \({\mathscr {O}}^{RNG}\).

We further apply our enhanced model to two existing RFID schemes and analyze their security with respect to RANDOMEYE adversary class. First, we address the scheme by Song and Mitchell [30], and then the scheme by Akgün and Çaǧlayan [31]. We show that these schemes are vulnerable to RNG attacks and are not RANDOMEYE private according to our extended model. Namely, the adversary can obtain the secrets of the RFID tags by benefiting from the improper usage of RNGs.

Finally, we point out that RNGs might be the bottleneck of many RFID schemes. We highlight that using RNGs to mitigate security and privacy concerns can be Achilles’ heel of an RFID authentication protocol.

2.3 Structure of The Paper

In Sect. 3, we present prior information about RFID protocols, RNGs and computational capabilities. This section also gives a glance of available literature. In Sect. 4, our new extended model that is a modification of Vaudenay’s model is presented. In Sect. 5, the security and privacy of some existing schemes are analyzed based on our model. Section 6 concludes the paper with a brief conclusion and highlighting future research directions.

3 Preliminaries

This section provides some background information on lightweight RFID protocols, random number generators and computational capabilities. This section also covers brief information on recent work related to the aforementioned topics.

3.1 Lightweight RFID Protocols

Unlike wireless protocols that require conventional cryptographic operations [29, 32,33,34] such as symmetric and public key algorithms, restricted systems (in terms of computational power, storage, bandwidth, etc.) require lightweight or ultra-lightweight authentication protocols. Low-cost RFID systems are one of the prominent real-life applications of these protocols due to the capabilities and the price range of RFID tags.

Lower cost and smaller size demands for RFID tags enforce them to be some resource limitations such as reduced number of logic gates, lower energy consumption and low computational complexity. Lightweight and ultra-lightweight protocols need to be designed by taking into account the constraints of low-cost RFID tags. Hence, low-cost tags introduce many challenges in terms of security and privacy; numerous researchers have proposed protocols in order to obviate the security and privacy concerns [8].

Extremely restricted RFID tags require ultra-lightweight protocols that only supports bitwise operations (such as XOR, AND, OR, rotation, permutation, etc.) and are compliant to EPC Class-1 Generation-2 specification. Some of the famous ultra-lightweight protocols are SASI [35], LMAP [36], M2AP [37], EMAP [38] and Gossomar [39]. On the other hand, lightweight protocols use the same bitwise operations, as well as RNGs and Cyclic Redundancy Check (CRC) but no cryptographic hash functions. Several well-known protocols are presented in [40,41,42]. However, the restrictions mentioned above greatly limit aptitudes of RFID tags and cause security and privacy vulnerabilities. Avoine et al. [43] have evaluated and compared well-known lightweight protocols and indicated the security and privacy weaknesses. Zeeshan has also quite recently addressed the security and privacy issues in low-cost RFID systems in his Ph.D. thesis in [2].

3.2 RNGs

There are two types of random number generator: pseudo-random number generator (PRNG) and truly random number generator (TRNG). TRNG is an algorithm that generates random numbers from a natural source of randomness. PRNG, also known as deterministic random number generator (DRNG), is an algorithm for generating random numbers with a provided initial value called a seed. The output of the PRNG is called a pseudo-random bit sequence. The output of a PRNG is much longer than the length of the seed. In addition to this, the output of a PRNG seems to be random because it has to be statistically indistinguishable from random values and it is assumed to be unpredictable when its seed is not known.

Two general conditions are required from the security perceptive for a pseudorandom random generator: (1) the output of a PRNG should be statistically indistinguishable from truly random sequences, (2) the next output of the sequence should be unpredictable to an adversary with limited computational resources. Theoretically, the next output can be predictable with a negligible probability such as \(2^{-80}\). In fact, the minimum security requirement is that the length of the random seed has to be sufficiently large (s-bit) to be infeasible for the adversary to search over a \(2^{s}\) sized space (s is called the security parameter). In other words, the complexity of that attack is \(2^{s}\).

It is impossible to prove that the output of an RNG is random but there are various statistical tests that measure the quality of an RNG. This is accomplished by taking sample output sequences and apply the tests. The tests are probabilistic so they determine whether the samples look like a truly random sequence or not. If the generator fails, the output is regarded to be non-random. On the other hand, if an RNG passes all the tests, it is not rejected as being non-random. The five basic tests are (1) frequency test (mono bit test), (2) serial test (two-bit test), (3) poker test, (4) runs test, (5) auto-correlation test [44]. Detailed information about tests, generators, algorithms and definitions are presented in [44]. Moreover, some institutes, research centers, government agencies or organizations have specified some criteria to control the randomness of RNGs. For instance, the German Federal Office for Information Security has established several procedures for quality assessment of RNGs [45].

The use of RNGs has become the key function in most private and secure light-weight RFID protocols for low-cost RFID tags. Low-cost RFID tags have approximately 5–10 K gates and only 0.4–4 K gates can be dedicated to security operations [46]. Furthermore, designers are also restricted with the time that is required by a tag while generating a random number because RFID readers should be able to read a bunch of tags in a certain amount of time. Many publications have been presented to design and use RNGs in low-cost RFID tags. Melia-Segui et al. [47] have presented a lightweight PRNG design for low-cost passive RFID tags, called J3Gen in 2013. J3Gen is based on a LFSR (Linear Feedback Shift Register) configured with multiple feedback polynomials that are changed during the generation of sequences from a physical source. They have demonstrated that their most efficient J3Gen design, that has a 32-bit LFSR output with 16-bit feedback polynomials, requires around 1.2 K logic gate equivalence (GE). Peinado et al. [22] analyzed J3Gen and they claimed that there are two possible cryptanalytic attacks on J3Gen. Garcia-Alfaro et al. [48] showed that Peinado et al.’s assumptions are incorrect and their attack against J3Gen is not valid. At this point, although Garcia-Alfaro et al. fend off the attack on J3Gen, the literature is still waiting for objections to J3Gen is PRNG.

Peris-Lopez et al. [46] proposed a PRNG, named LAMED, for low-cost RFID tags compliant with the EPC C1G2 standard in 2009. They claimed that LAMED successfully passes several randomness tests. LAMED requires roughly 1.6 K gates and 1.9 ms to generate a 32-bit random number.

Melia-Segui et al. [23] presented a practical attack on a weak PRNG proposed by Che et al. [49] designed for EPC Gen2 tags. Che et al. proposed a LFSR based PRNG with the combination of thermal noise signal modulation. Melia-Segui et al. obtained the feedback polynomial function of the LFSR that they could predict its generated sequences. They showed that an adversary can reach the PRNG configuration with a confidence of 42% by only eavesdropping 128 bits of PRNG data.

Garcia et al. [24] have shown that the PRNG used in the MIFARE Classic chip has vulnerabilities.

Armknecht et al. [3] have pointed out that ensuring a sufficient level of entropy for RNGs is still a difficult task. They said that different experts from industry who provided them information, all agree stated that generating more than 128 true random bits per authentication on an RFID tag in the price range of $0.05–$0.10 seems currently improbable.

The EPC C1G2 (Class-1 Gen-2) RFID standard was proposed and adopted by EPCglobal in 2004. In 2006, it was published as an amendment to the ISO 18000-6 standard for low-cost lightweight UHF RFID tags. The new version of standards has been recently ratified in 2013 with some optional cryptographic properties [40, 50]. According to the recent standard, a tag generates 16-bit pseudo-random numbers (RN16) using the RNG. The RNG shall meet three randomness criteria: probability of a single RN16, probability of simultaneously identical sequences and probability of predicting an RN16. Although these requirements may be more stringent, a brute-force attack can be applied to reveal the random numbers because lightweight low-cost RFID tags are able to use \(32-bit\) output of PRNG which is a weakness. If an adversary eavesdrops the messages between the reader and the RFID tag, then a brute-force attack or a time-memory trade-off attack can be used to reveal the secrets of a victim tag.

RNGs are implemented by electronic circuits and their randomness quality can be affected by various factors such as seed entropy, aging, environmental effects (such as temperature, humidity, pressure, vibration, electromagnetic field, chemicals, etc.). As a result, biased RNGs cause irretrievable weaknesses.

Bayon et al. [25] demonstrated a practical attack ring oscillator (RO) based TRNG by injecting an EM signal and they also mention previous work about another practical assault to RO based TRNGs by injecting a sine wave signal onto the power pad of the device. Both attacks showed that it is possible to dynamically control the bias of the TRNG output.

In [44], the authors claimed that randomness and size of key generation help to eliminate the advantages of adversaries. Then, they gave an example using Data Encryption Standart (DES) encryption algorithm has \(2^{56}\) key space size. In this case, when a secret key is selected by using a TRNG, an adversary has to try on average \(2^{55}\) possible searches to find the correct key. On the other hand, if the encryption key was selected by using a 16-bit random secret and expanding it into with a 56-bit key by using well-known functions the adversary would need to try on average only \(2^{15}\) possible keys to find the correct one.

In [51], the authors presented a detailed survey paper about random number generators. They compared different types of PRNGs and TRNGs. They also criticized about real randomness, theoretic and practical RNG approaches. They stated that most researchers chose the minimum-action strategy: design a TRNG, obtain at least one random number sequence that passes a chosen set of randomness tests and publishes. However, this does not mean that the corresponding TRNGs have a really good randomness quality because small variations in hardware can weaken them. Hence, a theoretical design cannot proceed towards a product without a detailed investigation of hardware and without extensive randomness proof. Furthermore, Barak et al. [52] proposed an extractor functions to make RNGs robust against aging, temperature changes, etc. Moreover, they presented a couple of weak RNGs caused by hardware imperfections.

3.3 Computational Capabilities

Hashcat is the well-known fastest password recovery cracker [53] and different versions are available for Linux, OSX, and Windows. It also comes in two variants: CPU-based (Hashcat password recovery tool) or GPU-based (oclHashcat, accelerated tool). oclHashcat is a GPU-based multi-hash cracker using a brute-force attack (implemented as a mask attack), combinator attack, dictionary attack, hybrid attack, mask attack, and rule-based attack.

The performance of oclHashcat in different operating systems (PC1Footnote 1, PC2Footnote 2, PC3Footnote 3 and PC4Footnote 4) for MD5, SHA1, SHA256, SHA512 is depicted in Table 1 [53]. It is seen that PC3 can do 135,232 Mh/s against MD5, which approximately accounts to 0.135 billion tries per second. Hence, if the same computer is used for exhaustive search, less than 32 ms will be required to find the result matching to the output of 32-bit PRNG.

Table 1 Performance list of oclHashcat in different operating systems
Full size table

4 The Proposed Modified Vaudenay Privacy Model

In this section, the main notation used throughout the paper (see Table 2) are provided and the proposed modified version of the well-known Vaudenay’s privacy model [14] is introduced before the analysis of privacy aspects of RFID schemes. Finally, in the context of our model, the adversary abilities which includes the proposed RANDOMEYE adversary class are presented. The main notation used in this paper is shown in Table 2).

Table 2 Main notation used throughout the paper
Full size table

An RFID system is basically composed of three entities: a tag \({{\varvec{T}}}\), a reader \({{\varvec{R}}}\) and a back-end system/database \({{\varvec{DB}}}\). A tag \({{\varvec{T}}}\) is interrogated by a reader \({{\varvec{R}}}\) and the reader identifies/authenticates \({{\varvec{T}}}\) by using a unique identifier of the tag ID (in this article it is sometimes denoted as \(ID_{{{\varvec{T}}}}\) to improve the readability). \({{\varvec{DB}}}\) stores all identifiers and secret keys of valid tags. \({{\varvec{R}}}\) communicates with both \({{\varvec{T}}}\) and \({{\varvec{DB}}}\) and provides a link between them. \({{\varvec{DB}}}\) might be considered as a part of the reader. Moreover, \({{\varvec{T}}}\) has a restricted memory and computational capacities and can communicate with \({{\varvec{R}}}\) for a limited distance. We assume that \({{\varvec{R}}}\) is much more talented than the tag which is the common case [16]. An adversary \({{\varvec{Adv}}}\) can corrupt a tag and use its internal secrets against the system but she cannot corrupt \({{\varvec{R}}}\). We also assume that the communications between \({{\varvec{R}}}\) and \({{\varvec{DB}}}\) is protected by a secure channel such as Secure Sockets Layer (SSL)/Transport Layer Security (TLS).

4.1 Definitions of RFID Scheme

An RFID system is defined by the following procedures.

  • SetupReader\(\left( 1^{\alpha }\right) \longrightarrow \left( K_{P},K_{S}\right)\) is a setup algorithm that generates a public-private key pair \(\left( K_{P},K_{S}\right)\) for the reader \({{\varvec{R}}}\) where \(\alpha\) is the security parameter, and then initializes an empty database \({{\varvec{DB}}}\) to store all identifiers and secret keys of all tags. Although \(K_{s}\) is kept secretly in the \({{\varvec{DB}}}\) with the security parameter \(\alpha\); \(K_{p}\) is publicly released.

  • SetupTag\(\left( K_{p},ID\right) \longrightarrow \left( K,S\right)\) is a probabilistic algorithm which returns a tag secret K and the initial state S of a tag \({{\varvec{T}}}\) with the input identifier ID. When \({{\varvec{T}}}\) is legitimate, the pair (ID, K) is to be stored in the database \({{\varvec{DB}}}\).

  • Ident\(\longrightarrow \textit{Output}\) is an interaction protocol between a tag \({{\varvec{T}}}\) and the reader \({{\varvec{R}}}\) to complete the protocol transcripts. At the end of the protocol, if \({{\varvec{T}}}\) is legitimate, \({{\varvec{R}}}\) accepts the tag (\({{\varvec{R}}}\) identifies \({{\varvec{T}}}\) ) and outputs its identifier Output=ID, otherwise (i.e. if it is not valid) \({{\varvec{R}}}\) refuses \({{\varvec{T}}}\) and outputs \(\bot\).

4.2 Definitions of the Oracles

An adversary \({{\varvec{Adv}}}\) against an RFID scheme acts as an honest reader and/or an honest tag to attack the system. We assume that there is only one legitimate reader \({{\varvec{R}}}\) in the RFID system and both valid readers and tags of the system have no prior information about the entity that is interacting with themselves. We also suppose that each experiment always starts with executing the algorithm SetupReader thus, \(K_{p},K_{s}\) and \(1^{\alpha }\) are already generated. We consider that \(K_{p}\) and \(1^{\alpha }\) are already available to \({{\varvec{Adv}}}\) but \(K_{s}\) is kept secret because \({{\varvec{R}}}\) cannot be corrupted. Furthermore, we assume that there are no tags in the system at the beginning of each experiment and \({{\varvec{Adv}}}\) is allowed to call \({\mathscr {O}}^{CreateTag}\) oracle to add new tags to the system.

According to Vaudenay’s model [14], a tag is considered as either a free tag or a drawn tags. Drawn tags are the set of tags that \({{\varvec{Adv}}}\) has visual contact and communicates \({{\varvec{Adv}}}\) cannot interact with initially free tags. When \({{\varvec{Adv}}}\) calls the \({\mathscr {O}}^{CreateTag}\) oracle, she generates a new tag whose status is free. The following oracles are used by the adversary \({{\varvec{Adv}}}\) to interact with the RFID system. First of all, \({{\varvec{Adv}}}\) setups a new tag of identifier ID.

  • \({\mathscr {O}}^{CreateTag}\left( ID,b\right)\): It creates a free tag \({{\varvec{T}}}\) with a unique identifier ID using SetupTag. \({{\varvec{T}}}\) is legitimate when \(b=1\), otherwise \(b=0\) and \({{\varvec{T}}}\) is not valid. It also inserts \(\left( ID,K\right)\) into \({{\varvec{DB}}}\). b is implicitly 1 when neglected.

Then, the adversary may change the status of the tag from free to drawn by calling the following oracle.

  • \({\mathscr {O}}^{DrawTag}\left( distr, n\right)\) \(\rightarrow\)(\(\psi _{{{{\varvec{T}}}}_{1}},b_{1},\ldots ,\psi _{{{{\varvec{T}}}}_{n}},b_{n}\)): It randomly selects n free tags among all existing ones with distribution probability of the given distr. The oracle assigns a new pseudonym, \(\psi _{{{{\varvec{T}}}}_{i}}\) for each tag and changes their status to drawn. Hence, the oracle returns an array of fresh pseudonyms \(\left( \psi _{{{\varvec{T}}}_{1}},\psi _{{{\varvec{T}}}_{2}},\ldots ,\ldots ,\psi _{{{\varvec{T}}}_{n}}\right)\) of the tags (\(\psi _{{{\varvec{T}}}_{n}}\) is the pseudonym of the nth tag). The pseudonyms are always changed from session to session so that the adversary may interact to drawn tags for only one single session. The relations (\(\psi _{{{{\varvec{T}}}}_{i}},ID_{i}\) ) are stored in a hidden table tbl such that \({tbl}\left( \psi _{{{\varvec{T}}}}{}_{i}\right) =ID_{i}\). This oracle also returns a bit array \(\left( b_{1},b_{2}\ldots ,\ldots ,b_{n}\right)\) where \(b_{i}\) of the ith tag shows whether it is legitimate or not. Furthermore, the oracle may return \(\bot\) if the querying tags are already drawn or there are no existing tags.

When the tag is drawn, the adversary is only able to interact to the tag with pseudonym \(\psi _{{{\varvec{T}}}}\). \(\psi _{{{\varvec{T}}}}\) is defined as a temporary identifier of a tag and used for pointing to the tag anonymously. In this case the following oracles can be called.

  • \({\mathscr {O}}^{Free}\left( \psi _{{{\varvec{T}}}}\right)\): This oracle changes the state of tag \({{\varvec{T}}}\) that is represented by the pseudonym \(\psi _{{{\varvec{T}}}}\) from drawn to free. Afterwards \({{\varvec{Adv}}}\) is no longer able to interact with \({{\varvec{T}}}\). The secret key of the tag with the pseudonym \(\psi _{{{\varvec{T}}}}\) is denoted as \(key\left[ \psi _{{{\varvec{T}}}}\right]\). The adversary can corrupt the drawn tags by using the following oracle and obtain the internal values of the tag including its secret key.

  • \({\mathscr {O}}^{Corrupt}\left( \psi _{{{\varvec{T}}}}\right)\)\(\rightarrow S\): S is the whole memory of \(\psi _{{{\varvec{T}}}}\). \({{\varvec{Adv}}}\) obtains the \(key\left[ \psi _{{{\varvec{T}}}}\right]\). Eventually, the tag \({{\varvec{T}}}\) with the pseudonym \(\psi _{{{\varvec{T}}}}\) is destroyed and \({{\varvec{Adv}}}\) cannot interact to \({{\varvec{T}}}\) any more.

  • \({\mathscr {O}}^{Launch}\left( \right)\)\(\rightarrow \pi\): This makes the reader \({{\varvec{R}}}\) start a new Ident protocol with transcript \(\pi\).

  • \({\mathscr {O}}^{SendReader}\left( m,\pi \right)\)\(\rightarrow m'\): This sends the message m to the reader \({{\varvec{R}}}\) in the protocol transcript \(\pi\) with outputs the response \(m'\).

  • \({\mathscr {O}}^{SendTag}\left( m,\pi \right)\)\(\rightarrow m'\): This sends the message m to \({{\varvec{T}}}\) and outputs the response \(m'\). Also, \({{\varvec{Adv}}}\) asks for the reader’s result of the protocol transcript \(\pi\). The adversary can use the corresponding oracle to change the state of the tag so she can start to interact with the tag change, the state to drawn or she can free the tag (after which she communicate). anymore.

  • \({\mathscr {O}}^{Execute}\left( \psi _{{{\varvec{T}}}}\right)\)\(\rightarrow \left( \pi ,transcript\right)\): This executes a complete protocol between the reader and the tag with pseudonym \(\psi _{{{\varvec{T}}}}\). It returns the transcript of the protocol instance that is the list of all successive messages of the protocol.

  • \({\mathscr {O}}^{Result}\left( \pi \right)\)\(\rightarrow x\): This returns \(x=1\) when \(\pi\) completes successfully after the Ident returns \(Output\ne \bot\) which means that the tag \({{\varvec{T}}}\) is identified. Otherwise, if \({{\varvec{T}}}\) is not identified and \(\textit{Output}=\bot\), this oracle returns \(x=0\) .

Finally, we introduce a new oracle called RNG oracle, \({\mathscr {O}}^{RNG}\) as follows. The adversary \({{\varvec{Adv}}}\) is allowed to obtain the results of the RNG bit string used in the protocol by a tag \({{\varvec{T}}}\) by querying the following oracle. For simple explanation, \(\pi _{i}\) denotes the ith protocol instance, \(s_{i}\) is the corruption state of the RNG of a tag \({{\varvec{T}}}\) for the ith protocol instance. If \(s_{i}=0\), \({{\varvec{Adv}}}\) does not corrupt \({{\varvec{T}}}\) but if \(s_{i}=1\), she corrupts \({{\varvec{T}}}\) and captures the \(key\left[ \psi _{{{\varvec{T}}}}\right]\) for the protocol instance \(\pi _{i}\). The array of (\(\pi _{i}\), \(s_{i}\)) values is denoted by \(\theta _{\pi }{:}{=}\left\{ \left( s_{1},\pi _{1}\right) ,\left( s_{2},\pi _{2}\right) ,\ldots ,\left( s_{n},\pi _{n}\right) \right\}\) and \(\theta _{\pi }\) defines the sufficient number of n tuples where each tuple includes the protocol transcript and tag corruption information.

  • \({\mathscr {O}}^{RNG}\left( \theta _{\pi },\psi _{{{\varvec{T}}}}\right) \rightarrow \left( RNG_{1},RNG_{2}\ldots ,RNG_{i},\ldots ,RNG_{n}\right)\): This outputs the set of the RNG bit string used on the tag \({{\varvec{T}}}\) with the unique identifier \(ID_{{{\varvec{T}}}}\) for each protocol instance \(\pi _{i}\) and the state \(s_{i}\). The oracle returns \(\bot\) for any protocol instance \(\pi _{i}\), when the RNG used in this instance cannot be obtained.

\({{\varvec{Adv}}}\) performs her attack by running an experiment or playing a game and obeying the corresponding rules. Firstly, she constructs an RFID system and uses the oracles and gets a result. She wins or looses depending on the corresponding rules.

4.3 Definition of the Adversary Classes

We define different adversary classes for playing security games. The definition includes Vaudenay’s model [14] and our own novel adversary class.

Definition 1

(Adversary Classes). An adversary \({{\varvec{Adv}}}\) against an RFID system who has an arbitrary number of accesses to the above oracles except the \({\mathscr {O}}^{RNG}\) oracle is regarded to be in one of the following classes.

  • STRONG \({{\varvec{Adv}}}\) uses all oracles without any restrictions.

  • DESTRUCTIVE \({{\varvec{Adv}}}\) cannot use an oracle against a tag after using \({\mathscr {O}}^{Corrupt}\) oracle (i.e. the tag has been killed).

  • FORWARD \({{\varvec{Adv}}}\) can only use \({\mathscr {O}}^{Corrupt}\) oracle after her first call to this oracle.

  • WEAK \({{\varvec{Adv}}}\) uses all oracles except \({\mathscr {O}}^{Corrupt}\) oracle

  • NARROW \({{\varvec{Adv}}}\) has no access to \({\mathscr {O}}^{Result}\) oracle.

  • RANDOMEYE \({{\varvec{Adv}}}\) can access the RNG oracle \({\mathscr {O}}^{RNG}\), and extracts the random number(s) used in a tag. This is a novel class introduced in this paper.

4.4 Security Notions

Some security properties of an RFID system such as completeness and soundness are visited below.

Definition 2

(Completeness). An RFID system is complete if the reader \({{\varvec{R}}}\) of the system returns the tag identifier ID at the end of the protocol (Ident) for a legitimate tag \({{\varvec{T}}}\) with very high probability.

Definition 3

(Strong Completeness). An RFID system is complete if the reader \({{\varvec{R}}}\) of the system returns the tag identifier ID at the end of the protocol (Ident) for a legitimate tag \({{\varvec{T}}}\) with very high probability although the RFID scheme has been already attacked.

According to Vaudenay’s model, security is a vital property and should be withheld against every attack by the strongest adversary. But it is obvious that the security of a scheme is violated when tag impersonation occurred if the adversary uses \({\mathscr {O}}^{Corrupt}\) oracle. Hence, the model permits an adversary to use all oracles except the \({\mathscr {O}}^{Corrupt}\) oracle.

Definition 4

(Soundness). An RFID system is said sound if an adversary \({{\varvec{Adv}}}\) impersonates a legitimate tag \({{\varvec{T}}}\) with a negligible probability [16].

4.5 Privacy

Vaudenay defines a privacy notion that is the deducing ability of an adversary to obtain the ID relations of a tag from its protocol instances. He explains anonymity and untraceability properties under the privacy notion in that one is about unveiling the ID of tags and the other is about indistinguishability of any two tags, respectively [14].

In the RFID literature, there are two types of untraceability notions: forward untraceability and backward untraceability. If an RFID system provides the forward untraceability feature, an adversary \({{\varvec{Adv}}}\) who compromises a legitimate tag at a time t, cannot trace the future interactions of the tag, \(t' > t\). If an RFID system provides the backward untraceability feature, \({{\varvec{Adv}}}\) cannot trace past interactions of the tag, \(t' < t\). The backward untraceability property is also referred to as forward privacy or forward secrecy and this notion is more important than forward untraceability for real life scenarios. Vaudenay also considers the privacy of the RFID system based on the adversary classes in Definition 1. In his model, he presents a blinded adversary called blinder \({{\varvec{B}}}\).

Definition 5

(Blinder, trivial adversary). A blinder \({{\varvec{B}}}\) for an adversary \({{\varvec{Adv}}}\) is a polynomial-time algorithm that observes the same messages as \({{\varvec{Adv}}}\) and simulates Launch, SendReader, SendTag, and Result oracles without having access to the secret keys nor the database of the system. The adversary \({{\varvec{Adv}}}\) uses all outputs of the oracles. A blinded adversary \({{\varvec{Adv}}} ^{{\varvec{B}}}\) is an adversary who never uses Launch, SendReader, SendTag, and Result oracles. An adversary \({{\varvec{Adv}}}\) is said to be trivial if there exists a blinded adversary \({{\varvec{Adv}}}^{{\varvec{B}}}\) such that \(\mid Prob[{{\varvec{Adv}}} \ wins] - Prob[{{\varvec{Adv}}}^{{\varvec{B}}}\ wins] \mid\) is negligible.

If the success probability of the simulator and the blind adversary is nearly the same, this means that the blind adversary has attack ability at least as high as the simulator of the system (except using the secret keys). Hence, the authentication and identification of a tag can be considered private. Vaudenay says that an adversary accomplishes his attack (plays a security game) into two phases. In the first phase, she queries the allowed oracles and collects the outputs. In the second phase, she analyses the obtained results without using any oracle. Between the two phases, she also has access to the hidden table tbl of the \({\mathscr {O}}^{DrawTag}\) oracle. If she outputs true from her analysis, then she wins the game.

Definition 6

(Privacy). An RFID system is P-private if all the adversaries who belong to class P are trivial following Definition 5 [14].

The following well-known links between Vaudenay’s privacy classes which are rather obvious by definition.

figure e

4.6 The Proposed RANDOMEYE Adversary Class

Now we are ready to explain our RANDOMEYE adversary class and its relationship to the other adversary classes. The RANDOMEYE adversary class formalizes the weakness and/or misuse of random number generators for real life RFID systems. Tangibly, an adversary \({{\varvec{Adv}}}\) that can query the \({\mathscr {O}}^{RNG}\) oracle, might learn the random numbers used in the authentication protocol. If \({{\varvec{Adv}}}\) cannot infer the ID of the tag by using this information, we consider that the protocol is RANDOMEYE private. Hence Vaudenay’s original adversary classes are not complete and the relationship between them has changed with the newly introduced class. Therefore, we give the new link for the STRONG class as follows for clear comprehensibility:

figure f

5 Case Study Protocols

In this section, we consider two popular existing RFID schemes to apply our new model and provide analysis. We first briefly introduce Song and Mitchell’s and Akgün et al.’s schemes. Then, we explain how an adversary attacks and break the schemes step by step. Our analysis further shows that the schemes do not provide security and privacy properties with respect to the presented weakness. Hence, according to our improved model, the protocols are not RANDOMEYE private.

5.1 First Study Example: Song and Mitchell’s Protocol

Firstly, we investigate the scheme designed by Song and Mitchell (SM) [30] to provide private and secure authentication between low-cost RFID tags. Their protocol is depicted below.

In this protocol the reader generates a nonce \({r_{1}}\) and sends it to the tag to start the protocol. The tag receives the nonce and generates a random bit string, \({r_{2}}\) as a temporary secret for the protocol instance. The tag computes \(M_{1}=r_{1}\oplus tid_{i}\) and \(M_{2}=f_{tid_{i}}\left( r_{1}\oplus r_{2}\right)\). Then, the tag sends \({M_{1}}\) and \({M_{2}}\) to the reader. The reader evaluates and searches its database by using \({M_{1}}\), \({M_{2}}\) and \({r_{1}}\). If the reader does not find any match, it will stop the session. In case of a successful match, the reader authenticates the tag and updates the tag information which is \(\left( u_{i}\right) _{old}\) and \(\left( tid_{i}\right) _{old}\). Then it computes \(M_{3}=u_{i}\oplus \left( r_{2}\gg {l}/{2}\right)\) and sends \(M_{3}\) message to the tag. The tag computes \(u_{i}\) using \(M_{3}\) and checks that \(h\left( u_{i}\right) =t_{i}\). If a match is obtained, the tag authenticates the reader and updates its \(u_{i}\) and \(t_{i}\) values. Otherwise, the tag does not update the current values. This process is shown in Fig. 1.

We prove below that a RANDOMEYE adversary can trace a tag in this protocol without corrupting it.

Theorem 1

The SM protocol does not ensure the RANDOMEYE-WEAK privacy.

Proof

An adversary Adv can perform the following attack.

  1. 1.

    Adv creates two legitimate tags by using \({\mathscr {O}}^{CreateTag}(tid_{1},1)\) and \({\mathscr {O}}^{CreateTag}(tid_{2},1)\) oracles. Then, Adv draws two tags from the system by calling \({\mathscr {O}}^{DrawTag}\left( \frac{1}{2},2\right)\)oracle and obtains two pseudonyms \({{\varvec{T}}}_{1}\) and \({{\varvec{T}}}_{2}\). At this point, Adv does not know \(tid_{1}\) and \(tid_{2}\) that are the identifiers of the \({{\varvec{T}}}_{1}\) and \({{\varvec{T}}}_{2}\) tags respectively.

  2. 2.

    Adv calls \({\mathscr {O}}^{Execute}\left( {{\varvec{T}}}_{1}\right)\) and gets \(\theta _{\pi }=\left( 0,\pi _{1}\right)\) for \({{\varvec{T}}}_{1}\).

  3. 3.

    Then, Adv requests \({\mathscr {O}}^{RNG}\left[ \theta _{\pi },{{\varvec{T}}}_{1}\right]\) and obtains \(\left( RNG_{1},1\right)\) for \({{\varvec{T}}}_{1}\). For this protocol \(RNG_{1}\) is equal to the random bit strings \(r_{2}\) generated by the tag, \({{\varvec{T}}}_{1}\). \({\mathscr {O}}^{RNG}\) oracle performs the following procedures:

    1. (a)

      It generates all possible random strings for \(r_{2}\) with respect to the seed of the RNG used in the tag. Lets call the list \(\varvec{R}=\left[ r_{2}^{1},r_{2}^{2},\ldots ,r_{2}^{j},\ldots r_{2}^{|K|}\right]\) where |K| is the entropy of the seed.

    2. (b)

      It has the list of all the possible \(\varvec{X}=\left[ tid_{1}^{1},tid_{1}^{2},\ldots ,tid_{1}^{j},\ldots tid_{1}^{|K|}\right]\) values by computing \(\varvec{X}=M_{1}\oplus \varvec{R}\) because \(M_{1}\) is obtained within the protocol instance.

    3. (c)

      Then, it does the exhaustive search to check for the \(M_{2}\) messages with computing \(f_{\varvec{X}}\left( r_{1}\oplus \varvec{R}\right)\). Finding \(M_{2}=f_{M_{1}\oplus r_{2}^{j}}\left( r_{1}\oplus r_{2}^{j}\right)\), Adv obtains \(r_{2}\) that is equal to \(r_{2}^{j}\).

  4. 4.

    Adv obtains the \(tid_{1}\) for tag \({{\varvec{T}}}_{1}\) computing \(M_{1}\oplus r_{2}\) and updates the internal values of the tag according to the protocol procedure. Therefore, Adv has the \(tid_{1\left( new\right) }\) value of \({{\varvec{T}}}_{1}\).

  5. 5.

    Adv performs step 2, step 3 and step 4 for the \({{\varvec{T}}}_{2}\) tag. Adv updates the internal values of the tag and gets the \(tid_{2\left( new\right) }\) value of \({{\varvec{T}}}_{2}\).

  6. 6.

    Adv frees both tags with request \({\mathscr {O}}^{Free}\left( {{\varvec{T}}}_{1}\right)\) and \({\mathscr {O}}^{Free}\left( {{\varvec{T}}}_{2}\right)\), then she reaffects only one of them using \({\mathscr {O}}^{DrawTag}\left( \frac{1}{2},1\right)\). She obtains a new \({{\varvec{T}}}_{3}\).

  7. 7.

    Adv performs step 2, step 3 and step 4 for the \({{\varvec{T}}}_{3}\) tag and obtains \(tid_{3}\).

  8. 8.

    Then Adv compares \(tid_{3}\) with \(tid_{1\left( new\right) }\) and \(tid_{2\left( new\right) }\).

  9. 9.

    If \(tid_{3}=tid_{1\left( new\right) }\), Adv claims that \(T_{3}=T_{1}\) else she claims that \(T_{3}=T_{2}\).

The success probability of this adversary is equal to 1. Therefore, it is clear that Song and Mitchell’s Protocol is not RANDOMEYE-WEAK private. \(\square\)

Fig. 1
figure 1

Song and Mitchell’s Protocol

Full size image

5.2 Second Study Example: Akgün et al.’s Scheme

Akgün and Çaǧlayan [31] introduced a new authentication protocol and claimed that it is the first protocol that provides destructive privacy according to Vaudenay’s model with constant identification time. This scheme is a simple challenge/response protocol enhanced with Physically Unclonable Functions (PUFs) in order to achieve higher level of privacy.

This scheme has two phases. In the first phase, the system initializes itself. In this initialization phase, a shared secret S is randomly generated for the back-end server. Two random values, a and b are generated for each tag. Then each tag performs its own PUF P(.) to calculate \(c=S\oplus P\left( a\right) \oplus P\left( b\right)\). The back-end server stores all values \([ID_i, a_i, b_i, DATA_i]\) for each tag where \(DATA_i\) contains the information about a tag \(T_i\).

In the second phase called authentication phase, the reader generates a random number \(r_1\) and broadcasts it to the tag.

Secondly, a tag \(T_i\) which receives the signal of the reader, generates another random number \(r_2\). The tag also computes \(M_{1}=H\left( r_{1},r_{2},a_{i}\right)\), \(M_{1}=H\left( r_{2},r_{1},1\right) \oplus ID_{i}\) and \(h=H\left( r_{2},1,2\right)\). Then, it uses PUF to calculate \(k=P_{i}\left( a_{i}\right) \oplus r_{2}\) and deletes the \(r_2\) and \(P_{i}\left( a_{i}\right)\) values from the volatile memory. The tag updates k by computing \(k=k\oplus P_{i}\left( b_{i}\right) \oplus c_{i}\) and then \(P_{i}\left( b_{i}\right)\) is deleted from the memory too. The tag transmits \(M_1, M_2\) and k back to the reader.

Thirdly, the reader generates a new random number \(r_3\) and computes \(r_{2}^{\prime }=S\oplus k\), \(ID_{i}^{\prime }=M_{2}\oplus H\left( r_{2}^{\prime },r_{1},1\right)\). Then, the reader checks that the \(M_1\) message is equal to \(H\left( r_{1},r_{2}^{\prime },a_{i}\right)\) to authenticate the tag \(T_i\). If the equality is confirmed, then the reader computes \(M_{3}=H\left( H\left( r_{2}^{\prime },1,2\right) ,r_{3},b_{i}\right)\) and sends \(r_3\) and \(M_3\) to the tag \(T_i\).

Finally, the tag \(T_i\) checks that the \(M_3\) message is equal to \(H\left( h,r_{3},b_{i}\right)\) to authenticate the reader. If the equality is confirmed, the tag authenticates the reader too. Thus, mutual authentication is accomplished and the protocol is terminated successfully. This is shown in Fig. 2.

Fig. 2
figure 2

Akgün et al.’s Authentication Protocol

Full size image

Akgün et al. claimed that their protocol scheme provides destructive privacy according to Vaudenay’s privacy and security model with constant time identification property. Their protocol does not need key-updating mechanism on both, tags and back-end server. The authors use the common secret S to identify a tag with \(O\left( 1\right)\) time complexity. They base the security and privacy of their protocol on the PUFs that are regarded to have robustness, unclonability, unpredictability and tamper-evident properties [31]. We realized that there is a RNG misuse in their protocol design. We can prove that their protocol is neither destructive private nor secure. A RANDOMEYE adversary can trace the past and future transactions of the tag as proven below.

Theorem 2

Akgün et al.’s protocol does not ensure the RANDOMEYE-WEAK privacy.

Proof

An adversary Adv can perform the following attack.

  1. 1.

    Adv creates two legitimate tags by using \({\mathscr {O}}^{CreateTag}(ID_{1},1)\) and \({\mathscr {O}}^{CreateTag}(ID_{2},1)\) oracles. Then, Adv draws two tags from the system by calling \({\mathscr {O}}^{DrawTag}\left( \frac{1}{2},2\right)\)oracle and obtains two pseudonyms \({{\varvec{T}}}_{1}\) and \({{\varvec{T}}}_{2}\). At this point, Adv does not know \(ID_{1}\) and \(ID_{2}\) that are the identifiers of the \({{\varvec{T}}}_{1}\) and \({{\varvec{T}}}_{2}\) tags respectively.

  2. 2.

    Adv calls \({\mathscr {O}}^{Execute}\left( {{\varvec{T}}}_{1}\right)\) two times and gets \(\theta _{\pi }=\left\{ \left( 0,\pi _{1}\right) ,\left( 0,\pi _{2}\right) \right\}\) for \({{\varvec{T}}}_{1}\).

  3. 3.

    Then, Adv requests \({\mathscr {O}}^{RNG}\left[ \theta _{\pi },{{\varvec{T}}}_{1}\right]\). Adv obtains \(\left( RNG_{1}\right)\) and \(\left( RNG_{2}\right)\) respectively for \({{\varvec{T}}}_{1}\). For this protocol scheme, \(RNG_{1}\) is equal to the random bit strings \(r_{2}\) generated by the tag, \({{\varvec{T}}}_{1}\) for the first protocol instance and \(RNG_{2}\) is the secondly generated random bit string \(r_{2}\). \({\mathscr {O}}^{RNG}\) oracle performs the following procedures:

    1. (a)

      It generates all possible random strings for \(r_{2}\) with respect to the seed of the RNG used in the tag. Lets call the list \(\varvec{R}=\left[ r_{2}^{1},r_{2}^{2},\ldots ,r_{2}^{j},\ldots r_{2}^{|K|}\right]\) where |K| is the entropy of the seed.

    2. (b)

      It has the list of all the possible \(\varvec{X^{1}}=\left[ ID_{1}^{1},ID_{1}^{2},\ldots ,ID_{1}^{j},\ldots ,ID_{1}^{|K|}\right]\) values by computing \(\varvec{X^{1}}=M_{2}\oplus H\left( \varvec{R,}r_{1},1\right)\) because \(M_{2}\) and \(r_{1}\) are obtained within the first protocol instance.

    3. (c)

      It has the second list of all the possible \(\varvec{X^{2}}=\left[ ID_{1}^{1},ID_{1}^{2},\ldots ,ID_{1}^{j},\ldots ,ID_{1}^{|K|}\right]\) values by computing \(\varvec{X^{2}}=M_{2}\oplus H\left( \varvec{R,}r_{1},1\right)\) because \(M_{2}\) and \(r_{1}\) are obtained within the second protocol instance.

    4. (d)

      Then, it compares \(\varvec{X^{1}}\) and \(\varvec{X^{2}}\) and defines the identifier of the tag by finding the equal bit string of each list.

    5. (e)

      Finally, it obtains the random bit string \(r_{2}\) by using the corresponding identifier of the tag \(ID_{1}\) .

  4. 4.

    Adv obtains \(ID_{1}\) for \({{\varvec{T}}}_{1}\) tag by computing \(M_{2}\oplus r_{2}\) using one of the protocol instances.

  5. 5.

    Adv performs step 2, step 3 and step 4 for the \({{\varvec{T}}}_{2}\) tag. Adv obtains \(ID_{2}\) for \({{\varvec{T}}}_{2}\) .

  6. 6.

    Adv frees both tags with request \({\mathscr {O}}^{Free}\left( {{\varvec{T}}}_{1}\right)\) and \({\mathscr {O}}^{Free}\left( {{\varvec{T}}}_{2}\right)\), then she re-affects only one of them using \({\mathscr {O}}^{DrawTag}\left( \frac{1}{2},1\right)\). She obtains a new \({{\varvec{T}}}_{3}\).

  7. 7.

    Adv performs step 2, step 3 and step 4 for the \({{\varvec{T}}}_{3}\) tag and obtains \(ID_{3}\).

  8. 8.

    Then Adv compares \(ID_{3}\) with \(ID_{1}\) and \(ID_{2}\).

  9. 9.

    If \(ID_{3}=ID_{1}\), Adv claims that \({{\varvec{T}}}_{3}={{\varvec{T}}}_{1}\) else she claims that \({{\varvec{T}}}_{3}={{\varvec{T}}}_{2}\).

Therefore, if the adversary Adv captures the IDs, she can trace the past and future transactions of the tags of the scheme using the unchanging ID. Hence, the scheme does not provide forward and backward untraceability properties. \(\square\)

Theorem 3

Akgün et al.’s protocol does not ensure the RANDOMEYE-DESTRUCTIVE privacy.

Proof

Akgün et al.’s protocol does not provide WEAK privacy. Hence, it is not DESTRUCTIVE private. \(\square\)

Theorem 4

Akgün et al.’s scheme is not secure against RANDOMEYE adversary.

Proof

It is clearly seen that the Akgün et al.’s scheme does not provide RANDOM-WEAK privacy and a passive adversary is able to reveal the ID of a tag. Let an adversary \({{\varvec{Adv}}}\) reveals the ID of a tag and consequently has the random bit strings \(r_{2}\). Adv also has the k value obtained during eavesdropping to the protocol session where \(k=P_{i}\left( a_{i}\right) \oplus r_{2}\oplus P_{i}\left( b_{i}\right) \oplus c_{i}\). The shared secret S is generated as \(S=P_{i}\left( a_{i}\right) \oplus P_{i}\left( b_{i}\right) \oplus c_{i}\) in the initialization according to the protocol description. Thus, the adversary Adv obtains the shared secret S by computing S= \(k\oplus r_{2}\). The scheme is not longer secure after the shared secret S is obtained and the whole system can be broken by the adversary Adv.\(\square\)

6 Conclusion and Future Work

In this paper, we focus on the improper usages of RNGs in privacy-friendly RFID authentication protocols and show that misusing RNGs in a protocol design might cause serious security and privacy weaknesses. To prove our claim, we first have revisited and enhanced an RFID privacy and security model proposed by Vaudenay by modeling a new attack based on misusing of the RNGs. In this context, we extend the model by introducing a new RNG oracle and RANDOMEYE adversary class. Then, we apply our improved model on recently published lightweight RFID authentication protocols. We show that Song and Mitchell’s [30] and Akgün and Çaǧlayan’s [31] schemes are vulnerable to RNG attacks. In our point of view, RNGs should only be utilized to increase the security and privacy level of the protocols instead of becoming a brittle point of the scheme. It is known that a chain is only as strong as its weakest link and we point out that misusing RNGs might be the weakest link in a protocol design. Moreover, for future analysis, a completely new RFID privacy model can be constructed.