# Format Preserving Encyption question

I've got a theorical question from an exercise. Here it is:

--- Exercise beginning ---

There are ways to convert a block cypher onto an FPE. One of them is the following:

Let $$E_{k}$$ a cryptographic primitive with size n.

$$FPE_k(x)$$ a cryptographic primitive with $$P = C = {0,1,..., m-1}$$ with $$m < 2^n$$

The pseudo-code looks like this

fpe = x
do {
x = fpe
fpe = Ek(x)
} while(fpe >= m)


It could be interesting to use this functions to create cupon codes. For example, if we consider cupons as numbers of 20 digits, we could generate 10000 cupons encoding numbers from 0 to 9999.

--- Exercise ending ---

Now my questions are:

1) I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings? As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.

2) The exercise asks what is the probability of an attacker to generate a valid cupon?

• Hint: for 1: the exercise is about generating 10000 distinct random-looking integers in $[0\ldots10^{20})$.The proposed method is to construct a pseudo-random permutation of this interval using the algorithm FPEk, and generate the desired integers as the image by that mapping of the interval $[0\ldots10^4)$. For 2: It can be shown that if the adversary can not distinguish Ek from a random permutation of $[0\ldots2^k)$ then s/he can not distinguish FPEk from a random permutation of $[0\ldots m)$.
– fgrieu
Feb 9 '20 at 17:35
• I do get part 1, thanks to you and crypto.stackexchange.com/questions/41450/…. Feb 10 '20 at 2:09
• Now could you help me a little bit more with part 2? Why are you working with powers of 2? Feb 10 '20 at 2:11

The questions you're getting confused by are, indeed, confusing, but I think I figured out what's going on. Imagine a scenario where:

1. A company want to issue exactly 10,000 numbered coupons;
2. They are concerned that malicious parties will forge coupons.

So they can't just naïvely number the coupons from 0 to 9999; instead, they wish to use some numbering code that makes it easy for them to detect forged numbers. So they have chosen to do this by assigning pseudorandom 20-digit codes generated by applying FPE to the "internal" coupon numbers 0 to 9999.

Now, seen in this (conjectural) light, your questions:

1) I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings? As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.

The idea is they'd apply 20-digit FPE to the "internal" coupon numbers, but they wouldn't use the whole input value range, but rather artificially restrict input values from 0 to 9999.

2) The exercise asks what is the probability of an attacker to generate a valid cupon?

The idea here is that an attacker who tries to forge a 20-digit coupon number, if they just naïvely pick any 20-digit code, is unlikely to pick one that decrypts to the 0 to 9999 range that the issuer uses internally, and that way they defender can recognize forgeries. The probability that a randomly chosen 20-digit code will be one of the 10,000 valid ones is one in $$10^4 / 10^{20} = 10^{-16}$$. Note the attacker gets to make more guesses their chances get better not just because they make more guesses but because this is a permutation.