Doubling the block length of a given block cipher

Question

IMHO the main essence of a Feistel cipher of block length $n$ is the working of a non-linear function $F$ that is applied to the two halves of the block of length $n/2$.

Now suppose a certain block cipher of block length $n$ as well as two keys of it are given. If one employs the given block cipher in the sense of $F$ on each half of a larger block of length $2n$ in parallel (actually invoked alternatingly with the two keys) for a number of rounds, one obtains evidently a new block cipher of Feistel genre having doubled block length and requiring a doubled key length.

Could anything in general be said on the security (or insecurity) of such a scheme?

---

It may be of interest to also examine the special case where the two keys are identical.

The scheme can be trivially generalized to achieve a block length of the larger cipher of $m \times n$ where $m \geq 2$ operating on $m$ subblocks of length $n$ as follows, with $E(K,P)$ denoting the given block cipher and $K[*]$ denoting the array of the keys:

for i in [1 .. number_of_rounds] do

    for j in [1 .. m] do

        subblock[j+1 mod m] ^= E(K[j],subblock[j])

Note that, in case $m$ is not fixed but the plaintext length is $m \times n$ (and there is one or more keys) one obtains a special kind of block chaining with the given block cipher.

Certainly there is an efficiency issue that needs to be examined for practical applications of the scheme.

Answer 1

Parallel construction

Then my first feeling is that you wouldn't lose that much in security however there are several drawbacks.

1. you would be basically having a kind of ECB inside your $2n$-block-cipher.

2. you do not have a full diffusion on your $2n$-block-cipher : if you change a bit in the first part, only that part is modified (orange diffusion on red).

---

$2n$-Feistel construction

However if you meant to use that $n$-block-cipher as $F$ in your Feistel $2n$-block-cipher, then you will have to make a sufficient number of rounds (at least 4 to get full diffusion : see p. 41). Therefore compared to a parallel CTR encryption method just using that $n$-block-cipher, you are 4 times slower and you don't really have a gain in security in term of key as the space is the same.

Your idea is this : given a $n$-bit block cipher, one can construct a $2n$ bit block cipher using a Feistel construction. More over you want to use 2 keys in order to increase the security margin.

Given enough rounds (at least 4), I can't see any security hole in that construction (but I'm not a cryptographer yet).

---

$m$-blocks Feistel construction ($m \times n$ bits-block-cipher)

for i in [1 .. number_of_rounds] do
    for j in [1 .. m] do
        subblock[j+1 mod m] ^= E(K[j],subblock[j])

This construction can be displayed as such (e.g. with 5 blocks, 2 rounds)

In order to get a full diffusion you need a strict minimum of 2 rounds. However this is the same as using the $n$-cipher as a keyed $S-box$. By the way, the more blocks you add, the closer you are to a SPN.