KEYTRANS Working Group Agenda - IETF 118

Time and Date


Administrivia (10 minutes)

Presentations (80 mins)

Discussion (30 mins)



Problem statement (Brendan McMillion) - 20 mins


Brendan McMillion: Problem statement: E2EE service providers often have
difficulty finding secure ways to associate end-user identities with
long-term public keys. Without trustworthy key management, it's
difficult to secure E2EE messaging system.
Key Transparency (KT) is a proposed solution, so the user's device can
monitor their own account against unexpected changes (impersonation for
instance). Think what happens what happens when you log in on
gmail/facebook. You get an email/notification to confirm it's actually
you. This is the same but for E2EE services.
Why does the IETF need to be involved in the problem?
KT has little adoption for various reasons:

Having a standard would address most of these issues. It should help
build an industry consensus on a solution, and scope the design space.
Then this would allow for trustworthy and complete open source
implementations. Documentation would also benefit from this as it would
be public and more consistent.
In IETF 116, people interrested in KT gathered to understand the state
of what's been deployed and what's possible. The community then started
aligning on the goals, with a charter negotiation. Most of the
discussion today is going to be on the architecture document, as
mentioned last month on the mailing [TODO: insert link]

The charter was initially written with a centralised service mindsert,
and has been updated to allow for federation. The conclusion are KT
should be: transparent, user friendly (no mandatory scan of QR code as
part of the security story), private, and efficient to be deployed at

Daniel Gillmor: Thanks for working on this, this is a long missing part
of the infrastructure. About the conclusion slide. I like that privacy
is part of the story. I note it's privacy of the keyholder. With E2EE,
you can violate the privacy of the correspondant. If someone knows that
Bob wants to talk to Alice, they can build a map of relationship without
compromising privacy of Alice.
Brendan McMillion: I absolutely agree with this. In the charter, I had
in mind the idea that the social graph is public.

Dmitri Zagidulin: For the chair. The emphasis has been on key directory.
Another part of the story is key rotation. Would this be part of the
Brendan McMillion: This would be a good application. I need to get back
to the charter to see if that's defined already.

Phillip Hallam-Baker: responding to Daniel. I agree with the privacy
concern. However, I don't want to preclude sharing the social graph.
There might be only very little information shared within it, and the
wording should reflect this.

Roman Danyliw: I read the charted. We say that we want to solve the
issue of E2EE messaging system. JWK might be an application.
Orie Steele: As I said on the mailing, this is definitely an
application, and the charter should reflect this to not lock ourselves.

Architecture document (Brendan McMillion) - 30 mins


Brendan McMillion: The purpose of an architecture document is to
discovered the components, and how they interact with each other. It
does not describe the communication protocol. The adoption of the
document is to transfer ownership from the person that initially wrote
it to the working group, making sure that there is consensus on
The basic operation model is a communication protocol between a client
and the server. They can search to know the value of a key, update to
provide a new value, and monitor to retrieve the updates for a key.
User only need to communicate with the Transparency Log, which simplify
the overall design.

The architecture defines three deployment modes, from trustless to semi
trusted, which greatly simplifies deployments. These deployment modes
are contact monitoring (Google KT, Apple iMessage), third party auditing
(WhatsApp KT), and third party management (Certificate Transparency,
Merkle Tree Certificate).
Contact monitoring forces the user to monitor for updates to their keys,
as there are no other parties that are able to do so. This presents some
online requirements.
Third party auditting introduces an auditor. The auditor verifies
updates for everyone. The Log does all the work to run the protocol,
process updates, communicate with user. The Log shows all changes to the
auditor, which provides a signature (kind of a seal), to attest they
verified the entries. The signature can then be provided by the Log to
the users.
Third party management has a third party manager, which the Log forwards
requests to. This is similar to Certificate Transparency, where the
Transparency Log is a CA, and the Third party manager is a Certificate
Transparency Log.

Out-of-Band Communication is important as well to prevent forked view.
This allows users to check that the view they are presented by the KT
Log is the same view that's presented to other users. This could be done
with P2P methods, like a QR code. Instead of scanning a specific user
key, you scan the current tree head, which ensures you have the same
state for all the Log over time. Another method would be to use
anonymous channels, which automate the p2p process. This method is
consistent with the charter aiming to minimise user action.

