Verifiably Private Computation

By Philipp Winter

This is the second post in a series on Brave’s commitment to ‘Privacy by Design’, standing beside the work covered in Published proxy configs.

The challenge

The principle of data minimization dictates that only necessary data should be collected for a given business purpose. Data minimization is a cornerstone of online privacy: You can’t abuse, sell, or lose what you never collected in the first place. Sometimes, however, it is necessary to process sensitive data, and cryptographic building blocks like multi-party computation or homomorphic encryption may not be an option.

Let’s consider a simple (and admittedly silly) example: imagine that Brave wants to wish you a happy birthday once a year. Most companies build such services by recording every user’s birthday in a database. They then check the database daily and send birthday wishes to everybody whose birthday it is. But birthdays are sensitive. There’s often no good reason for a company (or advertisers) to learn your birthday, especially given the risk of data leaks.

There’s often no good reason for a company (or advertisers) to learn your birthday, especially given the risk of data leaks.

How might Brave build a service like this without learning your birthday? Or more broadly: How might we build any service that processes private data, without actually seeing the data? To answer this question, we first need to introduce a technology called secure enclaves.

Secure enclaves

Secure enclaves allow your computer to process information in a way that’s isolated from other programs and data. An operating system is the trusted foundation of a computer, providing an environment where applications like Brave can run. If it has a security hole, all data on the computer is in danger. A secure enclave can mitigate this problem. Think of it like an isolated, tiny computer inside a computer. If the main computer is compromised, the secure enclave is unaffected, and can still be trusted. Many CPU manufacturers offer such secure enclaves, both on server and consumer CPUs. For example, Intel has Trust Domain Extensions and SGX; ARM has TrustZone; and AMD has SEV. Many companies have taken advantage of enclaves in creative ways: Signal uses this technology for private contact discovery; Apple for Face ID; and others use it for copyright protection and blockchain technology.

And Brave can use it for private birthday wishes.

To demonstrate this, we built upon a new type of secure enclave that was introduced by Amazon in 2020, called AWS Nitro Enclaves. We chose Nitro Enclaves over alternatives because they are virtual machines (VMs) that do not share resources with other VMs. This eliminates a class of bugs that has plagued SGX for years: the infamous side channel attack. Specifically, we built a free software tool kit called nitriding which makes it possible to run networked applications inside a Nitro Enclave—often with no modifications. Nitriding allows us to run our private birthday service inside an enclave. That said, we need to consider three attacks:

What if Brave wants to exfiltrate birthdays?
What if Brave claims to run one version of the code but secretly runs another?
What if Brave wants to intercept the birthdays on their way to the enclave?

Attack 1: Data exfiltration

What stops Brave from logging in to the secure enclave and obtaining all birthdays from memory? This attack is prevented by the very design of Nitro Enclaves. While Brave wrote the code that’s run inside the enclave, neither we nor Amazon (nor anyone else) can observe the code and its data at runtime. That means we can’t see the data that goes in or the computation happening inside. We cannot log in to a Nitro Enclave—it’s essentially a sealed black box. This ensures that once a birthday is in the enclave, it is protected.

We cannot log in to a Nitro Enclave—it’s essentially a sealed black box. This ensures that once a birthday is in the enclave, it is protected.

Attack 2: Secretly running malicious code

The benign code and malicious code below are nearly identical, but the malicious code contains a function (highlighted in red) that exposes the birthday. What’s to stop Brave from claiming to run the benign pseudo code, while instead running the malicious code?

func send_wishes() { for b in birthdays { if b == today { send_wishes(b) } } sleep(24h); }
func receive_birthdays() { while true { birthday = receive_birthday(); save_in_database(birthday); } }

a) Benign Code

func send_wishes() { for b in birthdays { if b == today { send_wishes(b) } } sleep(24h); }
func receive_birthdays() { while true { birthday = receive_birthday(); save_in_database(birthday); leak_to_attacker(birthday); } }

b) Malicious Code

This attack is prevented by another feature of Nitro Enclaves called remote attestation. Users can verify over the Internet that the code we claim to run is the code that’s actually running. If we secretly ran different code, our users would notice due to the cryptographic attestation process of the Nitro system. Remote attestation allows users to verify that the code Brave claims to run is actually running.

Note: Another blog post in this series will discuss how remote attestation works in practice.

Attack 3: Interception of data in transit

While we may not be able to exfiltrate birthdays from the enclave memory, or secretly run malicious code, what’s to stop Brave from intercepting birthdays as they are submitted to the enclave?

This attack is also prevented by our nitriding tool kit. Nitriding exposes a Web service that runs inside the enclave and cryptographically binds the Web service’s HTTPS certificate to the attestation document that’s issued by the Nitro system itself. This allows our users to verify that they are talking directly to the enclave, with no parties in the middle. In other words: Brave (or any other third party) can obtain a valid HTTPS certificate for the enclave, but cannot reference this malicious certificate in the attestation document, which acts as the root of trust. Users have a cryptographic guarantee, enforced by their client, that they are talking to the enclave and nothing else.

The downsides

Let’s sum up: If Alice wants to receive birthday wishes from Brave, she first audits the source code of our birthday service to convince herself that the code is safe and secure. Next, Alice establishes a TLS connection with the enclave application and verifies that it’s running the code that Alice just audited. Finally, Alice is willing to reveal her birthday to the enclave application because she knows that it’s going to remain safe.

In this case, Brave has demonstrated how to build with verifiably private computation.

However, Nitro Enclaves are no panacea. We consider their design more secure and flexible than Intel’s SGX, but Nitro Enclaves are new. The technology has yet to stand the test of time and face the scrutiny of security researchers. Another shortcoming is the proprietary nature of Nitro Enclaves: While AWS published the architecture, the hardware design itself (and some of the software) remains proprietary, which requires a level of trust in Amazon. This is no different from many other enclave designs, but still problematic because closed-source hardware and software cannot easily be verified by third parties.

With these limitations in mind, we have decided to experiment with enclave applications cautiously, without placing too many eggs in one basket. The next blog post in this series will present one such application: a service that plays a key role in the work-in-progress revamp of our privacy-preserving product analytics (P3A) system.