# Secure and efficient encryption of a continuous data stream on behalf of a third party using asymmetric cryptography

I want to design an API-based system that is able to securely encrypt a stream of data received on behalf of an external user in such a way that the data can only be decrypted using a secret that only the user knows (i.e. after encrypting the data, the server itself would not be able to decrypt it again). Naturally, my first thought was to use asymmetric cryptography for this:

• The server would generate a private/public key pair (e.g. using RSA)
• The private key would be securely handed to the user and erased from the server, the public key would be stored on the server.
• When new data arrives for the user, the server would generate a random key for a symmetric encryption scheme (e.g. AES) and use this key to encrypt the data. It would then use the users public key to encrypt the symmetric key and store it together with the data on the server.
• The user could then decrypt the data by downloading the encrypted data with the corresponding encrypted symmetric keys, decrypting the symmetric keys using his/her private key and finally decrypting the data using the decrypted symmetric keys.

The main challenge is that the data which is received on behalf of the user consists of many small packages that arrive continuously over time. In order to encrypt them following this scheme it would thus be necessary to generate and encrypt a new symmetric key each time a new data package arrives, which is doable. However, the decryption of the data could become very inefficient, as the decryption of an RSA-2048 encrypted message can take several milliseconds on modern hardware, so if there are many thousands or even millions of messages for a single user, their decryption could take hours.

I therefore have two questions:

• Is this a reasonable scheme? If now, which elements are missing or would be advisable to implement in addition (HMAC, signing, ...)?
• Is there any way to increase the efficiency of the decryption process, preferably one that does not involve storing the symmetric key on the server over an extended period (which would be a security risk)?

## Edit

The user does not upload the data, it is generated by a third-party on behalf of the user. The motivation behind the scheme is to provide the third party with a secure, asynchronous channel to store data that a user could securely pick up at a later point in time. The assumption is that the third party is not able or willing to provide the infrastructure for this by themselves and instead want to use an external service.

• If I am user, how I can trust you? Maybe you not erased private key. Maybe you will remember symmetric key. This scheme doesn't make sense for me. And why do you need new symmetric key every time? You can use single one. Aug 20, 2017 at 18:19
• That's a valid point, the user could of course generate his/her own private key and just provide the public key. Here I would assume though that there is trust between the user and the service provider (as well as the third party) and that the main motivation for encrypting the data is to protect it against theft or accidental leakage, and to reduce the resulting risk for the service provider. Aug 20, 2017 at 20:14
• Such scheme doesn't protect against theft. If I am theft/hacker, I can hack your server and modify code, and then, I will have access to private keys. Scheme will reduce risks in some cases, but not in general case. Aug 20, 2017 at 21:31
• Assume the attacker will compromise the server.
– zaph
Aug 22, 2017 at 19:59
• It looks like the information flow is: User1 uploads information to server, server encrypts the data, server stores the data, server forgets data and key, User1 downloads cryptogram from server, User1 decrypts. If User1 can decrypt, why can't they encrypt? Normally the User should encrypt the data before uploading it to the server. It is not cryptographically possible to ensure that the server (or any agent) forgets any information, so usually we don't give it the information to begin with (unless it is already encrypted of course). Aug 23, 2017 at 19:23

Let's start with most important piece that is only in comment, what we are protecting against:

main motivation for encrypting the data is to protect it against theft or accidental leakage, and to reduce the resulting risk for the service provider.

Accidental leakage is not threat really, since we cannot stop just leaking current data and your server won't decrypt unless someone tells it to. So let's mainly consider theft and let's try to optimize for user decryption, not encryption (but probably this is next thing we want to do).

Is there any way to increase the efficiency of the decryption process, preferably one that does not involve storing the symmetric key on the server over an extended period (which would be a security risk)?

Assume that your server was hacked. How exactly would you be able to pinpoint infection time? Would 5 minutes of key life-time really hurt? I'd say no, so let's assume that it is maximum time we want our data to lay unencrypted.

Also we don't focus on choosing algorithms here, so let's assume RSA,AES and generic KDF.

I'd go with something along:

