Properties of AES Encryption

Question

First of all, I apologize if these questions can be answered using a web search, but I'm sort of a crypto noob and don't know what to search for.

1. Given N AES encrypted messages (where the message length is much longer than the key length), and the corresponding N decrypted messages (all encrypted with different keys), is it possible to pair up each encrypted message with its decrypted counterpart?

2. Given one AES encrypted message and its decrypted counterpart, is it possible to reconstruct the key used for encryption if you know the key is 256 bits?

If AES cannot achieve these ends, is there a more suitable symmetric encryption algorithm that can?

Edit: I did some research and found the answer to #2. This type of attack is known as a plaintext attack, and AES is not known to be susceptible to this type of attack.

Answer 1

1). No, assuming a secure block-cipher mode (e.g., CBC, CTR) was used (basically any mode other than ECB) provided the initialization vectors are not reused. With ECB mode you could match up messages with patterns of repeated blocks in the plaintext to corresponding repeated blocks in the ciphertext. See ECB description on wikipedia for more.

Reusing the same initialization vector with multiple messages would completely undermine block cipher modes like CTR that construct a stream cipher out of the IV which is then XOR'd with the plaintext message to create the ciphertext. In CTR mode with a reused IV (again this is a misuse of AES, IV's are never supposed to be reused), all the plaintext messages will be XOR'd with the same bit-stream -- that the n-th ciphertext will be C[n] = AES_CTR-stream(IV) ⊕ M[n] where M[n] is the plaintext message. Note the following properties of XOR: it is commutative (x ⊕ y = y ⊕ x), associative (x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z), produces the zero bit-stream when XOR'd with itself (x ⊕ x = 0), and the zero bit-stream acts as the identity with XOR (x ⊕ 0 = x), hence (x ⊕ y ⊕ x = y). Thus you can simply take any two plaintext messages M[i], M[j] and XOR them with all the ciphertexts until you find two pairs that match. Note that C[n] ⊕ M[n] = AES_CTR-stream(IV) ⊕ M[n] ⊕ M[n] = AES_CTR-stream(IV), so at this point you've recovered the AES stream. (You still don't have the key, but at this point you can decrypt or alter or forge any ciphertext that uses this reused IV).

2). No, there are no known attacks that are significantly better than brute force in terms of computationally feasible (e.g., without taking billions of computers billions of hours to have a minute chance of finding the key). There are some published attacks on AES, but they either require very weird circumstances (e.g., related key attacks that require 2⁶⁴ messages to be encrypted with 2³¹ keys that are specific variants of the original key) or biclique only give a very small speed up (a factor of ~4 faster than brute force - 2²⁵⁴ instead of 2²⁵⁶), so there are no practical ways to break AES just having the ciphertext and plaintext that are publicly known.