Advanced

Another attack on A5/1

Ekdahl, Patrik LU and Johansson, Thomas LU (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
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
2007-08-02 14:24:32
date last changed
2018-08-26 04:30:04
@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},
  keyword      = {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},
  volume       = {49},
  year         = {2003},
}