Algebraic Attacks against Linear RFID Authentication Protocols

Abstract

The limited computational resources available on RFID tags imply a
need for specially designed authentication protocols. The light weight
authentication protocol $extsf{HB}^+$ proposed by Juels and Weis seems currently
secure for several RFID applications, but is too slow for many practical
settings. 
As a possible alternative, authentication protocols based on choosing
random elements from $L$ secret linear $n$-dimensional subspaces of
$GF(2)^{n+k}$ (so called linear $(n,k,L)$-protocols), have been considered. We show that to a certain extent, these protocols are vulnerable to algebraic
attacks.  Particularly, our approach allows to break Cicho'{n}, Klonowski and Kutyl owski's $	extsf{CKK}^2$-protocol,  a special linear
$(n,k,2)$-protocol,  for practically recommended parameters in less
than a second on a standard PC. Moreover, we show that
even  unrestricted $(n,k,L)$-protocols can be efficiently broken  if $L$ is too small.