Agenda for keytrans BoF — IETF 116

Chairs: Alexey Melnikov, Rohan Mahy
29/03/2023

Housekeeping and Agenda bashing (chairs) - 5 minutes

Slides

Alexey Melnikov: Welcome. Time at the end of session for questions and
discussion. This is a non working group forming BoF.

Rohan Mahy: This session is recorded. If you haven't, please read the
ToF. List of material is available on IETF 116 agenda.

Rohan Mahy: The agenda is as follow

• Housekeeping and Agenda bashing (chairs) - 5 minutes
• Problem statement (Brendan McMillion:) - 20 minutes
• Case study: Parakeet (Jasleen Malvai) - 10 minutes
• Case study: Keybase (Antonio Marcedone) - 10 minutes
• Systemizing Security Properties of KT (Esha Ghosh) - 10 minutes
• draft-mcmillion-key-transparency preso draft (Brendan
  McMillion:) - 25 minutes
• Next steps (chairs) 10 minutes

Problem statement (Brendan McMillion) - 20 minutes

Slides

Brendan McMillion: Problem statement: People have tools to do E2EE. One
problem that remains is how to distribute these public keys. The
distribution usually implies the user to trust the server or the service
provider.

Richard Barnes: To clarify, the problem is not about how to distribute
key from point A to point B, but ensuring the fidelity of this data?

Brendan McMillion: correct

Brendan McMillion: Key Transparency (KT) aims to address this. It works
like a key value database, where you have cryptographic properties
ensuring the consistency of the database. The power of KT is Alice key
seen by Alice is the same as seen by everyone else.

Rohan Mahy: This is a way of solving the problem. For the Transparency
property, we can see what has happened to the identity management tool.

Brendan McMillion: Yes, everyone sees the same data, and users are
responsible for making sure the data is correct.

Brendan McMillion: IETF already has efforts relating to Certificate
Transparency (TRANS), SCITT (Supply Chain Integrity), TIGRESS (Digital
Credentials). The main difference with KT is the existing logs are fully
public, while this is not necessarily something you want for an E2EE. In
addition, on the contrary to existing systems, KT requires efficient
search so users don't need to download the entire log.

Orie Steele: SCITT does not require the entire log to be public. Each
service can decide to reveal only part of the log based on an
authentication policy. A second point I want to mention is existing
systems (CT, TIGRESS) are already including some sort of key
transparency.

Brendan McMillion: Why does KT has little adoption? KT is technically
challenging, there is a lot in the literature, the engineering cost
might not be immediately relevant to companies.

Daniel Gillmor: What is the incentive? It seems to be similar to DNSSEC,
like it's an opportunity to screw up your own domain and look bad. In
addition, what are the implication for services that run it and look
bad, in comparison to services that don't run it and cannot be caught?

Brendan McMillion: Ideal End Goal is to reduce barrier to development. A
BoF is meant to bring industry consensus on what KT looks like, have
trustworthy open source implementation.

Brendan McMillion: To get there, we need to understand the state of
what's achievable (that's the state we are at today), then align on
common goals, and finally write the standard.

Eric Rescorla: In regards to incentives: CT is a thing because 2 major
browsers required it, and people had to follow along.

Konrad Kohbrok: Each approach aims both for Transparency and
Distribution. Could we aim to provide data only on certain commitments?

Brendan McMillion: Value in the key/value KT database is the public key,
but can be any other information about your account.

Orie Steele: People are putting keys in transparency services beyond
what they were used for initially. There are already some sort of KT
within SCITT for instance.

Daniel Gillmor: Why not storing commitment within the tree. I want to
observe that only putting the commitment is possibly privacy preserving.
The name of the key is also a concern.

Aron Wussler: We are deploying key transparency, and it's as hard as
described. Without commitents it's important to note that a server might
hide the value of the leaves, therefore not guaranteeing that you'll
know what was the server distributing.

Guilin Wang: Any considerations regarding the implementation?

Brendan McMillion: We don't want to move away too much from the problem.

