DMLS vs DMLS

Hi

• I'm Hubert Chathi (a.k.a. uhoreg)
• Crypto team an Element
• Matrix Spec Core Team
• investigated decentralizing MLS for Matrix
• wrote a partial, experimental MLS implementation in TypeScript

What is Messaging Layer Security (MLS)?

• IETF standard (RFC9420) for end-to-end encryption in instant messaging
• can be applied to many different systems
• encrypts messages
• handshake messages can be encrypted or cleartext (though the sensitive parts are encrypted)

• ensures consistent group state (e.g. membership, "group context")
• provides Forward Secrecy and Post-Compromise Security
• does not provide Deniability
• updates only require O(log(n)) average(?)-case work (though inviting still requires O(n) work)

How does MLS work?

• focus on just one small part
• MLS group goes through different "epochs"
• each epoch has an "epoch secret"
  • other secrets (e.g. encryption keys) are derived from it
  • derived from previous epoch secret and commit secret (which comes from the commit message that created the epoch)
  • old epoch secrets are thrown away

• commit messages are ordered: only one commit applies to each epoch, and any others are discarded
• Delivery Service responsible enforcing order
• what if we don't have a Delivery Service to order them?

Two approaches, as IETF drafts

• Decentralized MLS (a.k.a. DMLS) (https://datatracker.ietf.org/doc/draft-kohbrok-mls-dmls/)
  • written by Phoenix R&D, based on work by Amazon (formerly Wickr)
• Distributed MLS (a.k.a. DMLS) (https://datatracker.ietf.org/doc/draft-xue-distributed-mls/)
  • by Germ Network and researchers from US Naval Postgraduate School

Decentralized MLS

• allows epochs to have multiple descendants
  • instead of linear order of epochs, we get a tree
  • multiple senders can send commits that modify the same epoch
• uses Puncturable Pseudo-random Functions so that you can't re-derive an epoch secret – preserves forward secrecy

Questions

• how do you manage the forks?
• how do you determine membership and other shared group state?

My work (decentralised MLS)

• describes a way to decide which epoch to use, copy updates from one epoch to another
• assumes some sort of algorithm to determine membership/group state

Downsides to Decentralized MLS

• potentially requires a lot of storage (not clear when we can delete epochs, or if they need to be retained indefinitely)
• managing forks can be complicated

Distributed MLS

• each sender maintains their own MLS group ("sender group")
  • updates their own group, but can pull in information from other groups
• group membership determined by each sender, but pulls in updates from other senders' trees

Downsides

• lose log(n) performance
• lose shared group context
• lose shared membership (but recipients can still see sender group's membership)

Comparisons

Which one is more "MLS-like"?

• both, but for different reasons
• Decentralized MLS: tries to keep MLS semantics, but requires more modifications to protocol
• Distributed MLS: fewer changes to the MLS group operations, but loses semantics (e.g. shared group contetxt)

Which one is faster?

• Decentralized MLS by itself can be O(log(n))
  • managing forks can be expensive, depends on how many forks
• Distributed MLS is O(n) per operation

What are the storage requirements?

• Decentralized MLS: potentially unbounded, but depends on whether you can prune old forks, possibly close to O(n)
• Distributed MLS: O(n²) naively, or O(n)? if you don't keep unnecessary information

Which one to use?

• distributed MLS is more ready-to-use, decentralized MLS has more details to work out
• different tradeoffs
• depends on the underlying messaging protocol

• Matrix (servers are usually available and in contact with each other) - decentralized MLS?
• P2P (Ring, ToX, Briar) - distributed MLS?
• XMPP
  • MUC - plain MLS
  • 1-1
    • plain MLS (designate one server as Delivery Service)
    • distributed MLS?

Other approaches

• centralize handshake messages, decentralized application messages
  • if SPOF fails, group members can send messages, but can't make any group changes, so we lose Post-Compromise Security

• determine a server to be Delivery Service and pick a new one if the current one disappears
  • a lot of literature on leader elections
  • only feasible if "most" candidates are online (so, may not work for e.g. for P2P)

• DCGKA (Weidner et al), BeeKEM (Ink & Switch), or just keep using Signal protocol and variants (Olm/Megolm, OMEMO, etc.)

Questions?