TL;DR

Assuring the authenticity of the data that is pulled from web2 servers is an important task for the next phases of the Lido project. For the first phase, we check the existing solutions such as DECO, TLSNotary, and TLS-N. We examined the DECO and TLS-N protocol in separate notes.

TLSNotary is a protocol that allows a user (Requester) to prove to a verifier (Notary) that he interacted with a certain Server and that the transcript between them was not altered. It is a modified version of the standard TLS protocol.

The main idea of the TLSNotary protocol is to split the session keys of the client into two parts, and the Requester and the Notary participate in a two-party computation (2PC) with their key shares to jointly communicate with the server. Neither the Requester nor the Notary knows the session keys. They only have shares of them.

The first version of TLSNotary released in 2014 [1] only supports TLS 1.1 and older versions. However, we see that the TLSNotary protocol is updated so that it supports TLS 1.2 and newer versions.

Preliminary

There are three parties in the TLSNotary protocol, i.e. Requester, Notary, and Server.

The Requester

It is the party that interacts with the Server through a TLS session. The Requester can encrypt a request with a session key, and send it to the Server. Upon receiving the encrypted response from the Server, the Requester gets help from the Notary to decrypt it. Only the Requester can see the decrypted data.

The Notary

It is the party that the Requester aims to convince. He holds partial session keys, and he participates in two-party computation (2PC) with the Requester to achieve the TLS session. He doesn’t see the decrypted response of the Server, but he has a commitment to the decrypted data.

The Server

It is a standard party in a TLS session. It can be any server supporting TLS protocol. The protocol is transparent to the Server, i.e. the Server cannot distinguish whether it interacts with a client for a standard TLS or a TLSNotary session.

TLSNotary

First, we see the general workflow in the below figure, then we’ll describe each building block in the next sections.

Transcript

The Transcript is a collection of data that includes metadata, handshake data, and the commitments to the requests and the responses. If the Notary is not the verifier, the Notary is required to sign the Transcript to present it to a verifier.

Key Exchange

In all versions of the TLS protocol, the session keys are obtained by a key exchange protocol. To that end, the Server, the Requester, and the Notary participate in the below Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol. Assume that $\mathbb{G}$ is an elliptic curve group with prime order $q$ and generator $G$.

The 3-party ECDH protocol between the Server, the Requester, and the Notary results in Pre-master Secret (PMS) shares for the Requester and the Notary as follows:

1. The Server sends its public key $Q_s$ to the Requester, and the Requester sends it to the Notary.

2. The Requester picks a random private key $d_r$, and computes his public key $Q_r = d_rG$

3. The Notary also picks a random private key $d_n$, and computes his public key $Q_n = d_nG$

4. The Notary sends his public key $Q_n$ to the Requester.

5. The Requester computes the client public key $Q_c = Q_r + Q_n$, and sends it to the Server.

6. The Requester computes the elliptic curve point $(x_r, y_r)=d_rQ_s$

7. The Notary computes the elliptic curve point $(x_n, y_n)=d_nQ_s$

8. Addition of the elliptic curve points $(x_r, y_r)$ and $(x_n, y_n)$ results in $(x_c, y_c)$, where $x_c$ is the PMS (note that $y_c$ is not used in TLS)

Now the goal is to compute $x_c = \Big(\frac{y_n - y_r}{x_n - x_r}\Big)^2 - x_r - x_n$ by a secure two-party computation.

To do that, an M2A (multiplicative-to-additive) and A2M (additive-to-multiplicative) protocols from [7] are used.

• Apply A2M to $y_n + (-y_r)$ and obtain $A_nA_r$.

• Apply A2M to $x_n + (-x_r)$ and obtain $B_nB_r$.

• Now we can rewrite $x_r$ as
  • $x_c = (\frac{A_n}{B_n})^2(\frac{A_r}{B_r})^2 - x_r - x_n$,
  • $(\frac{A_n}{B_n})^2$ can be computed by the Notary, he obtains $C_n$,
  • $(\frac{A_r}{B_r})^2$ can be computed by the Requester, he obtains $C_r$.

• Now we have $x_c = C_nC_r - x_r - x_n$.

• Now apply M2A to $C_nC_r$ to obtain $D_n + D_r$.

• We have $x_c = (D_n-x_n) + (D_r-x_r)$

• The PMS share of the Notary is $(D_n - x_n)$

• The PMS share of the Requester is $(D_r - x_r)$

Key derivation

The Requester and the Notary must run the PRF -a secure 2PC- with their PMS shares as inputs

• to compute the symmetric keys that will be used in communication with the Server, and

• to compute the verify_data for the Client_Finished $(CF)$ and the Server_Finished $(SF)$ messages.

The PRF function is computed via an $HMAC$ as follows:

1. The Requester and the Notary participate in a 2PC to compute a PRF (see the above equation) that outputs the master secret $MS$.

2. Using $MS$ as the input, they compute their expanded key shares by 2PC.

3. Upon having expanded key shares, the Requester and the Notary jointly compute the $CF$ message and the verify_data that depends on random seeds, $MS$, and the $SHA256$ hash of the handshake data up to this point. (see the below code)

   # (handshake_hash) is a sha256 hash of all TLS handshake messages up to this point
   
   seed = str.encode('client finished') + handshake_hash
   a0 = seed
   a1 = hmac.new(ms, a0, hashlib.sha256).digest()
   p1 = hmac.new(ms, a1+seed, hashlib.sha256).digest()
   verify_data = p1[:12]

4. Then the Requester proceeds to encrypt and authenticate the verify_data and sends it to the Server.

5. Once the Requester receives the $SF$ from the Server, the Requester and the Notary jointly compute the verify_data for $SF$.

