Feistel networks

In a previous article, I showed how we can build a wide block cipher by using a Feistel network. We know that we need two read passes plus one write pass over the block to achieve a secure, general wide block cipher. But can we still achieve meaningful security by stripping away rounds and imposing limitations on the input and/or output? When framed a certain way, it becomes evident that Feistel networks can actually lead to a range of cryptographic modes, each with unique properties.

Overview

The overall flow of this article is as follows. First, we begin with the most general Feistel mode, which is WBC (wide block cipher). Then, we strip away every combination of outer round and analyze what we end up with. Below is a diagram that relates all of the modes together.

Feistel

WBC (wide block cipher)

As discussed prior, a wide block cipher can be constructed as follows:

Feistel

As long as we abide by the minimum length constraints, we achieve a general wide block cipher. Regardless of how we balance P_L and P_R, this mode requires two read passes plus one write pass over the data.

nWBC

When stripping away the first round of WBC mode, we must require that C behaves as if it were a pseudorandom function of P.

Feistel

RIV mode is a special case of this model and satisfies the PRF constraint by requiring P_R to be redundant and disallowing RUP on P_R.

Another way to satisfy the constraint is to require (K,W,P_L) to be a nonce and require redundancy in P_L. By keeping P_L short, it performs only one read pass plus one write pass over the data and allows for early rejection. One interesting observation is that its encipher oracle is isomorphic to the decipher oracle of WBCn, and vice versa.

WBCn

When stripping away the last round of WBC mode, we must require that P behaves as if it were a pseudorandom function of C.

Feistel

One way to satisfy the constraint is to require redundancy in P_R and disallow RUP. By keeping P_R short, it performs only one read pass plus one write pass over the data.

nWBCn

When stripping away both the first and last rounds of WBC mode, we must require that C behaves as if it were a pseudorandom function of P, and that P behaves as if it were a pseudorandom function of C.

Feistel

At first glance, the PRF constraints may seem unreasonable given that we only have two rounds to work with. Remarkably, there are a number of practical ways of satisfying the constraints. SIV mode is a special case of this model and satisfies the PRF constraints by requiring P_R to be redundant and disallowing RUP.

Another way to satisfy the constraints is to require (K,W,P_L) to be a nonce, require redundancy in P_R and disallow RUP. By keeping P_L short, it performs only one read pass plus one write pass over the data and allows for early rejection.