Tag Archives: Key Transparency

Global Consistency for AKD: Using Armored Witness to Prevent Split Views

Leave a reply

By Al Cutter and Ryan Hurst

When it comes to end-to-end encryption, securing the directory of public keys for each recipient is crucial so relying parties can have confidence they are talking to the right party. An attacker who can manipulate these directories can impersonate any participant in the communication without detection.

Over the years, various efforts have worked towards addressing this challenge. These efforts aimed to solve the problem of undetectable modifications to these central key servers. For example:

  • CONIKS was the first academic attempt to create a key transparency framework that enabled users to verify the authenticity of keys in a privacy-preserving way without relying solely on the key server’s integrity.
  • Google Key Transparency, based on CONIKS, was Google’s effort to prove it was possible to deploy these patterns at an internet scale.
  • Apple Contact Discovery was the first deployment of these patterns for a large-scale messaging system.

Arguably the most successful and well-understood implementation of these patterns though is Facebook’s Auditable Key Directory (AKD), which is intended to be used across its messaging offerings but is already deployed with WhatsApp. Like the other solutions mentioned above, it is reliant on constant monitoring and verification to ensure global consistency, mitigating “Split View” attacks against its relying parties and ensuring these end-to-end encrypted messaging solutions maintain the promised security properties.

A research paper by Sarah Meiklejohn et al., titled “Think Global, Act Local: Gossip and Client Audits in Verifiable Data Structures” (https://arxiv.org/abs/2011.04551), set out to define a verifiable scheme to perform this verification in a cost-efficient and provable way. The essential idea in the paper is that the problem can be solved by gossiping the state of the underlying verifiable data structure across a network of perspectives. The goal is to ensure that relying parties verify they are seeing the same version of the directory as everyone else who is participating.

Introducing Google’s Armored Witness

Google’s Armored Witness project aims to operationalize this concept by providing a geographically distributed network of secure hardware-based “notaries.” Its design is based on custom hardware, the USB Armory, designed with security, verifiability, and maximal openness given commercially available components and associated constraints. It modifies the USB Armory by removing unused components and adding Power over Ethernet (PoE).

The USB Armory platform uses a Go unikernel design, which has many benefits. For one, Go naturally supports “reproducible builds,” meaning that any attempt to rebuild from an application’s source will yield the same binary. This is important because it enables the hardware to report what firmware it is running and map that back to the source, allowing you to understand what is happening inside. 

The hardware itself also contains a trusted execution environment and a secure element that enables sensitive code to be isolated and the keys to be secured from many classes of logical and physical attacks. These keys are then used to do the “notarization” of their observation of these ledgers.

Check out this presentation from Andrea Barsani at 2024 CanSecWest to learn more about the hardware.

Hardware alone isn’t enough, though. We need a global network based on these devices so that relying parties can get assurance that an adequate number of network perspectives are seeing the same log contents.

If you want to learn more about the broader problem being solved, check out this video of Fillipo Valsorda from Real World Crypto 2024, and for more on the Witness network idea, Fillipo also talked about the work here at the CATS conference.

But How Armored Witness Might Apply to AKD?

Here’s how an integration of Google’s Armored Witness into Facebook’s AKD framework could work:

  1. Log Integration and Epoch Consistency: By integrating Armored Witness into the AKD framework, each Armored Witness device can act as a witness to a log of AKD epoch roots. Specifically::
    • Log Integration: Each AKD epoch root is added to the log, such that the Nth epoch root is present at the Nth log index.
    • Witness Network: The witness network, comprising Armored Witness devices, counter-signs checkpoints from these logs, providing an additional layer of verification.
  2. Client-Side Verification: As the AKD is updated, AKD clients are provided with  epoch update bundles, which include:
  3. Clients verify these bundles by:
    • Checking the signature on the directory epoch root.
    • Verifying the countersignatures on the log checkpoint.
    • Using the inclusion proof to confirm the correct log position of the epoch root, ensuring that the Nth root is in the Nth log position.
  4. Split View Protection: The distributed nature of Armored Witness devices ensures that:
    • Split views of the log are prevented due to the geographically distributed countersigning by the witness network.
    • The log sequence number matches the directory epoch number, maintaining a strict one-to-one correspondence.
  5. Heavy Lift Verifiers: Heavy lift verifiers, which perform more in-depth consistency checks, can source epoch roots from the log for pairwise append-only verification. This process ensures the correct operation of the directory over time, further strengthening the security framework.
  6. The new directory epoch root commitment.
  7. Inclusion proof hashes for the epoch root in the log.
  8. The countersigned log checkpoint.

Conclusion

Integrating Google’s Armored Witness with Facebook’s AKD framework offers a simple solution to a very hard problem. More importantly, adopting this approach not only addresses the split-view problem for Facebook but also provides a substrate that can protect all verifiable data structures.

By leveraging a generic network of geographically distributed Armored Witness devices, solutions dependent on verifiable data structures to prove integrity, such as AKD deployments, can achieve robust split-view protection, ensuring integrity and authenticity across different regions.

Secure, Privacy Preserving Key Discovery for End-To-End Encryption

1 Reply

A lot of products today claim to offer End-To-End Encryption but not all of these products offer the same level of protection. Some of the differences between these solutions are rooted in the protocols and cryptography that they use, in some, it is in the way they are implemented and in others it is the way they handle the discovery of the cryptographic keys of the peers involved in the session.

The topic of key discovery itself is a complicated one, on its surface, for a messaging application all you need to do is go to a directory to request the public key pairs associated with the user or their devices you will communicate with. Where things get tricky is how, as a relying party, you can tell if the key discovery mechanism is lying to you or not.

This is important because if the key discovery server is lying to you it can facilitate an impersonation of that user, add a hidden third-party to the encrypted session without your knowledge, or potentially trigger a re-encryption to a device not under your control without your knowledge.

To understand the implications here you just need to look at iMessage. Although many do not know this iMessage is actually End-to-End Encrypted! Matthew Green has done several great write-ups on its protocol [1] [2] and how the lack of verifiability in the key discovery mechanism utilized weakens the overall solution.

The most used End-to-End Encrypted messaging application is probably Facebook’s What’s App. Several years ago a security researcher [3] reached out to The Guardian to discuss what they described as a “backdoor” in What’s App, this “backdoor” was related to how it handled key discovery in device recovery use cases.

As a product person, you often need to make trade-offs to achieve your goals and that was what happened in this case. This “backdoor” was a design decision that was made to ensure billions of users could get some of the End-to-End encryption protections without compromising usability.

A number of security researchers, including myself, spoke up [4] which resulted in the article being updated to correctly reflect this reality [5] flawed reporting about WhatsApp.

Later WhatsApp and how Key Discovery happens came up in the news again, this time in an article from Wired [6. Alex Stamos, the former Chief Security Officer of Facebook, responded to this article [7] affirming some of the article’s points and talking about how a conscious decision was made to enable the associated use case:

“Read the Wired article today about WhatsApp – scary headline! But there is no secret way into WhatsApp groups chats. The article makes a few key points.”

While is response may be true, it is nor verifiably true as it relies on the behavior of the client and not cryptographic verifiability.

This is where systems like CONiKS [8], Keybase [9] and Google’s Key Transparency [10] come into play.

These solutions aim to enable automated trust establishment with untrusted communication through the use of an auditable directory of all of its users’ keys both past and present.

The fact that these solutions provide the auditable history of keys means that both the relying party and subscriber involved in the communication can reliably be made aware of when new keys have been associated with a users account, and importantly what entity added the key to the account.

With this information, they applications the users are using can both prevent messagings (via policy) being sent or notify the user when keys have changed unexpectedly.

This allows messaging clients to verify the identity of users automatically and prevents malicious/compromised servers from hijacking secure communications without getting caught.

On the surface, this sounds much easier than it is to acomplish at least at scale. WhatsApp serves over a billion users, any solution needs to be able to deal with key updates and reads at rates necessary to support such a large user base.

It needs to do this without leaking metadata associated with who the users are communicating with.

And do this without significantly increasing the amount of data a user must download or the time it takes to change keys.

While these are all tractable problems, they are not problems that are solved today in this context.

For this reason, applications that implement End-To-End Encryption typically either provide a mechanism that users who care about these risks can use to out of band verify cryptographic keys in person [11] or simply implicitly trust the key discovery service as an honest actor.

At Google, I have the pleasure of working on Google’s answer to this problem [12]. It is our hope that when complete that applications that need to securely discover keys in a verifiable way can simply download our solution and focus on their application and not need to spend years of energy to solve this problem for their applications.

I firmly believe the best way to ensure the right thing happens is to make sure that the right way is the easy way and fundamentally that is the goal for the Google Key Transparency effort.

  • [1] Attack of the Week: Apple iMessage
  • [2] Let’s talk about iMessage (again)
  • [3] The Guardian is backtracking on a controversial story about WhatsApp
  • [4] Security researchers call for Guardian to retract false WhatsApp “backdoor” story
  • [5] Flawed reporting about WhatsApp
  • [7] Read the Wired article today about WhatsApp – scary headline!
  • [8] CONIKS Project
  • [9] OKCUPID’S FOUNDERS WANT TO BRING ENCRYPTED EMAIL TO THE MASSES
  • [10] Google’s Key Transparency project aims to ease a tough task in cryptography)
  • [11] Safety number updates