You are looking at a specific version 20170905:045156 of this paper. See the latest version.

Paper 2017/412

Determining the Nonexistent Terms of Non-linear Multivariate Polynomials: How to Break Grain-128 More Efficiently

Ximing Fu and Xiaoyun Wang and Jiazhe Chen and Marc Stevens

Abstract

In this paper, we propose a reduction technique that can be used to determine the density of IV terms of a complex multivariable boolean polynomial. Using this technique, we revisit the dynamic cube attack on Grain-128. Based on choosing one more nullified state bit and one more dynamic bit, we are able to obtain the IV terms of degree $43$ with various of complicated reduction techniques for polynomials, so that the nonexistent IV terms can be determined. As a result, we improve the time complexity of the best previous attack on Grain-128 by a factor of $2^{16}$. Moreover, our attack applies to all keys.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Stream ciphersGrain-128Polynomial reductionDynamic cube attack
Contact author(s)
fxm15 @ mails tsinghua edu cn
History
2018-05-16: last of 2 revisions
2017-05-13: received
See all versions
Short URL
https://ia.cr/2017/412
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.