fault Injection Attack on Deep Neural Network - powerpoint

Pitfalls in Ultralightweight Authentication Protocol Designs

Gildas Avoine, Xavier Carpent, and Julio Hernandez-Castro

Abstract—This article introduces prudent engineering practices and offers recommendations to follow, together with typical mistakes

to avoid, when designing new ultralightweight authentication protocols. This work can help, as a sanity check, designers of RFID, NFC,

and sensor networks based security solutions to improve the security, reliability, and longevity of ultralightweight authentication protocol

designs. Additionally, it aims to help reviewers to quickly distinguish what is really new and worthy in a research area that has been

flooded lately with proposals of dubious quality.

Index Terms—Ultralightweight protocols, authentication, cryptanalysis, security, privacy, RFID, NFC, sensor networks

Ç

1 INTRODUCTION

RFID authentication is a very active and challengingresearch topic. It has strong requirements such as secu- rity of course, but also privacy, and yet very strong con- straints such as powerful adversaries and very constrained devices. This last point in particular is the focus of a signifi- cant part of the research community, and has spawned hun- dreds of papers [1]. Indeed, there is a strong incentive to build RFID tags below 5 cents that still provide some level of security. Such tags can not contain a battery, must make do with very few logic gates, and must be able to complete an authentication in very little time.

In response to that, a number of protocols have been created that rely on extremely simple operations to do basic cryptography. Such protocols have been named “ultralightweight”, a term coined by Chien in [2]. Although there is no precise definition adopted by authors of ultra- lightweight protocols, they can be broadly defined as proto- cols that are aimed at requiring about 1.5K GE (gate equivalents)1 or less, relying on only very simple operations on the tag’s side, and willing to accept compromises to offer some security level (See Chien’s definition [2]). This includes, in particular, most of the authentication protocols aimed at passive and inexpensive RFID tags.

As one might expect, most of these protocols are usually very weak, and are typically broken very quickly. More

importantly, there tends to be a certain lack of originality, novelty, and scientific soundness in these proposals, which is counter-productive and contributes to the relative stagna- tion in the field. A plausible reason why these papers are accepted is that reviewers not familiar with the related liter- ature fail to notice common mistakes in these protocols.

In this paper, we give a mature perspective on the situa- tion in the field of ultralightweight authentication protocols, and provide a description of most of the typical flaws that frequently undermine new proposals. This may be useful for potential reviewers to quickly determine if a proposal is worthy of publication or could be broken easily. It could also be used as a sanity check for ultralightweight protocol designers. Some authors, notably D’Arco and De Santis, highlighted in [5] a set of slightly different but related and often complementary observations to the ones we will examine in further detail and expand on this work.

The structure of the article is the following. In Section 2, we give some statistics related to the field and give addi- tional motivations for the article. In Section 3 we give a very quick description of the attacker model in ultralightweight authentication. In Section 4, we present the most typical mistakes found in ultralightweight protocols. In Section 5, we mention the problematic of dubious security proofs and detail why they are usually flawed. In Section 6, we present some recent proposals and propose attacks and comments on them based on the discussions from Sections 4 and 5. In Section 7, we end on a more positive note by presenting what we believe are the more promising approaches, and we finally present our conclusions in Section 8.

2 MOTIVATIONS

This section presents a few facts on the state of the art of ultralightweight protocols.

Table 1 presents a list of most prominent ultralightweight authentication protocols, and the first attack on each of them, when applicable. It also shows the date of publication of each article and highlights the time in months elapsed between the publication of a protocol and the publication of an attack on it. What we consider to be a “first attack” is the

1. It is relevant to point out that gate counts differ in the litterature, sometimes by a large margin. See a discussion on the subject in [3], [4].

� G. Avoine is with the D�epartement d’ingnierie informatique, Universit�e catholique de Louvain, Belgium, Brabant Wallon, Belgium. E-mail: gildas.avoine@uclouvain.be.

� X. Carpent is with the D�epartement d’ingnierie informatique, Universit�e catholique de Louvain, Louvain-la-Neuve, Brabant Wallon, Belgium. E-mail: xavier.carpent@uclouvain.be.

� J. Hernandez-Castro is with the School of Computing, University of Kent, Canterbury, Kent, United Kingdom. E-mail: J.C.Hernandez-Castro@kent.ac.uk.

Manuscript received 9 June 2014; revised 11 Sept. 2015; accepted 10 Oct. 2015. Date of publication 19 Oct. 2015; date of current version 2 Aug. 2016. For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org, and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TMC.2015.2492553

IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016 2317

1536-1233 � 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

chronologically first traceability or disclosure attack that tar- gets the specific construction of a protocol (we discarded desynchronization attacks because, although important, they do not target specific protocol weaknesses but rather general issues in their structure). The dates, both for proto- cols and attacks, are taken to be the earliest after becoming public (e.g., eprint or date of conference over proceedings).

Fig. 1 shows the distribution of the time required for the publication of an attack, based on data from Table 1. Although there are many factors influencing the data, it is clear that the time for publication of a serious attack is extremely short. The average number of months required is about 9.5.2 Half of the protocols are broken within eight months, and most of them within a year.

Note that depending on the journal or conference, it takes significant time to publish an attack on a protocol. We esti- mate that at least three to four months are required from fin- ished research to publication. Generally, it might also take time for the proceedings to become available. Note finally that some of these protocols have been published in rela- tively low-visibility venues, which has definitely helped increase their life expectancy. It is probably safe to assume that on average, a typical ultralightweight protocol is bro- ken in under four months following its publication.

In most cases, these protocols repeat time and again the same typical mistakes, and no progress is achieved. Many

proposals present striking similarities with existing proto- cols, and often have the exact same flaws, or even worse ones. Sometimes, hash functions or ciphers are used along- side usual ultralightweight operations such as XOR, addi- tions, rotations, etc. (we look at an example in Section 6). This makes the protocol basically not less expensive than a classical challenge-response, which is no longer ultralight- weight, and sometimes weaker. Moreover, there are typi- cally one to three papers presenting attacks on each protocol, and again they often exploit the same typical weaknesses.

In the following, we present briefly the attack model, and then go through the typical flaws that commonly appear in these ultralightweight protocols.

3 GENERIC ATTACK MODEL

Ultralightweight authentication protocols must primarily ensure that neither an impersonation attack, nor a key- recovery attack (even partial-recovery) is feasible. Protocol analyses usually consider the Dolev-Yao model [48], namely a model where the adversary is powerful but not almighty: the adversary cannot guess random numbers chosen in a sufficiently large space, she cannot decrypt or create valid ciphertexts without the correct secret, and she cannot

TABLE 1 List of Ultralightweight Protocols, the First Attack on them, and the Relevant Dates

Protocol Paper Publication Date First Attack First Attack Date Months

LMAP [6] 07-2006 [7] 05-2007 10 M2AP [8] 09-2006 [7] 05-2007 8 EMAP [9] 11-2006 [10] 04-2007 5 SLMAP [11] 10-2007 [12] 05-2009 19 SASI [2] 12-2007 [13] 06-2008 6 Qingling-Yiju-Yonghua [14] 8-2008 [15] 7-2009 11 Gossamer [16] 09-2008 N/A N/A N/A LMAP++ [17] 09-2008 [18] 04-2011 31 David-Prasad [19] 06-2009 [20] 06-2010 12 Lee-Hsieh-You-Chen [21] 08-2009 [22] 02-2010 6 Yeh-Lo-Winata [23] 02-2010 [24] 10-2010 8 Eghdamian-Samsudin [25] 11-2011 [26] 06-2012 7 RPAP [27] 10-2011 [26] 06-2012 8 NRS [28] 11-2011 [29] 12-2013 25 LPP [30] 12-2011 [29] 12-2013 24 PUMAP [31] 3-2012 [26] 06-2012 3 DIDRFID/SIDRFID [32] 5-2012 [26] 06-2012 1 RAPP [33] 5-2012 [26] 06-2012 1 Improved LMAP+ [34] 5-2012 [26] 06-2012 1 RIPTA-DA [35] 7-2012 [36] 7-2013 12 Pang-Li-He-Alramadhan-Wang [37] 3-2013 [38] 12-2013 9 DT [39] 5-2013 [40] 06-2013 1 RAPLT [41] 10-2013 this article 11-2013� 1� UMAP [42] 9-2013 this article 11-2013� 2� Ling-Shen [43] 11-2013 this article, same as [13] on [2] 02-2014� 3� LPCP [44] 11-2013 [38] 12-2013 1

� Date when the attack was found, not published. Numbers omitted in the discussions below for fairness.

Fig. 1. Histogram of the time for ultralightweight protocols to be broken.

2. We discarded Gossamer in these calculations since no attack has been published on it yet to the best of our knowledge. There are, how- ever, existing desynchronization attacks (see [45], [46], and [47]), but they are related to the structure of Gossamer, not its operations. These papers propose different fixes to the problem.

2318 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

retrieve private keys from public information. However, she can easily communicate with both a tag or a reader, eaves- drop communications in both directions, or perform relay attacks (possibly modifying the messages). This last point is often a source of confusion in ultralightweight proposals, which treat active attackers as being more powerful than eavesdroppers, despite relay attacks being in fact not harder than eavesdropping (see for instance the libnfc library [49]).

Ultralightweight authentication protocols usually also attempt to ensure privacy. The privacy property is com- monly defined in authentication protocols as the inability for an adversary to track a prover. Privacy is consequently also called untraceability and is represented by an experi- ment where two interactions prover–verifier are provided to the adversary, and the latter must recognize which one was produced by his target (previously queried—possibly with restrictions – during a learning phase). Several untra- ceability models exist, with different experiments. The most widely used models are due to Juels and Weis [50], Vaude- nay [51], Deursen, Mauw, and Radomirovic [52], Hermans, Pashalidis, Vercauteren, and Preneel [53], and Avoine, Coi- sel, and Martin [54]. It is today strongly advised to use such a well-established model instead of ad-hoc ones. A compari- son of existing models was done by Coisel and Martin [55].

Designing a privacy-friendly authentication protocol is a difficult question. While a classical challenge-response proto- col (where the identity of the prover is not sent in the clear on the channel) seems to be privacy-friendly at first sight, it suf- fers from a linear complexity search (all the keys stored by the verifier must be checked to identify the correct prover) and does not ensure forward-privacy: if the prover is com- promised, the privacy of the past interactions is no longer ensured. The latter issue can be mitigated by updating the key, but desynchronization attacks must be prevented in such a case. Vaudenay actually demonstrated that only pub- lic-key cryptography can ensure the highest attainable privacy level [56]. Ultralightweight authentication protocols do not necessarily target the highest privacy level, though. Avoine, Coisel, and Martin’s model of privacy [54] for instance introduced the notion of existential and universal traceability (intuitively, a protocol is existentially traceable if it is possible to identify a tag from two communication traces, unless a legitimate authentication took place between them).

