# Does it take brute force to find a pair of plaintext and ciphertext that each follow a certain condition, given an AES encryption key?

Suppose that I have an AES key $K$, and I'm instructed to find a plaintext such that the first 32 bits of the plaintext are some string of bits $S_1$, and the last 32 bits of the ciphertext once the plaintext has been encrypted with $K$ are another string of bits $S_2$.

Is this difficult? Is there a known attack against this that's faster than just fixing one of the $S$'s and brute-force searching for a text with the other $S$?

NO! AES is rated to withstand cryptanalysis so long as it remains a black box to the attacker (IE:round keys are unknown variables). Up until the SHA3 competition no one had done cryptanalysis on AES with known internal state. This is the relevant paper, specifically section 3.5 which solves the exact problem you are proposing. Given AES with a fixed key K acting as a pseudorandom permutation, find a solution to C=AESenc(P,K) with restrictions on C and P

There are also attacks on AES when used as a typical hash compression function (IE:state[i]=AES(state[i-1],K=data[i]). These allow for collisions and generally for breaking the pseudorandom permutation property of AES to find specific solutions for equations involving it.

There are probably some problems that remain hard, like reversing a one way function composed from AES (IE:F(X)=AES(X,Kfixed)⊕X , Y=F(X) , Find X given Y). Even here I'd be nervous but much less so. This is the ideal case. No degrees of freedom for the attacker to work with.

When you see "secure pseudorandom permutation" thrown around in the context of AES remember the fine print attached to all that analysis: "for unknown K"

Well, it's moderately difficult; you couldn't use that as a security assumption; however, it would be too difficult to expect someone to solve during an active protocol. There's no nonobvious trick to it; the two methods at your disposal would be:

• Select random plaintexts with the first 32 bits as $S_1$; encrypt them with key $K$, and check to see if the last 32 bits of the ciphertext happen to be $S_2$

• Select random ciphertexts with the last 32 bits as $S_2$; decrypt them with key $K$, and check to see if the first 32 bits of the plaintext happen to be $S_1$

Either approach will take an expected $2^{32}$ random trials before success; at 1 $\mu$sec per AES operation (quite conservative; modern CPUs typically can do several times as fast as that), we're looking at perhaps an hour or two.

Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out. For example, you might be hoping to translate the AES cipher into a large series of boolean operations (with the known key, and known 32 bits of plaintext and ciphertexts), and solve the resulting set of equations. However, AES has a fairly quick 'avalanche'; very quickly (within two rounds), all the internal bits will depend on all the unknown bits in subtle ways; the resulting set of equations will not have an easier solution than just trying various combinations of the 96 bits on one side (which is effectively what the straight-forward solutions do)

• That's what I was looking for; thanks. I was wondering whether there was any method easier than those two you listed. If there aren't, that's perfect. Jan 22 '13 at 11:57
• "Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out." Actually, I was hoping there wasn't such a way and that somebody would verify the fact. :P Jan 22 '13 at 12:07
• Could I use it as a security assumption if I upped the bit specification to 64? Jan 22 '13 at 17:29
• @JoeZeng: well, I suppose you could, depending on the adversary. Someone could solve with with around $2^{64}$ AES operations; there are real world organizations which could feasibly do that much for for something they really wanted. Of course, your potential adversaries might not fall into that camp -- that's a call you would need to make. Personally, I prefer solutions that require $2^{128}$ operations (or more) to defeat; that means I don't have to worry if a TLA would be interested. Jan 22 '13 at 20:56
• @Joe: Note that, if you fix 64 bits of the plaintext and 64 bits of the ciphertext of a 128-bit block cipher, then there's about a $e^{-1}\approx 0.37$ chance that no such pair will exist. (More generally, if you fix $j\gg0$ out of $n$ bits of the plaintext and $k\gg0$ out of $n$ bits of the ciphertext, then the probability of there being at least one matching pair is about $1-e^{-2^{n-j-k}}$.) Jan 23 '13 at 12:19

For an ideal 128-bit block cipher (a family of random permutations on the set of 128-bit blocks), there's no better way to find such pairs than the brute force method described by poncho. If a significantly more efficient method did exist for AES, that would allow efficiently distinguishing AES from an ideal block cipher, which would contradict the security assumptions of AES.

As no such attack has been published, despite the considerable amount of cryptanalytic research on AES, we can be fairly confident that there's no easily discoverable method to find such pairs that would be more efficient than brute force.