Probability of $D_k(a*k+b) =p$ for a PRP

Question

I'm wondering what the probability of a PRP having numerous keys (say 3 or more) with the same simple idempotent, or near identity, function. For example, does there exist values of $p, a, b, x_1,$ and $x_2$ where more than two keys, $k$, have the property:

$ AES_k(p) = (x_1 \oplus (a*k) + b) \oplus x_2 $

I can abstract out E_k(p) as some PRP that yields an "unrelated" value:

$ R_1 = (x_1 \oplus (a*k_1) + b) \oplus x_2 \\ \wedge R_2 = (x_1 \oplus (a*k_2) + b) \oplus x_2 \\ \wedge R_3 = (x_1 \oplus (a * k_3) + b) \oplus x_2 $

Then, entirely informally, I reason that since there are $2^{128} R_i, k_i$ pairs the probability here is pretty high. Is that other peoples gut instinct? Could someone help me formalize the math here a little since I'm stabbing around a little blindly?

EDIT: Addition ($+$) and multiplication ($*$) are mod $2^{128}$. The $\oplus$ operator is bitwise addition (exclusive-or). Algebraically, I can see how two keys with this property trivial to derive ($x_2$ yields obvious flexibility) but I am unsure about the probability of this property holding for $N$ keys ($N>2$).

Edit 2

Adding more details on my thoughts: We can get two keys for which this property holds through simple algebraic rewriting:

$ k_1 = random\\ b = 0, a = 1\\ p = D_{k1}(k_1\oplus x_1 \oplus x_2) \\ k_2 = random \\ x_2 = E_{k2}(p) \oplus x_1 \oplus k_2 \\ x_1 = E_{k3}(p) \oplus x_2 \oplus k_3 \\ $

At this point $x_2$ and $x_1$ are defined in a mutually recursive manner. We are left with:

$ x_1 = E_{k3}(p) \oplus E_{k2}(p) \oplus x_1 \oplus k_2 \oplus k\\ 0 = E_{k3}(p) \oplus E_{k2}(p) \oplus k_2 \\ $

I.E. Removing $a$ and $b$ from consideration, for an equation with two xored values the probability of two keys meeting this property is 1. However, finding the value (if any exists) for the third key appears to be more involved - the above construction yields $E_{k3}(p) = E_{k2}(p) \oplus k_2$ which is similar to obtaining a key from a single chosen plaintext.

It is not obvious to me that adjusting $a$ or $b$ can be leveraged efficiently to solve this problem or make it computationally tractable. This is the heart of my question. Is it computationally feasible to find constants, including three keys, for which this property holds?

Answer 1

Let's look at some simpler relations first. I'll be sloppy with the probabilities, I'm only trying to gauge the order of magnitude.

The probability that $E_{k_1}(p) = k_1$ is $2^{-128}$ for a given $p$, but must be true for some $p$ with every AES-128 key $k_1$.

• The probability that $E_{k_2}(p) = k_2$ for the same $p$ is $2^{-128}$ for a given $k_2$.
• The probability that there is some $k_2 \not = k_1$ for which $E_{k_2}(p) = k_2$ is about $2^{128}-1$ times as much, i.e. quite likely.
• The probability that there are three different $k_i$ for which it is true is again close to $2^{-128}$.

Now that was with a constant $p$ that we "found" with some key $k_1$. Take another key and there's another $p'$ for which a similar equality holds, and $p'$ is likely different. For that you can again look at all other keys, probably finding at most one other key that fulfills it, but finding three with probability around $2^{-128}$.

Go through all $p'$, of which there are a small factor fewer than $2^{128}$, and you are quite likely to find one for which three keys match $E_{k_i}(p) = k_i$. Not 100% likely, but maybe 10% or whatever.

Now you can make the equation more complex. If you XOR a random constant $x_1$ on the right side, you can approximate it as an independent equation. There are $2^{128}$ possible values of $x_1$ so now you are overwhelmingly likely to find one triplet of keys for which it holds. Might even find four, but probably not.

Your form is more complex so there's more freedom to choose the constants and $N$ is probably larger. However, my math was sloppy enough already that I won't guess at the value.