MPC-Over-Signal

Omer Shlomovits
Apr 5 · 10 min read

secure communication for all!

Intro

In this blog we show how we use the Signal messenger server to facilitate secure communication over the internet between nodes in a network. We leverage this infrastructure to run a secure multiparty computation (MPC) and specifically to run a threshold BLS signature protocol. Our open source library (written in Rust) utlilizes the existing yet undocumented Signal server API and can be used to build applications with baked-in security and privacy properties.

3 nodes (parties) running 2-out-3 threshold BLS signature using on top of Signal messenger

In this blog we describe the road we took until converging to what we believe is the right solution and give technical details about our code.

The pain

To understand how we resolved to eventually build on Signal, we first need to understand the pain.

There are few notable challenges in building threshold cryptography systems for the real world. In this work we focused on one of them, namely, “secure channels”:

Almost all MPC protocols have a common starting point. They operate in rounds of communication where the basic requirement is for peer 2 peer (p2p) secure channels between each two parties. On top, we can build simple broadcast channels or send direct messages.

Fiber optics is a nice analog to secure channels: information between sender and receiver is carried over light which is trapped inside the fiber (well almost)

What is a secure channel?

A channel is a link between a Sender (Alice) and a Receiver (Bob). The Sender must hold a unique identity known to the Receiver, and vice versa. This can be achieved using a public key infrastructure (PKI), such that each node is identified using its public key, attested by higher level authority. Trust on First Use (TOFU) then verify and web of trust are two decentralized alternatives to PKI.

A secure channel provides secure message transmission; that is, all communication in the link must be encrypted and authenticated. In a secure channel we get a guarantee that no Man-in-the-middle of the channel (Eve) can learn the information passing through the channel (except perhaps for some metadata like message length) or intervene in the communication without being noticed.

For completeness we mention Diffie Hellman key exchange protocol: a simple cryptographic protocol used as the main building block in secure channels. it allows a Sender and a Receiver to agree on a joint secret.

While conceptually simple, the practice of implementing secure channels turns out to be highly non-trivial (see for example the TLS 1.3 RFC) and prone to errors.

Secure channels main use case today is for client-server communication over the internet. This setting can rely naturally on certificate authorities (CA) as plug and play PKI. Working with secure channels in the multiparty/p2p setting is not as common and it is not clear how this setting can work with existing PKIs.

Finally, we note that certain security properties can be added to secure channels; For example, “forward secrecy” property makes sure that a compromised Sender/Receiver will not reveal past messages in the channel. Surprisingly, there is a significant number of security properties that can be added and each combination often results in a bit different key exchange protocols.

Where can I find secure channels ?

Our initial thought followed the paradigm we observed in the MPC literature: secure channels just exist: once we have the MPC protocol, we can just plug it into the most convenient trust mode (i.e. PKI), run some key agreement protocols and start sending encrypted, authenticated, (forward secure, etc.. ) MPC messages.

Sadly this is not as straightforward as we imagined. Let us take a concrete example. SCALE-MAMBA is a general purpose MPC framework. Here is how they handle secure channels (source):

Analyzing the above we observe:

  • Scale-Mamba uses openSSL implementation of TLS, one of the most popular protocol suites for secure channels

As a disclaimer, we note that Scale-Mamba is a research system.

TLS is actually a great choice. It is the protocol of choice for browsers and in general servers and applications in the web. It is highly supported: kind of a language that everyone understands. It is still not solving our problem, as we can see, it is left for the user to figure out how to set up the PKI and leaves a trail of open questions such as who takes the role of the CA and how to maintain the secure channels

A nice hack can be used in the unique case of two party secure computation: one party can play a web server while the other party a client. This is the classical setting of a secure server-client communication used widely across the internet which makes it easy to plug a secure channel based on TLS. Unfortunately, this does not scale well to the multiparty case.

Noise NX protocol (credit: David Wong)

Second try — Noise Framework

TLS is not the only secure channels protocol suite in town. Noise protocol framework is another such one, enabling a true p2p end-to-end (e2e) encryption. The framework is flexible and allows implementers to choose between a set of handshake patterns, all based on Diffie Hellman key exchange and each enables a specific combination of security properties (e.g forward secrecy). Noise is used in certain popular applications, providing e2e encryption, such as the Lightning Network, and WireGuard. This is a good step forward as it seems that Noise is well suited for p2p protocols. Yet, when trying to work with the framework we could not help but feel that the secure channels part of the MPC protocol turned from “should just exist” to a major overhead that requires: separate research, find an appropriate pattern and work with a low level library to implement the pattern. Moreover, some questions still remain unanswered: the trust model question for starters: (in the case of PKI) who is the “certificate authority” here? but also — how to pick the right Noise pattern? What happens if I pick the wrong one? If my secure channels implementation is buggy — how would it impact the MPC?

Finally — Using Signal

Secure channels should be seamless to the user and to the developer. They, indeed, should just exist.

