3
$\begingroup$

Alice wants to store files $m_i$ on Bob's untrusted cloud storage platform, with the additional restriction that she can only store one master key $k$ herself.

She encrypts the files with keys $k_i$ respectively and obtains $c_i := Enc_{k_i}(m_i) $. She also encrypts the keys as $k'_i := Enc_k(k_i)$ and sends the tuples $(k'_i,c_i)$ to Bob to store.

Seems quite natural that the encryption mode used for the $c_i$ be authenticated encryption. But for the $k'_i$, due to the high entropy nature of the payload and the fact they are used only for decrypting authenticated encryption, it seems that the encryption $Enc_k(k_i)$ does not need to be authenticated.

Is that true? If so, what is a more formal and coherent argument for it? If not, what attack does this relaxation enable?

$\endgroup$
4
  • 3
    $\begingroup$ Depending on the encryption mode and implementation used this can probably be used to mount related-key attacks. While these are generally somewhat on modern cipher designer's minds they don't always protect against them. $\endgroup$
    – SEJPM
    Jun 30, 2021 at 17:47
  • $\begingroup$ I think you can get around needing separate authentication of $k_{i}$ by using a key-committing AEAD for the message encryption, since that does essentially the same thing. The simple version is to put a hash of the key in the associated data. $\endgroup$ Jun 30, 2021 at 18:35
  • 1
    $\begingroup$ I would put the hash of the wrapped key in the AEAD, because unwrapping might put the key in a secure environment (that's how e.g. TPM's work). Another option is of course to store a salt or other "info" with the file, and derive the keys $k_i$. $\endgroup$
    – Maarten Bodewes
    Jun 30, 2021 at 18:51
  • $\begingroup$ An alternate solution $\endgroup$
    – kelalaka
    Jul 4, 2021 at 15:56

1 Answer 1

0
$\begingroup$

If it was possible for an AEAD cipher to validate when the wrong key a random key was used then I guess the cipher would be considered insecure. As such I think that the exclusion of the key in the calculation would make much of a difference.

On the other hand, it is unlikely to the extreme that an input AD would be handled as key in a block cipher. So including it into the AD should not make most algorithms insecure either. I'm still slightly worried about the internal MAC algorithm though; it could be that there is a weird mathematical relation that could be exploited; I don't think there is any specific requirement to avoid that.

Generally however I would not treat a key as data. That's probably more dangerous and tricky design-wise. Keys might be stored in containers that don't make the data available (e.g. in a hardware keystore or TPM). Even if you do not plan to use protected keys right now, it would exclude this option in the future.

So what other options are there:

  1. Include the ciphertext of the wrapped key as AEAD data. That way the key is double protected. However, if you use the wrong mode (such as counter mode) then an attacker could make bitwise changes in the key and additional data, which would make me a bit uncomfortable. So I'd use a key wrapping mode designed for the purpose in that case or fall back on CBC with a zero IV (yuk). That should not give the attacker much control over the key value.

  2. Instead of wrapping the keys, derive the keys using key derivation data (e.g. label / info / sequence counter / salt) stored with the ciphertext. If you want you can then include the stored key derivation data in the AD. This has the drawback that you cannot directly use random keys (generated locally) to encrypt the data.

Conclusion: I would be more worried about how you wrap or derive the keys used with the data. Including the derived keys themselves in the AD is a bad idea, but you could include other data such as the ciphertext or derivation data within the AD and make it harder for an adversary to create a wrapped key / ciphertext combination.


In addition to the special wrapping mode I would also recommend using 256 bit keys to avoid multi-target attacks. Using a special wrapping mode or key derivation would protect against related key attacks. With this kind of use case you might also have to worry about changes in files and adversaries swapping ciphertext contents of files.

$\endgroup$
3
  • $\begingroup$ As always, hoping for a more mathematical inspired answer from our more mathematically inclined users. For one, I guess a special AEAD cipher that performs badly under the given circumstances could be created, proving that there are dangers. If that's not possible then that could maybe be proven. $\endgroup$
    – Maarten Bodewes
    Jul 1, 2021 at 7:41
  • 1
    $\begingroup$ "If it was possible for an AEAD cipher to validate when the wrong key was used then I guess the cipher would be considered insecure." AES-GCM, AES-GCM-SIV, and ChaCha20-Poly1305 are all non-key-committing, it's possible to construct a message that validates under multiple keys. $\endgroup$ Jul 1, 2021 at 17:11
  • $\begingroup$ OK, I might have written that incorrectly as it would be a random key, the attacker cannot just include the key that they wish; they only have the ciphertext. Changed the answer to reflect that, thanks. $\endgroup$
    – Maarten Bodewes
    Jul 1, 2021 at 21:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.