Konrad Kohbrok: It would be good to have flexibility, and not fixate on
the messaging systems. Focusing on commitment would give us a lot of
flexibility.

Antonio Marcedone: Zoom published a whitepaper a year ago saying and
explaining how we would build KT.

Rohan Mahy: We want to figure out how people feel about the problem
statement, without diving into the specific of the implementation.

Chairs (using IETF web tool): Is the problem statement well defined?
Room consensus is Yes.

Case study: Parakeet (Jasleen Malvai) - 10 minutes

Slides

Harjasleen Malvai: Alice and Bob are two users of an E2EE messaging
service. To exchange encrypted messages, they need each other's public
key. They each ask the server to do so. We would like the server to have
a privacy preserving key directory, which support updates, lookup, and
addition of new users.

Harjasleen Malvai: It should be resistant against the identity provider
cheating or being malicious. The server wants to guarantee trust for
serving the correct public key. Users wants to know if there's a change
to their public key, and their friends should know this latest key.
Finally, auditors would like to guarantee the server is trustful.

Harjasleen Malvai: The system needs to be able to serve billions of
users, with possibly computationally limited devices.

Harjasleen Malvai: The problem breaks down in commitment and
verification for mutating the database, as well as disseminating small
commitments.

Harjasleen Malvai: Problems our work solves: State machine replication
using flexible storage, data structure for state commitment with limited
storage growth over the years, and users checking their own key with key
compaction.

Harjasleen Malvai: For disseminating commitment, the system could
gossip, but this presents a couple of problems.
Blockchain/blockchain-like are too costly. Our prefered solution is to
use independent auditors part of an industry consortium, that use
consensus.

Harjasleen Malvai: Code is open source, paper is on eprint.

Harjasleen Malvai: I think the problem statement covers our work.

Case study: Keybase (Antonio Marcedone) - 10 minutes

Slides

Antonio Marcedone: Overview of two systems: Zoom+Keybase. User identity
is different between the two systems, and we'll go over the implication.

Antonio Marcedone: Keybase maps social identities to cryptographic keys
in a public auditable manner. This is the only KT system in production
to the best of my knowledge.

Antonio Marcedone: Users can make social commitment, as in they can post
their Keybase identity on their social media. Then this proof can be
verified by every other user. Keybase stores the changes in user
identity over time. When there is a new device, it's signed by an
existing one. Similarily when there is a link to an online identity.

Antonio Marcedone: One problem is how can user reset their account. If
you lose your device, how can you reset your identity. Users can decide
to disable this feature, the enforcement is done server side but we
could imagine doing this in the signature chain.

Antonio Marcedone: Keybase leverages a merkle tree, which is publically
auditable (see slide for all infos). Its root is published periodically
to Stellar blockchain.

Antonio Marcedone: In 2020, Zoom published how we would KT. The identity
is different. There is a domain (company.com), and the email
(alice@company.com). Users can change email, and they could move across
domains. We allow users to add devices without approving them on an
already trusted device. They are able to attest this change later on.

Antonio Marcedone: We allow external IdP to vouch for the identity of
their users.

Antonio Marcedone: A difference in the Zoom Tree compared to the Keybase
tree is that commitments are stored under different part of the tree,
improving privacy.

Antonio Marcedone: Keybase provide immutable username, social proofs,
requires an existing devices to add a new one, and identities are
public. Zoom has mutable identity, allow IdP attestations, devices can
be approved before hand, and identities are private by default.

Antonio Marcedone: I think the problem statement captures what we are
doing, but our work go further and I'd like the problem statement to be
extensible.

Systemizing Security Properties of KT (Esha Ghosh) - 10 minutes

Slides

Esha Gosh: There is a service directory that maps public key of users,
and manages them on the client's behalf. When a client gets a public key
from this service, it also gets a cryptographic proof along with it.

Esha: Users register/update their public key, they can lookup their
contact's public key, and they can monitor their own public key.

Esha: Goal of the talk today

Esha: Dissemination of the Tree Head could be done via a bulletin board
(third party), or there is gossiping (p2p).

