Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Another attack on A5/1

Ekdahl, Patrik LU and Johansson, Thomas LU orcid (2003) In IEEE Transactions on Information Theory 49(1). p.284-289
Abstract
A5/1 is a stream cipher used in the Global System for Mobile Communications (GSM) standard. Several time-memory tradeoff attacks against A5/1 have been proposed, most notably the recent attack by Biryukov, Shamir, and Wagner, which can break A5/1 in seconds using huge precomputation time and memory. This correspondence presents a completely different attack on A5/1, based on ideas from correlation attacks. Whereas time-memory tradeoff attacks have a complexity which is exponential with the shift-register length, the complexity of the proposed attack is almost independent of the shift-register length. Our implementation of the suggested attack breaks A5/1 in a few minutes using 2-5 min of conversation plaintext.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
GSM, cryptanalysis, A5/1, correlation attacks, stream ciphers
in
IEEE Transactions on Information Theory
volume
49
issue
1
pages
284 - 289
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000180370400025
  • scopus:0037269216
ISSN
0018-9448
DOI
10.1109/TIT.2002.806129
language
English
LU publication?
yes
id
16810b89-c33b-4739-a471-390c3b2d07ee (old id 320385)
date added to LUP
2016-04-01 17:09:48
date last changed
2025-10-14 09:08:51
@article{16810b89-c33b-4739-a471-390c3b2d07ee,
  abstract     = {{A5/1 is a stream cipher used in the Global System for Mobile Communications (GSM) standard. Several time-memory tradeoff attacks against A5/1 have been proposed, most notably the recent attack by Biryukov, Shamir, and Wagner, which can break A5/1 in seconds using huge precomputation time and memory. This correspondence presents a completely different attack on A5/1, based on ideas from correlation attacks. Whereas time-memory tradeoff attacks have a complexity which is exponential with the shift-register length, the complexity of the proposed attack is almost independent of the shift-register length. Our implementation of the suggested attack breaks A5/1 in a few minutes using 2-5 min of conversation plaintext.}},
  author       = {{Ekdahl, Patrik and Johansson, Thomas}},
  issn         = {{0018-9448}},
  keywords     = {{GSM; cryptanalysis; A5/1; correlation attacks; stream ciphers}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{284--289}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{Another attack on A5/1}},
  url          = {{http://dx.doi.org/10.1109/TIT.2002.806129}},
  doi          = {{10.1109/TIT.2002.806129}},
  volume       = {{49}},
  year         = {{2003}},
}