Understanding Meet-in-the-Middle attack on block ciphers

Question

I understand how to implement a Meet-in-the-Middle attack on 2DES/3DES, by computing for one half all possible keys and storing the outcome and then subsequently do the same for the other half but compare with the previously stored outcome to see if there is a match somewhere. Very unprecise description I know but just to state that I know how to do it for 2DES/3DES

The problem is for Feistel ciphers, where it seems that the very same technique cannot be used. Consider the below (sorry for the poor drawing):

So for a simplified example let's say the Feistel structure above operates on 16-bit blocks and uses 8-bit independant round keys. Each branch block is thus of 8 bits.The S-box is an 8-bit AES S-box.

Given that the adversary knows the following:

• Full access to the code which encrypts a 16-bit block using the Feistel above
• Knows exactly two plaintext - ciphertext pairs.

So given the two pairs, the aim is to find the key which maps the plaintext to the ciphertext.

Given the assumptions above, how is a Meet-in-the-Middle attack applied here? I've tried to use the same approach as with the 2DES/3DES, but it just doesn't apply in the same way. I'm in need of a bit of guidance on how to proceed.

I can't see where the "middle" value is, and from where I should compute forwards and backwards to reach such a middle value.

Edit: Forgot to mention that there are 4 rounds in the Feistel cipher.

Answer 1

We really only need one plaintext-ciphertext pair, but the second can be used as a way to check candidate keys.

1. Make a guess to the final subkey (ie guess all of them).
2. Decrypt the final round of your ciphertext using your key. Store this result and the subkey you used.
3. Repeat for all 2^16 candidates for the final subkey.
4. Make a guess for the first three subkeys.
5. Using these keys, go through the first three rounds of encryption of your plaintext.
6. If there is a collision between your intermediary encrypted result and your partially decrypted ciphertext, good! You (probably) found the key! You can double check using your other ciphertext/plaintext pair.

Alternatively, if you have enough storage space, you could build your storage of partially-decrypted-ciphertexts by going through the first two rounds of decryption (which are the reverse of the final two rounds of encryption). In this case, you'd bruteforce all candidates for the final two subkeys instead of just the final one. This requires storing 2^(16 * 2) partially decrypted ciphertexts, but has a speedup of 2^16.