Is this the correct procedure for cycle walking using an FPE?

Question

To encrypt a value from a set (say a range of years from 1001 to 2001)

1. Rank the set

   {0 = 1001, 1 = 1002, 2 = 1003...999 = 2001}

2. Take the value you want to encrypt from the set (year = 1995) and determine the ranked value = 996

3. convert this to binary 996 = 1111100100

4. Encrypt binary value using FPE(1111100100) = En where n is the iteration

5. If En lands outside desired maximum of 999, take En and encrypt again FPE(En) = En+1

6. Stop when En+1 is inside range 0 - 999, else repeat step 5

Questions,

1. Is this the correct way to perform cycle walking using any FPE?

2. What is the smallest probability of landing outside the desired range? What is the largest?

Note: In my case I'm using BPS as my FPE which has the restriction of at least two 'characters' as input so for binary number the smallest input values possible would be 00, 01, 10, or 11. In decimal this is 0, 1, 2, 3. Therefore the smallest range you can create from these values is 0 - 1. So the probability of landing outside those two values would be 50%. Is this correct?

Would 50% be the max probability of landing outside the smallest range - with the probability getting smaller as the range increases?

Answer 1

Yes, what you're describing is the correct way to cycle walk with FPE.

In your case, the value you're encrypting is ten bits, so the largest possible ciphertext is 1024. You'll only need to cycle walk if the ciphertext is from 1000-1024, so 24 of the possible 1024 values will cause an iteration. This means your probability of cycle walking for any particular value is $\frac{24}{1024} \approx \frac{1}{40}$, which is pretty small.