9
$\begingroup$

With most encryption methods, if a message is encrypted first using key $k_1$ and then using $k_2$, to decrypt it you have to use first $k_2$ and then $k_1$.

I was wondering if there are any encryption methods that can be decrypted using the keys in any order. For example, if a message is encrypted using the keys $k_1$, $k_2$ and $k_3$, in this order, then it could be decrypted in the order of $k_2$, $k_3$, $k_1$ or in any other order, as long as all 3 keys are used.

Simple XORing the keys and the message is possible (where the key space is the same as the message space) but if multiple messages are encrypted, it is not secure.

So my question is: Is there an encryption method where the order of decryption is irrelevant to encryption, but which is also secure with multiple messages? The size of the keys doesn't matter.

$\endgroup$
2
  • $\begingroup$ Is your purpose to create a secret sharing scheme (e.g. you want to make sure that more than one person is needed to decrypt an encrypted document?) If so, there are specific algorithms for doing that. $\endgroup$
    – Pascal
    Commented Nov 7, 2016 at 9:04
  • 3
    $\begingroup$ The technical term is commutative encryption. $\endgroup$
    – Mikero
    Commented Nov 8, 2016 at 3:58

1 Answer 1

7
$\begingroup$

Any synchronous stream cipher, or block cipher in a stream-like mode of operation (such as counter-based modes), will have this property. That's because they are, in essence, stretching a user-supplied key to an arbitrary length, and then using it as an XOR mask to encrypt (or decrypt) the message. Since the message content isn't relevant to cipher stream, and the actual encrypt/decrypt operation is just XOR, the order is unimportant.

Note that ciphers like this are extremely vulnerable to some classes of attacks, such as a bit-flipping attack. It is therefore crucial that you include an integrity check, such as an HMAC, with your ciphertext.

In order to make this secure with multiple messages, you have to do the same thing you do with most ciphers when reusing a key: you need a new nonce or initialization vector (IV). This value is randomly generated for each message, and sent along with the ciphertext in the clear. It is useless for the attacker unless the attacker also has the key, but it allows the same shared key to produce different ciphertexts even when encrypting the same plaintext message. This means an attacker can't determine anything about the plaintext (other than its length, which can be mitigated via padding and so on) by comparing ciphertext messages, even if the attacker knows they were encrypted with the same key.

You do need to be absolutely sure to never re-use the IV, though. IV re-use makes it quite easy to break many crypto schemes. For example, the old Wired Equivalent Privacy (WEP) encryption used for early WiFi had short IV (only 24 bits) and this was weak enough that often possible to break the encryption with only a few minutes of analysis if the network was busy (and therefore had to generate a large number of IVs to encrypt all the packets it was sending).


With all that said... schemes like you describe aren't as secure as you might expect them to be. While they should remain at least as secure as only doing a single round of encryption, they might not be any better than that. Due to attacks such as meet-in-the-middle, using the same cipher for multiple operations (even with different keys) is less secure than you'd expect. Mixing encrypt and decrypt operations is more secure for ciphers where encrypt and decrypt are different operations (which is not the case for cipher classes mentioned above) but even then, it's less secure than you might expect. A real-world example of this is the Triple-DES cipher, which attempts to fix the weakness of the DES cipher's 56-bit key by using three keys, and doing encrypt-decrypt-encrypt (or the reverse, for the decrypt operation). You might think that would produce 168 bits of effective security, but due to meet-in-the-middle, it's actually only 112 bits effective (although you do still need all three keys to be distinct, which is 168 bits of key material).

Still, if you want to generate a bunch of independent keys, encrypt a message with all of them, and then require them all to be re-entered before the message is decrypted without caring about the order of re-entry... this scheme should work. Just don't expect it to be more resistant to cryptanalysis than just encrypting the message once.

$\endgroup$
3
  • $\begingroup$ You already obtain the 112 bit security level of 3DES with its two-key mode where the first and the last key is the same. In that case, you only have 112 key bits. Furthermore, encrypting with multiple keys as described by this answer is not less secure than encrypting with a single key. So if the OP wants to use multiple keys to require multiple parties to cooperate for decryption instead of increasing the security level, the downside you describe doesn't apply. The OP has to be aware that all IVs need to stay unencrypted and the mapping between IVs and keys must be available. $\endgroup$
    – Michael Karcher
    Commented Nov 7, 2016 at 6:50
  • $\begingroup$ @MichaelKarcher: Actually, triple-DES in keying option 2 (only 112 bits of independent key material) is vulnerable to some attacks (not meet-in-the-middle; they require some chosen- or known-plaintext) and is considered to only have 80 bits of security. The rest of your comment is correct (to the best of my knowledge), though, and I'll edit it accordingly. $\endgroup$
    – CBHacking
    Commented Nov 7, 2016 at 6:54
  • 1
    $\begingroup$ You would also need to design your message format to somehow indicate which IV goes with which key, otherwise you will have trouble decrypting the message out of order. This is not a huge issue (you could e.g. tag each IV with a hash of the corresponding key, or some other key check value), but it's worth noting. $\endgroup$ Commented Nov 8, 2016 at 4:19

Your Answer

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