Proxying Is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability

In a seminal work, Zhang et al. [33] proposed DECO, which overcomes this practicality barrier without making any changes to the TLS server-side code and using any trusted hardware. The core reason why the client in TLS can forge the TLS data is that the symmetric encryption and authentication key generated in the TLS session is shared by the client and the server (please see Section 2 for more details). DECO [33], essentially splits the role of the client in typical TLS into two parties, as shown in Figure 2(a), so that the client cannot learn the entire symmetric encryption and authentication key. In particular, the client and the verifier collaboratively communicate with the server using secure two-party computation (2PC). Moreover, while the client and the verifier collaborate, it is only the client that communicates with the server as in TLS. We call this design as “2PC-based TLS oracle” protocol. Later, the subsequent works [31, 9, 6] also follow the model.

In addition, Zhang et al. [33] also discussed another design framework, where the verifier acts as a proxy to communicate with the sender but the verifier still needs to perform 2PC with the client, as shown in Figure 2(b). We call this design as “proxy-but-2PC based TLS oracle” protocol. Xie et al. [31] proposed a solution in this model that utilizes a garble-then-prove scheme.

We can see that the previous works all rely on heavy 2PC between the client and the verifier. A natural question is “Is there a secure TLS oracle solution that can totally avoid heavy 2PC between the client and the verifier?”

To answer this question, in this work, we consider a pure proxy-based TLS oracle as shown in Figure 2(c), where the verifier only needs to forward the messages generated by the client and the server, without additionally introducing any heavy computation, which directly implies better performance. In addition, compared with the (proxy-but-)2PC-based TLS oracles, the proxy-based oracle enables better compatibility across different TLS versions, as the verifier only needs to forward messages. Moreover, the proxy-based oracle not only does not modify server-side code but also achieves client-side non-modification.

Given that AEAD (Authenticated Encryption with Associated Data) is the core building block of TLS, we investigate the security of two AEAD schemes, AES-GCM and ChaCha20-Poly1305, which are overwhelmingly used in TLS 1.2/1.3 with an adoption rate of over 99% [29]. Based on the security of AEAD, we systematically conduct an investigation that outlines the boundary between security and insecurity of the proxy-based TLS oracle protocol. Surprisingly, we find that the proxy-based TLS oracle can be securely used in two prevalent situations, HTTPS (see Section 6) and prefixed relevant data (see Section 7).

We observe that in the attack above, client $𝒫$ uses the AEAD key/nonce pair to generate a new ciphertext $c_r^{\prime }\ne c_r$, where $c_r$ is the original ciphertext from server $𝒲$. The essence of previous works [33, 9, 31, 6, 16] is to ensure that client $𝒫$ cannot obtain the complete AEAD key before he commits the message. Our preliminary attempt is to ensure that verifier $𝒱$ can directly obtain the ciphertext $c_r$ from server $𝒲$, such that verifier $𝒱$ can recognize any modifications on the ciphertext $c_r$. To this end, we treat verifier $𝒱$ as a proxy that forwards and records the messages between server $𝒲$ and client $𝒫$, as shown in Figure 3. In this way, the ciphertext $c_r$ cannot be modified by client $𝒫$. Moreover, verifier $𝒱$ records the transcript $𝒯$ generated during the handshake phase. Therefore, client $𝒫$ can provide $(m,(k_r,n_r))$ to verifier $𝒱$ to prove the following three statements: he holds a key/nonce pair $(k_r,n_r)$ that can decrypt $c_r$ to a message $m$; the message $m$ satisfies a preset requirement; the key/nonce pair $(k_r,n_r)$ is derived from the transcript $𝒯$.

Obviously, once obtaining $(m,(k_r,n_r))$, the verifier can verify the first two statements directly²²2Given that HTTP is a stateless protocol, to avoid using the same key the verifier obtained for future rounds of interaction, the client can terminate the current connection with the server and handshake again to restart one. For other protocols, we note that TLS 1.3 supports a key update mechanism (see Footnote 5) that allows us to refresh the key/nonce pair for subsequent communications without needing another handshake.. However, the verifier cannot verify the third statement, since it involves private information (namely, the secret used in Diffie-Hellman Handshake) held by the client (please see Figure 5 for more details). Note that if the client provide the private information used in Diffie-Hellman handshake process to the verifier, the verifier can know all the keys and nonces, and thus the verifier can decrypt the request ciphertext ($c_q$ in Figure 3) to learn the credential.

Using a zero-knowledge proof to prove the third statement is a straightforward way. However, the hash function used in TLS 1.2/1.3 to derive key/nonce is SHA256, which is not SNARK (Succinct Non-interactive Argument Knowledge)-friendly [13]. A concurrent and independent work by Ernstberger [12] have tried to reduce the cost for proving the statement. However, their results showed that the proof for this statement still occupies the cost $90\%$ in the public mode and the cost $60\%$ in the private mode (see Table 1). Therefore, to further reduce the overhead, we delve deeper into the potential of eliminating the proof that the key/nonce pair is derived from the transcript $𝒯$ (i.e., the above statement 3).

