Building a privacy-protecting contactless card query protocol

One of the big concerns people have about RFID systems such as RFID passports is that they leak identity information. In your most simple RFID protocol, the reader sends out a probe signal and the transponder (passport, tag, etc.) responds with its stored data. In the case of a price tag, it's some sort of identifier for the product and likely a unit-specific number. For a passport, it's your name, biometric information, etc. This protocol has two main drawbacks. First, any passive observer can capture your information. Second, anyone who can build or buy a reader can capture it.

The simplest fix for this is to encrypt the data on the token using some static key known to all the readers in an organization. This partially solves the problem of someone buying a reader on the open market--since they won't have the right key, but only partially. First, since the encrypted data is static, you can still track people even if you can't read their data. Second, it's subject to a catastrophic failure mode: if the attacker can get a reader with a valid key--or just the key--then he can decrypt the data. Nevertheless, this is the best we can do with a memory-only card. 1

If you're willing to do processing on the token, then you can do somewhat better: the reader provides its public key certificate. The token verifies the certificate and encrypts under the public key. This stops the tracking problem for readers without the key, but not for readers with the key. And since any reasonable-sized organization will have lots of readers, the probability that one will go missing is fairly high. In order to contain this, you need some kind of process for revoking readers, which makes life massively more complicated.

1.One exception is that if we have a side channel, we can encrypt the data with a per-token key communicated via the side channel. This has been proposed for passports (having the key printd on the passport) but doesn't really work for lots of applications, since much of the point of contactless cards is to avoid having to have such a side channel.