RFID Protocol Cryptanalysis Assume we have the following scheme for RFID:
TAG &amp; 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.
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:


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.)
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.