Linearizable view aims to ensure that consistency proofs can be used,
that the new view of the tree head is the same as the previously
retrieved one plus some valid updates. You do this to have a powerful
guarantee there has not been a fork. In addition, with third party
auditing, it allows client to have instant views, as you can accept new
updates knowing these updates are going to be included/verified by the
Log in the future.

Brendan McMillion: Are there objections?
Felix Linker: I think these are great slides, and I don't have anything
against the document adoption. We need to decide how much the Log should
be append-only. I would put getting a consistent view of the Log as a
forth item in addition to Search, Update, Monitor. This is mostly an
editorial change.
Brendan McMillion: There are multiple notions for linearizability.
Usually it's all in one queue. However, CT are allowed to take 24h to
process inclusion.
Felix Linker: There are designs where the old tree has to be part of the
new one.

Rohan Mahy: We also need to answer a question about the requirements. I
was hoping to see more discussion about the priority/optionality of the
requirements depending on deployments.
Brendan McMillion: Are you asking we should clearly delineate the
security requirement associated to each requirement?
Rohan Mahy: There are possible pitfalls down the line if these are not
correctly laid out.
Brendan McMillion: There is a security section in the draft. It was not
in the presentation, but addresses what you're saying. "TODO: specify
the security guarantees for the rest of the protocol".
Shivan Sahib: The draft architecture document should be clearer on what
OK and what's not OK.

Christopher Patton: Is there a core set of security and privacy
requirements for which the deployment modes are isomorphic?
Brendan McMillion: I believe yes. The draft mentions this.
Christopher Patton: Do we expect different privacy properties between
the different models?
Brendan McMillion: You should leak the same informations to the third
party in all modes.
Christopher Patton: Do we want one or multiple protocols based on these
Brendan McMillion: We're aiming for one.

Phillip Hallam-Baker: The work factor is the important factor. Forging
keys a long time in the past, like decades, is more difficult than doing
it yesterday. The other point I want to make is there is only one notary
chain. It's actually not a notary chains, but lattice. Each user has its
own chain, and they are cross-checking.

Shivan Sahib: Do you want to finish the presentation and move the
questions to the end?
Brendan McMillion: Let's do questions now

Kevin Lewi: This is a comment. It would be good to relax the linearized
view requirements as it's a burden to users. For WhatsApp for instance,
with multi-device, how does this work? Different parties have different
requirements, and requiring state sync is a hard requirement for
Brendan McMillion: We can take this offline.

Stephen Farrell: We've had history of key server going bad in the past
(going away, cryptographic issue, others). Do we have something in the
document trying to address what should client do in this case?
Brendan McMillion: This has not been laid out.

Jonathan Hoyland: If there is content that is required to be removed
from the tree (legal, dcma, others)?
Brendan McMillion: Given this is a merkle tree, this is doable, but
needs to be made clear on the document.

Brendan McMillion: Second part of the talk, feedback from the mailing
Most of the feedback have been about text that should be added.
First comment is sealed sender. You're looged in about one user, and
want to validate the key of another user. Understanding how KT fits this
should be added.
There were comments about life cycle management, to allow for migration
of one log t another.
Multiple comments were on federation, as well as legal requirements.

Immediate updates have been questioned as well. This implies there would
not be any inclusion proofs (similar to SCTs). It simplifies the
protocol descruption and operation, and support deployments that would
like to be more strict. However, this might preclude KT servers that are
not reliable/performant enough. The comment I have is that if an app is
operating a service already, you should be able to run KT in a similar

Daniel Huigens: We are deploying a version of KT based on CONIKS. In our
model, we do intermediate updates.
Brendan McMillion: Doing the proof and updating the tree should not be

Chairs: Is anyone opposed to propose the adoption of the document? The
chaires believe there is generally positive feelings. Similar to
Daniel Huigens: I support adoption. Thanks for working on it.
Rohan Mahy: I support adoption, with my previous comment being
Richard X: Adoption is binary, either the document is adopted, or not.
It means the group starts to work on it, not that it's almost done.
Rohan Mahy: Within the period of the week leading to adoption, updates
can happen on the mailing list for the document.
Orie Steele: It would happen on the list.
Felix Linker: I'm not sure I understand the remark on the requirements.
I think they are specific and broad enough to address what you mention.

