4
$\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$
  • 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. Jul 2 '16 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 Jul 2 '16 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. Jul 2 '16 at 18:18
  • $\begingroup$ What is an equivalent decryption key? $\endgroup$ – Andrew Hoffman Jul 3 '16 at 4:03
  • $\begingroup$ @AndrewHoffman it's two (or more) keys that all work to decrypt a ciphertext correctly. $\endgroup$ – user9070 Jul 3 '16 at 4:58
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$
  • 1
    $\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$ – CodesInChaos Jul 2 '16 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 Jul 2 '16 at 20:33
  • $\begingroup$ @CodesInChaos Yes, this was part of the question, I was wondering if it would lead to an attack. $\endgroup$ – user9070 Jul 2 '16 at 22:18
  • 1
    $\begingroup$ @CodesInChaos: I can prove that one time pad does not have equivalent keys. $\endgroup$ – Joshua Jul 2 '16 at 23:53
  • 1
    $\begingroup$ @Joshua A one-time-pad is hardly a "typical block cipher". $\endgroup$ – CodesInChaos Jul 2 '16 at 23:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.