Hello Protocol - progress since Prague

[oskarth]

Hello Protocol

Two weeks ago we met in Prague to discuss how we should think about creating a protocol. Whether we should do so at all, and if we do it, what this would imply in terms of efforts. You can read the meeting notes here.

What would a “Status protocol” be? From my point of view: essentially a reflection of our principles but in code. More precisely, as a family of protocols (a set of a set of rules to achieve certain properties). There’s a real lack of rigorous successful security-oriented communication protocols out there. The ones that exist, generally don’t build on or with something like Ethereum. There’s an amazing opportunity here if we do things right.

A few examples of successful protocols:

• TCP/IP with application protocols like HTTP, enabling the web as we know it today
• BitTorrent which enables a plethora of different client implementations
• Of course, Bitcoin and Ethereum with their associated protocols

Progress last two weeks

1. A Status protocol proposal draft was written.

This may be extended to something closer to Nimbus proposal, either before or as part of initial team formation. We also need a better name.

2. Initial early research.

An attempt to become more aware of blindspots, and get a better understanding of the field as a whole. This is a work in progress, and ensure we aren’t myopic and learn from the decades of work and thousands of man years that has gone into the fields of secure/anon/censorship-resistance communication. See protocol reading laundry list for primary artifact of this effort.

Some exciting highlights:

