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, 2017 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. Jul 2, 2017 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. Jul 2, 2017 at 20:32