Solution of a Conjecture: On 2-PCD RFID Distance Bounding Protocols

It is a popular challenge to design distance bounding protocols that are both secure and efficient. Motivated by this, many distance bounding protocols against relay attacks have been advanced in recent times. Another interesting question is whether these protocols provides the best security. In 2010, Kara et al. analysis the optimal security limits of low-cost distance bounding protocols having bit-wise fast phases and no final signature. As for the classification, they have introduced the notion of k-previous challenge dependent (k-PCD) protocols where each response bit depends on the current and the k previous challenges. They have given the theoretical security bounds for two specific classes k = 0 and 1, but have left the security bounds for k >= 2 as an open problem. In this paper, we aim to answer the open question concerning the security limits of 2-PCD protocols. We describe two generic attacks for mafia and distance frauds that can be applied on any 2-PCD protocols. Then, we provide the optimal trade-off curve between the security levels of mafia and distance frauds that determines the security limits of 2-PCD protocols. Finally our results also prove the conjecture that 2-PCD protocols enhance the security compared to 0-PCD and 1-PCD cases.