4 COMMON FLAWS

4.1 Linearity and T-Functions

We use here the same definition of T-functions proposed by Klimov and Shamir in [57], which is the following: A T-function is a mapping from n-bit words to n-bit words in which for each 0 � i < n, the bit i in any output word depends only on bits 0; 1; . . . ; i of any input word. This con- cept is very useful because all the Boolean operations and most of the numeric operations in modern processors are T- functions. Additionally, the composition of T-functions results also in a T-function.

These have many nice properties, but almost by defini- tion also a quite undesirable one: they achieve very poor levels of diffusion. By definition, in a T-function it is not possible that all output bits depend on all input bits, which is the ideal scenario for security purposes. This is

particularly dangerous in cryptographic applications, light- weight or otherwise. The only reasonable way to address this shortcoming is by combining these operations with other which do not exhibit this characteristic. But unfortu- nately many designers do not follow this simple combina- tion rule, and have proposed schemes entirely based on T-functions which are doomed to fail.

We start by showing some common mistakes found in the UMAP family of protocols. These were pioneer pro- posals in many ways but they incurred in what, with the hindsight gained after more than 8 years of research in the area, now looks like quite elementary mistakes. We show in the following the scheme used in LMAP, presented in [6] and pictured in Fig. 2, which is still one of the most clear examples of this vulnerability.

As we can see in Fig. 2, this early protocol is composed exclusively of T-functions (modular addition,�,_). This seri- ously limits its security due to their poor diffusion character- istics. Not only the message generation is marred by this, but it also affects the key update phase. This same pitfall is pres- ent in all members of the UMAP protocol family. The quick appearance of multiple attacks like those of [7], [58], [59] is, in retrospect, hardly surprising. Despite this, recent proposals continue to rely heavily and carelessly on T-functions.

Not only T-functions but also linearity should be avoided, or at least dealt with carefully in cryptographic protocols. Formally, an operation f is defined as linear in this context if fðx�yÞ¼ fðxÞ�fðyÞ. If a protocol or primitive is linear, it always accepts a better (and in most cases much better) attack than exhaustive key search. Not to mention linear

Fig. 2. The LMAP protocol.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2319

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

cryptanalysis. This, of course, flagrantly violates one of the basic design principles of every cryptographic design, hence the reasoning behind avoiding linearity at any price, as it constitutes a vulnerability in itself.

This may be clear to most members of the cryptography community, but seems less obvious for some of the design- ers of lightweight protocols. Most people know that some of the common bitwise operations are linear, but many seem to forget that permutations in general and rotations (for more security implications of the rotation operation, please see Section 4.3) in particular are also linear operations, so one should not base the security of a protocol on those oper- ations alone, because the composition of linear operations is also linear.

Nonlinearity needs to be injected at some stage of the design, or otherwise the protocol remains linear overall and, consequently, very insecure. Despite this, we can find in the literature many examples of designers disregarding this basic policy. Particularly notable and common exam- ples are the many proposals whose security seems to be based almost exclusively in the use of Cyclic Redundancy Codes (CRCs) that many authors seem to forget are also lin- ear and, as such, offer very little security if at all.

This is excusable to a certain extend in proposals that want to be compliant with the EPC-C1-G2 standard recom- mendations, but then the security claims of the proposed protocols should be adjusted down accordingly. CRCs are linear and they should under no circumstances be employed in cryptography. For a further example of this, see Section 5.2.

As an additional example of how pervasive this mistake is, the papers [44] and [37] are good very recent illustrations of this common failure. Not surprisingly they were both quickly dismantled in [38].

4.2 Biased Output

Another important weakness of many lightweight schemes proposed in the last years is that some of the operations used have a biased output, a feature that in many cases lead to additional security vulnerabilities. This is typical of Bool- ean functions such as OR (_) and AND (^), where x_y and x^y have, for unbiased random values of x and y, heavily (75 percent) biased outputs, respectively, towards 1 and 0. This can constitute a security weaknesses because these two Boolean functions leak information for both of their argu- ments. For example, if xi _yi ¼ 0, then xi ¼ yi ¼ 0, which discloses both the inputs. This happens roughly 25 percent of the times (similarly with AND, of course). This could be more than enough to, after seeing some exchanges, be able to completely recover all the inputs. An additional undesir- able property derived from these highly biased outputs is the possibility of message insertion. For instance, imagine that one of the exchanged messages, used for synchroniza- tion or authentication purposes, is the result of one of this biased operators. Then, an attacker can easily impersonate it with a high probability, so it is a very bad idea to use it for authentication purposes, as proposed in many protocols. Let’s exemplify again over the LMAP protocol. We have message B ¼ðIDS _K2Þþn1, a typical construction that has been seen in this or similar forms many times later. The issue here is that B is very biased and thus can be

impersonated with high probability even for an attacker who doesn’t know any of the secrets K2 or n1. Even more worryingly, as the value of B is public (it is exchanged in

the open), the attacker can use B �1 as a very good approxi- mation to the secret n1 (on average, 75 percent of the bits are correct), and this approximation can be used later in other parts of the protocol to approximate the secret.

4.3 Rotations

Rotations have been used for a long time in cryptography. Modern block ciphers and hash functions still mostly rely on ARX (addition, rotation, XOR) designs. Rotations are extremely cheap to implement, and they bring diffusion, which complements nicely the addition and the XOR (which exhibit poor diffusion properties, as shown in Section 4.1). Fixed-amount rotations are typically used in ARX designs, but data-dependent rotations, as first featured in the RC5 block cipher [60], also exist.

The SASI [2] protocol was the first ultralightweight authentication protocol to feature data-dependent rotations as far as we know. Since then, most ultralightweight proto- cols have used them, and in many cases they are the weak spot for ad-hoc attacks. Two types of rotations are typically used in these protocols: modular rotations (as used in RC5) and Hamming weight rotations. In the following, we denote the rotation operation by Rotðx; yÞ, in accordance with the literature. The rotation consists in a circular left shift of x by rðyÞ positions, where rðyÞ¼ y mod L for modular rotations, and rðyÞ¼HðyÞ for Hamming weight rotations.

One thing to bear in mind is that a rotation is a permuta- tion and is therefore linear, inheriting all the pitfalls com- mented in Section 4.1.

The most important shortcoming with data-dependent rotations is that there are only L possible outputs (where L is the size in bits of the input). Moreover, the distribution of these outputs is known a priori. The modulo operation has a uniform distribution over uniform input, and the Hamming weight has binomial distribution BðL; 1=2Þ over uniform input. Fig. 3 shows the distribution of probability of rðyÞ for the two rotations, with y a uniform random variable and with L ¼ 96.3

Modular rotations have a maximal entropy (log 2L ¼ 6:58 bits), since each shift is equiprobable. This minimizes the advantage of the adversary for guessing the output. Neverthe- less, they are quite probable to behave like the identity opera- tion (probability of 1=L). This has led to many attacks, whether when the attacker assumes this blindly (as the desynchronization attack on PUMAP in [26]) or when she is able to verify it (as the traceability attack on modular SASI in [61]).

Fig. 3. Distribution of probability of rðyÞ for the modular and Hamming weight rotations, with y a uniform random variable and L ¼ 96.

3. This is the value that is typically used in the literature for key lengths.

2320 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

Hamming weight rotations have worse entropy (e.g., 4:34 bits in the case of L ¼ 96) than modular rotations. In partic- ular, the three-sigma rule implies that, for instance in the case of L ¼ 96, the number of bits rotated is between 33 and 63 in 99.7 percent of cases. It is therefore even easier for an attacker to guess the output of a rotation. However, Ham- ming weight rotations virtually never behave like the iden- tity. Indeed, this would require either rðyÞ¼ 0 or rðyÞ¼ L, which happens only when y ¼ 0 or y ¼ 2L �1, respectively.

Mod n cryptanalysis [62] is also a promising tool to attack schemes using rotations and additions, although it has never been applied in the cryptanalysis of an ultralight- weight protocol. It has, on the other hand, been used to suc- cessfully attack block ciphers such as RC5P and M6, which use the same kind of operations.

4.4 Message Composition

Securely designing the messages exchanged over an ultra- lightweight protocol is a difficult and open problem. Keep- ing the secrets exchanged as secure as possible against any leakage is indeed a big challenge, particularly in such con- strained environments. Generally speaking, the messages should guarantee good confusion and diffusion properties for the secrets. That is, the secret should be thoroughly involved in the construction of the messages, and a subtle change in the secret should result in completely different messages. In block ciphers, for instance, these two proper- ties are usually achieved by using iterated substitution-per- mutation networks. However, due to the constraints of ultralightweight protocols, messages are usually built using a handful of operations, and in many cases good confusion and diffusion levels are not satisfied.

In LMAP for instance, the key update phase is defined by

IDSðnþ1Þ ¼ ðIDSðnÞ þðnðnÞ2 �K ðnÞ 4 ÞÞ� ID; (1)

where we can see that the ID, a secret that the protocol is designed to protect, is simply XORed with a mixture of pub- lic and secret values. This operation clearly exhibits poor confusion and diffusion properties. This quite frequent fea- ture heuristically leads to major leakage of secret bits, as the rest of the message the ID is combined with may include bias, or be partially known by the adversary.

There are many more examples that exhibit transgres- sions to this rule of thumb for minimizing secret leakage, even within the most recent proposals. Consider for instance this message of the RAPP protocol [33]:

C ¼ Perðn1 �K1; n1 �K3Þ� ID; (2) where we can see again that the ID is at the out most posi- tion of the message construction. This would have no seri- ous consequences if the rest of the message was perfectly random and unknown to an adversary (as in a One Time Pad), but this is not the case here.

4.5 Knowledge Accumulation

4.5.1 Knowledge Accumulation of a Static Secret

If partial leakage of a static secret occurs in a round of a pro- tocol, there is an obvious traceability issue. Indeed, it becomes possible for an attacker to correlate two leaked

traces of an eavesdropped exchange. A typical example is recovering the least significant bit of the static identifier (see for instance [13], the first traceability attack on SASI).

More importantly, an attacker is sometimes able to recover the full static secret after a few rounds. Indeed, she can combine the different observations using Bayesian inference. An example of such an attack was the full cryptanalysis of SASI [63].

4.5.2 Key Updating

