# Does the timing of cycle-walking pose a threat?

Cycle-walking is a technique for format-preserving encryption that involves repeating an encryption process until the result is inside a desired range.

For example, given an input P, a range R, and an encryption function E.

C := E(P)
Is C in R?
yes?
Output C and quit
no?
C := E(C)
Try again


My question is, does the variable timing of this pose a threat? It isn't constant time, but the time is dependant on E(P), which in theory shouldn't be a problem.

• Is that really a useful thing? Assuming E has good properties, the expected number of cycles is going to be 2^blocksize / size of R, which is going to be impractically large in all but a very few (artificial-feeling) cases. – Rup Jul 2 '17 at 1:57
• @Rup A block cipher of an arbitrary size can be constructed from a fixed block cipher using various means, bringing the chance of a success to at least 50%. And anyway I didn't come up with this idea, I'm just asking about it's properties. – Daffy Jul 2 '17 at 2:00
• The important thing here is not the number of cycles, but rather the average cycle length. Using the OP's notation, if the domain of the original cipher $E$ is not "very much" bigger than the set $R$ the average number of iterations is small. – pg1989 Jul 2 '17 at 20:32

## 1 Answer

Your intuition is correct: the timing channel in cycle walking does not affect the pseudorandom permutation (PRP) security of a format-preserving encryption scheme built using cycle walking.

More precisely, it is possible to prove that any FPE scheme which meets PRP security in the standard sense also meets a stronger notion of PRP security in which the time taken to encrypt a point is given to the adversary. Intuitively, this is because the distribution of cycle lengths for a random permutation can be simulated given only the size of the domain. See section 9 of the original FPE paper.