Eran Lambooij, Patrick Neumann

A Known-Plaintext Attack with Minimal Data Complexity on 25-Round CRAFT

Introduction

A known-plaintext attack with minimal data complexity on 25-round craft. Discover the first known-plaintext attack on 25-round CRAFT, requiring only two plaintext-ciphertext pairs to recover the full 128-bit key. Exploits Craft's decomposition.

Abstract

We present the first known-plaintext attack on up to 25 rounds of the tweakable block cipher Craft. These attacks require only two known plaintextciphertext pairs to recover the full key, and work independent of the used tweaks. Given the state and key size of 64 and 128 bits, respectively, this is the minimal data complexity an attack recovering the full key can have.At the basis of this attack is the observation that Craft can be decomposed into two loosely dependent functions: the state can be split in half such that the round function mixes only 4 bits of each half into the other. Since the key schedule does not provide mixing between these parts either, we can guess these 4 bits per round to mount a meet-in-the-middle attack on up to 25 rounds.While the best attacks on Craft by M’Foukh et al. cover up to 26 rounds, they are in the chosen-ciphertext setting and require (up to) the full code book. In fact, we show that their attacks (implicitly) use a similar decomposition, and therefore present the other end of a time-data trade-off for the same family of attacks.

Review

This paper presents a significant contribution to the cryptanalysis of the CRAFT tweakable block cipher, introducing the first known-plaintext attack (KPA) capable of breaking up to 25 rounds. A key strength of this work is its unprecedented data efficiency, requiring only two known plaintext-ciphertext pairs to fully recover the 128-bit master key, irrespective of the tweak values used. Given CRAFT's 64-bit state size, this achieves the theoretical minimum data complexity for a full key recovery attack, marking a critical advancement in understanding CRAFT's security in a more practical adversary model than often considered. The cornerstone of their approach lies in a novel observation regarding CRAFT's internal structure: the cipher can be effectively decomposed into two loosely coupled functions. The authors astutely identify that the 64-bit state can be halved, with the round function only mixing a mere 4 bits between these two halves in each round. Crucially, this structural characteristic is not compensated for by the key schedule, which also fails to provide sufficient mixing between these parts. This inherent weakness allows the attackers to employ a meet-in-the-middle strategy, where guessing these limited 4 bits per round becomes feasible, enabling the attack to penetrate a substantial 25 rounds with minimal data. When juxtaposed with existing cryptanalytic efforts, particularly those by M'Foukh et al., this work offers a valuable complementary perspective. While previous best attacks reached 26 rounds, they operated within the chosen-ciphertext setting and necessitated access to the entire codebook, representing a much stronger adversary model. This paper reveals that those chosen-ciphertext attacks implicitly exploit a similar underlying decomposition of CRAFT, thereby positioning the present known-plaintext attack as the other end of a time-data trade-off. This insight not only solidifies our understanding of CRAFT's fundamental vulnerabilities but also demonstrates the profound implications of its structural design flaws across different attack paradigms and resource constraints.

Full Text

Comments

You need to be logged in to post a comment.