MPC TLS Handshake: How many parties can AES encrypt in under 10s?

[Jonas Metzger]

Hi everyone,

I'm trying to figure out if there's a way to replace the AWS instance in TLSNotary/pagesigner (https://tlsnotary.org/) that acts as a "Notary" with a group of nodes that jointly perform the TLS handshake with a server.

The TLS handshake creates a shared secret between client and server via a DH key exchange, from which it creates the symmetric key for AES, which is subsequently used to enchrypt all messages.

TLSNotary introduces the "notary" as middleman, which essentially performs the handshake in lieu of the client, asks the client to commit to a hash of the AES encrypted server response before sharing the secret with the client, and signs that hash. This signature allows the client to prove (to anyone who trusts that the notary did not share the secret with the client before signing the hash) that they actually got a certain response from the server. I'd like to replace the notary with a group of notaries, trusting only 1 of n that they don't share their secret with the client before signing the hash.

The DH exchange part of the handshake seems easy to do via MPC because generating the public key can be done before the client even initiates the handshake with the server.

The problem is that in TLS, after the DH exchange, the server will only send the desired AES encrypted response after the client sends a short "finished" message containing the hash of the previous handshake messages, AES encrypted using the shared secret. The handshake needs to complete within 10s however.

So my question is, how long would it take for 1) the client to send the "finished" message, along with the servers public key to the group of notaries, then 2) the notaries performing a MPC to obtain the DH shared secret from their private key and the server's public key and use it to AES enchrypt the client's "finished" message, then 3) send it back to the client?

How many notaries could be used for the whole process to take less than 10s?

Thanks a lot!

Jonas

[Nigel Smart]

Sorry, we dont know specific answers like this. Suggest you do some timings
of the AES algorithm with the desired access structure from within the
system.

What you are trying to do is relatively complex, but not impossible.

Does not the finish message also include the key material, so you need to
compute the finish message also in MPC do you not?

Also you need to compute the hash of the DH exchange in MPC in order
to derive the key as well.

So there are lots of symmetric functions you will need to time

NOTE: SCALE is not really designed for this use case, but you can use
it to get some ball park figures for each operation.

Nigel

[Trieflinger Sven (CR/ADT3)]

Hi Jonas,

 

We recently published a paper on this at the RSA Conference:

 

Damiano Abram, Ivan Damgård, Peter Scholl, Sven Trieflinger:
Oblivious TLS via Multi-party Computation. CT-RSA 2021: 51-74

 

The paper also contains some preliminary high-level performance estimation on an SCALE/MAMBA based implementation. We expect a handshake time of 1 – 2s. But this of course highly depends on the bandwidth and latency of the underlying communication channels between the MPC parties.

 

There is also concurrent work on this by Chen et al.:

 

Weikeng Chen, Ryan Deng, Raluca Ada Popa:
N-for-1 Auth: N-wise Decentralized Authentication via One Authentication. IACR Cryptol. ePrint Arch. 2021: 342 (2021)

 

Hope that helps.

 

Best regards

Sven Trieflinger

SW Platforms and Technologies (CR/ADT3)
Robert Bosch GmbH | Postfach 10 60 50 | 70049 Stuttgart | GERMANY | www.bosch.com
Tel. +49 711 811-24801 | Mobil +49 1525 8813433 | Threema / Threema Work: KP6ZF79J | Sven.Tri...@de.bosch.com

Sitz: Stuttgart, Registergericht: Amtsgericht Stuttgart, HRB 14000;
Aufsichtsratsvorsitzender: Franz Fehrenbach; Geschäftsführung: Dr. Volkmar Denner,
Prof. Dr. Stefan Asenkerschbaumer, Filiz Albrecht, Dr. Christian Fischer, Dr. Stefan Hartung,
Dr. Markus Heyn, Harald Kröger, Rolf Najork
​

--
You received this message because you are subscribed to the Google Groups "SPDZ/SCALE-MAMBA Discussion Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to spdz+uns...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/spdz/80255001-54e5-4b95-8ae1-203e61669c71n%40googlegroups.com.

[Weikeng Chen]

Hi Jonas and Sven,

Thanks to Sven for mentioning our work. A quick conclusion from our paper would be the following:

- Majority of TLS key derivations (via SHA256) and ciphers (AES-GCM seems to be most efficient) are best done in garbled circuits (which SCALE-MAMBA also supports) since they have many rounds (and often latency is quite unavoidable).

- DH handshake can be done in SPDZ-like computation where the native field is the handshake curve's base field, but this field often has a low 2-arity, so that the native SCALE-MAMBA does not work for these curves.

- Although the online latency can be done within 1-2s, there is some sort of offline precomputation needed for each online processing, which can be 7-10s, for n=2 to 5 parties.

From an application perspective, 

- using an AWS instance might actually be a realistic solution, as AWS now provides "software enclaves" called Nitro enclaves, so only AWS can see the data, but not the person/company who runs the instances.

- Microsoft Azure has SGX-enabled instances, which may be the next-step solution for better decentralization.

Thanks,

Weikeng

[Nigel Smart]

Note if you have Q2 access structure then in SCALE we implement
these circuits in a non-constant round model now. So they are
much faster than when doing HSS style GC operations

Nigel

[Weikeng Chen]

Yes, that would make the AES-GCM part faster, as the cipher is combined with the counter mode and can run in parallel easily.

The difficult part is on key derivations where the SHA256 stands there...which is a little bit "roundy" (I just invented a new word)...

and the hash has some dependency on each other, so the latency would become an issue in that case. 

One way is to have the N notary parties set up TLS connections to popular websites beforehand, so the user actually reuses those computations.

