This is only true for one-time-pad encryption. For a given AES-256 cipher mode and ciphertext C, there are at most 2 * * 256 possible decryptions of C. For most pairs of ciphertext and plaintext (C, M2) longer than 32 bytes, there doesn't exist a key K2 that decrypts C to M2. Even if K2 exists, finding K2 given (C, M2) with an average work factor less than 2 255 implies you've found a weakness in AES-256.