How can AES + cycle walking be used as an FPE?

Question

I'm a bit confused after reading several articles that seem to provide conflicting information. Basically I was wondering if AES by itself can be used as an FPE? And if so is this something computationally prohibitive, or something reasonable to do. Furthermore how can we use AES by itself + cycle walking?

According to this paper it says one of the methods for FPE is

5.2 Cycle walking Method "The cycle walking works by encrypting the plaintext by repeatedly applying AES or 3DES until the cipher text becomes in acceptable range. The duration for ciphering is not deterministic. "

If this is the case, what is the general construct for this (I.e. how to set up your AES encryptor, key, IV, mode etc)

In that paper they also have a table that summarizes the speed of this method compared to others.

But in another article it is stated that it would be prohibitively expensive to use cyclewalking alone since it would take many iterations to get a value in the desired range.

"So, why can't we just use cycle-walking? Because it only works well if the block size is approximately right—if the size of the valid set is a lot smaller than the block size of the cipher, then you have to do a lot of iterations in order to get an in-range result. So, you can't use a 64-bit block cipher in order to encrypt an SSN because you end up having to do a prohibitive number if iterations; you need to use L-R to construct a block cipher of approximately the right size and then use cycle-walking to shave off the last few values."

I'm not sure if the result 1500 milliseconds in the comparison table above is considered prohibitive or not for such an encryption scheme.

Answer 1

The general construction to encrypt (inputs of less than 128 bits) with cycle-walking is:

# IN, OUT are 128-bit unsigned integers in the range 0..MAX
OUT = AES(K, IN)
while OUT > MAX do OUT = AES(K, OUT)
return OUT

AES is going to permute your 128-bit input into a seemingly-random 128-bit output. About $1/2$ of the time the top bit of the output will be 0. About $1/4$ of the time the top 2 bits will both be 0. About $1/(2^n)$ of the time the top n bits will all be zero.

The construction above keeps looping until your output is coincidentally in the desired range. This is non-deterministic: it could happen on the first iteration, or on the billionth. Statistically it is likely to happen, on average, around iteration $2^{128}/{MAX}$.

If your MAX is close to $2^{128}$ then cycle walking can produce an efficient FPE solution. But if your MAX is small - say a 9 digit account number ($MAX = 10^9$, which is close to $2^{30}$) then you can expect $2^{98}$ iterations to perform one FPE encryption. That's harder than brute-forcing 2-key TDES, and clearly in the territory of 'prohibitive'.