# RFID Protocol Cryptanalysis

Assume we have the following scheme for RFID:
TAG & READER both have initially k keys. Every session the TAG computes $k_i$=F($k_{i-1})$ where F is a function which computes XOR of previous key with randomly generated number,
e.g. $k_i^R$=F($k_{i-1}^L$) $\oplus$ $r_i$ , $k_i^L$=F($k_{i-1}^R$) $\oplus$ $r_i$ where $r_i$ is a random number for session i.
The READER receives ($k_i$, $r_i$) and performs same computation to verify $k_i$. If its correct replies with True either False. If READER replied True - they both add $r_i$ to the key set. If reader replied FALSE or message didn't arrive - key set are not updated. (if the message didn't arrive, READER does not respond at all).

I've read that one of the possible ways for analyzing this protocol is by creating a table of all possible keys which can be generated after obtaining $k_i$ and then looking for repeating rows.

What are other possible ways to analyze this scheme in order to find vulnerabilities ?

Thank you

Edit: I've clarified more the question for what I asked, are techniques for analyzing the protocol disregarding technical problems like lost messages.

• 4 bit keys? No countermeasures? What do True or False mean? How is the tag identified? You cannot analyze this scheme without more information. Commented Apr 14, 2015 at 9:38
• 4 bit keys are just an example, key can be of different size. True/False may be Open/Close lock/door. Tag is not identified, adversary can be passive or active. Commented Apr 14, 2015 at 9:40
• In RFID, the TAG goes from a READER to another; as far as I understand the scheme outlined, the various readers need to know the current sate of a given TAG, by communicating between each others in some way, which is not something to lightly consider for granted in the physical world. $\;$ Independently, it is frequent that a message is lost between TAG and READER (in either direction), and the protocol outlined does not seem to account for that inescapable fact. $\;$ So before asking if it's secure (and defining the meaning of that): does it even work in the absence of adversary?
– fgrieu
Commented Apr 14, 2015 at 11:50
• If message is lost, the READER does not respond at all. Commented Apr 14, 2015 at 12:04
• Think about it again: with the protocol as described, some message loss can turn the step "they both add $r_1$ to the key set" into something where one of TAG or READER did this, and the other did not.
– fgrieu
Commented Apr 14, 2015 at 16:06

As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync. (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey". But the current protocol, as described, does not have this feature. Also, note that this would have its own security implications, which would need to be analyzed.)

This protocol also has the inconvenient feature that each tag can only work for one reader, at least unless the readers communicate with each other to synchronize their state, or unless the tag actually holds multiple keysets, and uses some kind of a handshake with the reader to decide which key to send. (Again, neither of these features are part of the protocol as decribed, and so their security implications cannot be analyzed reliably.)

The fact that the protocol requires the tag to generate random numbers also worries me a bit. I'm not really familiar with the state of the art in RFID, but generally, securely generating unpredictable random numbers is not a trivial task. The protocol appears to be designed for tags that have very minimal computing capabilities, so I wouldn't fell comfortable automatically assuming that such a tag has a cryptographically secure RNG.

Also, obviously, 4-bit keys are trivially vulnerable to brute force attacks, but that's easy enough to fix. In the rest of this answer, I'll assume that the actual key length is at least 128 bits or so.

Even if all the issues mentioned above are addressed, though, the protocol as described has (at least) two obvious and serious security flaws:

1. An eavesdropper can impersonate the tag after observing four consecutive successful authentications. The random numbers generated by the tag are transmitted in the clear, and the keys depend only on the last four random numbers, so knowledge of those four numbers automatically lets an attacker compute the key.

When using the key thus obtained, a clever attacker could also perform four consecutive authentications, and recycle the random numbers so that the reader ends up in the same state it was in before. That way, the holder of the valid tag need not notice anything unusual, as their tag will still be in perfect sync with the reader.

(In fact, since the XORed key is also sent in plain, it's enough to observe the latest transaction and the fourth one before it. This is not enough to fully determine the state of the tag, but it does suffice for one fake authentication.)

2. The attacker doesn't even need to get near the reader to carry out this attacks, since it's trivial to impersonate the reader. The fake reader can just reply "true" to anything the tag sends it. This allows a number of attacks:

• An attacker can impersonate the reader, and (possibly after some delay) relay the tag's key and random number to the real reader. This will allow the attacker to authenticate as if they had the tag, and any logs will show the tag being used normally.

• Alternatively, an attacker with a fake reader can query the tag four times, replaying "true" every time, and thus steal the full state of the tag. At that point, the real tag will no longer work (until and unless the attacker deliberately sends the same sequence of four random numbers to the real reader to re-sync its state), but the attacker can now authenticate with the reader as many times as they like.

There are ways to address all of these issues, but honestly, by the time you've fixed them all, the result will no longer bear more than a passing resemblance to your original protocol. So, no, this is not a secure authentication protocol.

• Thanks, I actually saw this scheme in a peer reviewed article, though they recursively XORed all keys and not 4 last keys, but I don't think it makes any difference to the security (of course less secure but more confusing). I know it's not secure, I wanted to hear the possible ways of analyzing it for vulnerabilities. I later read an article which made a statistical analysis on this protocol. I think I should clarify my question more. Commented Apr 14, 2015 at 22:16
• Yes, you right. The actual key length is 128bit. Commented Apr 14, 2015 at 22:55
• XORing all the keys actually makes is worse: as soon as an attacker intercepts one $(k_i,r_i)$ pair, they can compute $k_{i+1} = k_i \oplus r_i$ and so impersonate the tag as many times as they want. Edit: The same holds also for $k_{i+1} = F(k_i)$, if anybody can compute $F$. If $F$ is secret (say, encryption with a secret key) then the first attack I describe won't apply, but the second may. Commented Apr 14, 2015 at 23:33
• You actually helped me gain a lot of insight into this, Thanks! Commented Apr 15, 2015 at 0:04