How does Key Transparency work?
Context
Lately, I’ve been thinking about how current e2e messaging applications distribute public keys as part of my job. There are two ways. You trust the service or check that the person you are talking with has the public key in his possession. The latter is better, but users must use a side channel (e.g. meet in person, phone call) to check it. That’s known as Trust On First Use (TOFU). The first time you talk with someone over the service, you don’t know who they are, but you can use a side channel to check it. From that point, you know that this person controls that public key. Unfortunately, this has some disadvantages.
The main reasons are that users won’t bother performing the flow and that doing it with every person is a burden. Besides, this doesn’t work for people who don’t know each other on real life.
Key Transparency was born.
What’s Key Transparency?
Key Transparency is a protocol based on append-only logs. The idea is that the server providing the public keys also gives proofs that it is behaving correctly. Hence, the public key is correct, and you can safely talk with the person controlling it.
How does it work (CONIKS)?
To get an idea, we are going to review the CONIKS implementation.
Data Structures
Merkle Tree
A Merkle Tree is a tree made of hashes that allows to verify that a node is in the tree. For example, to check that the tree includes the hash in red, we only need the hashes in green. Computing the hashes in a bottom up fashion with the read and green hashes should give us the same root hash.
That’s fast and easy to verify, can be done in the client’s device and allows any user to check that a specific public key is registered in the service. This Merkle Tree is computed from time to time, so we end with root hashes for different epochs. Each new Merkle Tree includes the previous epoch root hash. These chains prevent forking the history. Otherwise, the server could build Merkle Trees with malicious intentions without leaving any trace.
User identifier to Public Key map
We also need a map between public identifiers and public keys. The server hosting the information can be untrusted. If the information is wrong, the client will detect that when verifying the proofs.
| Public Identifier | Public Key |
|---|---|
| 6384e2b2184bcbf58eccf10ca7a6563c (alice public id) | alice pk |
| 9f9d51bc70ef21ca5c14f307980a29d8 (bob public id) | bob pk |
Protocol phases
Registration phase
- User creates a new account their device create a new key pair
- Client device creates a new key pair
- Client device sends public key to the server
- Server adds it to the map
- Server computes new Merkle Tree
That’s the simplified flow. However, the Merkle Tree isn’t computed for each new key due to scalability issues. It’s done after specific time intervals (e.g. every 5 minutes). When the time is right, the server creates a snapshot of that epoch. That includes all the new keys added in the last batch.
Lookup phase
- Alice asks for the public key of Bob
- Server sends public key and inclusion proof
- Alice verifies the inclusion proof (the given public key is included in the Merkle Tree)
Alice knows the given public key is inside the Merkle Tree and trusts that it’s Bob’s public key. If it wasn’t, Bob should have notice and raised an alarm somewhere.
Monitoring phase
It works the same as the lookup phase. Alice checks that the service gives her key when someone asks for her public key. Otherwise he can raise the alarm to her contacts.
Cross verification phase
Client asks to different providers to verify the Merkle Tree chain.
Some thoughts
Pretty cool, right? It’s a good step forward to improve public key distribution. However, it has it’s challenges. What time interval should we use to compute epochs? What happens if a new user wants to send a message while the epoch is still building? What if clients can’t ask various providers?
The biggest problem is that this protocol doesn’t work if the company owns the messaging channel and the public key distribution server and there aren’t other providers. We have no assurance that the company didn’t forge the history. Furthermore, they could add two public keys for each user. One controlled by the user and one by the server. That way, they can perform a MITM attack. The server would give the fake key to any user performing the lookup phase and the real key to any user performing the monitoring phase.
How does it work (WhatsApp)?
WhatsApp started with their own implementation of Key Transparency. It might be of more help than CONIKS implementation. The data structures are the same, but the phases change a bit.
Protocol phases
Registration phase
It works the same as in CONIKS.
Lookup phase
Similar to CONIKS. However, the client first asks for the root hash of the last published epoch. Then, the client asks WhatsApp for the public key included in the Merklee Tree with that root hash.
Challenges
We can learn a lot from WhatsApp implementation, especially from the challenges they had to face.
First, how can they distribute root hashes consistently? How can the clients trust they are building Merkle Trees as expected and behaving honestly? Ideally, with a distributed ledger technology like blockchain. However, they are not doing it for now. They have locked down server that the client has to trust. It’s not the best, but a step in the right direction.
Second, what happens if we always look up the latest key? The server could serve a malicious key to Bob, which he will automatically trust. Ideally, this could be detected with Key history checks. Each user would monitor that WhatsApp always represented their public key correctly. However, they didn’t find a way to implement it. Instead, they use dual lookup proofs. Whenever Alice requests a lookup proof for Bob, she will also ask one for her own key.
Some thoughts
That’s a step in the right direction for e2e encryption. We still have to trust WhatsApp server but I hope this won’t happen in the future. More importantly, we can learn a lot from their implementation and challenges in the future.
Conclusion
Key Transparency protocol brings some solutions to current limitations on public key distributions along with some challenges. Google and WhatsApp seem to be doing some work on those areas. Keep a look on them!!!