Can we find pairs $(c,m)$ with $f(c)=f(m)=true$ in $c = AES(m,K)$ with a fixed known Key $K$ significantly faster than brute force?

Question

Different to the usual adversary use case we do not want to find the hidden key but instead pairs of $(m,c)$ which each fulfill a certain property $f(x)=true$
An example property could be e.g. 42 leading '1' at the bit representation.

With brute force we could start at different such messages $m$ and receive an encrypted version $c$ which has a chance of $1 : 2^{42}$ to also fulfill this property. With this it it would take in mean round about $2^{42}$

Given now a constant known key $K$ can this pairing significantly (> 1000 times+) increased in computation speed?

Would it matter if the key $K$ has only a small bit number $\neq0$ or even is completely $0$ or a chosen specific key? Are there any simplifications for the AES algorithm if the Key is always equal.
(AES in ECB-Mode)

Answer 1

OK, you have asked a lot of questions in this vein, and they've mostly been answered, sometimes in great detail.

This is really not much different than the rest. You do seem to understand the idea of mean cycle size for such properties, which can only be understood when AES is modelled as a good pseudorandom permutation.

Your function $f,$ if it is a projection to a random subset that function is linear and partitions the space into different equal sized subsets. You already understand this from your comment.

If AES is pseudorandom, you cannot do better than the various time-memory tradeoffs, as expounded by Hellman, much later by Wiener (parallel collision search) etc.

If $f$ was nonlinear, it may not partition the input set $\{0,1\}^n$ to equal subsets, so then the analysis would no longer be correct, you might be stuck in a "small" subset, so the joint distribution of the subset sizes, namely $$ X_a=\{ x \in \{0,1\}^{128}: f(x)=a\} $$ would need to be analyzed as $a$ ranges over the codomain of $f$.

Finally, since AES can be well modelled as a good pseudorandom permutation it does not matter even one bit whether the key is zero, or it has mostly zero components. If it did, it would have come out at a first level with Sbox analysis, what if most input keys to most Sboxes were zero? Who cares, there is all the mixing steps, and constant addition which is composed with the galois field inverse in the Sbox

Answer 2

It is easy to see that for some $f$, such solutions will be easy to find. Indeed, denote the message space for AES with $\mathcal{P}$ and AES encryption under the fixed key $K$ with $E_K$ and assume that $S \subseteq \mathcal{P}$ is a set such that $m \in S$ can be easily generated. Now consider $\tilde{S} = S \cup E_K^{-1}(S)$, which for convenience we will call the relaxation of $S$. Then clearly, for all $m \in S$, we have $m \in \tilde{S}$ and $E_K(m) \in \tilde{S}$, and such $m$ are by assumption easy to generate.

Hence, setting $f$ to be membership in $\tilde{S}$ is an example of a relation where fullfilling both $f(m)$ and $f(E_K(m))$ is easy. If $S$ is a small set, finding such a pair by methods that are unaware of how $\tilde{S}$ was constructed will be much harder.

It is also clear that for some $f$, finding satisfying instances should be conjectured to be hard; for instance, satisfying the target predicate can already be hard without even considering the condition that both input and output of a fixed permutation satisfy it.

For natural $f$ (such as first $n$ bits zero), I would conjecture this to be difficult, but would not put much trust in the standard random-permutation arguments. In the known-key setting, it would not be a world-shattering revelation if for some natural $f$ some form of start-in-the-middle attack yielded a large advantage over the generic attack that treats $E_K$ as a black box. However, I would expect demonstrating this to involve some real research.