# Adding tweak to a block cipher

I know there are XEX, XTS and other ways to add tweak to block cipher without modifying cipher itself. However they are quite slow and/or complex.

If we assume we have a secure block cipher round function (like AES) with pseudo-independent round keys (generated with stream cipher). Is it safe to add tweak with same size as block directly (and same value every round) into round function the same way as round keys?

$F()$ = round function
$b$ = block
$k_r$ = round key (same size as block)
$t$ = tweak (same size as block)

$b = F(b)$
$b = b \oplus k_r \oplus t$

How strong tweak schedule should be?

• "Threefish has very simple tweak schedule, but it also has very simple and weak key schedule." <citation needed> Oct 14, 2014 at 0:38
• @LightBit Correlating "simple" with "weak" is a mistake unless you have references to back up the claim for the Threefish key schedule being vulnerable to attacks. I think this is what owlstead was referring to. Oct 14, 2014 at 6:39
• (besides, the Skein designers had incentive to keep the Threefish key schedule as simple as possible - it needs to be run for every compression function invocation of the hash function, and the Threefish permutation itself is already not that expensive relative to its key schedule) Oct 14, 2014 at 6:46
• I believe the TWEAKEY framework by Jean et al. eprint.iacr.org/2014/831 analyzes constructions similar to what you're describing. Jun 6, 2015 at 15:08

## 2 Answers

To emphasize that this isn't a generically good construction, we can show that AES with that tweak method is insecure (!).

This observation is based on a simple 1 round differential characteristic; it starts off with a differential in one of the bytes, and a carefully chosen differential in the tweak. With this initial differential, after the AddRoundKey and the SubBytes operation, the differential will be some nonzero $\delta$ in the active byte (and 0 elsewhere). If $\delta$ is a known constant, then after the ShiftRows and MixCollumn operations, there will be a known differential. At this point, we add in the tweak; we set our tweak differential to zero out the known differential within the cipher state, and reintroduce a delta into our active byte. We assume the same $\delta$ for each round, and hence the same differential in the tweak is appropriate.

This characteristic will hold if the differential after the sbox is our chosen constant after each round (at least, after each of the first 9 rounds for AES-128; the differential becomes detectable after the 10th round even if the $\delta$ there isn't what we expect). There are differentials through the sbox that hold with probability $2^{-6}$ (such as an initial 0x01 differential becoming a 0x1f differential after the sbox). THence we have an overall differential through tweaked AES-128 with probability $2^{-54}$.

The reason this sort of attack doesn't work against AES is that there is no way to prevent the differential after 1 round from spreading throughout the cipherstate in the next round; adding the tweak allows the attacker to keep it contained.

• Wouldn't this require same round key every round? Sep 5, 2021 at 18:34
• @LightBit: I assume you mean 'the same subkey every round' - no, it doesn't. For a specific round, the differential in the subkey will be the same (because that's injected by the tweak); the actual setting of the subkey is unimportant (and so it doesn't matter that the subkey values change each round) Sep 5, 2021 at 19:14
• Would rotating tweak bytes every round make this harder? Sep 5, 2021 at 20:30
• @LightBit: it would certainly make it less straight-forward; however you'd need to make sure that sure that there aren't more subtle approaches as well. Sep 5, 2021 at 21:15

This construction isn't generically secure, you need to analyze it for each blockcipher you want to use it with to see if it's secure.

For example, consider a block cipher that simply xors the key into the state between rounds. In that case your construction is equivalent to xoring the tweak into the key. This has several consequences:

• Since we generally assume related and attacker controlled tweaks, this exposes the blockcipher to related key attacks. There are blockciphers which are secure with random keys, but not related keys (e.g. AES)
• It enables multi-target attacks, with each tweak acting as a separate target. For example if the attacker sees a 4TiB of known plaintext, that corresponds to $2^{42-4}$ 128 bit blocks, reducing the security level of a 128 bit cipher to 90 bits.

Even if there is no direct interference between the cipher's key schedule and the tweak, the tweak gives an attacker more influence over what happens inside the cipher (assuming random keys but attacker controlled plaintext/ciphertext/tweak). To compensate for that, you need to increase the number of rounds, decreasing performance.

=> This construction might be worth a consideration when designing a new tweakable blockcipher to replace AES, but it's not something you should simply add to an existing cipher, like you can with XTS and similar constructions.