2. Split K1 into two using KDF: K1A and K1B
3. Encrypt message with key K1A (you probably want to use HMAC or AEAD scheme here, we don't want compromised/faulty server to serve random data). How much messages to save with one key is up to you (I'd argue that 5min is good, but configure to your liking).
4. Generate new key K2 and save: K1B xor K2.
5. Forget K1,K1A,K1B and Make K1:=K2.
6. Wait for next packet to encrypt to arrive. You can forget key at any point and just start with brand new one (at cost of asymmetric operation)

This gives attacker ability to view new data if he had compromised server at any point and never fully changed K1. This isn't really too bad, because you can enforce periodic changes and if server is compromised then everything is lost anyway.

As for performance it doesn't give perfect parallelization on either side. But multiple servers can operate on multiple keys at once (if data would be marked which key is used). For user this gives parallelization for each RSA bunch (you can decrypt all bunches at once, given enough cores). And inside bunches we only use symmetric crypto, but without parallelization between messages. So this could theoretically use only 1 new RSA-secured key daily or monthly without compromising security behind, only forward (at cost of parallelization).

Is this a reasonable scheme? If now, which elements are missing or would be advisable to implement in addition (HMAC, signing, ...)?

HMAC or AEAD is always good and not too costly. I don't see reasons to sign here. But you might want to hire someone to help you with that, since security is not easy thing.

The private key would be securely handed to the user and erased from the server, the public key would be stored on the server.

Please don't. Ignoring "securely handing", this puts more risk than is necessary.

• I'm happy to award you the bounty as it is the only answer that actually addresses the performance aspect of the encryption scheme in a way that was intended (i.e. not making any assumptions about the timing of the incoming data). I'll happily give you an upvote as soon as my reputation allows it as well. Aug 28, 2017 at 7:57

$\DeclareMathOperator{\X}{X25519}\DeclareMathOperator{\H}{HSalsa20}$Here is a candidate protocol.

I have amended the obviously insensible criterion of having the server hand the user a secret key. Since you haven't identified your specific performance constraints—how many CPU cycles, nanoseconds, or joules are available in your budget for cryptography per data record, on average and/or in the worst case, for the user and the server?—I picked a widely available, widely accepted composition of specific cryptographic primitives: NaCl crypto_box_curve25519xsalsa20poly1305.

Setup. The user generates an X25519 secret $u$ and public key $U = \X(u, \underline{9})$, using NaCl crypto_box_keypair, and configures server with $U$.

Data arrival. On receipt of a set $\{d_0, d_1, \dots, d_{n-1}\}$ of $n$ data records of bounded length at time $t$, the server

1. generates an X25519 secret $s_t$ and a public key $S_t = \X(s_t, \underline{9})$ using NaCl crypto_box_keypair;
2. computes the shared secret $k_t = \H(\X(s_t, U))$ using NaCl crypto_box_beforenm;
3. authenticates and encrypts each record $d_i$ with XSalsa20-Poly1305 under key $k_t$ and nonce $i$ giving authenticated ciphertext $c_i$ using NaCl crypto_box_afternm;
4. transmits $(S_t, i, c_i)$ to the user for each $i$, which adds 32 + 8 + 16 = 56 bytes of overhead per message; and
5. erases $k_t$, $s_t$, and each $d_i$.

Data usage. On receipt of a tuple $(S_t', i', c_i')$, the user

1. retrieves a cached shared secret $k_t'$ for public key $S_t'$, or computes the shared secret $k_t' = \H(\X(u, S_t'))$ using NaCl crypto_box_beforenm and caches it for subsequent records with $S_t'$;
2. verifies and decrypts the ciphertext $c_i'$ with XSalsa20-Poly1305 under key $k_t'$ and nonce $i'$—or rejects it if a forgery—giving record $d_i'$ if not forged, using crypto_box_open_afternm; and
3. processes the record $d_i'$.

