Paper 2021/723

Cache attack on MISTY1

Haopeng Fan; Wenhao Wang; Yongjuan Wang； Wenyu Zhang; Qingjun Yuan

Abstract

Side-channel attacks exploit information from physical implementations of cryptographic systems. Cache attacks have improved at recovering information by combining observations of the victim's cache access and knowledge of the cipher’s structure. Cache attacks have been implemented for most Feistel- and SPN-structured block cipher algorithms, but the security of algorithms for special structures has seen little attention. We perform a Flush+Reload attack on MISTY1, a class of block cipher with a recursive structure. The function is performed before the plaintext input S-box and after the ciphertext output S-box, making it difficult to attack the first and last rounds. However, the key scheduling part of MISTY1 leaks many bits of the key, which, together with the leakage of partial bits of the round key during encryption, is sufficient to recover it. We design an algorithm that can recover the MISTY1 128-bit key after observing encryption one time, and then use leakage during encryption to reduce its complexity. We experiment on 32- and 64-byte cache line environments. An adversary need observe as little as 5 encryptions to recover the 128-bit key in 0.035 second in the first case, and 10 encryptions to recover the key in 2.1 hours in the second case.