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

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.