One of the initial goals of synchronized protocols is to pro- vide forward privacy. Forward privacy is a stronger notion than privacy. Simply put, a protocol is said to be forward pri- vate if an attacker, having recovered the internal state of a tag, is not able to recognize the tag in past interaction traces. For a more formal definition, see [64]. Forward privacy can- not be achieved in a protocol if the secrets used in the exchange are all static. Indeed, if the attacker knows the secrets of a tag at some point, it also knows them in the past, since the secret does not change in the tag’s lifetime. There- fore, she can recompute the messages sent by a tag in previ- ous interactions, and recognize it easily. Note that a changing secret is required for forward privacy, but it does not guarantee it (indeed, there are many synchronized proto- cols that are not private, and therefore not forward private).

A positive side effect of changing the secrets is that it is conceivably harder to obtain the full secret at any given time, if only a partial leakage is obtained at every authenti- cation round. This seems to be a good feature as it is intui- tively harder to hit a moving target that a static one. However, this does not make the full cryptanalysis impossi- ble, just slightly harder, as has been demonstrated with the Tango attacks described in Section 4.7.3.

4.6 Desynchronization

Desynchronization attacks are active attacks. We study them here despite some ultralightweight protocols not claiming resistance against active attackers, only against passive ones. Nevertheless, as we point in Section 3, active attacks are par- ticularly relevant in the considered context. In any case, most authors aim to achieve resilience against active attacks, including some defense against desynchronization.

Desynchronization generally occurs when and active attacker is able to stop the prover and/or the verifier to engage in further successful executions of the protocol. It is generally achieved by tricking the prover, the verifier, or both, into believing that a successful authentication session has taken place, thus updating internal counters and varia- bles in an asynchronous way. Common implementations of this attack involve sending specially crafted messages to make only one of the involved parties reach an irreversible state from which it will not be capable of communicating in the future with other parties.

Many ultralightweight authentication protocols have been shown to be vulnerable to attacks of this kind. A wide- spread defense mechanism consists in storing the last state (pseudonym and keys) used, together with the current one, and use the former if the latter fails (as first suggested in LMAP [6], by using a flag that is activated when an authenti- cation session terminates abnormally). This approach

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2321

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

however modifies the behavior of the protocol, which opens the door to other attacks such as timing attacks [65]. More- over, it comes with the cost of storing an extra copy of the state, which is relatively expensive in terms of area. Although not exactly flawed, this solution is not perfect.

Desynchronization protection in ultralightweight authentication protocols is relatively poorly studied on its own, and in any case caution is recommended when analyz- ing the security against such attacks.

An example of two classical desynchronization attacks can be found in [66]. Desynchronization can be considered as a type of Denial of Service attack, and as most DoS attacks, it does not admit an easy, ideal solution.

4.7 Vulnerability to Generalist Attacks

There are only a handful of generalist attacks published in the relevant literature that have proven to be successful against ultralightweight protocols. By generalist we refer to attacks that are not based on ad-hoc methods, and that are then of application against a large class of ultralightweight protocols. We proceed to describe them in some detail on the following sections.

4.7.1 Recursive Linear and Differential Cryptanalysis

In 2013, Ahmadian et al. introduced in [67] a new frame- work for implementing full disclosure attacks against ultra- lightweight protocols based on the new concepts of recursive linear and recursive differential cryptanalysis. Both exploit the use of triangular functions, and recover all secrets in a recursive manner. The linear version of the recursive attack is applied to the Yeh-Lo-Winata and SLMAP protocols after passively eavesdropping just one authentication session. On the other hand, the differential version of their recursive attack is deemed to be even more powerful and can be successful against protocols immune to the linear attack, for example LMAP++ and SASI. How- ever, the differential attack is active as the attacker needs to block some exchanged messages, and also requires more (around 13) consecutive authentication sessions.

4.7.2 Gr€obner Basis Attacks

Daewan Han published in 2011 [68] new attacks against lightweight RFID authentication protocols that employed Gr€obner basis. He argued his attacks were superior to previ- ous ones because, by not using any specific characteristics of target protocols, they are generally applicable to a variety of them. In addition, he showed his approach was able to recover most secret bits of protocols such as LMAP, M2AP, EMAP, SASI, Lo et al.’s protocol, and Lee et al.’s protocol. The computations needed only a few seconds on a single, standard PC. His approach needed anything between 1 and 5 eavesdropped sessions,took between 0.4 and 151.8 sec- onds, and recovered from 94.9 to 100 percent of the secret bits. The author carried out his attacks with the help of the software package PolyBori, implemented in Sage. The major contribution of this paper is that the author presented over- whelming evidence that Gr€obner basis are a very powerful toolkit for the cryptanalysis of ultralightweight protocols.

The attacks presented in the previous two sections were published much later that the following two attacks, and

were no doubt influenced by them, so we will describe these two earlier attacks in some more detail in the following.

4.7.3 Tango Attack

The Tango Attack was first introduced in [20] and [24], and later employed in [69]. Its concept is extremely simple, but it is notable for being another generalist attack.

It could also be seen as a new tool to analyze lightweight protocols, and thus helpful in the design of more secure future proposals. The Tango attack is successful against other lightweight protocols, apart from those it was shown to break in the literature. This is a direct consequence of designers not having strict constraints on the resources needed for an adequate (i.e., highly nonlinear) mixture of the internal secret values in the message composition. This makes it hard to avoid leaking some secret bits in every ses- sion. The Tango is an attack that aims to obtain a full disclo- sure of all secrets that the protocol is designed to conceal. It is a passive attack that generally only needs to eavesdrop a small number of (possibly consecutive) authentication ses- sions, as shown in Fig. 4. This is a very realistic attack sce- nario. The Tango attack is a simple, yet powerful technique of cryptanalysis which is based on the computation and full exploitation of multiple approximations to said secret val- ues, using Hamming distances and the representation of variables in an n-dimensional space.

Its first use was against the David and Prasad proto- col [19], and it emerged as a passive (i.e., completely realis- tic in the underlying security model) and extremely efficient attack to fully recover the secret key values K1 and K2 and the static identifier of the tag ID.

The attack is divided into two main phases: 1) Selection of good approximations; and 2) Combination of these good approximations for disclosing Ki or ID. We briefly describe the two phases below.

Phase 1: The attack exploits the leakage of secret informa- tion over the insecure radio channel due to fact that exchanged messages are derived from secret values by using relatively simple (i.e., not highly nonlinear) opera- tions only. This is why the attacker can find and succeed in using multiple simple combinations of the exchanged

Fig. 4. A genetic tango attack against the David-Prasad RFID ultralight- weight authentication protocol, from [69].

2322 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

public messages fðA; B; D; E; FÞ as good approximations for the secrets Ki or ID. In weak protocols, public exchanged messages do not hide these secret values well enough. From all the set of approximations, the adversary is interested on those that are systematically closer (on aver- age) to the target secret value. That is, those for which the Hamming distance between an approximation Z and the value X deviates from the expected value 48, so either HðZ; XÞ < 48 or HðZ; XÞ > 48 significantly.

Phase 2: The basic idea at this stage of the attack is to com- bine multiple approximations obtained in different sessions, to construct a global one which is highly correlated with the secret values (i.e., keys Ki and static identifier ID). This can be done in a number of different ways and forms, but for instance in the case of the David-Prasad protocol, even a simplistic approach works quite nicely.

The procedure is the following: for each authentication session eavesdropped, a number of good approximations to the secret values is computed, and then stored as rows of three different matrices. After eavesdropping a given num- ber of sessions, the global values are computed simply by repeatedly adding each of the columns of the matrices, and returning a 0 if the total number of ones in the said column is below a given threshold, or a 1 otherwise. The simplest way to obtain a final value is to select the majority value in each column of this matrix. One can quickly sum all the rows to obtain a final vector. Then, if the value in a column of this vector is greater than half of the number of approxi- mations times the number of eavesdropped sessions, a 1 is conjectured in that column, or a 0 otherwise.

In the case of the David-Prasad protocol, this easy and efficient way of combining approximations works surpris- ingly well for producing accurate global approximations to all three secret values after eavesdropping a relatively small number of authentication sessions. Results are pow- erful enough to consider the protocol completely broken, as after observing only 5 or 10 sessions, an attacker can guess about 80 out of 96 bits of the keys and static identi- fier, as shown in Fig. 4. The remaining ones can be easily identified by an offline brute force search, or by eaves- dropping more sessions. These results contradict the security properties claimed in [19].

After conducting the attack, the adversary is able to retrieve all the secret information shared between the tag and the server, so she can trivially bypass any authentica- tion mechanisms (i.e., tag and reader authentication) and impersonate the tag in the future, or just clone it. Confiden- tial information is put at risk and tag’s answers can be tracked even though two random numbers are used in each session. A desynchronization attack against the tag (or the sever) is also quite straightforward, since the adversary can generate any desired valid synchronization messages.

In [69], a technique to automatically find new good approximations based on the use of genetic programming is described. This further automates the whole Tango attack, and makes it suitable for testing new proposals in a general- ist manner.

The Tango attack could be regarded as a close version of the linear cryptanalysis attack by Matsui [70], in which the attacker tries to find a linear approximation for the cipher with maximum possible bias, and extract secret information

once enough data is available to her. The main difference between the Tango and linear cryptanalysis is that the former is not limited to linear combinations of its inputs and is, in this sense and in this sense alone, more general than the latter.

4.7.4 Heuristic Simulation Attacks

The concept behind heuristic simulation attacks, again one of the few general-purpose published attacks against ultralight- weight protocols, is very simple: To infer all or part of the secrets used in a protocol by extracting information from the proximity between the exchanged messages in a real protocol run and those generated by an approximation to the secrets.

These attacks generally start from a randomly generated set of secret values. Then, by applying some heuristic tech- niques (like simulated annealing) it tries to approximate the true value of the secrets. For that it employs a fitness func- tion that is generally a function of the distance between gen- erated messages and the eavesdropped ones.

Different degrees of success in this approximation could lead to a key recovery attack (none published at the moment, but likely to be possible against weaker protocols) or to a traceability attack (when only some parts of the secrets can be recovered). Of course, a number of different heuristic techniques can be used ranging from hill climbing or simulated annealing to genetic algorithms. The fitness function is generally a measure of the distance between two sets of messages, but can be quite more complex, like weigh- ing some messages more than others, etc.

The first application of this approach was in [12], [71], which presented a traceability attack against SLMAP [11]. Authors showed a new meta-heuristic-based traceability attack on SLMAP and analyzed its implications. The main interest of their approach is that it is a complete generalist technique that does not make any assumptions on the com- ponents of the underlying protocol and can thus be easily generalized to analyze many other proposals.