As shown by the previous research [10, 1], the AEAD schemes used by TLS do not satisfy the key commitment property (see Lemma 3); an adversary can efficiently construct a ciphertext $c$ and two distinct key/nonce pairs $(k_1,n_1)$ and $(k_2,n_2)$, such that $c$ can be decrypted to two distinct messages $m_1$ and $m_2$ by using $(k_1,n_1)$ and $(k_2,n_2)$ respectively. At first glance, in our proxy-based oracle protocol, client $𝒫$ cannot launch the above attack, since client $𝒫$ seems unable to construct the ciphertext sent by server $𝒲$. However, we observe this is not true, since client $𝒫$ obtains the key/nonce pair $(k,n)$ as soon as completing the handshake phase. Then, client $𝒫$ can construct a ciphertext $c$ such that it can be decrypted into $m$ and $m^{\prime }$ under key/nonce pair $(k,n)$ and another key/nonce pair $(k^{\prime },n^{\prime })$ respectively. Moreover, $m^{\prime }$ meets the predetermined requirement, while $m$ does not. Subsequently, the client can change the record in server $𝒲$ to $m$ through external interactions, so that server $𝒲$ produces and sends the ciphertext $c$. Finally, client $𝒫$ can use $(k^{\prime },n^{\prime })$ to convince verifier $𝒱$ that $m^{\prime }$ satisfying the preset requirement is the corresponding plaintext. For example, if the message is about bank balance, client $𝒫$ can adjust his balance to $m=10$, and then prove that balance $m^{\prime }=1000$ by using $(k^{\prime },n^{\prime })$ (see Section 5).

With Variable Padding. According to the above analysis, we know that key commitment is necessary for a secure proxy-based oracle protocol without proving that the key is derived from a given transcript. Fortunately, we observe that if the plaintext is well-formatted as seen in HTTPS (or more formally, has a variable padding), the adversary cannot break the key commitment. Intuitively, even if the adversary can generate $(c,k,n,m)$ and $(c,k^{\prime },n^{\prime },m^{\prime })$, the probability that $m$ and $m^{\prime }$ are both well-formatted is negligible (see Section 6).

In practice, HTTPS (using TLS on the application layer protocol HTTP) satisfies the above condition, since HTTP headers are variably padded [20]. Therefore, our proxy-based oracle protocol without proving the key origin and 2PC protocols is secure with HTTPS. While HTTPS is one of the most popular protocols and thus the current results are already sufficient to address a wide range of application scenarios, we also discuss if our proxy-based oracle protocol can be securely used for other protocols whose messages are not variably padded.

Without Variable Padding. In the above attack, we assume that client $𝒫$ can arbitrarily modify the record in server $𝒲$. However, in some scenarios (e.g., ages, stock prices and insurance numbers), client $𝒫$ is not able to perform modifications. In these cases, the AEAD used in TLS only needs to satisfy a weaker security property: given a ciphertext $c$, a key/nonce pair $(k,n)$ and the corresponding message $m$, the adversary cannot construct another key/nonce pair $(k^{\prime },n^{\prime })$ such that $c$ can be decrypted to another message $m^{\prime }$. In Section 7, we formally define this security property as context unforgeability (CFY-security) and systematically investigate if the AEADs (including AES-GCM and ChaCha20-Poly1305) used in TLS satisfy this new security property. We prove that AES-GCM does not satisfy the context unforgeability, whereas ChaCha20-Poly1305 does.

Besides designing an efficient proxy-based oracle protocol, our newly proposed security property, context unforgeability, bridges the gap in the security analysis of AEAD, as shown in Figure 5. Interestingly, combined with the previous properties, context commitment³³3The works [10, 15] first proposed the key commitment problem. Then Bellare et al. [2] extended to committing nonce and associated data, and Menda et al. [18] summarized them as context commitment. [10, 15, 18] and context undiscoverability [18], the hierarchical security of AEAD precisely corresponds to the hierarchical security of hash functions.

We use $|m|$ to denote the bit-length of a string $m$, and $m[i:j]$ to represent its substring starting at $i$ ($0$-based) with length $(j-i)$, and $m||n$ to denote the concatenation of strings $m$ and $n$. We represent the set size as $|S|$.

Recall that in key-committing attack (see Definition 2), the adversary (i.e., the client $𝒫$) can generate a ciphertext $c$ and two contexts $(k,n,a)$ and $(k^{\prime },n^{\prime },a)$, where $(k,n)\ne (k^{\prime },n^{\prime })$, such that the ciphertext $c$ can be successfully decrypted under the two contexts. At first glance, the key-committing attack is not applicable to our scenario, as it is the server that generates the response ciphertext $c$. However, since the client $𝒫$ can obtain $(k,n)$ after the handshake phase and the associated data $a$ can be known beforehand according to the specification of TLS [25, 24], the client $𝒫$ can manipulate the data stored by the server through a side channel to build a ciphertext $c$. For instance, the client’s balance in some bank can be manipulated by withdrawing or saving funds. Specifically, we then construct an attacker $𝒜$ that does the following:

