Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Hell, Martin LU and Johansson, Thomas LU orcid (2007) 13th International Workshop, SAC 2006 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
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
cryptanalysis, stream ciphers, Pomaranch, linear approximation
host publication
Selected Areas in Cryptography/Lecture notes in computer science)
volume
4356
pages
220 - 233
publisher
Springer
conference name
13th International Workshop, SAC 2006
conference location
Montreal, Canada
conference dates
2006-08-17 - 2006-08-18
external identifiers
  • wos:000251036300016
  • scopus:38149026933
ISSN
1611-3349
0302-9743
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
2016-04-01 12:20:00
date last changed
2024-01-08 16:51:34
@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         = {{1611-3349}},
  keywords     = {{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}},
  doi          = {{10.1007/978-3-540-74462-7}},
  volume       = {{4356}},
  year         = {{2007}},
}