Paper 2019/809

On the Data Limitation of Small-State Stream Ciphers: Correlation Attacks on Fruit-80 and Plantlet

Yosuke Todo, Willi Meier, and Kazumaro Aoki

Abstract

Many cryptographers have focused on lightweight cryptography, and a huge number of lightweight block ciphers have been proposed. On the other hand, designing lightweight stream ciphers is a challenging task due to the well-known security criteria, i.e., the state size of stream ciphers must be at least twice the key size. The designers of Sprout addressed this issue by involving the secret key not only in the initialization but also in the keystream generation, and the state size of such stream ciphers can be smaller than twice the key size. After the seminal work, some small-state stream ciphers have been proposed such as Fruit, Plantlet, and LIZARD. Unlike conventional stream ciphers, these small-state stream ciphers have the limitation of keystream bits that can be generated from the same key and IV pair. In this paper, our motivation is to show whether the data limitation claimed by the designers is proper or not. The correlation attack is one of the attack methods exploiting many keystream bits generated from the same key and IV pair, and we apply it to Fruit-80 and Plantlet. As a result, we can break the full Fruit-80, i.e., the designers' data limitation is not sufficient. We can also recover the secret key of Plantlet if it allows about $2^{53}$ keystream bits from the same key and IV pair.