# Is there a time-space tradeoff attack for breaking symmetrical cryptos?

Is there any known techniques for using time-space tradeoff for speeding up symmetrical crypto breaking? Kind of like rainbow tables speed up breaking hashes by using huge precomputed tables.

Is something similar possible for symmetrical cryptos like AES? If not, why? Is there a difference between block and stream ciphers in this regard? Couldn't you get at least a head start on brute forcing by searching through gigantic tables where a lot of plaintext "heads" have been pre-computed?

-
For AES128, the tables would be more than a trillion times the size of the entire internet... PER KEY, of which there are a 340 trillion trillion trillion possibilities. Dont even ask about AES256 – Richie Frame Mar 26 '14 at 10:17
Why would these tables be so large? Why couldn't a subset of them still be usable? Maybe expand this into an answer? – monoceres Mar 26 '14 at 10:29

The idea you have is: lets say we have a known plaintext/ciphertext pair; can we use a precomputed table to speed up the recovery of the key?

Well, the main problem with that precomputed tables don't actually speed up the search time, if you count the time taken to generate the precomputed table. What the table precomputation does is (for example) generate lots of key/ciphertext pairs (for a given plaintext), and store those in a table (in a clever way that makes the table much smaller than just storing each set individually. That's the real meaning of the phrase "time/memory trade-off"; it doesn't reduce the amount of time taken by using memory, it reduces the amount of memory (in terms of table space) by making the table lookup harder.

Then, when given a plaintext/ciphertext pair, it checks the table to see that if that ciphertext appeared in a key/ciphertext pair; if so, you have a solid guess of the key.

Now, if the key/ciphertext pair never occurred during the precomputation phase, you won't find it in the table; hence to generate a table where a lookup has a $2^{-32}$ probability of finding a 128-bit AES key, you need to spend at least $2^{96}$ time; that's no better than brute force; and we already believe brute force is too hard.

So, you say, why then do we use rainbow tables? Because we can spend the time to compute those tables once, and then use the same table multiple times. So, if we have $2^{32}$ different crypto texts with $2^{32}$ different keys, with each crypto text containing the encryption of the same plaintext block (and that same plaintext block would result in $2^{32}$ different ciphertexts), we could (with the above $2^{96}$ precomputation) have a decent chance at recovering the key to one of those sessions.

Isn't that some benefit? Well, in theory it might, but in practice, not so much. Remember, we generally run ciphers such as AES within a mode, and the mode may not give us consistent access to the same plaintext across sessions. For example, for CBC mode, the plaintext we present to the AES block cipher is effectively randomized; that means that you are quite unlikely to get the same plaintext used by even two different sessions, and so rainbow tables are not a win here; brute force is actually more efficient.

-
Excellent answer! I feel enlightened :) – monoceres Mar 26 '14 at 11:59