Security of McCallum-Relyea exchange

Question

I recently learned of the McCallum-Relyea exchange which allows for a method of key escrow without actually transmitting the key.

It was developed at RedHat and is used by the tang and clevis utilities (and further described here) to allow for automated decryption, in particular for an encrypted root partition for Linux machines. So a client machine could only boot and decrypt its disk if it is on a network where it can access the server machine.

I haven't found any analysis of this protocol so I was wondering what level of security it offers compared to a more conventional method such as the server storing the key and transmitting it over a TLS channel, and also if there are any flaws in the exchange that might be exploited.

---

The exchange is a modified / extended version of ECDH which functions as follows:

The server side first generates a long-lived EC key pair with private key $s$ and public key $S = [s]G$.

The client, wanting to protect a message $M$, generates private key $c$ and public key $C = [c]G$. The client then requests a key from the server over a plaintext channel. The server responds with $S$ signed with $s$. The client-side user validates the server key via some out-of-band method and records the hash of the server key. The client then performs half of an ECDH exchange to yield $K = [c]S = [cs]G$. $K$ is then used (either directly or indirectly) to encrypt $M$ via a symmetric cipher, after which the client discards $K$ and $c$ and retains only $C$. At this point, the client is unable to decrypt $M$ without the server.

When the client wants to decrypt $M$, it creates an ephemeral keypair $e$ and $E = [e]G$, then calculates $X = C + E$ and sends $X$ to the server. The server then performs half of an ECDH exchange with $X$ and $s$ to generate $Y = [s]X$ and transmits $Y$ back to the client, using $S$ to sign the message.

Having received $Y$ from the server and validating the server's signature, the client then performs another ECDH half with $S$ and $e$ to calculate $Z = [e]S$. The client then calculates:

Y - Z = sX - eS 
      = s(C + E) - eS 
      = sC + sE - eS 
      = scG + seG - esG
      = scG
      = K

To recover $K$ and decrypt $M$.

Answer 1

Interestingly, the confidentiality of the scheme is as strong as the confidentiality of $C$ independent of hardness assumptions (apart from the strength of the symmetric cipher and the secure deletion of $K$, $c$ and plaintext). In contrast the server-side store-and-transmit model over TLS relies on the hardness of the TLS key establishment mechanism and its authentication.

If $e$ is selected uniformly at random then $X$ contains zero information about $C$. Note that transmission of $X$ is the only communication by the client in the entire protocol and so represents the only opportunity for a Dolaev-Yao attacker to access information about client-confidential values. The uniformity of $X$ also means that it is impossible for a serve to verify whether a client is requesting escrow for a key to which they legitimately have access and so anyone that does manage to gain knowledge of $C$ can use the protocol to recover $K$.

Decryption without the co-operation of the escrowing server is prevented by the confidentiality of $s$ AND the strength of the computational Diffie-Hellman protocol for the elliptic curve in question (which can be compromised by a quantum attacker, poor parameterisation or a variety of other means) AND also the strength of the authentication scheme used to validate the server's messages. This means that the failure of any of these three protections permits decryption without the server.

The escrowing mechanism can be invoked multiple times without re-encryption as multiple $X$ transmissions will still not contain any information about $C$.

There is no non-repudiation in the system for legitimate users. If I make a query $X$ and later claim that it is associated with a particular $C$ value, this claim cannot be validated. Even if required to reveal $e$, create a secondary $C$ value $C'=C+dG$, in which case the pair $(C,e)$ generates an $X$ that could also be generated by $(C',d+e)$.