persisting sensitive binary data encrypted (+integrity)

Question

[#not_a_crypto_expert]

rather than forming the question by the techniques I'll describe the use case:

I'm persisting blocks of sensitive binary data in a remote store, the communication is secure (lets assume), but the store may not be.

1. The data needs to be sent and stay encrypted on the remote store - it doesn't get decrypted immediately, just stays encrypted until some time when it's needed.
2. The data needs to have proof that it was not altered
3. The data needs to have proof that it came from the source
4. block i+1 should have proof that it is the following block of block i

Putting the last requirement aside for a sec, what I have in mind it the following:

1. Encrypt the data with the user's private key (for authenticity)
2. Encrypt the data with the server's public key (for encryption) with symmetric encryption
3. MAC the ciphertext for integrity
4. Send the encryption + MAC

Thoughts about the above:

1. While I think it has the desired security properties it's an awkward use of symmetric encryption - as the data is not immediately decrypted on the other side, but instead remains encrypted for a long time which will require saving the symmetric secret for a very long time - which I think is not the typical case.

2. If I just replace AES symmetric encryption above with encryption with the server's public key - I'm not sure this preserves the security properties of the MAC then encrypt.

Thanks, Z

Answer 1

There are at least two ways to do this:

1. Using asymmetric encryption. This may be advantegeous if you want to use hardware-enforced keys or something like that. However, such keys tend to be "weak" for long-term storage (in a theoretical sense).
2. Using symmetric encryption. This may be advantegeous as you can easily use a password or a hardware-enforced AES key to do this. However such devices are much rarer than those supporting e.g. RSA.

Now classically you would do the following:

1. Encapsulate the data's symmetric key using asymmetric and / or symmetric encryption and / or key derivation methods.
2. Encrypt each block using said data key and an authenticated encryption mode (e.g. AES-CCM, AES-GCM or AES-EAX), using the index as the nonce.
3. If you use asymmetric encryption: Compute a signature over the complete ciphertext and store it for later verification (because an attacker could use the public key to just replace the data).

Now the data is immune to re-ordering attacks (because the authenticated nonces would miss-match).