6. They proceed to decrypt and authenticate the $SF$ data in 2PC. Then the Requester checks whether theverify_data that they compute matches the decrypted one.

We skip the details on 2PC. For further information please see here.

Commitment

At the end of the TLSNotary protocol, the Requester has some encrypted data (AES ciphertext). Although this may also be seen as a commitment to a plaintext, this kind of commitment is not flexible enough, especially for cases when a Requester wants to partially reveal the plaintext.

So, how can a Requester transform the ciphertext into a commitment?

It is stated in the documents that proving the decryption in zero-knowledge is not the computationally cheapest way to do that. For the same purpose, two approaches are proposed:

1. Decrypting the ciphertext with Garbled Circuits and producing a hash commitment to the wire labels. (useful for committing to the data to be made public)

2. Producing a Poseidon hash over the private data (useful for proving the statements about some private data in zero-knowledge)

We skip the details. For further information please see here.

Implementation

• In 2015, the first version of PageSigner, which is a Chrome extension for the TLSNotary client side, was announced.

• In 2020, PageSigner v.2 (supporting TLS 1.2) was announced.

• On November 21, 2021, Pagesigner v.3 was announced. (supporting TLS 1.2+)

Comparison of DECO and TLSNotary

Both protocols seem to be WIP, they haven’t been released yet. We compare them according to the DECO paper and TLSNotary sources in the references. Note that the TLSNotary documentation and GitHub repositories are not very clear to compare it to the DECO paper.

TLSNotary and DECO protocols have the same functionalities, and they use the same building blocks such as garbled-circuits protocols [13], A2M (Additive-to-multiplicative), M2A (multiplicative-to-additive) share conversion protocols [7][14], etc., for achieving those functionalities.

We give some possible differences below:

• Both protocols support the AES cipher in two modes: CBC-HMAC and GCM.

• For the premaster secret share generation
  • The DECO paper proposes to use the M2A protocol using Paillier homomorphic encryption in [14], and The TLSNotary documents propose to use A2M and M2A protocol implementations from [7].
  • For the CBC-HMAC cipher suit, DECO paper proposes to split the MAC key into two parts, for the prover and the verifier, and the encryption key is directly given to the prover. However, the TLSNotary documents do not specify the encryption key and the MAC key clearly.
  • For the AES GCM cipher suit, both protocols proceed similarly.

• DECO paper uses garbled circuit protocol from [13]. TLSNotary proposes to use the Dual Execution protocol [15] as 2PC HMAC computations.

• For encryption of the client’s query and the decryption of the server’s response
  • For the CBC-HMAC cipher suit,
    • DECO paper proposes to generate the tag with a 2PC of HMAC, but the encryption is done by only the prover.
    • TLSNotary documents do not specify how it is done. According to the figure on the GitHub page, both encryption and decryption are performed by a 2PC.
  • For the AES GCM cipher suit,
    • DECO paper proposes to use the 2PC AES protocol
    • On the other hand, the TLSNotary GitHub page states that encryption is computed via 2PC, but it doesn’t give details.

• For committing the data and the proof generation,
  • the DECO paper proposes to use a technique called selective opening that allows the prover to efficiently reveal or redact substrings in plaintext. The main idea is to prove in zero-knowledge that the last three blocks of ciphertext are the encrypted tag data.
  • On the other hand, TLSNotary documents state that proving the decryption of the ciphertext in zero-knowledge is computationally expensive. Instead, it proposes
    • to decrypt the ciphertext with garbled circuits and produce a hash commitment to the wire labels. (useful for committing to the data to be made public)
    • to produce a Poseidon hash over the private data (useful for proving the statements about some private data in zero-knowledge)

• Security:
  • DECO protocol UC-securely realizes $\mathcal{F}_{Oracle}$ in the $(\mathcal{F}_{2PC}, \mathcal{F}_{ZK})$-hybrid world, against a static malicious adversary with abort. See Theorem 4.1 in the DECO paper.
  • We couldn't see any adversarial assumption or security analysis in the TLSNotary documents.

References

1. https://github.com/tlsnotary/tlsnotary/blob/master/src/documentation/TLSNotary.pdf

2. https://github.com/tlsnotary

3. https://github.com/tlsnotary/tlsnotary

4. https://tlsnotary.github.io/docs-mdbook/

5. https://tlsnotary.org/TLSNotary.pdf

6. https://en.wikipedia.org/wiki/Elliptic-curve_Diffie–Hellman

7. Efficient Secure Two-Party Exponentiation https://www.cs.umd.edu/~fenghao/paper/modexp.pdf

8. https://en.wikipedia.org/wiki/Garbled_circuit

9. POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems https://eprint.iacr.org/2019/458.pdf

10. https://old.tlsnotary.org/wp/?p=8

11. https://www.rfc-editor.org/rfc/rfc5246#section-1.2

12. Hubert Ritzdorf, Karl Wüst, Arthur Gervais, Guillaume Felley, and Srdjan Čapkun. 2018. TLS-N: Non-repudiation over TLS Enabling Ubiquitous Content Signing.. In NDSS https://eprint.iacr.org/2017/578.pdf

13. Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017. Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation. In ACM CCS. https://eprint.iacr.org/2017/030

14. Rosario Gennaro and Steven Goldfeder. 2018. Fast multiparty threshold ECDSA with fast trustless setup. In ACM CCS. https://eprint.iacr.org/2019/114.pdf

15. A Pragmatic Introduction to Secure Multi-Party Computation https://securecomputation.org/docs/pragmaticmpc.pdf

16. Aug 2019. (Bristol Format) Circuits of Basic Functions Suitable For MPC. https://homes.esat.kuleuven.be/~nsmart/MPC/old-circuits.html.