# 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?

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)

• can you specify what $f$ is beyond an example? otherwise your question is arbitrary Feb 3, 2023 at 18:37
• @kodlu $f$ is just a place holder. Given all elements in $\{1,0\}^{128}$ we select a target subset of any size (in example size $=2^{128-42}=2^{86}$ ). Function $f(x)$ returns $true$ if $x$ is an element of the set. The question is if we can find $c,m$ which are both part of the set faster than just with trial and error. Or do I miss something? What could $f$ be to be a different complexity class? Feb 3, 2023 at 18:52
• If you define $F(m,c) := f(m) \land f(c)$ then we can say you are looking for a particular relation between the plaintext and the ciphertext and that relation is defined by $F$. So isn't this related to the notion of ciphertext equivocation? Being able to decide given a ciphertext whether it "pairs" to a certain plaintext? I'm not sure, just a suggestion...
– Amit
Feb 3, 2023 at 19:23
• @Amit not sure if I understood you correctly but those 'pairs' are related to the chosen key. The goal is to find any $c$ and $m$ which a part of the same chosen set as quick as possible. If the chosen set has a size of $N$ we can start at any of those $N$ elements and 'hope' the result is also any of those $N$ elements. Unlike normal use case we don't have a single $m,c,K$ but instead multiple $m,c$ are possible values. Feb 3, 2023 at 19:42
• I am trying to say that it seems to me that your question can be formulated as a question about relations between plaintexts and ciphertexts, where of course we have $(m,c)=(m,E_k(m))$ so they are related via a specific key. The relation can be described by the function $F$ I defined before. From here I refer you to what @kodlu answered already below... if we assume AES is a good pseudorandom permutation, there shouldn't be such a relation that can be found faster than exhaustive search. At least that's how it seems to me - this is certainly no proof :)
– Amit
Feb 3, 2023 at 19:47

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

• Thank you for the posted answer but I don't get the $f$ nonlinear part. Maybe I defined $f$ not well enough. We only have 2 subsets. One where $f$ returns $true$ for every member and $false$ for every other element. The smaller the $true$-set gets the higher the ratio of members which do not pair with any element of the $true$-set. If too small no pairs may exist at all. Feb 3, 2023 at 20:23
• Lets assume we use the example case with 42 leading '1' bits. The $true$-set would have a size of $2^{86}$. Given a fixed key $K$ how long would it take to find any pair $m,c$ which are inside the $true$-set? round about a) $2^{40}$ b) $2^{30}$ c) $2^{20}$ d) even less than this Feb 3, 2023 at 20:24

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.

• Can't find anything to 'start-in-the-middle attack'. Or do you mean man-in-the-middle attack? How would this work out of that case? Ye, $f$ can be constructed in that way but the main motivation for this question is not about $f$ but instead if we can compute AES significant faster if start and goal is not a single value but instead a set of values. Assuming the set size is $M\cdot N$. Compared to a set with size $N$ the trivial speed up factor would be $M$-times that fast (assuming its big enough to find some match). The question is if it can be done fast instead of testing it just one by one Feb 4, 2023 at 2:05
• or if the AES algorithm can be simplified if the Key is constant. According to the already posted answers this seems to not be the case. Feb 4, 2023 at 2:07
• @J.Doe if what you are searching for is "weak keys" then this is in fact a well studied (as far as I know) subject in block ciphers. DES was discovered to have weak keys and I think a lot has been written about this. It may give you an idea on how to search for weak keys in other ciphers as well.
– Amit
Feb 4, 2023 at 14:05
• The natural way to try to force a desired input and output starting from the middle here would be to work with the ideas of the rebound attack (Mendel et al., FSE 2009). The particular key value shouldn't matter here, but if the adversary is able to pick the key, this will give them additional degrees of liberty that can be put to use in rebound-style attacks. I don't expect forcing e.g. a state with many zeroes to be straightforward (or even in the end practical) using these methods, but I don't think it's necessarily hopeless for all "natural" $f$ either. Feb 5, 2023 at 4:16