Cryptanalysis of Reduced Kreyvium

• WATANABE Yuhei

  SEI-AIST Cyber Security Cooperative Research Laboratory

• ISOBE Takanori

  Graduate School of Applied Informatics, University of Hyogo

• MORII Masakatu

  Graduate School of Engineering, Kobe University

Abstract

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.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A (9), 1548-1556, 2018-09-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• differential cryptanalysis
• conditional differential
• higher-order differential
• distinguisher
• key recovery attack
• Kreyvium

Details

• CRID: 1390564238018453888
• NII Article ID: 130007479525
• DOI: 10.1587/transfun.e101.a.1548
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E101.A/9/E101.A_1548/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed