Cycle walking

In cryptography, cycle walking is a method for constructing a cipher on a finite message space, such as the integers from 0 to $k - 1$ , from a block cipher whose domain is larger. A message is enciphered by repeatedly applying the block cipher, starting at the message, until one gets back to a point in the message space. The method works well if the message space is "dense" in the domain of the block cipher.^[1] It is a common solution for format-preserving encryption and building permutations of a domain.^[2]

The construction was analyzed under the name "cycle-walking cipher" by John Black and Phillip Rogaway in 2001.^[3] They noted that the Hasty Pudding cipher of Richard Schroeppel and Hilarie Orman already used essentially the same method, internally iterating the cipher until a proper domain point is reached.^[4]

Method

Fix an integer $k$ and let $M$ be the set $[0, k - 1]$ . Let $N$ be the smallest power of 2 larger than or equal to $k$ , let $n = \lg N$ , and let $E_{K}$ be an $n$ -bit block cipher under the key $K$ . The cycle-walking cipher ${C y}_{K}$ on the set $M$ is constructed by computing $t = E_{K} (m)$ and iterating if $t \notin M$ . The enciphering and deciphering algorithms are:^[3] $\begin{matrix} Algorithm {C y}_{K} (m) & Algorithm {C y}_{K}^{- 1} (c) \\ t \leftarrow E_{K} (m) & t \leftarrow E_{K}^{- 1} (c) \\ if t \in M return t & if t \in M return t \\ else return {C y}_{K} (t) & else return {C y}_{K}^{- 1} (t) \end{matrix}$

The permutation $E_{K}$ can be viewed as a family of cycles: any point $m \in M$ lies on some cycle, and repeated applications of $E_{K}$ can be viewed as a particle walking along the cycle, starting at $m$ . To encipher any point $m \in M$ , walk along the cycle containing $m$ until some point $c \in M$ is encountered. Then $c = {C y}_{K} (m)$ . This assumes that one can efficiently test for membership in $M$ . This is trivial when $M = [0, k - 1]$ , but might not be for other sets.^[3]

The map ${C y}_{K}$ is well defined: given any point $m \in M$ , if $E_{K}$ is applied enough times, a point in $M$ is reached, because walking on $m$ 's cycle must eventually arrive back at some point in $M$ , even if that point is $m$ itself. It is also invertible, since inverting ${C y}_{K} (m)$ is equivalent to walking backwards on $m$ 's cycle until finding some element in $M$ . Therefore ${C y}_{K}$ is a permutation on $M$ .^[3]

Though the method is described for the domain $[0, k - 1]$ , it works in other domains too. For example, to encipher in the multiplicative group $ℤ_{N}^{*}$ , where $N = p q$ is a 1024-bit product of two primes, one can use cycle walking, iterating in the highly unlikely event that a point is in $ℤ_{N}$ but not in $ℤ_{N}^{*}$ .^[5]

Example

Let $M = [0, 1 0^{6}]$ . Then $N = 2^{20}$ and so $n = 20$ . Some known method is used to build a 20-bit block cipher $E_{K}$ on the set $T = [0, 2^{20} - 1]$ . Suppose the point $m = 314159$ is to be enciphered. Compute $c_{1} = E_{K} (314159)$ , which yields some number in $T$ , say 1040401. Since $c_{1} \notin M$ , iterate by computing $c_{2} = E_{K} (1040401)$ , which is, say, 1729. Since $c_{2} \in M$ , output 1729 as ${C y}_{K} (314159)$ . Decipherment is simply the reverse of this procedure.^[3]

Security

Black and Rogaway's security goal is described by two games. In the first game one chooses a random key $K$ and hands an adversary an oracle for $E_{K}$ . In the second game one chooses a random permutation $π$ on $M$ and hands the adversary an oracle for $π$ . The adversary should be unable to distinguish these two types of oracle without spending a huge amount of time, even though the domain is so small that the adversary might well ask for the value of the oracle at every point.^[1] This is the notion of a pseudorandom permutation, adapted to finite message spaces.^[4]

The question arises of how much security is lost in deriving the permutation ${C y}_{K}$ . Black and Rogaway's answer is "nothing". They prove the following theorem. Fix $k \geq 1$ and let $M = [0, k - 1]$ . Let $E_{K}$ be an ideal block cipher on the set $T$ , where $M \subseteq T$ . Choose a key $K$ uniformly at random and construct ${C y}_{K}$ using $E_{K}$ . Then ${C y}_{K}$ is a uniform random permutation on $M$ .^[3] The proof fixes a permutation $π$ on $M$ and shows that an equal number of keys $K$ give rise to $π$ . The construction thus retains all of the security of the underlying block cipher.^[6]

The theorem is an information-theoretic result. Passing to the corresponding complexity-theoretic result is standard. Because no security is lost in the information-theoretic setting, and because $E$ is applied an expected two times or fewer, an adversary's maximal advantage in distinguishing $E_{K}$ from a random permutation of $ℤ_{2^{n}}$ in expected time $2 t$ approximately upper-bounds an adversary's maximal advantage in distinguishing ${C y}_{K}$ from a random permutation on $M$ in time $t$ .^[6]

Efficiency

Black and Rogaway describe the cycle-walking cipher as "quite practical". If $k$ is just smaller than some power of 2, the number of points to walk through during any given encipherment is correspondingly small. In the worst case, however, $k$ is one larger than a power of 2, and with extremely bad luck about $k$ calls to the underlying block cipher might be needed to encipher just one point. But if the underlying block cipher is good, an expected two calls to it are needed to encipher and decipher any point, even in the worst case.^[5]

References

1 2 Black & Rogaway 2001, p. 1.
↑ Miracle & Yilek 2017, §1.
1 2 3 4 5 6 Black & Rogaway 2001, p. 5.
1 2 Black & Rogaway 2001, p. 3.
1 2 Black & Rogaway 2001, p. 8.
1 2 Black & Rogaway 2001, p. 6.

Sources

Black, John; Rogaway, Phillip (12 February 2001). "Ciphers with Arbitrary Finite Domains". Cryptology ePrint Archive (2001/012).
Miracle, Sarah; Yilek, Scott (2017). "Cycle Slicer: An Algorithm for Building Permutations on Special Domains". Advances in Cryptology – ASIACRYPT 2017. Lecture Notes in Computer Science. Vol. 10626. Springer. pp. 392–416. doi:10.1007/978-3-319-70700-6_14.

This article incorporates text by John Black and Phillip Rogaway available under the CC BY 4.0 license. The source's description, example and analysis have been condensed and reused, with light changes of wording.

[FOOTNOTEBlackRogaway20011-1] 1 2 Black & Rogaway 2001, p. 1.

[FOOTNOTEMiracleYilek2017§1-2] Miracle & Yilek 2017, §1.

[FOOTNOTEBlackRogaway20015-3] 1 2 3 4 5 6 Black & Rogaway 2001, p. 5.

[FOOTNOTEBlackRogaway20013-4] 1 2 Black & Rogaway 2001, p. 3.

[FOOTNOTEBlackRogaway20018-5] 1 2 Black & Rogaway 2001, p. 8.

[FOOTNOTEBlackRogaway20016-6] 1 2 Black & Rogaway 2001, p. 6.

[1]

[2]

[3]

[4]

[5]

[6]