Gröbner Basis Attacks on Lightweight RFID Authentication Protocols
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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 2^m 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 Gröbner 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, M^2AP, EMAP, SASI, Lo et al.'s protocol, and Lee et al.'s protocol, can be recovered within a few seconds on a single PC.
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 2^m 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 Gröbner 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, M^2AP, EMAP, SASI, Lo et al.'s protocol, and Lee et al.'s protocol, can be recovered within a few seconds on a single PC.
참고문헌 (28)
- W.W. Adams, "An Introduction to Gröbner Bases", Graduate Studies in Mathematics, 3 (1994), AMS
- B. Alomair, "Passive Attacks on a Class of Authentication Protocols for RFID", Proceedings of ICISC 2007, LNCS 4817, pp.102~115 (2007), Springer-Verlag
- G. Avoine, "Cryptography in Radio Frequency Identification and Fair Exchange Protocols" (2005), EPFL
- M. Brickenstein, "A Framework for Gröbner Basis Computations with Boolean Polynomials", Electronic Proceedings of the MEGA 2007 - Efficient Methods in Algebraic Geometry, Strobl, Austria (2007)
- J. Buchmann, "Block Ciphers Sensitive to Gröbner Basis Attacks", Proceedings of CT-RSA 2006, LNCS 3860, pp.313~331 (2006), Springer-Verlag
- T. Cao, "Security Analysis of the SASI Protocol", IEEE Transactions on Dependable and Secure Computing, 6(1), pp.73~77 (2009)
- H.-Y. Chien, "SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication ans Strong Integrity", IEEE Transactions on Dependable and Secure Computing, 4(4), pp.337~340 (2007)
- C. Cid, "Algebraic Aspects of the Advanced Encrpytion Standard" (2006), Springer-Verlag
- N. Courtois, "Cryptanalysis of Block Ciphers with Over-defined System of Equations", Proceedings of Asiacrypt 2002, LNCS 2501, pp.267~287 (2002), Springer-Verlag
- N. Courtois, "Fast Algebraic Attacks on Stream Ciphers with Linear Feedback", Proceedings of Crypto 2003, LNCS 2729, pp.176~194 (2003), Springer-Verlag
- N. Courtois, "Algebraic Attacks on Stream Ciphers with Linear Feedback", Proceedings of Eurocrypt 2003, LNCS 2656, pp.345~359 (2003), Springer-Verlag
- J.-C. Faugère, "A New Efficient Algorithm for computing Gröbner bases (F4)", Journal of Pure and Applied Algebra, 139, pp.61~88 (1999)
- J.-C. Faugère, "A New Efficient Algorithm for computing Gröbner bases without Reduction to Zero (F5)", Proceedings of ISSAC 2002, pp.75~83 (2002)
- J.-C. Faugère, "Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems using Gröbner bases", Proceedings of Crypto 2003, LNCS 2729, pp.44~60 (2003), Springer- Verlag
- M. Feldhofer, "Strong Authentication for RFID Systems Using AES Algorithm", Proceedings of CHES 2004, LNCS 3156, pp.357~370 (2004), Springer-Verlag
- M. Feldhofer, "A Case against Currently Used Hash Functions in RFID Protocols", Proceedings of RFIDSec 2006 (2006)
- C. Hung-Yu, "Security of ultra-lightweight RFID authentication protocols and its improvements", ACM SIGOPS Operating Systems Review, 41(4), pp.83~86 (2007)
- A. Juels, "RFID Security and Privacy: A Research Survey", IEEE Journal on Selected Areas in Communications, 24(2), pp.381~394 (2006)
- A. Juels, "The Blocker tag: Selective Blocking of RFID Tags for Consumer Privacy", Proceedings of CCS 2003, pp.103~111 (2003), ACM Press
- A. Juels, "Authenticating Pervasive Devices with Human Protocols", Proceedings of Crypto'05, LNCS 3621, pp.293~308 (2005), Springer-Verlag
- Y.-C. Lee, "A New Ultralightweight RFID Protocol with Mutual Authentication", Proceedings of WASE 2009, 통권 : 2, pp.58~61 (2009), ICIE
- N.-W. Lo, "A Design of RFID Mutual Authentication Protocol Using Lightweight Bitwise Operations", Proceedings of JWIS 2008 (2008)
- P. Peris-Lopez, "LMAP: A Real Lightweight Mutual Authentication Protocol for Low-cost RFID tags", Proceedings of UIC 2006, LNCS 4159, pp.912~923 (2006), Springer-Verlag
- P. Peris-Lopez, "M2AP: A Minimalist Mutual-Authentication Protocol for Low-cost RFID tags", Proceedings of UIC 2006, LNCS 4159, pp.912~923 (2006), Springer-Verlag
- P. Peris-Lopez, "EMAP: An Efficient Mutual Authentication Protocol for Low-cost RFID tags", Proceedings of IS 2006, LNCS 4277, pp.352~361 (2006), Springer-Verlag
- R. C.-W. Phan, "Cryptanalysis of a New Ultralightweight RFID Authentication Protocol- SASI", IEEE Transactions on Dependable and Secure Computing, 6(4), pp.316~320 (2009)
- "Sage distribution of mathematical software"[URL]
- S. A. Weis, "Security and Privacy in Radio-Frequency Identification Devices" (2003), Massachusetts: Massachusetts Institute of Technology (MIT)