$𝒜$ starts the protocol. It starts handshaking with the server $𝒲$ through verifier $𝒱$ to obtain $(k,n)$.

$𝒜$ builds a ciphertext $c$ and another context $(k^{\prime },n^{\prime })\ne (k,n)$, such that $m={\mathrm{𝖣𝖾𝖼}}_k(n,a,c)$ and $m^{\prime }={\mathrm{𝖣𝖾𝖼}}_{k^{\prime }}(n^{\prime },a,c)$ through traditional key commitment attacks (see Lemma 3).

$𝒜$ modifies the server-side data to $m$ via side-channel methods, such that the verifier $𝒱$ receives and records the response ciphertext $c$.

$𝒜$ uses $(k^{\prime },n^{\prime })$ to convince the verifier $𝒱$ that $m^{\prime }$ is the plaintext. $◀$

A real-life attack scenario can also be found in the famous Facebook attack [10]. In the Facebook attack, the attacker constructs a specific ciphertext after the handshake, when it knows the symmetric key that will be used in the communication. It has the server store this ciphertext, which it will decrypt later using a different key other than the one in the handshake.

Nevertheless, not all hope is lost. We observe that the attack in the theorem exploited the fact that the AEAD scheme in TLS is not key-committing. In fact, as we will see in the theorem below, ${\mathrm{\Pi }}_{\mathrm{𝖯𝗋𝗈𝗑𝗒}}$ realizes ${ℱ}_{\mathrm{𝖮𝗋𝖺𝖼𝗅𝖾}}^{\mathrm{𝖲𝗍𝖽}}$ if and only if the underlying AEAD is key-committing.

We refer the readers to Full Version’s Appendix E for proof details.

It is known that a lot of AEAD schemes do not have the most robust commitment security. One prominent example of an exploit is the attack on Facebook Messenger by Dodis et al. [10]. Commitment security on AEAD has received a lot of research since around that time [15, 8]. Menda et al. provided a generalization and analysis on the topic [18], which we leverage in this paper. Albertini et al. analyzed several possible ways to fix popular AEAD schemes [1]. Our work builds and extends on the framework by Menda et al. [18] and gives it a practical scenario. With this toolset, we are able to reason the security of proxying and give concrete security bounds with proof.

Using TLS under multi-party scenarios has been investigated a number of times under different scenarios [19, 3, 14, 27]. TLS oracle protocols have also recently been studied by a variety of academic papers. Earlier results often include modifying the TLS server to some extent and using trusted hardware which are considered not universal [32, 26]. DECO by Zhang et al. [33] in 2020 is one of the first papers that combines a TLS oracle with zero-knowledge proof to preserve user privacy over a general TLS server. Janus by Lauinger et al. [16] demonstrates an efficient two-party computation that optimizes the performance of zero-knowledge proof by the client. A work in a similar direction by Xie et al. [31] uses the garble-then-prove technique instead. DIDO by Chan et al. [9] proposes further optimization based on TLS 1.3. ORIGO [12], an independent and concurrent work of ours, observed that the ZK proof for key derivation can be optimized.

Meanwhile, there is also significant industry effort on this topic. The recent Reclaim Protocol [22] provides an implementation that is based purely on proxying without the three-party handshake but provides no security proof of the integrity of the data. Thus our work is also a theoretical discussion of the industry effort that validates its usage under common scenarios but also points out its limitations.

We observe that the NIZK proof of the protocol does not reveal the key/nonce pair used in the communication. Therefore, our protocol naturally supports the client and the server communicating in multiple rounds after a handshake connection, as in the original TLS.

In practice, when the data do not involve privacy, the client can choose to directly reveal the key/nonce pair and data to the verifier, rather than using the NIZK proof. In this case, since HTTP is a stateless protocol, the client can terminate the connection and handshake again to start a new one for future rounds. Moreover, we note that TLS 1.3 supports a key update mechanism (see Footnote˜5) that allows us to refresh the key/nonce pair for subsequent communications without needing another handshake.

Our protocol does not stop an adversarial client from connecting to the server simultaneously without proxying through the verifier. In fact, when the web server is not restricted in its response, there is an attack using a side channel connection (see Theorem 4), and we prove that the HTTPS response format can be used to defend against the attack. Moreover, in our scenario, the purpose of the client is to have the data obtained from the server validated by the verifier so that the data can be submitted to the blockchain. Therefore, the client has no motivation to bypass the verifier when he tries to acquire the data.

In the main body of the paper, we assumed that the verifier has a trusted connection to the TLS server. Indeed, the problem is not meaningful if the server is not trusted or if there is no trusted way to access the server, since there would not exist any root of trust under this scenario.

Here, we note that if the client can adaptively corrupt the connection between the verifier and the TLS server, it can first establish the connection with the real server and obtain the HTTPS certificate, and then hijack the connection to transmit the message with the master secret it knows. This attack works even if the verifier pins the server certificate in advance, but requires the client to adaptively corrupt the connection.