Can I build a secure tweakable block cipher from a normal one by adding key and tweak?

Let (E,D) be a secure block cipher.

Consider the following tweakable block cipher:

E'(k,t,x) = E( (k+t) mod |K|, x)
D'(k,t,c) = D( (k+t) mod |K|, c)


Is (E',D') secure?

-

2 Answers

Well, whether it is a secure tweakable block cipher depends on how resistant (E,D) are to related key attacks; that's not a standard assumption for block ciphers.

For example, this would not be a secure tweakable block cipher with 3DES; because every 8th bit is ignored, the attacker can effectively test the value of the 7 adjacent bits (except for the 7 MSBits) by a choosen tweak attack. For example, if he can find a value t with (for an arbitrary block x):

E'(k,t,x) = E'(k,t+256,x)
E'(k,t+2,x) != E'(k,t+258,x)


then he can deduce that the addition of k and t+258 was just enough to propagate a carry past bit 8 (which doesn't affect the operation of 3DES) into bit 9 (which does). This allows him to immediate deduce the lowest 7 used bits of the key.

Repeating this observation for the rest of the key bits allows us to recover all but 7 bits of the key with about 400 adaptively chosen tweaks; the last 7 is easy to brute force.

-
I never understood why DES was treated as having a 64 bit key, and not a 56 bit key. – CodesInChaos Aug 30 '12 at 22:32

To expand / generalize @poncho's reply, given a block cipher $(E,D)$ with keylength $n$, you can make a new one $(E',D')$ with key length $n+1$, which ignores the last bit of the key and just runs $(E,D)$. If $(E,D)$ is a secure PRP, then so is $(E',D')$. But plugging $(E',D')$ into the OP's construction does not yield a secure tweakable block cipher. To see this, ask for encryptions of the same block under tweaks 0, 1, and 2. Two of the three resulting blocks will be identical (depending on whether the secret key was chosen to be even or odd), whereas they should all look independently random. So the construction requires more than just standard [s]PRP security of the underlying block cipher.

Note that the construction you suggest $E'(k,t,x) = E( (k+t) \bmod |K|, x)$ is a special case of a related-key secure PRP (see A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications by Bellare & Kohno). In their terminology, you are asking for the block cipher to be secure against a group-induced key relation -- in this case, the group operation is addition mod $N$. Some PRPs were shown secure against these kinds of attacks in two papers (Pseudorandom Functions and Permutations Provably Secure Against Related-Key Attacks by Bellare & Cash, Fast Cryptographic Primitives Based on the Hardness of Decoding Random Linear Codes by Applebaum). Neither of these uses addition mod N as the underlying group operation, I think. Instead they use the group operation in a DDH group and XOR.

-