How can you make an invertible function out of non-invertable parts? Why would you want to?
Encryption functions must be invertible. If the intended recipient can’t decrypt the message then the encryption method is useless.
Of course you want an encryption function to be really hard to invert without the key. It’s hard to think all at once of a function that’s really hard to invert. It’s easier to think of small components that are kinda hard to invert. Ideally you can iterate steps that are kinda hard to invert and create a composite that’s really hard to invert.
So how do we come up with components that are kinda hard to invert? One way is to make small components that are non-linear, and that are in fact impossible to invert [1]. But how can you use functions that are impossible to invert to create functions that are possible to invert? It doesn’t seem like this could be done, but it can. Feistel networks, named after cryptographer Horst Feistel, provide a framework for doing just that.
Many block encryption schemes are based on a Feistel network or a modified Feistel network: DES, Lucifer, GOST, Blowfish, LOKI, etc.
The basic idea of Feistel networks is so simple that it may go by too fast the first time you see it.
You take a block of an even number of bits and split it into two sub-blocks, the left half L and the right half R. The nth round of a Feistel cipher creates new left and right blocks from the left and right blocks of the previous round by
Here ⊕ is bitwise XOR (exclusive or) and f(Rn−1, Kn) is any function of the previous right sub-block and the key for the nth round. The function f need not be invertible. It could be a hash function. It could even be a constant, crushing all input down to a single value. It is one of the non-invertible parts that the system is made of.
Why is this invertible? Suppose you have Ln and Rn. How could you recover Ln−1 and Rn−1?
Recovering Rn-1 is trivial: it’s just Ln. How do you recover Ln−1? You know Rn-1 and the key Kn and so you can compute
The main idea is that XOR is its own inverse. No matter what f(Rn-1, Kn) is, if you XOR it with anything twice, you get that thing back.
At each round, only one sub-block from the previous round is encrypted. But since the roles of left and right alternate each time, the block that was left alone at one round will be encrypted the next round.
When you apply several rounds of a Feistel network, the output of the last round is the encrypted block. To decrypt the block, the receiver reverses each of the rounds in the reverse order.
A sketch of DES
The DES (Data Encryption Standard) algorithm may be the best-known application of Feistel networks. It operates on 64-bit blocks of data and carries out 16 rounds. It takes a 56-bit key [2] and derives from it different 48-bit keys for each of the 16 rounds. In the context of DES, the function f described above takes 32 bits of data and a 48-bit key and returns 32 bits. This function has four steps.
- Expand the 32 bits of input to 48 bits by duplicating some of the bits.
- XOR with the key for that round.
- Divide the 48 bits into eight groups of 6 bits and apply an S box to each group.
- Permute the result.
The S boxes are nonlinear functions that map 6 bits to 4 bits. The criteria for designing the S boxes was classified when DES became a standard, and there was speculation that the NSA has tweaked the boxes to make them less secure. In fact, the NSA tweaked the boxes to make them more secure. The S boxes were modified to make them more resistant to differential cryptanalysis, a technique that was not publicly known at the time.
More cryptography posts
[1] These functions are impossible to invert in the sense that two inputs may correspond to the same output; there’s no unique inverse. But they’re also computationally difficult to invert relative to their size: for a given output, it’s time consuming to find any or all corresponding inputs.
[2] When DES was designed in the 1970’s researchers objected that 56-bit keys were too small. That’s certainly the case now, and so DES is no longer secure. DES lives on as a component of Triple DES, which uses three 56-bit keys to produce 112-bit security. (Triple DES does not give 168 bits of security because it is vulnerable to a kind of meet-in-the-middle attack.)
A recent Computerphile video on Feistel networks:
https://www.youtube.com/watch?v=FGhj3CGxl8I
It seems to me that a more natural way to express this process would be as a kind of twisted Fibonacci sequence:
R_(n+1) = R_(n-1) + F(R_n, K_n)
where each R_n is a vector over Z_2.
When expressed this way, the symmetry of the process becomes fairly obvious, since you can just solve the equation for R_(n-1). Also, you could easily generalize it to moduli other than 2, if you wanted.
One application of Feistel networks that isn’t cryptographyc is to construct invertible hash functions.
This is occasionally useful, for example, for implementing succinct hashing on integers.