License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-19576
URL: http://drops.dagstuhl.de/opus/volltexte/2009/1957/
Go to the corresponding Portal

Krause, Matthias ; Stegemann, Dirk

Algebraic Attacks against Linear RFID Authentication Protocols

pdf-format:
Document 1.pdf (297 KB)

Abstract

The limited computational resources available on RFID tags imply a need for specially designed authentication protocols. The light weight authentication protocol $extsf{HB}^+$ proposed by Juels and Weis seems currently secure for several RFID applications, but is too slow for many practical settings. As a possible alternative, authentication protocols based on choosing random elements from $L$ secret linear $n$-dimensional subspaces of $GF(2)^{n+k}$ (so called linear $(n,k,L)$-protocols), have been considered. We show that to a certain extent, these protocols are vulnerable to algebraic attacks. Particularly, our approach allows to break Cicho'{n}, Klonowski and Kutyl owski's $ extsf{CKK}^2$-protocol, a special linear $(n,k,2)$-protocol, for practically recommended parameters in less than a second on a standard PC. Moreover, we show that even unrestricted $(n,k,L)$-protocols can be efficiently broken if $L$ is too small.

BibTeX - Entry

@InProceedings{krause_et_al:DSP:2009:1957,
  author =	{Matthias Krause and Dirk Stegemann},
  title =	{Algebraic Attacks against Linear RFID Authentication Protocols},
  booktitle =	{Symmetric Cryptography },
  year =	{2009},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  number =	{09031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1957},
  annote =	{Keywords: RFID Authentication, HB+, CKK, CKK2}
}

Keywords: RFID Authentication, HB+, CKK, CKK2
Seminar: 09031 - Symmetric Cryptography
Issue Date: 2009
Date of publication: 30.03.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI