Using same encryption key in different schemes

Question

Is it safe to encrypt possibly same plaintexts with 2 different algorithms using same secret encryption key? This question is similar to this question except they use 2 keys. More formally:

$E_k(m) = E_{1,k}(m)||E_{2,k}(m)$

I understand that this could be easily made secure by producing few more keys out of the one key that is provided by, for example, using a stream cipher over predefined plaintexts or by hashing the key with predefined prefixes. I am wondering if there are any non-obvious problems with mixing schemes. I suspect there may be, since both ciphertexts together provide more information to an attacker than each ciphertext alone.

Consider this. Both schemes use 512 bit keys. First encryption outputs a ciphertext that is a function of message and first half of the key, concatenated with second half of the key in the clear. This scheme is secure in itself, because the key bits essential to security are kept secret. Remaining bits are considered junk. Second encryption does the opposite where first half is outputed in the clear. Together, entire key is revealed.

On side note, I am aware that same RSA keys should not be used for encryption and authentication. GPG uses separate keys. Feels like a similar issue.

Answer 1

I understand that this could be easily made secure by producing few more keys out of the one key that is provided by, for example, using a stream cipher over predefined plaintexts or by hashing the key with predefined prefixes.

This would be the task of a Key Based Key Derivation Function or KBKDF for short. HKDF is such a KBKDF that quickly has made inroads. It is possible to construct keys using other methods as well, but basically you'd be creating simplified KDFs.

So usually it is better to use a KDF to derive each separate key.

I am wondering if there are any non-obvious problems with mixing schemes. I suspect there may be, since both ciphertexts together provide more information to an attacker than each ciphertext alone.

As you already found out, it is very easy to create a set of two theoretical ciphers where reusing the key is insecure. You could however take a set of normal ciphers that are very different. In that case you have to find an equation where one cipher leaks information about the other, or you have to retrieve the key from one of the ciphers (i.e. breaking it). Nobody here is going to take two of the final AES candidates and break this scheme.

On side note, I am aware that same RSA keys should not be used for encryption and authentication. GPG uses separate keys. Feels like a similar issue.

Now you're getting into dangerous waters. Unlike the AES candidates keys for asymmetric ciphers generally have a specific structure that is tied to the algorithm (e.g. RSA). So you can probably only use them for algorithms that are directly related. In that case it might very well be that you leak information and possibly even the key.

The same indeed goes for cipher modes that simply split the key into multiple parts such as SIV of course. You would not want any key reuse for those kind of modes of operation.

---

Note that besides theoretical issues there may be practical issues as well. Many API's won't allow you to use a key of one specific type as another. Imagine you've got an RSA or AES key in a HSM. You cannot just use that for any other algorithm.

Answer 2

It sounds like you already answered your own question, however I will try and offer an alternative.

Assume your first encryption scheme is a substitution cipher that shifts each character by key+4. The second scheme shifts each character by key-3. If you use an identical key and plaintext, an attacker now has extra information to begin cryptanalysis. They know that the key will work both +4 and -3.

Of course with AES or other more advanced ciphers, it will be much more complicated, but I believe this illustrates the main issue.