1

I am trying to implement an FPE for a 19-digit long number. I am trying to follow the lecture of Prof. Dan Boneh and here is how I understand it:

  1. Get the nearest power of two greater than $10^{19} \rightarrow 2^{64}$,
  2. Get the binary representation of the 19-digit number,
  3. Split the 64-bit long binary representation into two 32-bit for Feistel network,

  4. Perform 7 rounds of Feistel network with AES (PRF),

    • pad zeroes to left of 32-bit until 128 bits for AES,
    • truncate cipherText obtained to the 32 Least significant bits for Feistel XOR and next rounds,

  5. Convert the output of the Feistel network to Decimal and check if it is in the range of $0 - 10^{19}$ (some values are between $10^{19}$ and $2^{64}$), if not perform Feistel on the cipher text until it is within the range.

I am trying to do pad-encrypt-truncate for step 4 but I was not able to recover the plaintext from the truncated ciphertext. I am doing these decrypt steps right now:

  1. Pad zeroes to the left of the 32-bit ciphertext (truncated) until 128-bits,
  2. Decrypt using AES,
  3. Truncate to Least Significant 32 bits (this is different from the ciphertext).
e-sushi
  • 17,891
  • 12
  • 83
  • 229
Frank Smith
  • 111
  • 2
  • Truncation is not reversible. These truncated values are only used in the Feistel network. The feistel network ensures reversibility even when using a non reversible function. – CodesInChaos Aug 20 '14 at 12:12
  • 2
    You might want to take a look at FFX mode which uses a pretty similar principl. – CodesInChaos Aug 20 '14 at 12:14
  • Thanks for the info. I'll look into FFX later. For now, how should I implement the decryption algo for the FPE I used above? I am still trying to learn the basic :D – Frank Smith Aug 20 '14 at 12:21
  • Read the Feistel network article I linked. – CodesInChaos Aug 20 '14 at 12:23
  • Thanks!! I missed the definition of function F... I'm just wondering for step 5, if I need to find a ciphertext within a specific range, since i will be using the same function F for encrypt and decrypt in feistel, is there a big chance that I may end up with the original plain text? how should i avoid this if it do? – Frank Smith Aug 20 '14 at 12:56
  • Ending up with the ciphertext equaling the plaintext is not a problem. The probability for that is 1 in 10^19. – CodesInChaos Aug 20 '14 at 12:57
  • oks thanks again!! what a shame i do not have enough reputation to vote up your answers – Frank Smith Aug 20 '14 at 13:07
  • Two comments: for a Feistel cipher, you need to make each round function different (say, stir in the round index as an input to AES); otherwise, you open yourself up to slide attacks. Also, step 5 says "if the ciphertext is not in range, keep on doing Feistel until it is". Actually, to be able to decrypt unambiguously, you need to rerun the entire encryption procedure (including all 7 rounds). – poncho Aug 20 '14 at 13:49
  • will changing the key for AES of each round suffice? for step 5 i am actually doing the step 1 to 4 for the ciphertext – Frank Smith Aug 20 '14 at 14:12
  • 1
    Yes, changing the AES key round would suffice, but (IMHO) is more heavy weight than you need. Instead, I would suggest you put the round index into the (currently zero) padding you use to pad out the 32-bit into a full 128 bits. – poncho Aug 20 '14 at 15:52
  • I've removed the Java code from the comments, showing how to perform ECB mode of encryption is not really useful. – Maarten Bodewes Aug 20 '14 at 16:27
  • Why are you decrypting using AES ? AES_decrypt is never needed ! may be that is the reason you are not able to recover, share the code on pastebin.com or so , its easier that way for us to tell – sashank Oct 23 '14 at 15:29
  • In case your work is done, can you share the source code? – hola Sep 29 '18 at 15:29

1 Answers1

1

In the decrypting steps use AES_encrypt itself instead of AES_decrypt, AES decrypt is never needed.

Remember while encrypting, AES_encrypt is only used as a Pseudo Random Function, we don't really need AES_decrypt method even in decrypting phase. This might seem little confusing at first but not needed. Please check the proof given for this answer

Community
  • 1
sashank
  • 6,174
  • 4
  • 32
  • 67