Cryptanalysis of Reduced Kreyvium

Yuhei WATANABE  Takanori ISOBE  Masakatu MORII  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1548-1556
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1548
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
differential cryptanalysis,  conditional differential,  higher-order differential,  distinguisher,  key recovery attack,  Kreyvium,  

Full Text: PDF(1MB)
>>Buy this Article


Summary: 
Kreyvium is a NLFSR-based stream cipher which is oriented to homomorphic-ciphertext compression. This is a variant of Trivium with 128-bit security. Designers have evaluated the security of Kreyvium and concluded that the resistance of Kreyvium to the conditional differential cryptanalysis is at least the resistance of Trivium, and even better. However, we consider that this attack is effective for reduced Kreyvium due to the structure of it. This paper shows the conditional differential cryptanalysis for Kreyvium, and we propose distinguishing and key recovery attacks. We show how to arrange differences and conditions to obtain good higher-order conditional differential characteristics. We use two types of higher-order conditional differential characteristics to find a distinguisher, e.g. the bias of higher-order conditional differential characteristics of a keystream and the probabilistic bias of them. In the first one, we obtain the distinguisher on Kreyvium with 730 rounds from 20-th order characteristics. In the second one, we obtain the distinguisher on Kreyvium with 899 rounds from 25-th order conditional differential characteristics. Moreover, we show the key recovery attack on Kreyvium with 736 rounds from 20-th order characteristics. We experimentally confirm all our attacks. The second distinguisher shows that we can obtain the distinguisher on Kreyvium with more rounds than the distinguisher on Trivium. Therefore, Kreyvium has a smaller security margin than Trivium for the conditional differential cryptanalysis.