1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – fgrieu Feb 9 at 17:35
  • $\begingroup$ I do get part 1, thanks to you and crypto.stackexchange.com/questions/41450/…. $\endgroup$ – Alejandro Feb 10 at 2:09
  • $\begingroup$ Now could you help me a little bit more with part 2? Why are you working with powers of 2? $\endgroup$ – Alejandro Feb 10 at 2:11
1
+50
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Not sure if I am correct about this, but let me give it my best.

  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.

It seems that the problem assumes that all numbers are written as 20-digit nature numbers. So for the number 45 you might have '00000000000000000045'. This keeps all of your numbers in the same size and format. It also means that the output space is quite large (10^20).

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

Well, the attacker doesn't know the values of the input numbers (and the input coupon numbers don't necessarily need to be 0 through 9,999, rather, they can be any 10,000 numbers in the space. So that means that the attacker will likely have to try a random input number and then check with the server if the coupon has value. As there are 10,000 valid coupons (10^4) and a space of 10^20, we can simply divide to get 10^4/10^20. So 1/10^16 chance of hitting a valid coupon code.

Hope that answers your questions.

| improve this answer | |
$\endgroup$

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.