Advanced

Not so greedy : Enhanced subset exploration for nonrandomness detectors

Karlsson, Linus LU ; Hell, Martin LU and Stankovski, Paul LU (2018) International Conference on Information Systems Security and Privacy In Communications in Computer and Information Science 867. p.273-294
Abstract

Distinguishers and nonrandomness detectors are used to distinguish ciphertext from random data. In this paper, we focus on the construction of such devices using the maximum degree monomial test. This requires the selection of certain subsets of key and IV-bits of the cipher, and since this selection to a great extent affects the final outcome, it is important to make a good selection. We present a new, generic and tunable algorithm to find such subsets. Our algorithm works on any stream cipher, and can easily be tuned to the desired computational complexity. We test our algorithm with both different input parameters and different ciphers, namely Grain-128a, Kreyvium and Grain-128. Compared to a previous greedy approach, our algorithm... (More)

Distinguishers and nonrandomness detectors are used to distinguish ciphertext from random data. In this paper, we focus on the construction of such devices using the maximum degree monomial test. This requires the selection of certain subsets of key and IV-bits of the cipher, and since this selection to a great extent affects the final outcome, it is important to make a good selection. We present a new, generic and tunable algorithm to find such subsets. Our algorithm works on any stream cipher, and can easily be tuned to the desired computational complexity. We test our algorithm with both different input parameters and different ciphers, namely Grain-128a, Kreyvium and Grain-128. Compared to a previous greedy approach, our algorithm consistently provides better results.

(Less)
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
Distinguisher, Grain-128, Grain-128a, Kreyvium, Maximum degree monomial, Nonrandomness detector
host publication
Information Systems Security and Privacy - 3rd International Conference, ICISSP 2017, Revised Selected Papers
series title
Communications in Computer and Information Science
volume
867
pages
22 pages
publisher
Springer Verlag
conference name
International Conference on Information Systems Security and Privacy
conference location
Porto, Portugal
conference dates
2017-02-19 - 2017-02-21
external identifiers
  • scopus:85049107964
ISSN
1865-0929
ISBN
9783319933535
DOI
10.1007/978-3-319-93354-2_13
language
English
LU publication?
yes
id
971eb793-8fba-446e-96e1-a69cbe6d1cfe
date added to LUP
2018-07-09 13:37:40
date last changed
2018-11-21 21:40:43
@inproceedings{971eb793-8fba-446e-96e1-a69cbe6d1cfe,
  abstract     = {<p>Distinguishers and nonrandomness detectors are used to distinguish ciphertext from random data. In this paper, we focus on the construction of such devices using the maximum degree monomial test. This requires the selection of certain subsets of key and IV-bits of the cipher, and since this selection to a great extent affects the final outcome, it is important to make a good selection. We present a new, generic and tunable algorithm to find such subsets. Our algorithm works on any stream cipher, and can easily be tuned to the desired computational complexity. We test our algorithm with both different input parameters and different ciphers, namely Grain-128a, Kreyvium and Grain-128. Compared to a previous greedy approach, our algorithm consistently provides better results.</p>},
  author       = {Karlsson, Linus and Hell, Martin and Stankovski, Paul},
  booktitle    = {Communications in Computer and Information Science},
  isbn         = {9783319933535},
  issn         = {1865-0929},
  keyword      = {Distinguisher,Grain-128,Grain-128a,Kreyvium,Maximum degree monomial,Nonrandomness detector},
  language     = {eng},
  location     = {Porto, Portugal},
  month        = {01},
  pages        = {273--294},
  publisher    = {Springer Verlag},
  title        = {Not so greedy : Enhanced subset exploration for nonrandomness detectors},
  url          = {http://dx.doi.org/10.1007/978-3-319-93354-2_13},
  volume       = {867},
  year         = {2018},
}