# Can RSA be securely used for "blind decryption"?

Assume we have the following setup:

• A client with trusted storage and computing capabilities (e.g. a smartcard)
• A server with trusted computing and short-term storage capabilities (e.g. RAM + CPU, possibly with something like Intel SGX). The server has no trusted large-scale long-term storage capabilities and may only store small amounts of data confidential and integrity protected (like the HTTPS private key).

The problem is: The server should be able to be shut-down and started-up, no passwords should be involved and the server has no HSM, yet the server should be able to provide somewhat secure access to some data without the clients needing to decrypt it themselves (for complexity reasons). So the storage need to be encrypted and the transfer (-> TLS) as well.

The solution is now (what I call it): blinded decryption.

The server uses some homomorphic encryption scheme (e.g. EC-ElGamal or RSA) with the message space $\mathcal M$. He chooses a random $k\in \mathcal M$ and uses $H(k)$ ($H:\mathcal M \rightarrow \{0,1\}^{256}$) as the key for the authenticated encryption of the data. The server now either stores the (asymmetric) encryption of $k$, called $\mathcal E(k)$ in his trusted area of the drive(s) or may store it in an untrusted section (with back-ups) if server authentication is required and the private key for this authentication is already stored in the trusted area.

For the temporary unlock of the encrypted data, the server loads $\mathcal E(k)$. Then he blinds it using some operation $f(\cdot,\cdot)$ (multiplication for ElGamal and RSA, addition for EC-ElGamal) using some random $r\in \mathcal M$ as $c=f(\mathcal E(k),\mathcal E(r))=\mathcal E(g(k,r))$ with $g(\cdot,\cdot)$ being the "inner homomorphism" (same as $f$ in many cases). The $r$ is kept available in trusted short-term memory and the $c$ is sent to the client.

The client decrypts $c$ using his trusted device and returns $c'=g(k,r)$ to the server. Finally the server unblinds $c'$ using his $r$ and uses the obtained $k$ to derive $H(k)$ and allow access to the data.

Now (finally) the question:
Given the above and standard assumptions (RSA-assumption, DDH-assumption in ECC and $\mathbb Z_p^*$,$H$ is a random oracle, the symmetric encryption is secure and authenticated,...) is it safe to instantiate $\mathcal E$ with textbook RSA?

As pointed out in the comments, every good question about "is this secure?" requires a threat model, so here's mine:
The security of the whole protocol is broken if an attacker is able to learn the secret symmetric key $H(k)$ while it's valid. The attacker may not compromise the server (i.e. he can't control/spy on RAM / CPU and may not learn the stored $\mathcal E(k)$). An attacker not breaking into the server may have successfully attacked the client (except for the trusted device) and he may be able to completely modify and read the network traffic. I think an attacker without having broken into the server may be computationally unbounded.

If not clear until now, the instantiation of $\mathcal E(k)$ is $\mathcal E(k):=k^e \bmod N$ with $e,N$ being standard RSA parameters.

