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

HFFH (WBC)

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

This mode has the following properties:

This mode is reasonably efficient given all of the features that it offers; but still, it requires two read passes plus one write pass over the data.

FFH (RIV)

What happens if we strip off the first round? We lose the optimal expansion property and keep the resistance against the release of unverified plaintext. We obtain RIV mode.

Note that because we cannot trust the left branch in the encipherment direction, it must be fixed to 0s and in fact becomes the authentication tag on the output side. The amortized costs of the WBC and RIV modes are identical, and because we lose the optimal expansion property in RIV mode, I tend to recommend just using WBC instead.

FF (SIV)

What happens if we strip off the last round as well? We lose resistance against the release of unverified plaintext. Instead, the right branch can no longer be trusted in the decipherment direction. We obtain SIV mode.

The decipher oracle must validate redundancy in the left branch before releasing any plaintext, which simply means it must validate the tag.

HFF (SIV-Plus?)

Observant readers may have noticed that there is one more combination we haven't tried. What if we had stripped off the last round as opposed to the first round of the wide block cipher mode? We'd lose resistance against the release of unverified plaintext but keep the optimal expansion property.

Note that because this mode does not provide resistance against the release of unverified plaintext, the decipher oracle requires access to verifiable redundancy. In fact, the verifiable redundancy must be present in the left branch: because we stripped off the last round, we can not trust the contents of the right branch in the decipherment direction. Note that I intentionally made the left branch one block in width to maximize performance; in fact, this mode performs only one read pass plus one write pass over the data, making its amortized cost identical to SIV mode!

Conclusion

To summarize the features offered by each mode:

Mode Nonce reuse resistance Optimal expansion RUP resistance Passes
FF 1R+1W
HFF 1R+1W
FFH 2R+1W
HFFH 2R+1W

The first H-round protects the left branch against chosen plaintext attacks (CPA), and the last H-round protects the right branch against chosen ciphertext attacks (CCA). By protecting the left branch against CPA, we gain the feature of optimal expansion. By protecting the right branch against CCA, we gain the feature of resistance against the release of unverified plaintext. This line of reasoning also nicely explains why we're able to get away with using a differentially uniform function that outputs only a single block for the first and last rounds; the purpose of the outer two rounds is different than the inner two rounds.