2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Erratum: In place of "subblock[j+1 mod m]" please read "subblock[(j mod m) +1]". Sorry. $\endgroup$ – Mok-Kong Shen Feb 21 '16 at 11:14
  • $\begingroup$ The scheme could apparently be useful if a current secure block cipher at a future timepoint becomes insufficiently secure due to growth of adversary's computing power (including the case when the dream of quantum computing comes true), since it could obviate the necessity (or at least urgent necessity) of a new design of block cipher in response. $\endgroup$ – Mok-Kong Shen Feb 23 '16 at 8:38
2
$\begingroup$

Parallel construction

enter image description here 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). enter image description here


$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.

enter image description here

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)

enter image description here

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.

$\endgroup$
  • $\begingroup$ Why is it useful? Full-Disk-Encryption which uses "poor man's authentication" relies on large block ciphers. There are also some nice applications (where collision resistance is required) for large blocksize blockciphers. $\endgroup$ – SEJPM Feb 19 '16 at 19:18
  • $\begingroup$ @Biv: I do mean what you wrote in your last paragraph. I don't understand why there wouldn't be a gain in security, since a double lengthed key is involved (that affects at least bruteforcing). $\endgroup$ – Mok-Kong Shen Feb 20 '16 at 10:03
  • $\begingroup$ Actually, your $m$-blocks Feistel construction doesn't give full diffusion until you hit $m$ rounds; it works fine in the encrypt direction, but consider how it handles a one-word delta in the decrypt direction... $\endgroup$ – poncho Jul 26 '16 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.