Abstract In truncated differential cryptanalysis of symmetric primitives, a generalized framework is to search a distinguisher concerning part of output differences, like truncated differential distribution (TDD) on certain bits (e.g. a nibble) first, and then append several rounds before and after it to recover the secret key. The logarithmic likelihood ratio statistic with respect to the TDD is usually used to distinguish guessed key bits. In this paper, we study how to improve the effect of truncated differential cryptanalysis by considering key schedules of the attacked ciphers. It turns out that for a cipher with a simple key schedule, certain guessed subkey bits may reveal information of the master key, which will help build a stronger TDD distinguisher and reduce the key recovery complexity or attack more rounds. As a result, we explore heuristic techniques to search key-recovery-friendly TDDs and construct automatic search models based on MILP. The refined methods are applied to two recent designs of symmetric primitives, WARP and Orthros, together with peculiarities of their structures as well. For WARP, after making two observations on relations between certain differences with key bits, we propose an algorithm that can find TDDs with low complexities and having potentialities to cover more rounds. Consequently, we launch key recovery attacks on 24 to 27 rounds of WARP. When it comes to Orthros, we present a two-step search algorithm to balance the number of guessed key bits and TDDs, obtaining a key recovery attack on a 7-round variant of it in the weak-key setting. Finally, we perform several verification experiments on round-reduced versions of WARP and Orthros, and the experimental results are consistent with the theoretical distributions and the analysis of generalized key recovery attack framework.

Abstract The fast correlation attack (FCA) is one of the most important cryptanalytic techniques against LFSR-based stream ciphers. In CRYPTO 2018, Todo et al. found a new property for the FCA and proposed a novel algorithm which was successfully applied to the Grain family of stream ciphers. Nevertheless, these techniques cannot be directly applied to Grain-like small state stream ciphers with keyed update, such as Plantlet, Fruit-v2 and Fruit80. In this paper, we study the security of Grain-like small state stream ciphers by the FCA. We first observe that the number of required parity-check equations can be reduced when there are multiple different parity-check equations. With exploiting the Skellam distribution, we introduce a sufficient condition to identify the correct LFSR initial state and derive a new relationship between the number and bias of the required parity-check equations. Then, a modified algorithm is presented based on this new relationship, which can recover the LFSR initial state no matter what the round key bits are. Under the condition that the LFSR initial state is known, an algorithm is given against the degraded system and to recover the NFSR state at some time instant, along with the round key bits. As cases study, we apply our cryptanalytic techniques to Plantlet, Fruit-v2 and Fruit-80. As a result, for Plantlet, our attack takes $ 2^{73.75} $ time complexity and $ 2^{73.06} $ keystream bits to recover the full 80-bit key. Regarding Fruit-v2, $ 2^{55.34} $ time complexity and $ 2^{55.62} $ keystream bits are needed to determine the secret key. As for Fruit-80, $2^{64.47}$ time complexity and $2^{62.82}$ keystream bits are required to recover the secret key. More flexible attacks can be obtained with lower data complexity at the cost of increasing the attack time. Especially, for Fruit-v2, a key recovery attack can be launched with data complexity of $2^{42.38}$ and time complexity of $2^{73.31}$. Moreover, we have implemented our attack methods on a toy version of Fruit-v2. The attack matches the expected complexities predicted by our theoretical analysis quite well, which proves the validity of our cryptanalytic techniques.