Cryptology ePrint Archive: Report 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.

Category / Keywords: Stream ciphers, Grain-128, Polynomial reduction, Dynamic cube attack

Date: received 11 May 2017, last revised 4 Sep 2017

Contact author: fxm15 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20170905:045156 (All versions of this report)

Short URL: ia.cr/2017/412

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]