2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ah, I think I get it? So if I tweak the padding then I no longer need to change keys? Also, I guess this isn't exactly relevant to this topic, but why do all the implementations of Feistel networks that I see in Java use arrays? Is there some downside to simply using strings, ints, etc.? $\endgroup$ – EL_BR_CV Jul 23 '15 at 19:55
  • $\begingroup$ Yes, if you tweak the padding you don't need to change the keys. (I don't know anything about programming so I can't help you with the other issue.) $\endgroup$ – Yehuda Lindell Jul 23 '15 at 19:58
  • $\begingroup$ Just to make sure again, when I decrypt, should I still be padding the exact same way as encryption? Or should I reverse the padding to be last round, 2nd to last round, as the tweak? $\endgroup$ – EL_BR_CV Jul 23 '15 at 20:36
  • $\begingroup$ When you decrypt it is the reverse order. $\endgroup$ – Yehuda Lindell Jul 24 '15 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.