1. SoK Messaging - see breaking apart problem below
2. Onion Routing vs Mix Networks breakdown aha moment in terms of fundamental difference (bifurcation from Chaum '81 paper in terms of anonymity research afaict)
3. Loopix - mix network with better security guarantees than Tor, while still having a low latency
4. The existence of Delay-tolerant Networking as a tool for censorship-resistance/sneakernet
5. Briar’s beautiful problem decomposition - BTP/BSP/BQP
6. Douglas Comer on protocol layering - worth thinking more about.

This effort will be continued, along with write-ups of more precise problem statements and requirements. See section below for a start.

3. Very early team scoping.

As Gmbh and Core is being restructured, right now the only person who is dedicated to this effort right now is Oskar. There are also some in-house expertise at Status that can be leveraged, but there’s a clear need for experts in this field. These are people who have designed open, battle-tested, p2p protocols, as well as people who take part in security research, or been part of RFC efforts.

A very rough list of individuals/projects worth reaching out to has been started here.

This work will continue over the coming weeks, by seeding candidate list and work with talent team to figure out how to best approach these.

Breaking apart the problem, somewhat

One of the most important things in this effort is to break down a set of problems into separate layers/efforts/protocols, that each deal with their specific subproblems. This simplifies the design, makes it easier to understand, more robust, and generally aids mental clarity.

Having clear separation of concerns enables us to attack the problem(s) separately, independently and in parallel.

Aside from classical protocol layering (see RFC793 - TCP and Comer Internetworking with TCP/IP - Principles, Protocols, and Architectures (chapter 11)) principles, one way of breaking down the problem of secure messaging is elaborated on in SoK: Secure Messaging overview.

This way of breaking things apart is in no way exhaustive, and it might be wrong in some ways (.e.g it doesn’t take transfer of value via Ethereum into account, and the role of censorship-resistance isn’t clearly outlined). Nonetheless, it’s a useful framework.

The main idea is to break secure messaging apart into three separate parts:

• Trust Establishment. Provide initial key distribution and provenance.
• Conversation Security. Provide protection of exchanged messages.
• Transport Privacy. Hiding communication metadata.

In terms of things blind spots of this framework, here are two heuristics for how to think about it:

Heuristic 1: Err on the side of extreme security, take these properties beforehand.

Notice how this goes against what the author suggests, but it’s more along the lines of don’t compromise on core principles as building blocks. This is an interesting question in terms of usability and adoption, and what the path to that looks like - is it a question of money, to what extent can less secure stuff be added on top of a secure base layer, etc.

Heuristic 2: Thing that might be missed due to focus on ‘secure messaging’ and 2015 focus.

Example: Censorship-resistance, premium on p2p solution, enabling transfer of value and contract logic, new mixnetwork stuff since 2015 (Loopix), new secure messaging advanced (Briar, e.g. see QR Introducing contact logic).

Regarding all these properties, it’s worth keeping in mind this is about trade-offs - it’s naive to think we can achieve all possible desired properties across the board.

This laundry list of properties gives us a rough design space to play around in.

Trust establishment aka key exchange

Users verifying that the entity they want to talk to is actually in possession
of a long-term key.

To do this securely likely requires making some concessions on usability and immediate adoption. See Briar QR BQP protocol, as well as their “Introduction” feature for ways to alleviate this.

Security properties

Network MitM Prevented
Operator MitM Prevented
Operator MitM Detected
Operator Accountability
Key Revocation Possible
Privacy Preserving

Usability

Automatic Key Initialization
Low Key Maintenance
Easy Key Discovery
Easy Key Recovery
In-Band
No Shared Secrets
Alert-less Key Renewal
Immediate Enrollment
Inattentive User Resistant

Adoptability

Multiple Key Support
No Service Provider
No Auditing Required
No Name Squatting
Asynchronous
Scalable

Conversation security protocol

Once trust has been established, this protocol protects security and privacy of messages. This includes data and metadata of messages, how encryption is performed and what cryptographical protocols are used.

How trust is initially established or how data reaches recipient is explicitly out of scope.

A better term here might be w.r.t exchange of value. Secure Communication Tool. IM is one aspect, or extension.

Security and Privacy

Confidentiality
Integrity
Authentication
Participant Consistency
Destination Validation
Forward Secrecy
Backward Secrecy
Anonymity Preserving
Speaker Consistency
Causality Preserving
Global Transcript
Message Unlinkability
Message Repudiation
Particip. Repudiation

Adoption

Out-of-Order Resilient
Dropped Message Resilient
Asynchronicity
Multi-Device Support
No Additional Service

Group chat

Computational Equality
Trust Equality
Subgroup Messaging
Contractable
Expandable

Transport privacy layer

Defines how messages are exchanged. Hides message metadata, such as sender/receiver/conversation provenance.

Also, censorship-resistance here? Internet out, traffic morphing, etc.

In general, this layer is too complex. Not clear with synthesis is of p2p overlay / mixnetworks etc is.

Privacy

Sender Anonymity
Recipient Anonymity
Particip. Anonymity
Unlinkability
Global Adv. Resistant

Usability

Contact Discovery
No Message Delays
No Message Drops
Easy Initialization
No Fees Required

Adoption

Topology Independent
No Additional Service
Spam/Flood Resistant
Low Storage
Low Bandwidth
Low Computation
Asynchronous
Scalable

Next steps

1. Team formation - seeding list and outreach
2. More early research - teasing out layers/subproblems
3. Rough write-up up of these layers and properties / consideration (taking Prague meeting thoughts into account)

Appreciate feedback, thoughts, concerns. Especially around:

• individuals/projects worth reaching out to
• ways of simplifying the problem through layering (e.g. transport privacy)
• general approach

[jarradhope]

Thanks for this post, this is a great start. I felt this post shows your progression in thought through time, but it was a little hard to follow in certain points, perhaps the info in future could be recomposed in a way that shows progression in terms of concepts, starting with broad strokes and getting into the details. Certain things aren’t explained such as the rationale for breaking the problem into Trust Establishment, Conversation Security and Transport Privacy (and in contrast to what?)

For next steps:

I agree finding potential allies (the Web3 Foundation has expressed interest), sourcing people who have the relevant expertise and interest to work on this project.

I would say we need to have a structured document outlining our draft preferred requirements in order of preference before we reach out to others, think about implementation details or how the protocol should be structured (although that’s not to say we can’t do research in parallel).

[burdges]

I’ve an unfinished analysis of the space of Sphinx-like mixnet packet formats that answers questions like: Where do I put the SURB? How can mailbox servers be “decentralized”?

In particular, we want roughly the Loopix-like cover traffic in a mixnet, but we’d face resistance over the “service provider” model proposed by loopix not being “decentralized”, and my “aggregation points” aka decentralized mailbox servers help enormously.

I address DoS attacks directed at users too, but not full network DoS attacks. There are tools like rerandomizable credential schemes for this, but we might find simpler solutions once we start discussing this.

I’m afraid there are only unsatisfactory answers for post-quantum protections and forward secrecy there. A naive post-quantum solution using the module LWE scheme Kyber costs like 1k per hop, or else only includes a few post-quantum hops. CSIDH was started partially to address this complication, but isogenies remain quite slow. We do at least know roughly how the protocol would grow in these directions though.

We just hired a second mixnet researcher here at W3F. At the Web 3 Summit, I spoke briefly about a reward strategy for nodes, based on turning a small amount of cover traffic into secret shopper packets, which we’ll start writing up soonish. We’ll also explore an idea for providing some shadow of a verifiable mixnet security properties, but extremely cheaply.

[burdges]

I’d mostly considered direct messaging before, but we could deliver “status updates” too:

Alice has an “aggregation point” account as described in my repo linked above. Bob has a “status point” account where he sends his outgoing status messages. Alice creates a “generator point” account and configures it to build SURBs going from Bob’s “status point” account to her “aggregation point” account and send them to Bob’s “status point” account.

We identify accounts by encrypting the account identifier to the point using roughly universal reencryption. In this way, the “generator point” can rerandomize the encryption of the account information. We cannot afaik hide the number of subscribers from the “status point”.

What does this give us?

An online user can send more SURBs to a “status point” thus picking up extrac status updates, but an offline user only recieved updates for SURBs issued by their “generator point”, so the number of updates is capped at some fixed number per time interval.

A “generator point” knows some status updates pass from a given “status point” to a given “aggregation point”, but not the accounts. An honest “generator point” does not know when its SURBs get used, but a dishonest one could replace SURBs to learn this.¹ At present, I think the only attack vector here would be deanonymizing your subscribers aggregations point, so that you can knock them offline or learn their incoming message pattern.

We could accept these attacks, use different “aggregation points” for status updates, and document that status update have a weaker threat model, which holds anyways since the “status point” knows the number of subscribers.

¹ As an aside, we could prove correct SURB construction with SNARKs or STARKs, but SNARKs are too slow and STARKs are too big. We could rotate “generator points” easily enough, which helps. We could send cover traffic with the resulting SURBs but that sounds expensive too. Instead, we could detect bad “generator points” if clients occasionally query the SURBs their “generator points” provided to other’s “status point”. If “generator points” are staked, then bad ones could be slashed, but this makes them a service that requires rewards and I dislike making privacy crypto-economic.