1
$\begingroup$

What is the effect on Format Preserving Encryption security if I reorder text before FPE encryption?

Take as an example Canadian postal codes (letter-digit-letter digit-letter-digit):

  • Parliment: K1A 0A6
  • Santa Claus: H0H 0H0
  • Easy to remember: A1B 2C3

Using the postal code as a base 36 number and applying FF1 (NIST 800-38g test vector AES128 key, no tweak) gives this ciphertext:

$$E_k(\mathtt{K1A0A6}_{36}) ==> U7F8BD_{36}$$

But the original format is not preserved (last character is not a number).

What is the difference effect on the security of encryption if I

  1. Group digits and characters toghether prior to encryption
  2. Reduce the base to 26 and 10 for letters and digits, respectively
  3. Apply FF1 on the two sets
  4. Re-order the ciphertext so format is preserved

Something like this:

\begin{gather} E_k(\mathtt{KAA}_{26}) ==> FDE \\ E_k(\mathtt{106}_{10}) ==> 143 \\ \end{gather}

Would end up with FF1 encrypted postal code: F1D 4E3

Improve this question
$\endgroup$
1
  • $\begingroup$ If you want to preserve the integer use radix 10 on that part. See examples of FF1 $\endgroup$
    – kelalaka
    Commented Nov 21, 2019 at 22:15

1 Answer 1

Reset to default
2
$\begingroup$

I'd strictly perform FF1 on the entire postal code. That means converting the code to a number in the range $\big[0,26\cdot10\cdot26\cdot10\cdot26\cdot10\big)$ and then encrypting, decrypting and getting it back. This is relatively simple base conversion so it should be easily done using division and remainder math.

Obviously, otherwise you may leak repetition of parts of the input. For instance, if we encrypt the first and second part separately, you may also have Sneezy's postal code, $\mathtt{H0H\space1H0}$ in there ($\mathtt{H1H\space0H1}$ was already taken by the evil witch). Now you can see that $\mathtt{H0H}$ repeats, so anybody knowing Sneezy's code will also indicate the first part of Santa's code; not good.

With many known postal codes - many of which may already be known - this means that it will become easy to quickly guess all the postal codes. If one is relatively unique then it clearly indicates a rather sparsely populated part of the country.

Other schemes - like the one you are proposing - may have similar issues, it kind of depends on how the postal codes are generated. By converting the entire postal code to a number issues such as these can be avoided.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So with b = 26^3*10^3, I would convert to base b, encrypt, and convert back to base b to get the encrypted value in the right "human readable" or "format preserved" format. This can be extended to support arbitratry alphabets, like Quebec medicare digits that hides the birth sex in month number (+50 if female, so alphabet for first digit of month is 0,1,5,6). $\endgroup$
    – ixe013
    Commented Nov 23, 2019 at 13:50
  • $\begingroup$ Yep, that sounds about right, I think you've got the gist. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 23, 2019 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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