The fitness function used is shown in Equation (3):

fS ¼ Xi¼N

i¼0 HðMi �M0iÞ �LN�i; (3)

where Hð�Þ is the Hamming weight, M0i are approximations to the real eavesdropped messages Mi, L is the length of each message, and N is the number of observable messages.

The main idea behind this approach is to transform the cryptanalysis of a security protocol into a search problem, where a large number of different search meta-heuristics can be applied. In general, during this search one tries to find which are the secret state values (keys, nonces, etc.) of some subset of the parties involved in the protocol.

This could be done in various ways, but the most natural approach is to measure the cost of the tentative set of secret values by the proximity of the messages produced by these tentative solutions to the real public messages generated and exchanged during the actual protocol execution, as in Equation (3).

Most cryptographic protocols should exchange one or more messages to accomplish their intended objective(s) (authentication, key exchange, key agreement, etc.), and in the vast majority of cases these messages are sent via an insecure or public channel that can be easily snooped.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2323

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

In this attack model, the cryptanalyst generally tries to infer the secret values that the two parties intend to hide by exploiting the knowledge of the exchanged messages. In a robust, secure, well-designed cryptographic protocol, even states that are very close to the real state should not produce messages that are very close (for any useful distance defini- tion) of the real public messages.

This should be done, typically, by means of a careful design and message construction based on the use of some highly-nonlinear cryptographic primitives such as block ciphers or hash functions.

Unfortunately, new proposals in the field of lightweight cryptography, which are intended towards very computa- tionally constrained environments (such as low-cost RFID systems) cannot use classical cryptographic primitives.

Then, for this search problem, a number of meta-heuris- tic techniques can be used to minimize the distance between the candidate and the real exchanged messages. In [12], the authors used a Simulated Annealing technique, which is a meta-heuristic technique that is extremely efficient and has some ability to avoid becoming quickly trapped in local minima.

Algorithm 1. Meta-Heuristic Traceability Attack against SLMAP

Snoop an SLMAP run Known IDSn; A; B; C; D repeat k times Start a Simulated Annealing to minimize fS Run SLMAP over the Known values Compute approximation for IDSnþ1 and store in ListIDS

end MajIDS majority vector of ListIDS Get IDS0 and IDS1, candidate values for IDSnþ1 r0 correlation between MajIDS and IDS0 r1 correlation between MajIDS and IDS1 if r0 > r1 then output 0

else output 1

end if

With this, the next IDS can be predicted with sufficient accuracy despite not knowing the protocol secrets, and hence to mount a successful traceability attack. One impor- tant characteristic of their attack is that it was successful after eavesdropping only one authentication session, which is a very economic requirement compared with those of other passive attacks.

The general traceability attack algorithm is described in Algorithm 1.

This attack is efficient and effective, with a quite high success probability (around 95 percent) for a number of tri- als k ¼ 50 as shown in Table 3 in Appendix.

4.7.5 Use

These attacks are quite simple, powerful, and attractive due to their generality and potential.

We strongly encourage that new proposals be tested against them to avoid major pitfalls before publication.

Resilience against all these attacks will of course not prove that the security of the new protocol is foolproof, but at least will offer guarantees that the scheme has avoided some of the trivial security weaknesses that plague most of current proposals.

5 DUBIOUS PROOFS OF SECURITY

We to examine in the following some of the many security proofs that different authors have used over the years in an attempt to prove the security of their proposals.

5.1 Randomness Tests

As shown in Fig. 2, one of the first proposals in this area, LMAP, tried to prove some degree of security by verifying that the exchanged messages looked random enough. For that, multiple sessions of the protocol were run and the exchanged messages recorded and later analyzed with dif- ferent randomness test batteries such as the well-known ENT [72], Diehard [73] and NIST [74].

The results were indeed impressive, with the messages used for running the protocol passing all tests with flying colors. However, this does not prove any security level, as LMAP was broken shortly afterwards. This simple method- ological approach presents a number of limitations. Let us have a deeper look on the protocol, as shown in Fig. 2. First, the most obvious one is that we are injecting into the mes- sages two fresh random numbers, n1 and n2, generated by the reader, and this makes it hardly surprising that some of the exchanged messages, that are combined with these two random messages, look random. Randomness might appear, then, not as a consequence of a well designed proto- col but just as a result of employing these sources of ran- domness repeatedly during message composition. Let us examine an artificial, very simple, and Trivially Weak authentication protocol, depicted in Fig. 5.

TABLE 2 Randomness Tests over the Set of LMAP Exchanged Messages

A B C D

Entropy (bits/byte) 7.999999 7.999999 7.999999 7.999999 Compression Rate 0% 0% 0% 0% x2 Statistic 250.98 (50%) 255.71 (50%) 244.46 (50%) 255.18 (50%) Arithmetic Mean 127.5062 127.4977 127.4946 127.5030 Monte Carlo p Estimation 3.1413 (0.01%) 3.1417 (0.0%) 3.1417 (0.0%) 3.1413 (0.01%) Serial Correlation Coefficient �0.000040 0.000010 �0.000077 �0.000036 Diehard Battery (Overall p-value) 0.227765 0.775516 0.641906 0.410066 NIST Battery @ @ @ @

2324 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

It is clear that, in this case, an attacker can trivially recover the values of all secrets involved simply by solving the trivial equations involved. Indeed,

n2 ¼ A �D n1 ¼ B �E K1 ¼ A �B�E K2 ¼ B �A�D K3 ¼ A �B�C �D�E

IDtag ¼ F �C:

Nevertheless, even in this very simple and weak protocol, exchanged messages pass all randomness statistical tests.4

At the very least, to prevent the indirect measure of the randomness of the source of n1 and n2 one has also to examine in detail all the correlations between these exchanged messages.

So if by now it seems clear that randomness of the exchanged messages is not a sufficient condition, it should also be clear that it is neither a necessary one. Another triv- ial way of showing this is by thinking about highly format- ted messages and how, even if a protocol is secure, due to formatting and padding of some or all of its messages these may not pass some randomness test.

So we just have intuitively shown that randomness of the exchanged messages is neither a sufficient nor a nec- essary condition for protocol robustness, and as such it should no longer be used to prove any kind of security level in future proposals.

5.2 BAN and GNY Logic

Some authors have tried to use BAN logic to prove the secu- rity of their proposals. A notable example is [14]. Needless to say, this approach did not worked out as intended and,

despite being accompanied by a formal security proof in BAN logic the proposal was broken shortly afterwards in [15]. Let us analyze this example in some more detail: The authors mistakenly employed CRC as recommended by the EPC-C1-G2 standard, but instead of using them as sim- ple error detection tool, they employed them for encryption. In their idealized model, they identified their CRC usage as equivalent to encryption, so some of the BAN logic rules (for exampleR1: Message-meaning rule) do not hold any more. This is a particularly flagrant mistake because CRCs are linear and should never be used for encryption, hashing or any other cryptographic purposes. But it is also a very common error, as never an idealized scenario like the one modeled by BAN logic (with perfect, unbreakable and zero- leaking ciphers) accurately models reality. The level of abstraction needed in the modeling phase basically makes it impractical for most realistic situations. This is, unfortu- nately, not only a limitation of BAN logic but, to different extents, is also in most formal models (GNY, etc.) which makes them not very relevant for our purposes.

A recent example of the current and continuous use of these quite limited approaches is [75], where again BAN logic was used again to proof the security of the proposal, despite its severe limitations and unrealistic assumptions. Another recent case can be found in Section 6.3, where a protocol published in November 2013 uses GNY logic to prove its security. Needless to say, this proposal can be attacked quite straightforwardly as mentioned in Section 6.3.

5.3 Other Approaches

Recently, some authors are taking a different approach to this problem, by using automatic analysis tools previously employed on the formal analysis of classical protocols. Two interesting examples are [76], and [77].

In the first, the author uses the AVISPA [78] tool to ana- lyze the security of the LMAP protocol. We have presented multiple vulnerabilities of this protocol along the article, so we are a little wary of the conclusion of this work, where apparently only two attacks have been discovered by AVI- SPA and the author proposed an easy patch.

Although these results have to be examined with more caution, we believe the general approach is promising and that better proposals will appear if using the AVISPA and similar tools becomes commonplace in the area.

In [77], the authors propose a key establishment and deri- vation protocol for EPC Gen2 tags, and employ model check- ing techniques to verify whether the security properties needed hold in a finite state machine. For that, they use auto- mated reasoning, specifically the Constraint-Logic based Attack Searcher (CL-AtSe), and the HLPSL input language.

We strongly believe this should be an approach to encourage in the future, and that all new proposals should have been tested by automated tools prior to acceptance. Of course attacks could still exist after this check, but at least we will avoid proposals that fall flat on well-known mis- takes from the past.

6 WEAKNESSES IN RECENT PROTOCOLS

In this section, we present three recently published ultralight- weight protocols, and propose attacks on them. These attacks

Fig. 5. The Trivially Weak protocol, for demonstration purposes.

4. Provided, of course, that the (P)RNG used for creating n1 and n2 is good enough.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2325

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

are new as far as we know, and illustrate the discussions of Sections 4 and 5 by highlighting weaknesses in their design.

6.1 Bilal and Martin

Bilal and Martin proposed in September 2013 a protocol called UMAP [42]. For reference, the protocol is depicted in Fig. 6 in Appendix. It uses modular rotations, so a natural first attempt at analyzing its security is to look at what hap- pens when they behave like the identity. This happens with a non-negligible probability of L�2. The relevant equations of the protocol become:

A ¼ n2 þ IDS þK þID þn1 B ¼ n1 þ IDS þK þID þn2

IDSnext ¼ n1 þ IDS þn2 Knext ¼ n2 þK þn1:

Note that in particular, we have that A ¼ B. We thus have that, with probability L�2, an attacker can authenticate in place of a tag, just by knowing the IDS of some target tag (this may be obtained beforehand simply by sending hello to the tag), and by replicating A as sent by the reader. This attack vector is addressed in Section 4.3.

Another point regards the function f. It is described in [42] as a “lightweight pseudo random function”. If such a func- tion is readily available on the tag, and if it has good security properties, then why bother with the other constructions? As mentioned in Section 2, a very basic challenge-response pro- tocol, such as the following, works just as well:

R ! T : hello T ! R : IDS R ! T : r; fKðrÞ T ! R : f0KðrÞ:

6.2 Jeon and Yoon