• $\mathcal E(k)$ is RSA KEM if $\mathcal E$ = RSA, right? So the encryption/decryption should be no issue... Aug 25 '15 at 15:12
• Two observations: a) the scheme relies on $\mathcal E$ being homomorphic, but standard non-textbook RSA is not; thus the scheme does not allow decryption with standard non-textbook RSA, thus its security is moot; first define the variant of RSA you consider for the security analysis. b) define your security goals and threat model, in particular if an adversary impersonating the server to the client (which seems trivial since the server has no credential), or actively eavesdropping connection between actual client and server, are considered a break.
– fgrieu
Aug 26 '15 at 5:50
• @fgrieu a) I don't like it either having to rely on textbook RSA. I want to learn by this question if I could allow fall-back to RSA in case EC-ElGamal isn't an option. The problem is I don't have any other (better) options. I could use an IND-CCA2 scheme and just store the encrypted key on the server, but then the client would have to send the key in clear over the wire (or maybe TLS but the attacker could still break by compromising the client or the server and could still break the protocol with storage theft). I can't afford requiring a HSM($) which would be the most secure solution. – SEJPM Aug 26 '15 at 9:41 • (continued), obviously (lacking better options)$\mathcal E(k):=k^e\bmod N$if we decide to use textbook RSA. b) I've added the security model to the question. In short: the scheme is broken if the attacker learns the key without breaking into the server. – SEJPM Aug 26 '15 at 9:43 • Some notes: It seems the server must store the client's public key in integrity-trusted storage, and$\mathcal E(k)$in integrity+confidentiality-trusted storage, despite the last sentence in second bullet.$\;$The client seems to need to know$H(k)$, and it is not told how; that part of the exchange might interfere with the rest. – fgrieu Aug 26 '15 at 20:21 ## 1 Answer Let's try to simplify and abstract your protocol a bit. Instead of your server and client, we just have two parties, let's call them Sally and Charlie. • Charlie has a key pair$K = (K_i, K_u)$for a suitable asymmetric cryptosystem$\mathcal E$. We assume that this cryptosystem is partially homomorphic, such that$\mathcal E_K(a) \otimes \mathcal E_K(b) = \mathcal E_K(a \odot b)$, where$\otimes$and$\odot$are two group operations. • Sally knows the public half$K_u$of Charlie's key pair, so that she can compute$\mathcal E_K(a)$given a plaintext$a$, but not the private half$K_i$that would let her compute$a$from$\mathcal E_K(a)$. • Sally has a message$\mathcal E_K(m)$encrypted with Charlie's key pair, and wants to decrypt it without revealing the decrypted message$m$to Charlie (or to anyone who might impersonate him). • Charlie wants to help Sally decrypt her message, but does not wish to reveal his private key$K_i$, or anything equivalent to it, to Sally (or to anyone who might impersonate her). The protocol you've suggested amounts to Sally picking a random element$r$uniformly from the group of all possible plaintexts, encrypting it using$K_u$to get$\mathcal E_K(r)$, and sending$\mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$to Charlie. Charlie then decrypts the message, and sends$m \odot r$back to Sally, who applies the group inverse$r^{-1}$of$r$to obtain$m = (m \odot r) \odot r^{-1}$: 1.$S:\ $choose$r$uniformly at random, compute$E_K(r)$and$r^{-1}$; 2.$S \to C:\ \mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$; 3.$C:\ $decrypt$\mathcal E_K(m \odot r)$to get$m \odot r$; 4.$C \to S:\ m \odot r$; 5.$S:\ $compute$m = (m \odot r) \odot r^{-1}$. The first security claim (that Charlie cannot learn$m$) should be easy to prove, regardless of the specific cryptosystem used. Since the plaintexts form a group, and$r$is chosen uniformly at random from that group,$m \cdot r$is also uniformly distributed, and so reveals no information about$m$to anyone who doesn't know$r$. Indeed, even if Sally repeats the protocol with several different random values$r_i$, and so reveals$m \odot r_i$to Charlie, this will give him no additional information as long as all the$r_i$are uniformly chosen and independent of$m$. The tricky part is the second claim, and especially the part about Charlie not revealing "anything equivalent to$K_i$" to Sally. After all, in the protocol as described, Charlie is acting as an unrestricted decryption oracle! It seems to me that, for this protocol to make sense at all, we need at least the following assumptions: • Sally cannot be compromised in any manner that would directly reveal$m$to the attacker; she can only be made to disclose$\mathcal E_K(m)$. • Access to Charlie is strictly limited, so that even if an attacker obtains$\mathcal E_K(m)$, they cannot simply query Charlie for$m$. The latter assumption may indeed make sense in your scenario, where Charlie is physically connected to Sally (and only intermittently so connected, being securely stored at other times), if we also assume that Sally is resistant to active compromise (i.e. she may certain data items, but an attacker cannot modify her behavior). That's a pretty huge assumption in practice, but if you're willing to make it, the protocol described above seems like it should work. (That said, if you're really willing to make all those assumptions, why not simply have Charlie store$m$and provide it directly to Sally upon request? I'm having some trouble coming up with a reasonable attack scenario where that wouldn't be secure, yet the protocol above would be.) • I might well be missing a reasonable use case for this protocol, though; it's getting late here and I really should get some sleep. What does seem clear to me, though, is that the ability to use Charlie as a decryption oracle is a major and rather fundamental security issue here. Aug 26 '15 at 23:22 • The part about Charlie not revealing "anything equivalent to Ki" does not seem so much of a problem to me: although we do not have a proof of that, it is widely accepted that in textbook RSA, temporary access to a decryption oracle can not allows extraction of a private key, or otherwise help the decryption of random messages drawn after access to the decryption oracle has stopped. – fgrieu Aug 27 '15 at 4:38 • I would say that the protocol works, in the sense that if Sally is able to store$\mathcal E(k)$and keep it secret, she can get back to$k$, thus$H(k)$, without revealing these, with the help of Charlie; further, verifying what Charlie returns, which is easy, prevents an active adversary from messing with the recovered$k$.$\;$However I fail to see why the server does not keep$k$or$H(k)$rather than$\mathcal E(k)$; if we assume Charlie does its task without any check or limit in time, that seems to achieve the same result, in a much simpler way. – fgrieu Aug 27 '15 at 4:56 • @IlmariKaronen, if Charlie just sends$m$every time Sally needs it, Charlie knows$m$which increases the attack surface. The point of the protocol is to make the best out of the situation at hand (-> no HSM :( ) So while it would work, it would be "worse" in terms of security than the given protocol. – SEJPM Aug 27 '15 at 8:57 • @fgrieu, the server could just store$H(k)$, but this increases the attack surface as there may be the case as there are (some, not many) cases where the above protocol still is secure whereas simply storing$H(k)\$ would fail (f.ex. if the data is at rest, an attacker breaks the confidentiality but Charlie notices that before accepting any unlock queries and starts re-newing keys)
– SEJPM
Aug 27 '15 at 9:01