Advanced

Attack the dragon

Englund, Håkan LU and Maximov, Alexander LU (2005) In Lecture Notes in Computer Science 3797. p.130-142
Abstract
Dragon is a word oriented stream cipher submitted to the ECRYPT project, it operates on key sizes of 128 and 256 bits. The original idea of the design is to use a nonlinear feedback shift register (NLFSR) and a linear part (counter), combined by a filter function to generate a new state of the NLFSR and produce the keystream. The internal state of the cipher is 1088 bits, i.e., any kinds of TMD attacks are not applicable. In this paper we present two statistical distinguishers that distinguish Dragon from a random source both requiring around O(2(155)) words of the keystream. In the first scenario the time complexity is around O(2(155+32)) with the memory complexity O(2(32)), whereas the second scenario needs only O(2(155)) of time, but... (More)
Dragon is a word oriented stream cipher submitted to the ECRYPT project, it operates on key sizes of 128 and 256 bits. The original idea of the design is to use a nonlinear feedback shift register (NLFSR) and a linear part (counter), combined by a filter function to generate a new state of the NLFSR and produce the keystream. The internal state of the cipher is 1088 bits, i.e., any kinds of TMD attacks are not applicable. In this paper we present two statistical distinguishers that distinguish Dragon from a random source both requiring around O(2(155)) words of the keystream. In the first scenario the time complexity is around O(2(155+32)) with the memory complexity O(2(32)), whereas the second scenario needs only O(2(155)) of time, but O(2(96)) of memory. The attack is based on a statistical weakness introduced into the keystream by the filter function F. This is the first paper presenting an attack on Dragon, and it shows that the cipher does not provide full security when the key of size 256 bits is used. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Lecture Notes in Computer Science
volume
3797
pages
130 - 142
publisher
Springer
external identifiers
  • wos:000234716000011
  • scopus:33646823005
ISSN
1611-3349
DOI
10.1007/11596219
language
English
LU publication?
yes
id
bc63001b-6473-448b-8a7d-91c95264cf19 (old id 209614)
date added to LUP
2007-08-02 16:20:54
date last changed
2017-09-03 03:47:38
@article{bc63001b-6473-448b-8a7d-91c95264cf19,
  abstract     = {Dragon is a word oriented stream cipher submitted to the ECRYPT project, it operates on key sizes of 128 and 256 bits. The original idea of the design is to use a nonlinear feedback shift register (NLFSR) and a linear part (counter), combined by a filter function to generate a new state of the NLFSR and produce the keystream. The internal state of the cipher is 1088 bits, i.e., any kinds of TMD attacks are not applicable. In this paper we present two statistical distinguishers that distinguish Dragon from a random source both requiring around O(2(155)) words of the keystream. In the first scenario the time complexity is around O(2(155+32)) with the memory complexity O(2(32)), whereas the second scenario needs only O(2(155)) of time, but O(2(96)) of memory. The attack is based on a statistical weakness introduced into the keystream by the filter function F. This is the first paper presenting an attack on Dragon, and it shows that the cipher does not provide full security when the key of size 256 bits is used.},
  author       = {Englund, Håkan and Maximov, Alexander},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {130--142},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {Attack the dragon},
  url          = {http://dx.doi.org/10.1007/11596219},
  volume       = {3797},
  year         = {2005},
}