Jeon and Yoon presented in October 2013 their protocol RAPLT [41]. This protocol (shown in Fig. 7 in Appendix for reference) introduces two new lightweight operations: MerðA; B; K; CÞ and SepðC; K; A; BÞ. Their definition is the following. MerðA; B; K; CÞ merges the values A 2f0; 1gL and B 2f0; 1gL into C 2f0; 1g2L using the bits of K 2 f0; 1g2L: if a bit in K is 0, then a bit of A is moved to C, else a bit of B is used. SepðC; K; A; BÞ does the opposite: if a bit in K is 0, the next bit in C is moved to A, else it is moved to B.

The first thing to note is that these operations are ill- defined as they both require that HðKÞ¼ L. The authors make no mention of any way to guarantee that, and it would anyway result in a smaller entropy. Regardless, we assume that this property is satisfied in what follows.

The usage of Sep in the protocol does not follow the defi- nition. The protocol specifies SepðM1; M2; K2jjK1; B1jjB2Þ, but we assume that the authors meant SepðM1jjM2; K2jj K1; B1; B2Þ, since else the variables would not have the right sizes.

Another point is that these operations, that consist in rearrangements of bits of some of their inputs, have linear properties. The only other operation used is the XOR, which makes the protocol entirely linear. This problem is addressed in Section 4.1.

Finally, a traceability attack may easily be mounted against the protocol by using the fact that the two new oper- ations are Hamming-weight invariant. A very similar attack was previously done on RAPP [33] in [26]. We have that, after MerðA; B; K; CÞ, or after SepðC; K; A; BÞ,

HðAÞþHðBÞ¼HðCÞ¼HðC1ÞþHðC2Þ; and we also have that

HðA�BÞ�HðAÞþHðBÞðmod 2Þ; for any A, B. Therefore, we can deduce the following:

HðB3Þ�HðB1ÞþHðB2Þ �HðM1ÞþHðM2Þ �HðN1ÞþHðN2ÞþHðK2ÞþHðK1Þ ðmod 2Þ

HðA1ÞþHðA2Þ�HðN1ÞþHðN2Þ ðmod 2Þ: Therefore,

HðKÞmod 2 ¼ HðB3ÞþHðA1ÞþHðA2Þð Þmod 2: Since A1, A2 and B3 are public, and since K is static, it is easy for an attacker to trace a tag by observing its communi- cations with a genuine reader.

6.3 Ling and Shen

In an article of November 2013, Ling and Shen [43] present a protocol that is strongly inspired on the SASI protocol [2]. A formal proof using GNY logic is made, which should indi- cate that the protocol is secure.

However, since messages C and D are exactly the same ones as in SASI, Phan’s simple traceability attack [13], which allows a passive attacker to recover one bit of the secret, works here too. Without going into the details, it essentially relies on the fact that the OR (_) operation has biased out- put, an issue that has been covered in Section 4.2.

This attack proves that the formal security proof made in [43] is not valid, a point that was already raised in Section 5.2.

7 PROMISING TRENDS

7.1 Ultralightweight Primitives

Rather than designing an authentication protocol from scratch using ultralightweight operations, another (argu- ably more reliable) approach to designing an ultralight- weight authentication protocol is to use a classical challenge-response authentication protocol, and employ an ultralightweight construction as the underlying crypto- graphic primitive.

In the category of ultralightweight primitives, that goes up to around 1.5K GE, there is generally no room for highly optimized versions of standard ciphers like AES and IDEA, or slight modifications of classical block ciphers like DES (DESL, DESXL) [79].

Only newly and purposefully designed low-cost prim- itives can generally be ascribed to it. Fortunately for the area, more and more of the new proposals fall within this limit. There seems to be a growing consensus that

2326 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

this is about the maximum GE that most devices would be able to devote to security.

Within this upper limit, there was not any proposal at all before the publication of PRESENT [80] in 2007, as both DES (2,300-3,000 GE) or even DESXL (2,168 GE) are too large. AES needs even more gates, with around 3,600 GE (recent results [81] put this at 2,400 GE, still well above the 1.5K limit). Not even well-known extremely efficient and even easy to memorize algorithms such as TEA [82] (2,100) and XTEA (2,000) were light enough. Other recent proposals like MCRYPTON [83] (2,949 GE), HIGHT [84] (3,000) and SEA [85] (2,280) were also not adequate for our purposes.

After 2007, on the other hand, we have witnessed a blos- soming of new primitives. This new trend includes most notably PRESENT (1,570 GE) that, based on the AES finalist Serpent, can rightly be considered a pioneer in this area.

The European eSTREAM project was also relevant, as it looked for stream ciphers suitable for efficient hardware implementation, and it contributed to the development of Trivium (2,599 GE) and Grain (1,294 GE). Of course only Grain [86] is adequate for our intended environments.

Continuing with ultralightweight block cipher proposals, we have LBlock (2,011) which uses 1,320 GE, but also many other recent algorithms like the block cipher TWINE (1,116 GE), MIBS (1,400), KATAN/KTANTAN [87] (from 688), Piccolo (683 to 1,043), LED [88] (1,040) and the PRINTcipher (503) or PRINCE.

From this long list, specially notable are the KATAN and LED proposals, which have gained some respect and popu- larity after resisting cryptanalysts’ efforts for a time. Although all have received some minor attacks, these look at the moment like a particularly good trade-off between security and efficiency.

It is important to note that we have to be cautious on any comparison based exclusively on gate count, because not all of these algorithms operate over the same keysize, blocksize or produce the same throughput.

Lastly, it is significant to note that even the NSA came with two proposals in this area, called SIMON (763 GE) and SPECK (884 GE). These were meant to provide high performance across a range of devices. In the light of recent NSA scandals these two proposals, independently of their respective merits, will probably never prove very popular within the cryptogra- phy community. On top of that, there are some attacks [89] that present a not particularly rosy view on either of them.

But not only block and stream ciphers designers have been attracted to the challenge of devising ultralightweight primitives. There are also some interesting, though less numerous, proposals in other areas of cryptography. Partic- ularly attractive are the SPONGENT [90] (from 738 GE to 1,950) and QUARK [91] (from 1,379 to 4,460 GE) families of lightweight hash functions. These two, despite being by far the most popular, are not the only ones available as there is also the PHOTON [92] family (1,122 to 2,768 GE).

We believe this is one of the most promising trends in ultralightweight cryptography, and one of the more sound approaches to provide in the near future with adequate security solutions for low-cost devices. We encourage more work on the area, both in proposing new schemes and in assessing the security of existing ones. For speeding up this process, we believe that a new AES or SHA-3 like

competition would be very helpful to set new ultralight- weight standards primitives. It would probably be very well received, and would no doubt contribute greatly to advance the state of the art and to progress in the wide- spread adoption of these or new proposals.

7.2 Human-Based Protocols

Juels and Weis introduced in 2005 an authentication proto- col, known as HBþ [93], which is based on HB, a secure identification scheme for Human beings designed by Hop- per and Blum in 2001 [94]. HBþ requires only lightweight calculations from the prover and the protocol benefits from a security proof based on a reduction to the Learning Parity with Noise (LPN) problem: let x b a secret k-bit vector, a a

random known k-bit vector, � 2 0; 1 2 ½ a noise parameter, and

h a bit noise where Prðfh ¼ 1gÞ¼ �; it is hard to learn x from the value r ¼ a �x�h.

In spite of attractive properties, analyses of HB-based pro- tocols should be done with the utmost care. Indeed, while HBþ benefits from security proofs in restricted security mod- els [93], [95], the protocol becomes insecure when considering active adversaries who can modify the messages exchanged between the involved parties. Gilbert, Robshaw, and Sibert pointed out this weakness in [96] (2005). Many attempts to make HBþ secure against man-in-the-middle attacks were published, but Gilbert, Robshaw, and Seurin then raised flaws in 2008 [97] in the published variants of HBþ, namely HBþþ [98] (2006) and a variant by Piramuthu [99] (2006), HB� [100] (2007), HB-MP and HB-MP0 [101] (2007).

Gilbert, Robshaw, and Seurin then introduced RAN- DOM-HB# and HB# [102] (2008), broken by Ouafi, Over- beck, and Vaudenay in [103] (2008). Rizomiliotis then

introduced an improvement on RANDOM-HB#, known as HB-MAC [104] (2009).

In parallel, improvements on HB-MP were suggested: HB- MPþ [105] (2008), HB-MPþþ [106] (2009), and HB-MP� [107] (2011), and more recently HB-MP received improvements from Tsaur et al. in [108] (2011) and [109] (2012).

Other variants include Trusted-HB [110] (2008), demon- strated to be insecure by Frumklin and Shamir in [111] (2009), NLHB and NLHBþ [112] (2010), a bilinear version of HB named HBN [113] (2011), and a construction by Kiltz et al. [114] (2011) based on Pietrzak’s work [115] that is still based on the LPN problem but which significantly differs from the HB family. Finally, Rizomiliotis and Gritzalis intro-

duced GHB# [116] (2012) to make secrets shorter than the ones needed in [114].

The HB family also includes branches related to Physically Unclonable Functions (PUF) including HB+PUF [117] (2008) and PUF-HB [118] (2008), and tree-based authentication pro- tocols that aim to protect privacy by Halevi, Saxena, and Halevi [119], [120] (2009) whose weaknesses are highlighted in [121] (2010), followed by Tree-LSHB+ [122] (2013).

As a consequence, any HB-related authentication scheme should be analyzed considering the previous unsuccessful attempts. Two references should also be the keystones of the analyses, namely [97] and [103].

Finally, note that HB and its variants are considered not so lightweight by some experts, and in particular do not fit within the 1,500 GE margin. See [123] for a thorough discus- sion on the subject.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2327

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

8 CONCLUSION

In this paper we described the state of the art of ultralight- weight protocols security, and tried to address some of its many issues. We showed that virtually all protocols are bro- ken, with half of them having been broken within eight months and most of them within a year of their publication. We reviewed the most critical and most frequent mistakes encountered in these protocols and illustrated them on three very recent proposals. These new attacks show that little effort is often sufficient to break such schemes, and that the topics addressed in this work are relevant for the analysis of novel proposals.

Our work provides guidelines to quickly assess the security of new proposals and should additionally help reviewers to efficiently distinguish those of merit. Likewise, authors of new ultralightweight protocols could review the

points addressed in this article in order to evaluate the cor- rectness of their claims.

Despite the current situation, which may seem to indi- cate that ultralightweight protocols are bound to fail, there is no clear evidence that designing a secure protocol with such constraints is impossible. Much to the contrary, recent advances in lightweight cryptography present an optimistic future for research in the area. In particular, we have highlighted in Sections 4.7.1, 4.7.2, 7 the current developments that, in our opinion, show greater promise.

We are hopeful that our work will help to improve the quality of future proposals in the field, avoiding common past and present mistakes, and help the area mature towards the creation of new standards.

