Grobner Basis Attacks on Lightweight RFID Authentication Protocols

Daewan Han
Volume: 7, No: 4, Page: 691 ~ 706, Year: 2011
Keywords: RFID, Authentication Protocol, Algebraic Attack, Grobner Basis
Full Text:

Since security and privacy problems in RFID systems have attracted much attention, numerous RFID authentication protocols have been suggested. One of the various design approaches is to use light-weight logics such as bitwise Boolean operations and addition modulo 2m between m-bits words. Because these operations can be implemented in a small chip area, that is the major requirement in RFID protocols, a series of protocols have been suggested conforming to this approach. In this paper, we present new attacks on these lightweight RFID authentication protocols by using the Grobner basis. Our attacks are superior to previous ones for the following reasons: since we do not use the specific characteristics of target protocols, they are generally applicable to various ones. Furthermore, they are so powerful that we can recover almost all secret information of the protocols. For concrete examples, we show that almost all secret variables of six RFID protocols, LMAP, M2AP, EMAP, SASI, Lo et al."s protocol, and Lee et al."s protocol, can be recovered within a few seconds on a single PC.

Article Statistics
Multiple requests among the same broswer session are counted as one view (or download).
If you mouse over a chart, a box will show the data point's value.

Cite this article
IEEE Style
D. Han, "Grobner Basis Attacks on Lightweight RFID Authentication Protocols," Journal of Information Processing Systems, vol. 7, no. 4, pp. 691~706, 2011. DOI: 10.3745/JIPS.2011.7.4.691.

ACM Style
Daewan Han. 2011. Grobner Basis Attacks on Lightweight RFID Authentication Protocols, Journal of Information Processing Systems, 7, 4, (2011), 691~706. DOI: 10.3745/JIPS.2011.7.4.691.