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.
