Qualifying Information Leakage in Tree-Based Hash Protocols

Radio Frequency Identification (RFID)systems promise large scale, automated tracking solutions but also pose a threat to customer privacy. The tree-based hash protocol proposed by Molnar and Wagner presents a scalable, privacy-preserving solution. Previous analyses of this protocol concluded that an attacker who can extract secrets from a large number of tags can compromise privacy of other tags. We propose a new metric for information leakage in RFID protocols along with a threat model that more realistically captures the goals and capabilities of potential at- tackers. Using this metric, we measure the information leakage in the tree- based hash protocol and estimate an attacker�s probability of success in tracking targeted individuals, considering scenarios in which multiple in- formation sources can be combined to track an individual. We conclude that an attacker has a reasonable chance of tracking tags when the tree- based hash protocol is used.

Nohl, Karsten, and Dave Evans. "Qualifying Information Leakage in Tree-Based Hash Protocols." University of Virginia Dept. of Computer Science Tech Report (2006).