Adding tweak to a block cipher

Question

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?

Answer 1

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.

Answer 2

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.