Improved Linear Analysis on Block Cipher MULTI2

摘要

Developed by Hitachi, MULTI2 is a block cipher used mainly to secure the multimedia content. It was registered in ISO/IEC 9979 and was patented in US and Japan. MULTI2 uses the Feistel structure and operates on the 64-bit blocks. The encryption key has 256 bits. This paper studies the linear analysis on MULTI2. We give a detailed bias analysis on MULTI2 round functions. For the first time formal proofs on their bias properties are given. This allows to find a new 4-round bias 2~(-2) Previously, the best 4-round bias 2~(5.7) was proposed. Using our results on the MULTI2 round functions, we propose the linear attacks on r-round MUTLI2 to recover the encryption key. Our linear attack can recover the 256-bit encryption key in time 2~(46), 2~(60.4), 2~(83.8), 2~(91.7), 2~(123.4), 2~(123.2) of r-round encryptions for r = 8,12, 16, 20, 24, 28 respectively. Further, we can recover the 32-bit sub-key in last round much faster than the whole encryption key recovery, i.e., in time 2~(37) for r = 8,12, 16,20,24. Note that previously, the best linear key-recovery attack was a 20-round attack with time 2~(93.4) (of 20-round encryptions) and data 2~(39.2). As ISO register recommends to use at least 32 rounds, our attacks remain to be theoretical and do not threaten security for the practical use currently.