Advanced

On the problem of finding linear approximations and cryptanalysis of Pomaranch Version 2

Hell, Martin LU and Johansson, Thomas LU (2007) 13th International Workshop, SAC 2006 In Selected Areas in Cryptography/Lecture notes in computer science) 4356. p.220-233
Abstract
We give a simple algorithm that can find biased linear approximations of nonlinear building blocks. The algorithm is useful if the building block is relatively small and exhaustive search is possible. Instead of searching all possible linear relations individually, we show how the most biased relation can be found in just a few steps. As an example we show how we can find a biased relation in the output bits of the stream cipher Pomaranch Version 2, a tweaked variant of Pomaranch, resulting in both distinguishing and key recovery attacks. These attacks will break both the 128-bit variant and the 80-bit variant of the cipher with complexity faster than exhaustive key search.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
cryptanalysis, stream ciphers, Pomaranch, linear approximation
in
Selected Areas in Cryptography/Lecture notes in computer science)
volume
4356
pages
220 - 233
publisher
Springer
conference name
13th International Workshop, SAC 2006
external identifiers
  • wos:000251036300016
  • scopus:38149026933
ISSN
0302-9743
1611-3349
ISBN
978-3-540-74461-0
DOI
10.1007/978-3-540-74462-7
language
English
LU publication?
yes
id
d769d545-dec3-4330-86fc-1ad7a953c745 (old id 603346)
date added to LUP
2007-11-30 13:45:33
date last changed
2017-01-01 05:03:06
@inproceedings{d769d545-dec3-4330-86fc-1ad7a953c745,
  abstract     = {We give a simple algorithm that can find biased linear approximations of nonlinear building blocks. The algorithm is useful if the building block is relatively small and exhaustive search is possible. Instead of searching all possible linear relations individually, we show how the most biased relation can be found in just a few steps. As an example we show how we can find a biased relation in the output bits of the stream cipher Pomaranch Version 2, a tweaked variant of Pomaranch, resulting in both distinguishing and key recovery attacks. These attacks will break both the 128-bit variant and the 80-bit variant of the cipher with complexity faster than exhaustive key search.},
  author       = {Hell, Martin and Johansson, Thomas},
  booktitle    = {Selected Areas in Cryptography/Lecture notes in computer science)},
  isbn         = {978-3-540-74461-0},
  issn         = {0302-9743},
  keyword      = {cryptanalysis,stream ciphers,Pomaranch,linear approximation},
  language     = {eng},
  pages        = {220--233},
  publisher    = {Springer},
  title        = {On the problem of finding linear approximations and cryptanalysis of Pomaranch Version 2},
  url          = {http://dx.doi.org/10.1007/978-3-540-74462-7},
  volume       = {4356},
  year         = {2007},
}