Esha: Consistency: Given Bob has public key pk_B, and Alice's query for
Bob's public key, does she see malicious key pk_C. Only Bob can assess
that his public key is pk_B. Strong consistency means that Bob detects
inconsistency the first time they come online. Weak consistency means
that Bob might not detect the problem the first time they come online.
Additional checks have to be performed, either by Alice or Bob.

Esha: Contact-Statefulness means that clients have to retains certain
information about their contact.

Esha: Owner signing: If a server publishes a malicious tree head, it
would not be able to withold this misbehavior from clients.

Esha: Privacy. Content Hiding: hides public key and user name from
unauthorised party, and possibly metadata hiding so that users can hide
some actions such as first registration or updates.

Esha: Deployment modes are two: either 3rd party management, or 3rd
Party auditing. The former can assess properties when they happen, the
other when they are published.

Esha: I think the problem statement correctly refers this problem.

Rohan Mahy: How many systems did you evaluate?

Esha: About 10 proposals

Richard Barnes: Thanks for synthetising. Given the Working Group would
standardise a single protocol, we need to use this work as a guide.

IETF considerations (chairs)

Chairs: Is the problem well stated? Room consensus is Yes (strong)

Chairs: Should this work be done at IETF? Room consensus is Yes (strong)

draft-mcmillion-key-transparency preso draft (Brendan McMillion) - 25 minutes

Slides

Brendan McMillion: Model where users are Search, Update, and Monitor. I
tried to make the API look like a key-value database, and remove p2p
need in favor of communication with the provider.

Brendan McMillion: Design goals

• Non controversial: efficient verification, small state, have PQ
  secure algorithm,
• Nice to have: Instance inclusion of new entries in the log
• Interesting: operate trustfully without a third party (for practical
  concern, while theory usually assumes one), metadata privacy (not
  addressed).

Richard Barnes: I'm comfortable accepting the constraint of a third
party auditor. CT requires it.

Raphael Robert: Gossip system, along with MLS, seems to provide enough
guarantees without the need for a third party.

Daniel Gillmor: I have not yet seen a good design where anyone can act
as a third party. Design seems to consider someone the server operator
trusts. Another question is how does a failure in a system like this
looks like.

Konrad Kohbrok: Architectural changes in term of auditing. The working
group ?MIC? has a federated auditing system. There is another tree
hierarchy on top of everything.

Brendan McMillion: The idea for KT is we can agree on a common KT
construction, and then have multiple configurable deployment modes to
address people specific needs. The deployment modes being considered
(mentioned in a previous presentation) are 1. Contact monitoring 2. 3rd
Party auditing 3. 3rd party management.

Brendan McMillion: Contact monitoring implies that users verify that the
key from their contact does not change over time.

Brendan McMillion: Third Party Auditing implies that an auditor signs on
bulk updates to the database. Then, eventually, users stop trusting the
service provider sometime after the service provider misbehaves.

Brendan McMillion: Third Party Management is similar to SaaS model. The
manager is responsible for building the tree and signing it. The
interesting thing is auditing is happening continuously.

Brendan McMillion: One more mode would be anonymous third-party
auditors. It's been omitted due to the try to not assume out-of-bound
communication, and this types of endpoints tends to be expensive to
support while providing an easy target for abusers.

Next steps (chairs) 10 minutes

Alexey Melnikov: To clarify: we are not asking the room to accept this
draft as the starting point. It's meant to prove the problem is
solvable.

Chairs: Modulo 3rd party auditing and metadata privacy, are these design
goals close to what we want? Room Consensus: Yes

Chairs: Who's willing to contribute text/review documents/participates
in mailing list discussion? 24 people say yes.

Lixia: It seems to me the critical dependency on this third party
auditing, which remains open, is a concern

Alexey Melnikov: This is something we will need consensus on in the WG,
if formed.

Roman Danyliw (the responsible Area Director for this BoF): I want to
note it's the first time proponents of a BoF are all remote. We have
room consensus doing this work, but we need to be more concrete on
things we have talked about.