# Proof that a function constructed from a PRP is, or is not a PRF?

Let $E$ be a family of Pseudo-Random Permutations of $b$ bits, with $E_K$ indistinguishable from random permutation with effort less than $O(2^b)$, easily computable as well as the inverse permutation, e.g. as instantiated by AES-192 for $b=128$. Let $E_A$ and $E_B$ be two public members of this family.

For an $E_K$ in $E$, let $F_K$ and $G_K$ be the functions $$F_K:x\mapsto F_K(x)=E_K(E_A(x))\oplus E_K(E_B(x))$$ $$G_K:x\mapsto G_K(x)=E_K(E_A(x)\lor1)\oplus E_K(E_B(x)\land\overline{1})$$ where $\lor1$ (resp. $\land\overline{1}$) sets (respectively clears) the rightmost bit, and $\oplus$ is exclusive-OR.

Question: Are $F$ and $G$ families of Pseudo-Random Functions indistinguishable from random function with effort less than $O(2^b)$ ?

Note: formerly, I thought of an attack on $F$ by considering a cycle in $x\mapsto E^{-1}_B(E_A(x))$; but thinking about it, that attack is $O(2^b)$.

-
The best attack I can find against $F$ requires something like $2^b$ steps of computation, as a precomputation, just to find the attack. Does that match your attack on $F$? I don't know if you're thinking of a different attack against $F$ than I am.... –  D.W. Nov 19 '12 at 0:05
Are you sure that "$F$ is not ... $O(2^b)$"$\hspace{.01 in}$? $\;\;$ I only see how to show that "$F$ is not necessarily ... $O(2^b)$". –  Ricky Demer Nov 19 '12 at 0:26
@RickyDemer: no, I'm not sure. Actually, the attack I thought of does not work. –  fgrieu Nov 19 '12 at 7:34

Here's a different attack, one that runs in $O(2^{b/2})$ time. I'll also present a theoretical framework for how to think about the security of these sort of schemes. The bottom line is that it looks like no scheme of this form can be secure; I'll try to make more precise what I mean by that, below.

We can consider a generalized scheme, $H_K(x) = E_K(f(x)) \oplus E_K(g(x))$, where $f,g$ are public functions that can both be inverted (given $f(x)$, one can rapidly find all possible values of $x$, and the same for $g(x)$).

Definition. Define the graph for $H$ to be an undirected graph with vertex set $\{0,1\}^b$ and an edge $(f(x),g(x))$ for each possible input $x$. In other words, for each possible input $x$, if $H_K(x)$ takes the form $E_K(u) \oplus E_K(v)$, then we add the edge $(u,v)$.

Example. The graph for $F$ is the graph of a random permutation (namely, $\pi = E_B \circ E_A^{-1}$).

Example. The graph for $G$ is a bipartite graph, where each of the two vertex-sets has size $2^{b-1}$. Roughly speaking, each vertex is connected to two random other vertices on the opposite side of the bipartite graph.

Notice that the assumptions on $f,g$ mean that we can readily traverse this graph: for instance, given a vertex $v$, we can rapidly find all edges incident on $v$.

The intuition is as follows: we think of each vertex $v$ of the graph as being labelled with the value $E_K(v)$, and we think of each edge $(f(x),g(x))$ of the graph as being labelled with $H_K(x)$. These labels have a special property. If $(u,v)$ is an edge in the graph, then given any two of the three following values you can infer the third value: the label on $u$, the label on $v$, the label on $(u,v)$. Of course, we'll be given only the labels on the edges, not the labels on the vertices, but this perspective is helpful to frame our thinking.

Attack 3. Now here's an attack on $G$. Construct the graph for $G$. Construct a spanning tree that links some $2^{b/2}$ vertices together into a single connected component (without any cycles).

How do you find such a spanning tree? An easy way is to pick an arbitrary root vertex $r$, then do a depth-first (or breadth-first) search starting from $r$, until you've visited $2^{b/2}$ different vertices. Along the way, if you discover a cycle, there is a separate way to distinguish $G$ from random (see below), so without loss of generality we will assume this search does not detect any cycle. Thus you can readily form a spanning tree of all the edges that were traversed.

Once you have a spanning tree $T$, we query the oracle on the input corresponding to each edge in $T$. This tells us the labels on all of those edges.

