Using AES for smaller blocks in a Feistel network

Question

I was wondering how decryption would work for FPE in the case of cycled Feistel ciphers. I understand that simply reiterating through the networks with reversed key order will generate the ciphertext inputted at the beginning of the network.

The ciphertext is a bit representation of some number, so I'm just expanding the number to search for correct length before stopping.

However, the question that I have is that I am using AES as my round function. However, I need significant padding (0s), as the AES block size is 128 and the block size (of each half) is significantly smaller at 10-30 bits. I am simply appending these 0s to the end of my string, then using AES to get an encrypted 128 bit output.

At this point, I am not too sure what to do. I truncate by removing the last ~100 bits and only taking the beginning of the string. However, this seems to me as if I am losing data, and I cannot understand how I would be able to decrypt using this same method.

Is this simple method of truncating actually the correct way of implementing AES for smaller blocks, or should I be padding/truncating in a different way? Also, if it is correct, could someone explain why it is or link me to some relevant literature?

Cheers!

I have seen the related link Recover plaintext from truncated ciphertext using AES for FPE , but I either don't understand the comments or a solution was never posted.

Answer 1

In a Feistel network you can use ANY function and it will be invertible. Of course, in order to get security you need the function to fulfill some property. One of the main reasons to use a Feistel network is to get a pseudorandom permutation. For this to work, you need 3 or 4 rounds of Feistel with a pseudorandom function (with tweaks or independent keys at each round). Now, truncated AES is a pseudorandom function (and a very efficient one) so this is a good idea. You can pad with zeroes as you said, but you MUST also add the round number into the padding (this is the "tweak"), or alternatively use a different key in each round. The latter option is much less efficient since you need to run the AES key schedule multiple times. The use of the round function essentially guarantees a "computationally independent" pseudorandom function in each round (and so essentially the same as using a different key in each round).

In order to see that it works, just draw it and trace the decryption. The magic of Feistel is that you don't need to invert the round function in order to decrypt.