Paper 2015/762

A Meet-in-the-Middle Attack on Reduced-Round Kalyna-b/2b

Riham AlTawy, Ahmed Abdelkhalek, and Amr M. Youssef

Abstract

Kalyna is an SPN-based block cipher that was selected during Ukrainian national public cryptographic competition (2007-2010), and its slight modification was approved as the new encryption standard of Ukraine (DSTU 7624:2014) in 2015. The cipher supports a block size and a key length of 128, 256 and 512 bits where the size of the key can be either double or equal to that of the block length. According to its designers, the cipher provides strength to several cryptanalytic methods after the fifth and sixth rounds of the 128-bit and 256-bit block versions, respectively. In this paper, we present a meet-in-the-middle attack on the 7-round reduced versions of Kalyna where the key size is double the block length. Our attack is based on the differential enumeration approach where we carefully deploy a four round distinguisher in the first four rounds to bypass the effect of the carry bits resulting from the pre-whitening modular key addition. We also exploit the linear relation between consecutive odd and even indexed round keys which enables us to attack seven rounds and recover all the round keys incrementally. The attack on Kalyna with 128-bit block has a data complexity of $2^{89}$ chosen plaintexts, time complexity of $2^{230.2}$ and a memory complexity of $2^{202.64}$. The data, time and memory complexities of our attack on Kalyna with 256-bit block are $2^{233}$, $2^{502.2}$ and $2^{170}$, respectively.