APPENDIX

TABLE 3 Attacks Results for 20 Runs, After Observing One Auth. Session, from [12]

Experiment Good Approx. Bad Approx. Correct bits Correlation Rand. Corr. Exp. Result

1 46 4 60 0.23591 -0.00532 Success 2 37 13 60 0.24760 -0.08020 Success 3 36 14 53 0.10418 0.02094 Success 4 39 11 56 0.13681 -0.01610 Success 5 44 6 59 0.22518 -0.03496 Success 6 34 16 53 0.10919 -0.12903 Success 7 41 9 56 0.17157 0.12330 Success 8 43 7 62 0.29247 0.08456 Success 9 45 5 60 0.24967 -0.06447 Success 10 42 8 58 0.19593 0.19375 Success 11 44 6 58 0.21009 0.09940 Success 12 35 15 53 0.10707 -0.11736 Success 13 38 12 53 0.09923 -0.02172 Success 14 47 3 61 0.026238 -0.04895 Success 15 35 15 53 0.10629 0.14811 Fail 16 47 3 66 0.36751 -0.16724 Success 17 44 6 59 0.21093 0.03115 Success 18 39 11 55 0.14885 0.08340 Success 19 31 19 52 0.10013 -0.01543 Success 20 39 11 58 0.20798 0.03845 Success

Averages 40.3 9.7 57.25 0.19 0.01 95% Success

Fig. 6. Bilal and Martin’s protocol.

2328 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

REFERENCES [1] G. Avoine. (2014, Mar.). RFID lounge [Online]. Available: http://

www.avoine.net/rfid/ [2] H.-Y. Chien, “SASI: A new ultralightweight RFID authentication

protocol providing strong authentication and strong integrity,” IEEE Trans. Dependable Secure Comput., vol. 4, no. 4, pp. 337–340, Dec. 2007.

[3] Z. Liu, D. Liu, L. Li, H. Lin, and Z. Yong, “Implementation of a new RFID authentication protocol for EPC Gen2 standard,” IEEE Sensors J., vol. 15, no. 2, pp. 1003–1011, Feb. 2015.

[4] H. Martin, E. S. Milan, P. Peris-Lopez, and J. E. Tapiador, “Efficient ASIC implementation and analysis of two EPC-C1G2 RFID authentication protocols,” IEEE Sensors J., vol. 13, no. 10, pp. 3537–3547, Oct. 2013.

[5] P. D’Arco and A. De Santis, “On ultralightweight RFID authenti- cation protocols,” IEEE Trans. Dependable Secure Comput., vol. 8, no. 4, pp. 548–563, Jul./Aug. 2011.

[6] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, “LMAP: A real lightweight mutual authenti- cation protocol for low-cost RFID tags,” in Proc. Workshop RFID Security, Jul. 2006, pp. 12–24.

[7] T. Li and G. Wang, “Security analysis of two ultra-lightweight RFID authentication protocols,” in Proc. IFIP TC-11 22nd Int. Inf. Security Conf., May 2007, pp. 109–120.

[8] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, “M2AP: A minimalist Mutual-authentication protocol for Low-cost RFID tags,” in Proc. Int. Conf. Ubiquitous Intell. Comput., Sep. 2006, pp. 912–923.

[9] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, “EMAP: An efficient mutual authentication protocol for low-cost RFID tags,” in Proc. OTM Federated Conf. Workshop: IS Workshop, Nov. 2006, pp. 352–361.

[10] T. Li and R. H. Deng, “Vulnerability analysis of EMAP—an effi- cient RFID mutual authentication protocol,” in Proc. 2nd Int. Conf. Availability, Rel. Security, Vienna, Austria, Apr. 2007, pp. 10–13.

[11] T. Li and G. Wan, “SLMAP—a secure ultra-lightweight RFID mutual authentication protocol,” in Proc. Adv. Cryptol., Oct. 2007, pp. 19–22.

[12] J. C. Hernandez-Castro, J. E. Tapiador, P. Peris-Lopez, J. A. Clark, and E.-G. Talbi, “Metaheuristic traceability attack against SLMAP, an RFID lightweight authentication protocol,” in Proc. 23rd IEEE Int. Parallel Distrib. Process. Symp., May 2009, pp. 1–5.

[13] R. C.-W. Phan, “Cryptanalysis of a new ultralightweight RFID authentication protocol—SASI,” IEEE Trans. Dependable Secure Comput., vol. 6, no. 4, pp. 316–320, Oct.–Dec. 2009.

[14] C. Qingling, Z. Yiju, and W. Yonghua, “A minimalist mutual authentication protocol for RFID system & BAN logic analysis,” in Proc. ISECS Int. Colloq. Comput., Commun., Control, Manage., Aug. 2008, vol. 2, pp. 449–453.

[15] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, T. Li, and J. C. van der Lubbe, “Weaknesses in two recent light- weight RFID authentication protocols,” presented at the Work- shop RFID Security, Leuven, Belgium, Jul. 2009.

[16] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda, “Advances in ultralightweight cryptography for low-cost RFID Tags: Gossamer protocol,” in Proc. Workshop Inf. Security Appl., Sep. 2008, pp. 56–68.

[17] T. Li, “Employing lightweight primitives on low-cost RFID tags for authentication,” in Proc. 68th Veh. Technol. Conf., Sep. 2008, pp. 1–5.

[18] N. Bagheri, M. Safkhani, M. Naderi, and S. K. Sanadhya, “Security analysis of LMAPþþ, an RFID authentication proto- col,” Cryptology ePrint Archive, Rep. 2011/193, IACR, 2011.

[19] M. David and N. R. Prasad, “Providing strong security and high privacy in Low-cost RFID networks,” in Proc. 1st Int. ICST Conf. Security Privacy Mobile Inf. Commun. Syst., Jun. 2009, pp. 172–179.

[20] J. C. Hernandez-Castro, P. Peris-Lopez, R. C. Phan, and J. M. Estevez-Tapiador, “Cryptanalysis of the David-Prasad RFID ultralightweight authentication protocol,” in Proc. Workshop RFID Security, Jun. 2010, pp. 22–34.

[21] Y.-C. Lee, Y.-C. Hsieh, P.-S. You, and T.-C. Chen, “A new ultra- lightweight RFID protocol with mutual authentication,” in Proc. WASE Int. Conf. Inf. Eng., Aug. 2009, pp. 58–61.

[22] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and J. C. A. van der Lubbe, “Security flaws in a recent ultralight- weight RFID protocol,” in Proc. Workshop RFID Security, Feb. 2010, vol. 4, pp. 83–93.

Fig. 7. Jeon and Yoon’s protocol.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2329

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

[23] K.-H. Yeh, N. Lo, and E. Winata, “An efficient ultralightweight authentication protocol for RFID systems,” in Proc. Workshop RFID Security, Feb. 2010, vol. 4, pp. 49–60.

[24] P. Peris-Lopez, J. C. Hernandez-Castro, R. C.-W. Phan, J. M. E. Tapiador, and T. Li, “Quasi-linear cryptanalysis of a secure RFID ultralightweight authentication protocol,” in Proc. 6th China Int. Conf. Inf. Security Cryptol., Oct. 2010, pp. 427–442.

[25] A. Eghdamian and A. Samsudin, “A secure protocol for ultra- lightweight radio frequency identification (RFID) tags,” in Proc. Int. Conf. Informat. Eng. Inf. Sci., Nov. 2011, pp. 200–213.

[26] G. Avoine and X. Carpent, “Yet another ultralightweight authen- tication protocol that is broken,” in Proc. Workshop RFID Security, Jun. 2012, pp. 20–30.

[27] H. Ning, H. Liu, and C. Yang, “Ultralightweight RFID authenti- cation protocol based on random partitions of pseudorandom identifier and pre-shared secret value,” Chin. J. Electron., vol. 20, no. 4, pp. 701–707, Oct. 2011.

[28] H. Fernando and J. Abawajy, “Mutual authentication protocol for networked RFID systems,” in Proc. 10th Int. Conf. Trust, Secu- rity Privacy Comput. Commun., Nov. 2011, pp. 417–424.

[29] M. R. Alagheband and M. R. Aref, “Simulation-based traceability analysis of RFID authentication protocols,” Wireless Pers. Com- mun., vol. 77, no. 2, pp. 1019–1038, Dec. 2013.

[30] X. Fan, G. Gong, D. W. Engels, and E. M. Smith, “A lightweight Privacy-preserving mutual authentication protocol for RFID sys- tems,” in Proc. IEEE GLOBECOM Workshops, Dec. 2011, pp. 1083–1087.

[31] R. Bassil, W. El-Beaino, W. Itani, A. Kayssi, and A. Chehab, “PUMAP: A PUF-based ultra-lightweight mutual-authentication RFID protocol,” Int. J. RFID Security Cryptography, vol. 1, no. 1, pp. 58–66, Mar. 2012.

[32] Y.-C. Lee, “Two ultralightweight authentication protocols for low-cost RFID tags,” Appl. Math. Inf. Sci., vol. 6, no. 2S, pp. 425– 431, May 2012.

[33] Y. Tian, G. Chen, and J. Li, “A new ultralightweight RFID authentication protocol with permutation,” IEEE Commun. Lett., vol. 16, no. 5, pp. 702–705, May 2012.

[34] J. Gurubani, H. Thakkar, and D. Patel, “Improvements over extended LMAP+: RFID authentication protocol,” in Proc. 6th Int. Conf. Trust Manage., May 2012, pp. 225–231.

[35] L. Gao, M. Ma, Y. Shu, and Y. Wei, “A security protocol resistant to intermittent position trace attacks and desynchronization attacks in RFID systems,” Wireless Pers. Commun., vol. 68, pp. 1–17, Jul. 2012.

[36] N. Bagheri, P. Gauravaram, M. Safkhani, and S. K. Sanadhya, “The resistance to intermittent position trace attacks and desynchronization attacks (RIPTA-DA) protocol is not RIPTA- DA,” in Proc. Workshop RFID Security, Jul. 2013, pp. 57–68.

[37] L. Pang, H. Li, L. He, A. Alramadhan, and Y. Wang, “Secure and efficient lightweight RFID authentication protocol based on fast tag indexing,” Int. J. Commun. Syst., vol. 27, pp. 3244–3254, 2014.

[38] M. Akg€un and M. U. Çaǧlayan, “On the security of recently pro- posed RFID protocols,” Cryptology ePrint Archive, Rep. 2013/ 820, IACR, 2013.