In the landscape of secure channels, unique to Signal specification is the use of a forwarding server in the middle. The idea is to have servers to route messages among peers. This has several benefits. One of them relevant to MPC is collapsing the p2p channels to a single channel per party connected to the server. The downside is that the server, run by a party not participating in the MPC can DoS the protocol.

This design choice is one we followed in our previous iterations of building a communication layer for our MPC protocols:

  • multi-party-ecdsa is a threshold ECDSA implementation where we use a single http server as a relay

Using the server, Signal provides a way to build virtual secure channels between peers such that privacy is kept and the server only observes metadata. Signal uses plain phone numbers as the unique identifier for users. This costs somewhat in privacy as the phone number enters the metadata exposed to the server, but otherwise, provides a remarkable foundation for the decentralized trust model we need: The user will generate its long live public key on first use of Signal and will register it with the server together with the phone number as her unique identity (In Signal messenger the trust model is TOFU then verify).

The Signal specifications spans four different parts:

  1. The digital signature (named XEdDSA), to be used mainly in the key agreement as a way to authenticate sender identity

The combination of these elements provides us with the secure channels we need. The challenge we now face is how to use them in our own application, or any other application besides Signal for that matter. The project we will present next does just that: allowing any application to set up a Signal server and run the app through it, thus, providing the application immediately with e2e encrypted, authenticated (and more) secure channels.

One more thing: If running your own Signal server is not an option, we show in our demo how to use the existing Signal messenger application servers. Our hope is that app developers building on our library will run and maintain their own Signal servers and will even offer them for free for fellow developers in need of testing and running applications with privacy.

In any case, abusing the Signal messenger server to run your application is discouraged. Our code using it is ONLY for demonstration purposes. We fully support the Signal foundation and its cause. Here is how to donate to Signal: https://signal.org/donate/

Signal server code is open source and there are unofficial instructions on deploying it (e.g. here, here).

Our Implementation

We implemented a library that allows to establish secure channels for messaging among nodes using Signal. There is also a demo showing how to use the library to run threshold BLS keygen & signing.

Demo video: https://www.youtube.com/watch?v=G15vGg4cMaU

We now go through the various steps of the Demo explaining the technical details!

Linking with Signal Account

To communicate through Signal, we will need to have a Signal account. In the library we provide only the ability to link with an existing account. Creating a new account is done by downloading Signal messenger.

The linking process is the same as if linking a desktop Signal app: We prompt a QR code and ask to scan it with the phone. No login or password are required.

Note: when running self-hosted Signal server, we need to build a mobile app, unofficial instructions are available (e.g. here).

Linking MPC device

As with Signal for desktop, the QR code contains an ephemeral public key and unique identifier obtained from the server. The mobile app asymmetrically encrypts its Signal keys (identity, profile private keys, etc.) using the public key contained in the QR code and sends it to the new device through Signal forwarding server using the unique identifier included into the QR code.

Using the same unique identifier, the new device receives encrypted keys, and decrypts them using its ephemeral private key. The new device is now equipped with all the secret data it needs to open secure channels. The new device needs to register with the server as a new device, generate pre keys (signed pre key + bunch of one-time pre keys) and register them too (i.e. make a few more API calls). After that, We have got a fully functional device that can send and receive messages!

A few notes worth mentioning:

  1. Our code implements device linking from scratch: technically, we implemented Signal’s SubProtocol and reversed engineered the provision message encryption algorithm.

Messaging

Before we can actually start messaging, the parties must exchange their public identities. In the demo, this is done by sending a list of addresses out-of-band.

Once we have got a linked device, sending and receiving messages is straightforward . To receive messages we establish a secure WebSocket connection that uses the already familiar (from the linking part) WebSocket-Resource design. Sending a message is a simple PUT request to the Signal API.

Sending and receiving follow the Sesame algorithm, mostly implemented in Rust crate libsignal-protocol, we just needed to put the API calls in the appropriate places.

We have made one step aside from the Sesame algorithm. Sesame implies that any direct message sent to the recipient should be sent to their every device, and the server enforces this rule. This is not desirable for us: we want an MPC message to be received only by an MPC device. We use a hack so the MPC device receives its MPC message whereas other devices receive improperly formatted messages that will be discarded.

Another difference compared to a regular Signal client: we prepend to every outgoing message a special tag allowing us to determine whether it is an MPC message or not, so we can avoid handling irrelevant messages before decryption. Irrelevant messages might appear if we have linked an MPC device with a personal Signal Account: any direct message received by the phone will be received by an MPC device as well (but dropped).

Closing thoughts

This project aims to make practical applications that require secure channels but cannot afford the overhead of building an entire infrastructure.

The Signal protocol has been implemented over the years by leading messaging applications. It is by now safe to assume that the protocol is sound and battle tested.

Running Signal protocol opens the door for some cool features, designed to work specifically with Signal messenger. One such example is multicast with the Signal private group system. We hope that our code will make these features accessible for other use cases and can’t wait to see the applications people will come up with.

Acknowledgements

We would like to thank David Wong, Claudio Orlandi and Ittay Eyal for reviewing and commenting iterations of this blog. We thank Ittay Eyal for his mentorship.

ZenGo

Crypto is now zen

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store