3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Rup
    Jul 2, 2017 at 1:57
  • 2
    $\begingroup$ @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. $\endgroup$
    – Daffy
    Jul 2, 2017 at 2:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – pg1989
    Jul 2, 2017 at 20:32

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.