Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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

share|improve this question

2 Answers

up vote 4 down vote accepted

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)

share|improve this answer
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. – Joe Z. Jan 22 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 – Joe Z. Jan 22 at 12:07
Could I use it as a security assumption if I upped the bit specification to 64? – Joe Z. Jan 22 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. – poncho Jan 22 at 20:56
1  
@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}}$.) – Ilmari Karonen Jan 23 at 12:19
show 2 more comments
up vote 3 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.