Now, intuitively, we are going check whether there exist any two vertices $v,w$ in $T$ that have the same label. How can we do this, when we are not given the labels on the vertices? The answer is that we will actually check a different criterion: for every pair $v,w$ of vertices in $T$, we will examine the path from $v$ to $w$ (there is always exactly one such path, since $T$ is a spanning tree) and we will check whether the labels on the edges of this path xor to zero. If they do, we will infer that the oracle is instantiated with a random function. If this never happens, we will guess that we are interacting with an oracle for $H_K$.

Why does this work? If we are interacting with an oracle for $H$, then the labels on all vertices should always be distinct, since $E_K$ is bijective. Of course, the xor of the labels on the edge in a path from $v$ to $w$ is exactly the same as the xor of the label on $v$ and the label on $w$, so if $v,w$ have distinct labels, then this path-xor must be non-zero. On the other hand, if our oracle is instantiated as a random function, then each path-xor is a random value, so by the birthday paradox there is a good chance that some such path-xor will be zero.

On the surface, it looks like this attack requires $2^{b/2} \times 2^{b/2} = 2^b$ steps of computation, to check all possible pairs $u,v$. However, it can actually be implemented in $2^{b/2}$ time, with a slightly more cleverness. For each vertex $v \in T$, we compute the path-xor for the path from $v$ to the root of $T$. All of these values can be computed in $2^{b/2}$ steps using a top-down traversal of $T$. Next, we sort or hash all of these values to check whether there exist a pair of vertices $u,v$ that received the same value in this stage. Why does this work? It's because the path-xor from $u$ to $v$ is zero if and only if the path-xor from $u$ to the root is the same as the path-xor from $v$ to the root.

So, this gives us a distinguishing attack on $G$ with running time about $2^{b/2}$. In fact, if you think about it, it gives us an attack on any scheme that has the form $H$, where $H$ is as above.

Now let me develop the theoretical framework for analyzing all such schemes of this type (i.e., that can be expressed as a $H_K$ as above). Construct the graph for $H$. I claim that the security of these schemes comes down to the cycle structure of this graph.

For a warmup, suppose that instead of using a PRP for $E_K$, we instead use a random function for $E_K$. Then I claim:

Theorem. $H$ is secure if and only if the graph for $H$ has no cycles. More precisely, there is a distinguishing attack on $H$ requiring $q$ queries if and only if there exists a cycle of length $\le q$ in the graph for $H$.

Proof. The "if" part is easy: If there's a cycle of length $q$, then we can query our oracle on the $q$ inputs corresponding to those $q$ edges. If the responses xor to zero, then we are dealing with $H$; otherwise, we are dealing with a random function. This works, since due to the way $H$ is constructed, the xor of the labels on the edges in a cycle is always guaranteed to be zero, whereas when we are interacting with a random oracle, the path-xor around the cycle is a uniformly random value.

The "only if" part: Suppose there's no cycle in the graph of length $\le q$. Then let's look at any attack that queries the oracle on $q$ inputs. These $q$ inputs correspond to $q$ edges, and by assumption there are no cycles among these edges. Thus, we can construct a forest of spanning trees that covers each of these edges exactly once.

Let's consider a single spanning tree $T$. Consider what happens when we are interacting with the real $H$ as our oracle. By assumption, the label on each vertex in $T$ is uniformly random and independent of all others. If we traverse the tree in a top-down fashion (starting with the root), we can see that the label on each edge is also uniformly random and independent of all previously visited edges. Thus the labels on the edges are uniformly random and mutually independent -- exactly the same distribution as one obtains when interacting with a random function as our oracle. Since the distributions are identical, no attack can distinguish between these two cases.

This potentially suggests a direction for finding some construction $H$ that would be secure, if we could instantiate $E_K$ as a random function.

Unfortunately, it looks like that's a dead end. When all we have is a block cipher (i.e., when $E_K$ is instantiated with a PRP or a random bijection), then it appears there's no hope: there will always be a distinguishing attack of complexity $\le 2^{b/2}$. If there's any cycle in the graph of length $\le 2^{b/2}$, then the scheme is insecure, using the attack above. On the other hand, if there are no such cycles, then we can use the attack I described against $G$ to distinguish: construct a spanning tree that connects $2^{b/2}$ edges, then use the birthday effect to check whether there's any path through the spanning tree whose path-xor is zero.

