If you are sending a single block message with single encryption, there is a non-zero possibility that multiple distinct keys will map one specific plaintext to one specific ciphertext or that there no keys that will work.
A block cipher is simply a pseudo-random permutation. Ideally, the key just selects a random permutation of the input space to an output space -- and it is necessarily a permutation so the decryption function can reverse it.
As a toy example of a pseudo-random permutation with a very small key space and very small input/output space, imagine the following encryption function that has a 2-bit key (0,1,2, or 3) that permutes a 2-bit input message into a 2-bit output message. Specifically:
- with key 0: the inputs {0,1,2,3} respectively encrypt to the ciphertexts {2,0,3,1}
- with key 1: {0,1,2,3} respectively encrypt to {1,0,3,2}
- with key 2: {0,1,2,3} respectively encrypt to {3,1,2,0}
- with key 3: {0,1,2,3} respectively encrypt to {3,1,0,2}
(These permutations were randomly generated in python with scipy.random.permutation(range(4))).
Note in this toy example, that for some pairs like (m=1, c=2) and (m=0, c=0) where there no keys that would work. Meanwhile for other pairs like (m=0, c=3) and (m=1, c=1) there are multiple keys (in both cases k=2 or k=3) that would work.
So as a worst-case for this toy encryption function you would need 3 blocks to uniquely identify. (E.g., if your first two messages were 0 and 1 you wouldn't be able to distinguish between key 2 and 3 until you got a 3rd input).
However, with large block sizes having multiple collisions between the same two keys will be very unlikely. Hence in practice if you brute-force two pairs of encrypted single block messages/ciphertext with overwhelming probability there would be only one key that works for both.
Note, doing double encryption (with two independent keys K1, K2) works exactly the same as analysis of single encryption of a key that is the concatenation of K1 and K2.
