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
10
$\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 agree to our terms of service, privacy policy and cookie policy