(This would mean that users are no longer a part of the multi-party TLS, which actually changes the trust assumption.)

[Nigel Smart]

Good point this "optimization" may depend on your ping time and
"roundiness" of your function being computed as to whether it is
a good idea. This should be easy to turn off though [its a flag
created in SetUp]

Nigel

> --
> You received this message because you are subscribed to the Google
> Groups "SPDZ/SCALE-MAMBA Discussion Group" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to spdz+uns...@googlegroups.com

> <mailto:spdz+uns...@googlegroups.com>.

> To view this discussion on the web, visit

> https://groups.google.com/d/msgid/spdz/af8d1305-2480-4718-a575-635d4f81208bn%40googlegroups.com
> <https://groups.google.com/d/msgid/spdz/af8d1305-2480-4718-a575-635d4f81208bn%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Jonas Metzger]

Hi Nigel, Sven and Weikeng,

Great to meet you all and thank you for this interesting discussion! I'm excited that you made so much progress on this important problem. I believe it enables a very attractive oracle solution for smart contracts, that I'd like to get your thoughts on:

Say the goal is to allow a client to commit to a hash of the AES encrypted website on a blockchain, with a protocol that ensures the client wasn't aware of the TLS secret before doing so. The idea is that the client can at any later point in time submit the information to any smart contract, which can then verify its integrity. If we are fine with hard-coding the public keys of a specific AWS/Azure instance (with Nitro or a TEE) into the contract, and we trust that it won't be shut down by the owner or cloud provider, then we can basically use the already existing TLSNotary/PageSigner service. (As a hobby project, I currently build a tool that allows any contract on Ethereum to verify the PageSigner signature and process the signed data using Truebit). As Weikeng suggested, adding MPC to this would add some m-of-n fault tolerance in case some of the instances are shut down.

But I think the MPC TLS protocol could enable a more attractive solution in terms of trust assumptions, where we don't have to assume the permanence of the AWS instance during contract deployment and where anyone skeptical about the process could become the 1 in the 1-of-N trust assumption that ensures the client doesn't know the secret. Anyone could put a deposit into a "Notary Contract" to become a notary node. This process also allows us to register any set of AWS instances, which can even be updated in the future. Then a client requests a new TLS attestation by putting down another deposit. A committee of N nodes (where N is the largest number of nodes such that the online phase is fast enough for TLS) is randomly selected and performs any necessary preprocessing for the TLS MPC off-chain. If a privacy guarantee is desired, the client could be part of the committee. The client interacts with the server and the MPC participants in a way that ensures the TLS handshake is completed without knowing the TLS secret and even without sharing the content of the website with the committee (this is the only part that has to happen quickly). Afterwards, the MPC parties reveal the secret to the client, and there's some on-chain resolution process using the deposits to disincentivize malicious participants from sabotaging the handshake.

This isn't meant for recurring, real-time data feeds (where you can hire and trust Chainlink nodes to perform your custom but recurring query), but for the case where e.g. two parties want to write a contract about a one-time, future event published on a trusted https website (e.g. earthquake or tornado insurance, a bet on a newspaper headline, etc), with minimal trust assumptions and without requiring any custom behavior from the notary nodes for different queries.

Does this sound feasible (and useful) to you? Thanks a lot!

Jonas

[Jonas Metzger]

Dear Sven and Weikeng,

Do either of you have code implementing some form of TLS MPC that you'd be willing to share?

Thanks a lot!

Jonas

[Weikeng Chen]

Our implementation has not been fully ready. But we have released some of the circuits: https://github.com/n-for-1-auth/circuits

The application that you are referring to seems to be closely related to DECO: https://www.deco.works/

[Jonas Metzger]

Thank you for sharing your repo! Could you quickly describe which parts are missing for a full TLS handshake? It looks like the primitives for an appropriate TLS cipher spec are all there, right? Is the problem how to bundle up the parts in a way that’s performant?

 

I’m familiar with DECO and look forward to its release. My main issue is that no DECO code is available yet and Chainlink could not provide a release date so far. At a theoretical level, it also relies on the assumption that the majority of oracle nodes are honest (each perform a TLS 2PC with the client). If it’s feasible for multiple nodes to partake in a joint MPC, then it would suffice to only trust one party, rather than a majority, which I’d find much more attractive.

--
You received this message because you are subscribed to a topic in the Google Groups "SPDZ/SCALE-MAMBA Discussion Group" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/spdz/g-pNz4s8GGE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to spdz+uns...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/spdz/a38aad60-c349-4913-b3e2-8050ac19eadan%40googlegroups.com.

 

[Damiano Abram]

Hey,

Oblivious TLS is very similar to DECO (they are concurrent work) but supports any number of parties. Security is guaranteed as long as one player is honest.

I agree with Weikeng's estimations of performance in the 2-party case. Regarding the Offline phase, it is true that LWE-based constructions don't really suit the field on which the DH curves are defined. However, OT-based and Ring-LPN-based triple generations don't suffer from the same problem (I'm not sure whether SCALE-MAMBA supports them, though). Regarding AES encryption, we also considered an alternative approach to GC, namely the one described in

Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquez, and Srinivas Vivek, "Faster Secure Multi-Party Computation of AES and DES Using Lookup Tables", ePrint 2017/378.

The protocol relies on a rather heavy preprocessing phase but has a very light online phase (if I recall well, GC has a lower round complexity but higher computational complexity).

In Oblivious TLS, we just estimated the performance by means of tests and experiments, so there is no proper implementation. I think I have a description of the circuits I used for the key derivation somewhere, but they are essentially a messier version of the ones in Weikeng's repository.

Best regards

Damiano