So, as far as I can see, when $E_K$ is instantiated via a block cipher and $H_K(x)= E_K(f(x)) \oplus E_K(g(x))$ where $f,g$ satisfy the conditions outlined above, it appears there's no hope for this to be secure beyond $2^{b/2}$ queries.

-

Here are two different ways to break $G$.

Attack 1. $G$ is unlikely to be a secure PRF, at least against non-uniform adversaries. In particular: there is likely to exist a fast attack (though it might take $2^b$ steps of computation to find the attack).

The idea of the attack: With high probability, there exists $x,x'$ such that $E_A(x)\wedge 1 = E_A(x') \wedge 1$ and $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$. This immediately yields a distinguishing attack on $G$, since (regardless of $K$) we are guaranteed that $G_K(x)= G_K(x')$, something that should happen with just $1/2^b$ probability (not with probability 1).

I don't know how to efficiently find $x,x'$. I can see how to find such a pair in about $2^b$ steps of computation. Basically, pick a random $b$-bit value $y$, then compute $E_A^{-1}(y)$ and $E_A^{-1}(y) \oplus 1$; this gives a candidate pair $x,x'$, and you can then check whether $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$ holds. The latter holds with probability $1/2^{b-1}$, so you'll probably have to try about $2^{b-1}$ different values of $y$ before success. Nonetheless, even though the attack is hard to find, once you know the attack, the attack requires only 2 oracle queries and minimal computation. This suffices to demonstrate that $G$ is not a secure PRF, at least under standard definitions of security.

Attack 2. I'll show an attack on $G$ that has about the same complexity as the best attack I can find on $F$. In both cases, the attack requires about $2^b$ steps of precomputation just to find the attack, but then once the attack is known, it takes a lot less than $2^b$ steps to distinguish $G$ (or $F$) from a random function.

My attack on $G$ is an adaptation of my attack on $F$, so let me start by spelling out the attack on $F$ that I have in mind. Define the permutation $\pi$ by $\pi(y)=E_B(E_A^{-1}(y))$. The precomputation is as follows: find a short cycle of $\pi$, say $y_0,y_1,y_2,\dots,y_k$ (where $y_k=y_0$ and $y_{i+1}=\pi(y_i)$ for each $i$). Define $x_i=E_A^{-1}(y_i)$. Then we are guaranteed that $F_K(x_1)\oplus F_K(x_2) \oplus \dots \oplus F_K(x_k) = 0$. This gives a distinguishing attack on $F$ that requires $k$ oracle queries and trivial work. Since $\pi$ is effectively a random permutation, we should be able to find a short cycle in $\pi$: it is very likely that a short cycle will exist.

How long does it take to find the attack on $F$? I can't see how to do it much faster than $2^b$ steps of computation.

Now here's the attack on $G$. First, we're going to construct a new function $H$, as follows: $H_K(x) = G_K(x) \oplus G_K(x')$, where $x' = E_A^{-1}(E_A(x) \oplus 1)$. Notice that, if you have an oracle for $G$, you can extract an oracle for $H$. Also, expanding the definition of $H$ yields $H_K(x) = E_K(E_B(x) \wedge \overline{1}) \oplus E_K(E_B(E_A^{-1}(E_A(x) \oplus 1)) \wedge \overline{1})$. By analogy to the attack on $F$, let's define a permutation $\sigma$ by $\sigma(y) = E_B(x') \wedge \overline{1}$ where $x=E_B^{-1}(y)$, i.e., $\sigma(y) = E_B(E_A^{-1}(E_A(E_B^{-1}(y)) \oplus 1)) \wedge \overline{1}$. During precomputation, find a short cycle of $\sigma$, say $y_0,y_1,y_2,\dots,y_k$, and define $x_i=E_B^{-1}(y_i)$. Then we are guaranteed that $H_K(x_1)\oplus \dots \oplus H_K(x_k)=0$. This in turn implies a relation on $G$, where the xor of $2k$ $G$-outputs is guaranteed to be zero (regardless of $K$). Thus, any short cycle in $\sigma$ yields a distinguishing attack on $G$. The distinguishing attack itself is very fast (assuming $k$ is small).

How long does it take to find the attack on $G$? I can't see how to do it much faster than $2^b$ steps of computation---in other words, about the same complexity as finding the attack on $F$.

This provides an alternate way to break $G$.

-
I had found your attack on $F$ and got its complexity wrong :-( Thanks for straightening that, and many other things. –  fgrieu Nov 19 '12 at 7:51