5
$\begingroup$

Do all ciphers suffer from the problem of multiple equivalent decryption keys? Is the existence of equivalent keys an essential property for the security of a cipher?

If you could prove that a cipher had no equivalent keys, would that lead to a procedure for recovering the key under the known-plaintext attack model?

$\endgroup$
5
  • 3
    $\begingroup$ Are you talking about symmetric key ciphers? Because most modern block ciphers are designed to have no weak keys, which includes equivalent keys (like the weak and semi-weak keys of DES). What lead you to believe that equivalent keys would be essential for security? $\endgroup$
    – J.D.
    Commented Jul 2, 2016 at 17:55
  • $\begingroup$ A linear system has a unique solution if it is non-singular and requires no guesswork. But it seems guessing is a desirable feature of a cipher solution. $\endgroup$
    – user9070
    Commented Jul 2, 2016 at 18:07
  • 2
    $\begingroup$ A block cipher is ideally very far from a linear system. Large classes of equivalent keys greatly weaken the cipher, because a key-guessing attacker only has to test one key per equivalence class. $\endgroup$
    – J.D.
    Commented Jul 2, 2016 at 18:18
  • $\begingroup$ What is an equivalent decryption key? $\endgroup$ Commented Jul 3, 2016 at 4:03
  • $\begingroup$ @AndrewHoffman it's two (or more) keys that all work to decrypt a ciphertext correctly. $\endgroup$
    – user9070
    Commented Jul 3, 2016 at 4:58

1 Answer 1

11
$\begingroup$

Do all ciphers suffer from the problem of multiple equivalent decryption keys?

No. The number of non-equivalent keys is bounded by the number of permutations. Since the number of permutations is very high there is a very big chance that ciphers do not have equivalent keys. This is especially true for ciphers with a high block size (AES with 128 bits). Even if an equivalent key would exist, it would probably be rather tricky to find a set of two equivalent keys. How tricky depends on the cipher of course.

Is the existence of equivalent keys an essential property for the security of a cipher?

Therefore no.

If you could prove that a cipher had no equivalent keys, would that lead to a procedure for recovering the key under the known-plaintext attack model?

No. Finding that a cipher does not have equivalent keys would enhance the security of the cipher, not decrease it.

More information about equivalent keys here.

$\endgroup$
7
  • 2
    $\begingroup$ Efficiently proving the absence of equivalent keys for typical block ciphers sounds pretty difficult. It seems possible that if your cryptoanalysis is successful enough for such a proof it'll also be successful in breaking the cipher. $\endgroup$ Commented Jul 2, 2016 at 20:20
  • 1
    $\begingroup$ @CodesInChaos Depends a bit on the key schedule I suppose. It could be that the key schedule is not that strong while the rest of the cipher is. That would probably exclude the cipher from being used in the construction of a hash function, but it may not break the cipher (thinking out loud here). $\endgroup$
    – Maarten Bodewes
    Commented Jul 2, 2016 at 20:33
  • 1
    $\begingroup$ @CodesInChaos: I can prove that one time pad does not have equivalent keys. $\endgroup$
    – Joshua
    Commented Jul 2, 2016 at 23:53
  • 2
    $\begingroup$ @Joshua A one-time-pad is hardly a "typical block cipher". $\endgroup$ Commented Jul 2, 2016 at 23:57
  • 1
    $\begingroup$ Just how many more permutations than keys there are is worth emphasizing. 2^128 factorial is a number with more than 2^128 bits in it. If ciphers approximate random permutations like they should, ciphertexts under any two keys shouldn't match for more than a few plaintexts. $\endgroup$
    – twotwotwo
    Commented Jul 3, 2016 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.