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.

Wide block cipher (WBC)

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

Feistel

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.

Robust IV (RIV)

What happens if we strip off the first round? We keep the resistance against the release of unverified plaintext but at the cost of requiring 2s explicit redundancy. We obtain RIV mode.

Feistel

Note that because we cannot trust the right 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 have 2s explicit redundancy in RIV mode, I tend to recommend just using WBC instead.

Synthetic IV (SIV)

What happens if we strip off the last round as well? We lose resistance against the release of unverified plaintext. Instead, the left branch can no longer be trusted in the decipherment direction. We obtain the nonce reuse resistant mode described prior, sometimes also referred to as SIV mode.

Feistel

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

Synthetic IV+ (SIV+)

Observant readers will 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 "no explicit redundancy" property.

Feistel

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 cannot 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!

Nonce-based WBC (nWBC)

All of the modes covered thus far have built-in resistance against nonce reuse. For completeness, we now perform the exercise of imposing a nonce requirement on each mode to see if we arrive at something novel.

Let's apply the nonce requirement to WBC. Thanks to the nonce, the first round is no longer necessary.

Feistel

The interesting thing about this mode is that it performs only one read pass plus one write pass over the data, and yet it inherits important properties from WBC: resistance against RUP and no explicit redundancy. Another interesting thing is that its encipher oracle is isomorphic to the decipher oracle of SIV+, and vice versa. The cost is that it requires a nonce in the tweak W or the left branch PL.

Conclusion

To summarize the features offered by each mode, including SANE for completeness:

Mode Nonce reuse resistance Explicit redundancy RUP resistance Passes
WBC 2R+1W
RIV 2s 2R+1W
SIV 2s 1R+1W
SIV+ 1R+1W
nWBC 1R+1W
SANE s (Not needed) 1R+1W

The first round protects the left branch against chosen plaintext attacks (CPA), and the last round protects the right branch against chosen ciphertext attacks (CCA). By protecting the left branch against CPA, we gain the feature of less explicit redundancy. 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 output only a single block for the first and last rounds; the purpose of the outer two rounds is different than the inner two rounds.