5

I know in single encryption you would simply require at least 1 pair of plaintext-ciphertext, to carry out an exhaustive key search; you continue trying different keys until one is found that corresponds correctly to the pair you have.

Having more pairs would ideally be better as you could then find out for sure if that key is correct by trying it on the other pairs.

However, when using double encryption with two k-bit keys chosen uniformly at random how many pairs of plaintext-ciphertext would be required to identify the keys K1 and K2 in an exhaustive key search?

1

At a minimum I can't see why you'd need more than one.

You're essentially just combining the key space by encrypting it twice with two keys.

You simply decrypt the cipher-text with every value in the K2 space, then decrypt every result with every value in the K1 space. When you find a match you have the correct K1 and a K2.

  • That's what I thought too, but wasn't sure. Because surely one pair of keys may give the same answer as the correct pair, but not be correct for the rest of the pairs? Or could that not happen? – A.N Oct 25 '15 at 8:23
  • That depends on the cipher(s) used. Even if you used the same cipher, that might or might not make a difference, e.g. there might be one key that yields the same results as double-keys. – Tobi Nary Mar 23 '16 at 7:30
0

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.

  • What do m and c in your toy example refer to? – bvpx Apr 17 '17 at 20:23
  • @bvpx - m is the plaintext message and c is the (encrypted) ciphertext. – dr jimbob Apr 19 '17 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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