[39] P. Dusart and S. Traor�e, “Lightweight authentication protocol for low-cost RFID tags,” in Proc. 7th IFIP WG 11.2 Int. Workshop Inf. Security Theory Practice. Security Mobile Cyber-Phys. Syst., May 2013, pp. 129–144.

[40] V. Banciu, S. Hoerder, and D. Page, “Lightweight primitive, feather-weight security—a cryptanalytic knock-out. (prelimi- nary results),” Cryptology ePrint Archive, Rep. 2013/421, IACR, 2013.

[41] I.-S. Jeon and E.-J. Yoon, “A new ultra-lightweight RFID authentication protocol using merge and separation oper- ations,” Int. J. Math. Anal., vol. 7, no. 52, pp. 2583–2593, Oct. 2013.

[42] Z. Bilal and K. Martin, “Ultra-lightweight mutual authentication protocols: Weaknesses and countermeasures,” in Proc. 8th Int. Conf. Availability, Rel. Security, Sep. 2013, pp. 304–309.

[43] J. Ling and J. Shen, “New defending ultra-lightweight RFID authentication protocol against DoS attacks,” in Proc. 3rd Int. Conf. Consumer Electron., Commun. Netw., Xianning, China, Nov. 2013, pp. 423–426.

[44] L. Gao, M. Ma, Y. Shu, and Y. Wei, “An ultralightweight RFID authentication protocol with CRC and permutation,” J. Netw. Comput. Appl., vol. 36, no. 6, pp. 37–46, Nov. 2013.

[45] A. M. Zeeshan Bilal and F. Kausar, “Security analysis of Ultra- lightweight cryptographic protocol for low-cost RFID tags: Gos- samer protocol,” in Proc. Int. Conf. Netw.-Based Inf. Syst., Aug. 2009, pp. 260–267.

[46] D. Tagra, M. Rahman, and S. Sampalli, “Technique for prevent- ing DoS attacks on RFID systems,” in Proc. 18th Int. Conf. Softw. Telecommun. Comput. Netw., Sep. 2010, pp. 6–10.

[47] K.-H. Yeh and N. Lo, “Improvement of two lightweight RFID authentication protocols,” Inf. Assurance Security Lett., vol. 1, pp. 6–11, 2010.

[48] D. Dolev and A. C. Yao, “On the security of public key protocols,” IEEE Trans. Inf. Theory, vol. IT-29, no. 2, pp. 198–208, Mar. 1983.

[49] (2015). Libnfc. The free/libre near field communication (NFC) library [Online]. Available: http://nfc-tools.org/

[50] A. Juels and S. Weis, “Defining strong privacy for RFID,” in Proc. Int. Conf. Pervasive Comput. Commun., Mar. 2007, pp. 342–347.

[51] S. Vaudenay, “On privacy models for RFID,” in Proc. 13th Int. Conf. Theory Appl. Cryptol. Inf. Security: Adv. Cryptol., Dec. 2007, pp. 68–87.

[52] T. van Deursen, S. Mauw, and S. Radomirovi�c, “Untraceability of RFID protocols,” in Proc. Workshop Inf. Security Theory Practice, May 2008, pp. 1–15.

[53] J. Hermans, A. Pashalidis, F. Vercauteren, and B. Preneel, “A new RFID privacy model,” in Proc. 16th Eur. Symp. Res. Comput. Security, Sep. 2011, pp. 568–587.

[54] G. Avoine, I. Coisel, and T. Martin, “Untraceability model for RFID,” IEEE Trans. Mobile Comput., vol. 13, no. 10, pp. 2397–2405, Oct. 2014.

[55] I. Coisel and T. Martin, “Untangling RFID privacy models,” J. Comput. Netw. Commun., vol. 2013, pp. 1–26, Jul. 2013.

[56] S. Vaudenay, “RFID privacy based on public-key cryptography (abstract),” in Proc. Int. Conf. Inf. Security Cryptol., Nov./Dec. 2006, pp. 1–6.

[57] A. Klimov and A. Shamir, “New applications of T-functions in block ciphers and hash functions,” in Proc. 12th Int. Workshop Fast Softw. Encryption, 2005, pp. 18–31.

[58] M. B�ar�asz, B. Boros, P. Ligeti, K. L�oja, and D. Nagy, “Passive attack against the M2AP mutual authentication protocol for RFID tags,” presented at the 1st Int. EURASIP Workshop RFID Technol., Vienna, Austria, Sep. 2007.

[59] M. B�ar�asz, B. Boros, P. Ligeti, K. L�oja, and D. Nagy, “Breaking LMAP,” presented at the Conf. RFID Security, Malaga, Spain, Jul. 2007.

[60] R. Rivest, “The RC5 encryption algorithm,” in Proc. 2nd Int. Workshop Fast Softw. Encryption, Dec. 1995, pp. 86–96.

[61] J. C. Hernandez-Castro, J. M. Estevez-Tapiador, P. Peris-Lopez, and J.-J. Quisquater, “Cryptanalysis of the SASI ultralightweight RFID authentication protocol with modular rotations,” presented at the Int. Workshop Coding Cryptography, Ullensvang, Nor- way, May 2009.

[62] J. Kelsey, B. Schneier, and D. Wagner, “Mod n cryptanalysis, with applications against RC5P and M6,” in Proc. 6th Int. Work- shop Fast Softw. Encryption, 1999, pp. 139–155.

[63] G. Avoine, X. Carpent, and B. Martin, “Strong authentication and strong integrity (SASI) is not that strong,” in Proc. Workshop RFID Security, Jun. 2010, pp. 50–64.

[64] M. Ohkubo, K. Suzuki, and S. Kinoshita, “Cryptographic approach to ‘privacy-friendly’ tags,” presented at the RFID Pri- vacy Workshop, MIT, Cambridge, MA, USA, Nov. 2003.

[65] G. Avoine, I. Coisel, and T. Martin, “Time measurement threat- ens privacy-friendly RFID authentication protocols,” in Proc. Workshop RFID Security, Jun. 2010, pp. 138–157.

[66] H.-M. Sun, S.-M. Chen, and K.-H. Wang, “Cryptanalysis on the RFID ACTION protocol,” presented at the Int. Conf. Security Manage., Las Vegas, NV, USA, Jul. 2011.

[67] Z. Ahmadian, M. Salmasizadeh, and M. R. Aref, “Recursive lin- ear and differential cryptanalysis of ultralightweight authentica- tion protocols,” IEEE Trans. Inf. Forensics Security, vol. 8, no. 7, pp. 1140–1151, Jul. 2013.

[68] D. Han, “Gr€obner basis attacks on lightweight RFID authentication protocols,” J. Inf. Process. Syst., vol. 7, no. 4, pp. 691–706, Dec. 2011.

[69] D. F. Barrero, J. C. Hernndez-Castro, P. Peris-Lopez, D. Cama- cho, and M. D. R-Moreno, “A genetic tango attack against the David-Prasad RFID ultra-lightweight authentication protocol,” Expert Syst., vol. 31, pp. 9–19, Feb. 2014.

2330 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

[70] M. Matsui, “The first experimental cryptanalysis of the data encryption standard,” in Proc. 14th Annu. Int. Cryptol. Conf.: Adv. Cryptol., 1994, vol. 839, pp. 1–11.

[71] J. C. Hernandez-Castro, P. Peris-Lopez, J. M. E. Tapiador, R. C.- W. Phan, and T. Li, “Passive Black-box cryptanalysis of an ultra- lightweight protocol after eavesdropping one authentication session,” in Proc. Workshop RFID Security, Apr. 2011, vol. 6, pp. 3–17.

[72] J. Walker, “ENT, a pseudorandom number sequence test program,” Fourmilab, Oct. 1998. http://www.fourmilab.ch/ random/

[73] G. Marsaglia. (2008). The marsaglia random number cdrom including the diehard battery of tests of randomness (1995) [Oline]. Available: URL http://www. stat. fsu. edu/pub/ diehard

[74] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo, “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” National Institute of Standards and Technology (NIST), pp. 800–22, 2001.

[75] J.-S. Chou, G.-C. Lee, and C.-J. Chan, “A novel mutual authenti- cation scheme based on quadratic residues for RFID systems,” Inform. Security Group (GSI), UCL, Louvain-la-Neuve, Belgium, IACR, 2007.

[76] S. Islam, “Security analysis of LMAP using AVISPA,” Int. J. Secu- rity Netw., vol. 9, no. 1, pp. 30–39, 2014.

[77] W. Tounsi, N. Cuppens-Boulahia, J. Garcia-Alfaro, Y. Chevalier, and F. Cuppens. (2014). Kedgen2: A key establishment and deri- vation protocol for {EPC} gen2 {RFID} systems. J. Netw. Comput. Appl. [Online]. 39, pp. 152–166 Available: http://www. sciencedirect.com/science/article/pii/S1084804513001458

[78] A. Armando, D. Basin, Y. Boichut, Y. Chevalier, L. Compagna, J. Cu�ellar, P. H. Drielsma, P.-C. H�eam, O. Kouchnarenko, J. Man- tovani, et al., “The AVISPA tool for the automated validation of internet security protocols and applications,” in Proc. 17th Int. Conf. Comput. Aided Verification, 2005, pp. 281–285.

[79] G. Leander, C. Paar, A. Poschmann, and K. Schramm, “New lightweight DES variants,” in Proc. 14th Int. Conf. Fast Softw. Encryption, 2007, pp. 196–210.

[80] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. Robshaw, Y. Seurin, and C. Vikkelsoe, “Present: An ultra- lightweight block cipher,” in Proc. 9th Int. Workshop Cryptographic Hardware Embedded Syst., 2007, pp. 450–466.

[81] M. Feldhofer, J. Wolkerstorfer, and V. Rijmen, “AES implementa- tion on a grain of sand,” IEE Proc. – Inf. Security, vol. 152, no. 1, pp. 13–20, Oct. 2005.

[82] D. J. Wheeler and R. M. Needham, “Tea, a tiny encryption algo- rithm,” in Proc. Workshop Fast Softw. Encryption, 1995, pp. 363–366.

[83] C. H. Lim and T. Korkishko, “mCrypton—a lightweight block cipher for security of low-cost RFID tags and sensors,” in Proc. 6th Int. Workshop Inf. Security Appl., 2006, pp. 243–258.

[84] D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B.-S. Koo, C. Lee, D. Chang, J. Lee, K. Jeong et al., “Hight: A new block cipher suitable for Low-resource device,” in Proc. 8th Int. Workshop Cryptographic Hardware Embedded Syst., 2006, pp. 46–59.

[85] F.-X. Standaert, G. Piret, N. Gershenfeld, and J.-J. Quisquater, “Sea: A scalable encryption algorithm for small embedded applications,” in Proc. 7th IFIP WG 8.8/11.2 Int. Conf. Smart Card Res. Adv. Appl., 2006, pp. 222–236.

