A Key-Recovery Attack on the LCMQ Authentication Protocol
(2024) 2024 IEEE International Symposium on Information Theory (ISIT) p.1824-1829- Abstract
- We present a simple key-recovery attack on the LCMQ Authentication Protocol, an RFID authentication protocol proposed by Li, Gong, and Qin in 2013. We show that a successful attack is performed by solving a Learning Parity with Noise instance in a not-too-large dimension. For the proposed LCMQ parameters, the attack requires only a few invocations with the tag under attack. When there is no restriction on the number of invocations, state-of-the-art LPN solvers recover the keys with complexity below 251 and 286 , when attacking LCMQ parameters for security levels 80-bit and 128-bit, respectively. To the best of our knowledge, this is the first attack on LCMQ with complexity below exhaustive key search.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/a95d09e5-a898-45b4-9bb3-57107d1b19f0
- author
- Nguyen, Vu LU ; Johansson, Thomas LU and Guo, Qian LU
- organization
- publishing date
- 2024-07-05
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 2024 IEEE International Symposium on Information Theory (ISIT)
- pages
- 5 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2024 IEEE International Symposium on Information Theory (ISIT)
- conference location
- Athens, Greece
- conference dates
- 2024-07-07 - 2024-07-12
- external identifiers
-
- scopus:85202845168
- ISBN
- 979-8-3503-8284-6
- DOI
- 10.1109/ISIT57864.2024.10619211
- language
- English
- LU publication?
- yes
- id
- a95d09e5-a898-45b4-9bb3-57107d1b19f0
- date added to LUP
- 2024-09-16 16:27:45
- date last changed
- 2024-09-17 09:29:31
@inproceedings{a95d09e5-a898-45b4-9bb3-57107d1b19f0, abstract = {{We present a simple key-recovery attack on the LCMQ Authentication Protocol, an RFID authentication protocol proposed by Li, Gong, and Qin in 2013. We show that a successful attack is performed by solving a Learning Parity with Noise instance in a not-too-large dimension. For the proposed LCMQ parameters, the attack requires only a few invocations with the tag under attack. When there is no restriction on the number of invocations, state-of-the-art LPN solvers recover the keys with complexity below 251 and 286 , when attacking LCMQ parameters for security levels 80-bit and 128-bit, respectively. To the best of our knowledge, this is the first attack on LCMQ with complexity below exhaustive key search.}}, author = {{Nguyen, Vu and Johansson, Thomas and Guo, Qian}}, booktitle = {{2024 IEEE International Symposium on Information Theory (ISIT)}}, isbn = {{979-8-3503-8284-6}}, language = {{eng}}, month = {{07}}, pages = {{1824--1829}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{A Key-Recovery Attack on the LCMQ Authentication Protocol}}, url = {{http://dx.doi.org/10.1109/ISIT57864.2024.10619211}}, doi = {{10.1109/ISIT57864.2024.10619211}}, year = {{2024}}, }