(The prime marks are a reminder that what the user receives may be a forgery, not what the server transmitted. The standard adversary can of course generate their own public key altogether and forge messages using that with wild abandon, but can't selectively modify messages transmitted by the server. See the caveats below.)

Cost. The main cost is the $\X(a, B)$ calculation, which is very roughly about half a million CPU cycles on typical widely available hardware, or half a millisecond at 1 GHz. See https://bench.cr.yp.to/impl-dh/curve25519.html for more detailed measurements on specific hardware, and https://bench.cr.yp.to/results-dh.html for comparison of different DH functions (warning: not all DH functions listed there have the same security level or defense against side channel attacks).

Sharing the key between multiple data records, and caching it when processing nearby data records, may significantly reduce the time and/or energy cost—under certain usage patterns.

Can the server work on records in batches, or must it lose its ability to decrypt each individual record the moment it transmits that record to the user? If the largest batch of records the server can sensibly ingest is $n = 1$, then you can simplify the protocol but there's no faster option short of picking a different DH function or KEM, which will invariably be less widely adopted, such as FourQ. But if the server can work on larger batches, then it can save time and/or energy by reusing each shared secret for multiple records.

If the server can work in batches, does the user process nearby records together, or are the access patterns uniformly distributed? If the user processes nearby records, then the user can save time and/or energy by caching the shared secrets in a memo table and skipping X25519 computations.

Note that if the user processes records strictly sequentially, then you can save much more time and energy by eliding the public-key business altogether with a method left as an exercise for the reader.

Caveats.

• Don't use the same key material for anything else. If you are tempted to do so, study domain separation.

• The standard adversary—who can adaptively control the data and control the channel from server to user—can't decrypt records or partially modify records, but can forge completely new records, and can block records of their choice, and can waste the user's memory up to the longest data record size by transmitting an attempted forgery of that size. It is left as an exercise for the reader to identify exactly what potentially relevant security properties this protocol does and doesn't provide.

Payment. Please send payment for this cryptography engineering consulting work to

Mx. Squeamish Ossifrage
Room 641A
521 Mersenne Curve
Anytown, ST 25519
Untied Steaks of Armorica

• Thanks for this thorough answer, since I gave up all my reputation for the bounty I cannot upvote it now but will do so as soon as I have amassed enough points. It seems that your method still would use a new asymmetrically encrypted key for each data entry / batch, correct? Aug 24, 2017 at 8:09
• @ThePhysicist you possibly should check my answer which has protocol that removes need to asymetric crypto on each message, at cost of forward security. I hate to bring that but that's all I can do when my answer is fairly hidden. Aug 24, 2017 at 11:10
• @ThePhysicist: Correct. You can interpret ‘batch’ however you like—you can dribble out records incrementally: handle $d_0$, and then wait, and then handle $d_1$, and so on, and then once in a while generate a new server key pair $(s_{t'}, S_{t'})$ at time $t'$. Each record requires no public-key operations once you've already computed $S_t$ and $k_t$. The salient point of batches is that when you erase the keys $s_t$ and $k_t$, the server can no longer decrypt past messages it has sent. This is sometimes glibly referred to as ‘forward secrecy’, a term that obscures when it happens. Aug 24, 2017 at 13:07
1. Any hybrid cryptosystem would be a resonable scheme for your application, that's for sure. You may like to check out the ECIES algorithms.

Use authenticated encryption to encrypt the data, leave enough room for the integrity tag, which who knows might turn out to be useful someday.

2. Generate a symmetric master key, then use a KDF (key derivation function) with moderate number of rounds to derive the actual symmetric encryption subkeys - You only encrypt the master key once using RSA, encryption keys are derived from the master key and some serial number.

Regenerate new master keys periodically for each new session.

3. Follow up to 2, alternatively, you can generate new keys from previous keys within the same session using one-way KDFs (which are most ones). This way, you can discard old keys once they're not needed, and old keys cannot be easily recovered by the server.

• Key derivation was an idea that I considered, but it was not clear to me how one could derive the subsequent keys without having knowledge of the master key (my understanding is that if I am able to calculate one derived key I would also be able to calculate previous derived keys, thereby allowing me to decrypt earlier messages in violation with the proposed constraint)? Can you elaborate on this? Also, how would I regenerate new master keys without knowing the users private key? Aug 23, 2017 at 10:05