Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A Key-Recovery Attack on the LCMQ Authentication Protocol

Nguyen, Vu LU orcid ; Johansson, Thomas LU orcid and Guo, Qian LU (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:
author
; and
organization
publishing date
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}},
}