Simon Friedberger: There should be more specific guarantees for people
and service operators on privacy.
Hannes Tschofenig: The document is great and I support adoption.
Shivan Sahib: The chairs should discuss with Brendan to understand if
there are text updates we can do, and then propose adoption on the list.

Orie Steele: Brendan, do you have questions you want to discuss now, or
should we take it to the list?
Brendan McMillion: Let's take it to the list.

Security Properties of Key Transparency (Esha Ghosh) - 15 mins


Esha Ghosh: There has been great discussion on security. In this
presentation, I want to lay out dimensions of security properties we
might be considering for KT.
In KT, service providers maintain a directory of userid to public key
mapping. User can search, update, monitor.
The service provider builds tree divided in epoch. User request proofs
from the service proider and validate it.

We define two dimensions for security porperties:

When consisteny property should be detected and by who is to be
discussed later.
A key point is to correctly disseminate Treeheads to users. To detect
forking of a log, users need to compare these.
The key owner (Bob) should have authority on the distributed key would
be fake. Bob needs to monitor for updates of their key. They need to
recall the epoch of their last update, and monitor it.
The key owner may be required to request updates/monitor for another
user. If Alice sees Bob's key, they might need to remember when they
have seen this key.

When an inconsistency is detected, two check need to happen. The
receiver should ensure the key they see has been commited to the server.
The origin tasks is to ensure the distributed key is correct.

Third party auditor is trusted to download and authenticate the log
content. It's added for efficiency for client that trust the auditor to
behave correctly. Users should still be secure performing checks

Takeways are security has multiple subtle dimensions, it would be great
to think about the properties for KT systems, and the combinations and
their tradeoffs.

Privacy Properties of Key Transparency (Kevin Lewi) - 15 mins


Kevin Lewi: It's about interesting thing we should consider, not a
formal definition.

Service providers need to be careful to not inadvertantly leak data
through normal operations: search, updates, monitor. For instance, it
should not leak how often users are updating their keys. We assume there
is a database of users represented as a merkle tree.

First example of a privacy leakage has to do with proofs served to user
to check for inclusion. Along with the inclusion proof of the user, we
have to serve siblings (merkle tree). This could reveal the height of
the tree. it's not too bad because the height doesn't change much for
when the tree is big.

Example two. How do we deal with repeated updates to the same entry?
Imagine someone updates their key five times in a row. Does it look the
same as five different users updating their key independantly? If not,
an adversary could learn statistics such as the frequency distribution
of how often people are updating their keys. I don't know if we want to
protect this, but we should be considerate here.

For the third example, I want to discuss leakage as part of updates to
the history in the context of identifier re-use. Should a user be able
to look arbitrarily far into the past for update history for their phone
numbers? With recycling, it might allow users to get informations about
another person.

The forth example is hoe the service provider learns information based
on users query. The service providers inherently learns information as
it gets query. This is a problem even without key transparency. With KT,
it's amplified as users would be asking for their history for instance.

Some tools have been discussed to address this:

Rohan Mahy: Could you clarify the requirement on PQ secure KT? does the
attacker has to be actively involved, compared to harvest now decrypt
Kevin Lewi: It depends on how we plan to publish these proofs. If we use
a public ledger for instance, it's different from a server model.

Daniel Gillmor: The secret key leaked by a machine would leak these
privacy. The tranparency would not be lost, but the user id would.
Kevin Lewi: I would not surprise if that were true.

Kevin Lewi: Handling data deleting is challenging as well. Merkle tree
nodes correspond to hashes of user data. Is it sufficient to just delete
the raw user data without deleting hashes. Given that KT Log keeps
growing, should service providers reset the tree at some point? Should
updates get cleaned after a specific period of time?

Hannes Tschofenig: User identifier is solely that, not necessarily owned
by the user?
Kevin Lewi: That's true. This is what's registered by the service

Daniel Gillmor: I don't think it's good to expect infnite lifetime.
Certificate Transparency Logs are sharded by year.

Phillip Hallam-Baker: What proof wo we want to give from this tree? When
I connect to someone else on signal, I would like to see a box telling
me that this person key has not been seen in years.
Kevin Lewi: We are taking snapshot for every epoch. Time of last update
might or might not be revealed.

Kevin Lewi: Takeways are that managing privacy leakage is tricky, and we
should be careful about this in the design we are proposing. Finally,
different service providers may make different choices on what is/is not
of to leak.