[86] M. Hell, T. Johansson, and W. Meier, “Grain: A stream cipher for constrained environments,” Int. J. Wireless Mobile Comput., vol. 2, no. 1, pp. 86–93, 2007.

[87] C. De Canniere, O. Dunkelman, and M. Kne�zevi�c, “KATAN and KTANTAN family of small and efficient hardware-oriented block ciphers,” in Proc. 11th Int. Workshop Cryptographic Hardware Embedded Syst., 2009, pp. 272–288.

[88] J. Guo, T. Peyrin, A. Poschmann, and M. Robshaw, “The led block cipher,” in Proc. 13th Int. Conf. Cryptographic Hardware Embedded Syst., 2011, pp. 326–341.

[89] H. Tupsamudre, S. Bisht, and D. Mukhopadhyay. (2014). Differ- ential fault analysis on the families of simon and speck ciphers, Cryptology ePrint Archive, Rep. 2014/267 [Online]. Available: http://eprint. iacr. org, Tech. Rep..

[90] A. Bogdanov, M. Kne�zevi�c, G. Leander, D. Toz, K. Var{c{, and I. Verbauwhede, “Spongent: A lightweight hash function,” in Proc. 13th Int. Workshop Cryptographic Hardware Embedded Syst., 2011, vol. 6917, pp. 312–325.

[91] J.-P. Aumasson, L. Henzen, W. Meier, and M. Naya-Plasencia, “Quark: A lightweight hash,” J. Cryptol., vol. 26, no. 2, pp. 313– 339, 2013.

[92] J. Guo, T. Peyrin, and A. Poschmann, “The photon family of lightweight hash functions,” in Proc. 31st Annu. Cryptol. Conf. Adv. Cryptol., 2011, pp. 222–239.

[93] A. Juels and S. Weis, “Authenticating pervasive devices with human protocols,” in Proc. 25th Annu. Int. Cryptol. Conf.: Adv. Cryptol., Aug. 2005, pp. 293–308.

[94] N. J. Hopper and M. Blum, “Secure human identification proto- cols,” in Proc. 7th Int. Conf. Theory Appl. Cryptol. Inf. Security: Adv. Cryptol., Dec. 2001, pp. 52–66.

[95] J. Katz, J. S. Shin, and A. Smith, “Parallel and concurrent security of the HB and HB+ protocols,” J. Cryptol., vol. 23, no. 3, pp. 402– 421, Jul. 2010.

[96] H. Gilbert, M. Robshaw, and H. Sibert, “An active attack against HBþ – a provably secure lightweight authentication protocol,” IET Electron. Lett., vol. 41, no. 21, pp. 1169–1170, Oct. 2005.

[97] H. Gilbert, M. Robshaw, and Y. Seurin, “Good variants of HB+ are hard to find,” in Proc. 12th Int. Conf. Financial Cryptography Data Security, Jan. 2008, pp. 156–170.

[98] J. Bringer, H. Chabanne, and E. Dottax, “HBþþ: A lightweight authentication protocol secure against some attacks,” in Proc. IEEE Int. Conf. Pervasive Services, Workshop Security, Privacy Trust Pervasive Ubiquitous Comput., Jun. 2006, pp. 28–33.

[99] S. Piramuthu, “HB and related lightweight authentication proto- cols for secure RFID tag/reader authentication,” presented at the Collaborative Electron. Commerce Technol. Res., Basel, Switzer- land, Jun. 2006.

[100] D. N. Duc and K. Kim, “Securing HB+ against GRS man-in-the- middle attack,” in Proc. Symp. Cryptography Inf. Security, Jan. 2007, pp. 23–26.

[101] J. Munilla and A. Peinado, “HB-MP: A further step in the Hb- family of lightweight authentication protocols,” Comput. Netw., vol. 51, no. 9, pp. 2262–2267, Jun. 2007.

[102] H. Gilbert, M. J. Robshaw, and Y. Seurin, “HB#: Increasing the security and efficiency of HB+,” in Proc. Int. Conf. Theory Appl. Cryptographic Techn.: Adv. Cryptol., Apr. 2008, pp. 361–378.

[103] K. Ouafi, R. Overbeck, and S. Vaudenay, “On the security of HB# against a man-in-the-middle attack,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Security: Adv. Cryptol., Dec. 2008, pp. 108–124.

[104] P. Rizomiliotis, “HB-MAC: Improving the Random - HB# authentication protocol,” in Proc. 6th Int. Conf. Trust, Privacy Security Digital Bus., Aug. 2009, vol. 5695, pp. 159–168.

[105] X. Leng, K. Mayes, and K. Markantonakis, “HB-MPþ protocol: An improvement on the HB-MP protocol,” Proc. IEEE Int. Conf. RFID, Apr. 2008, pp. 118–124.

[106] B. Yoon, “HB-MPþþ protocol: An ultra light-weight authentica- tion protocol for RFID system,” in Proc. IEEE Int. Conf. RFID, Apr. 2009, pp. 186–191.

[107] A. Aseeri and O. Bamasak, “HB-MP�: Towards a man-in-the-mid- dle-resistant protocol of HB family,” in Proc. 1st Int. Conf. Wireless Commun. Mobile Comput., Istanbul, Turkey, Jun. 2011, p. 4.

[108] C.-M. Lin, S.-C. Tsaur, Y.-C. Chen, and I.-C. Lin, “Hb family rfid mutual authentication protocol,” in Proc. Int. Conf. Intell. Inf. Hid- ing Multimedia Signal Process., Jan. 2011, pp. 230–235.

[109] S.-C. Tsaur, H.-Y. Chen, and J.-P. Pai, “Lightweight RFID authen- tication protocol without asynchronous flaw,” Int. J. Comput., Consumer Control, vol. 1, no. 2, pp. 32–39, Nov. 2012.

[110] J. Bringer and H. Chabanne, “Trusted-HB: A low-cost version of HBþ secure against man-in-the-middle attacks,” IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 4339–4342, Sep. 2008.

[111] D. Frumkin and A. Shamir, “Un-trusted-HB: Security vulnerabil- ities of trusted-HB,” presented at the Workshop RFID Security, Leuven, Belgium, Jul. 2009.

[112] M. Madhavan, A. Thangaraj, Y. Sankarasubramaniam, and K. Viswanathan, “NLHB : A non-linear Hopper Blum protocol,” in Proc. IEEE Int. Symp. Inf. Theory Proc., Jun. 2010, pp. 2498–2502.

[113] C. Bosley, K. Haralambiev, and A. Nicolosi, “HBn: An HB-like protocol secure against man-in-the-middle attacks,” Cryptol. ePrint Archive, Rep. 2011/350, IACR, 2011.

[114] E. Kiltz, K. Pietrzak, D. Cash, A. Jain, and D. Venturi, “Efficient authentication from hard learning problems,” in Proc. 30th Annu. Int. Conf. Theory Appl. Cryptographic Techn.: Adv. Cryptol., May 2011, pp. 7–26.

[115] K. Pietrzak, “Subspace LWE,” in Proc. 9th Int. Conf. Theory Cryp- tography, Mar. 2012, pp. 548–563.

AVOINE ET AL.: PITFALLS IN ULTRALIGHTWEIGHT AUTHENTICATION PROTOCOL DESIGNS 2331

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.

[116] P. Rizomiliotis and S. Gritzalis, “GHB#: A provably secure HB- like lightweight authentication protocol,” in Proc. 10th Int. Conf. Appl. Cryptography Netw. Security, Jun. 2012, pp. 489–506.

[117] G. Hammouri, E. €Ozt€urk, B. Birand, and B. Sunar, “Unclonable lightweight authentication scheme,” in Proc. Int. Conf. Inf. Com- mun. Security, Oct. 2008, pp. 33–48.

[118] G. Hammouri and B. Sunar, “PUF-HB: A Tamper-Resilient HB based authentication protocol,” in Proc. 6th Int. Conf. Appl. Cryp- tography Netw. Security, May 2008, pp. 346–365.

[119] T. Halevi, N. Saxena, and S. Halevi, “Using HB family of proto- cols for Privacy-preserving authentication of RFID tags in a pop- ulation,” presented at the Workshop RFID Security, Leuven, Belgium, Jul. 2009.

[120] T. Halevi, N. Saxena, and S. Halevi, “Tree-based hb protocols for Privacy-preserving authentication of RFID tags,” J. Comput. Secu- rity – Special Issue RFID Syst. Security, vol. 19, no. 2, pp. 343–363, Apr. 2011.

[121] G. Avoine, B. Martin, and T. Martin, “Tree-based RFID authenti- cation protocols are definitively not privacy-friendly,” in Proc. Workshop RFID Security, Jun. 2010, pp. 103–122.

[122] G. Deng, H. Li, Y. Zhang, and J. Wang, “Tree-LSHB+: An LPN- based lightweight mutual authentication RFID protocol,” Wire- less Pers. Commun., vol. 72, no. 1, pp. 159–174, Jan. 2013.

[123] F. Armknecht, M. Hamann, and V. Mikhalev, “Lightweight authentication protocols on Ultra-lightweight RFIDs – myths and facts,” in Proc. Workshop RFID Security, Nov. 2014, pp. 1–18.

Gildas Avoine received the bachelor’s degree in mathematics and the bachelor’s and master’s degrees in computer science from the University of Caen, France. He received the PhD degree in cryptography from EPFL, Switzerland. He is a professor of information security and cryptogra- phy at the INSA Rennes, France. He is also an invited professor at the UCL in Louvain-la-Neuve, Belgium, and a member of the Institut Universi- taire de France. Previously, he was a researcher at the MIT, USA, and at the EPFL.

Xavier Carpent received the graduate degree as an engineer in computer science from the UCL and the UPC, Barcelona. He received the PhD degree from the UCL in Louvain-la-Neuve, Bel- gium, in 2015. His primary research interests include RFID authentication protocols and time- memory tradeoffs.

Julio Hernandez-Castro received the PhD degree in 2003 in computer science from Carlos III University in Madrid, Spain. He is a lecturer of computer security at the School of Computing, University of Kent, Canterbury Campus, United Kingdom. His main research interests include RFID authentication protocols, lightweight cryp- tography, CAPTCHAs, Steganography, Steganal- ysis, and network and computer forensics.

" For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib.

2332 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 15, NO. 9, SEPTEMBER 2016

Authorized licensed use limited to: Kennesaw State University. Downloaded on May 19,2021 at 17:10:51 UTC from IEEE Xplore. Restrictions apply.