# Interleaving bytes to make an effectively larger block size

Will applying a 16 byte bit block cipher such as AES over a 256 byte block to in the following way result in a much stronger cipher:-

• Apply block cipher with first key digest to each 16 byte group.

• Then interleave the bytes. I.E. Place the bytes horizontally into a 2D (16 times 16) byte array and then remove the bytes vertically so that each new 16 byte group now has one byte of each of the old 16 byte groups.

• Then apply block cipher with second key digest.

• Then interleave.

• Then apply block cipher with third key digest.

-
"key digest" $\: \mapsto \:$ "part of the key" $\;\;\;$ ? $\;\;\;\;\;\;\;$ –  Ricky Demer Aug 5 at 5:43
My intuition is that enough rounds of this should be secure, but that you'll need more than 3 rounds. –  CodesInChaos Aug 5 at 8:27
Looks very similar to the way the block-cipher underlying BLAKE works (it uses a 4x4 matrix of 32/64 bit words, not a 16x16 matrix of 8 bit words), so I believe it's possible to construct a secure cipher that way. But BLAKE has about 20 cheap rounds, not 3 expensive rounds. I have doubts that 3 rounds are enough, even with a secure PRP as building block. –  CodesInChaos Aug 5 at 9:38
There are simple techniques to construct wide PRPs which are much faster than this and provably secure (reducing to the security of AES). So there is no reason to use your construction in practice. –  CodesInChaos Aug 5 at 9:39
What is the meaning of "much stronger cipher" in this context? Do you get a PRP over a larger blocksize? Yes, kinda. Is it harder to break? That's a tricky question. If there is no efficient attack on AES and brute force is not applicable, then we are already at the limit. And any fundamental attack against AES would break this too. Is it efficient? Ewk, no. Applying the original scheme three times on every value is two times too often. –  tylo Aug 5 at 11:03

Alternative 1, Interleave = ShiftRows

• Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
• Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
• AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
• Interleave so that $c_{16i+j} = b_{16(i+j)+j \bmod 256}$

The problem here is that if $A_i = A_j$ for all $0 \le i, j \lt 16$, then $C_i = C_j$ for all $0 \le i, j \lt 16$. This equality will propagate through all three rounds, making it easy to distinguish your 2048-bit composite function from a random 2048-bit permutation with only a single query.

Clearly, if $A_i = A_j$, then $E_{K_0}(A_i) = E_{K_0}(A_j) = B_i = B_j$. This means that $b_{16i+k} = b_{16j+k}$ for all $0 \le k \lt 16$. If this relation holds for all $0 \le i, j \lt 16$ then, for each $0 \le k \lt 16$, $b_{16i + k} = b_{16j + k}$ for all $0 \le i,j \lt 16$.

In particular, $b_{16i+j} = b_{16(i+j)+j \bmod 256}$.

In other words, if $A_i = A_j$ for all $0 \le i, j \lt 16$, then the interleave step will be the identity function. The composite function will for such inputs only consist of three consecutive AES-ECB operations.

Alternative 2, Interleave = Transpose

1. Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
2. Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
3. Round = 0
4. AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
5. If round = 2, exit
6. Interleave so that $c_{16i+j} = b_{16j+i}$
7. round = round + 1, $A = C$ jump to step 4.

In this case, if $A_i = A_j$ for all $0 \le i,j \lt 16$, then, in the first round = 0, $c_{16i+j} = c_{16i + k}$ for all $0 \le i,j,k \lt 16$. This means that after the second round = 1, there are only $2^8$ different values for the $B_i$ blocks.

Hence, find two 128 bit values $A$ and $A'$ such that $E_{K_0}(A) = b_0..b_{15}$ and $E_{K_0}(A') = b'_0..b'_{15}$ differ only in a single byte $b_i \neq b'_i$, and such that $E_{K_1}(b_i..b_i) = c_0..c_{15}$ and $E_{K_1}(b'_i..b'_i) = c'_0..c'_{15}$ are equal in two different byte positions $c_j = c'_j$ and $c_k = c'_k$. If this happens, the two inputs to the composite function that consist in sequences of $A$ and $A'$ respectively, will result in two output, such that both the $j$th blocks and the $k$th blocks are identical. The probability two random 128 bit blocks will have this relation is $\frac{16}{2^{8\times15}}\times\frac{16\times15}{2^{8\times2}}$, which is significantly greater than the probability that you would get the same relation between the corresponding outputs of a 2048 bit pseudo random permutation, and great enough to expect to get such a relation after only $2^{64}$ attempts.

-
I don't follow your argument and can't see how a symmetry would propagate through enough rounds. –  CodesInChaos Aug 5 at 8:25
I'm reading the interleaving function differently from you. I think it's supposed to be a matrix transposition, i.e. $c_{16i+j} = b_{16j+i}$. –  CodesInChaos Aug 5 at 9:28
If by "interleaving" you mean transposing, please see the second case in my answer. Your function has approximately the same collision rate as CBC mode or CFB mode under CPA, but at the expense of three AES invocations per 128 bits, instead of just one. –  Henrick Hellström Aug 7 at 7:57
@CodesInChaos: Yes that is what I mean by interleaving, which is Henrick's alternative 2. Im trying to comprehend the weakness he describes, though. –  Stephen Braithwaite Aug 7 at 7:58