Grobner Basis Attacks on Lightweight RFID Authentication Protocols


Daewan Han, Journal of Information Processing Systems Vol. 7, No. 4, pp. 691-706, Dec. 2011  

10.3745/JIPS.2011.7.4.691
Keywords: RFID, Authentication Protocol, Algebraic Attack, Grobner Basis
Fulltext:

Abstract

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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from November 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Han, D. (2011). Grobner Basis Attacks on Lightweight RFID Authentication Protocols. Journal of Information Processing Systems, 7(4), 691-706. DOI: 10.3745/JIPS.2011.7.4.691.

[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.