Proposed end-to-end encryption protocol

[vith]

Background

This protocol is an adaptation of Matrix.org's Olm and Megolm encryption to the IRC protocol.
Olm is an implementation of the double ratchet algorithm developed by Open Whisper Systems and
first used in the Signal app.

The IRC adaptation is being designed under KiwiIRC with the goal of creating a modern end-to-end
encryption standard for IRC that could be implemented by many different clients.

Peer sessions

Raw byte arrays are base64 encoded without padding for transmission as Message Tag values.

To establish a one-on-one session with another user, we must first obtain their public identity key
and a one-time-key.

# request public identity key
@+kiwi/olm-identity-request TAGMSG bob

# receive public identity key response
@+kiwi/olm-identity=2XA4WCDGeTi9OW/XaiKXN550LUTsw0sQpi0UKANAxWZd7lLodg :bob!bob@example.com TAGMSG alice

# request one-time-key
@+kiwi/olm-onetimekey-request TAGMSG bob

# receive one-time-key response
@+kiwi/olm-onetimekey=2XA3WCDNR7uNOVnzjrvXRVA9p3FyHWLUPBP/w+GVUXkXneHYaw :bob!bob@example.com TAGMSG alice

At this point, alice can construct an outgoing session to bob using the onetimekey and identity and
start sending encrypted payloads such as OlmMessages:

# encrypted OlmPacket containing an OlmMessage with the text "hello"
@+kiwi/olm-packet=2XA1g1ggGsgfjI52+dKMvHbHOu9ujGcUq+7Z905ah+lh+8rpehEAWKgDCiAjcvT3D6AQNHKzFXOmb6jNssLC7m+G2kHC1AsZsJOaBBIglK1cV5dWjyWpc5aTxcJhTNuXkJdlwb5Msah6jQDp9m0aIBrIH4yOdvnSjLx2xzrvboxnFKvu2fdOWofpYfvK6XoRIj8DCiDVs+9A28hvj/YpQ+7aNgh92SpAZvBJSE6hckSgF8iUZxABIhD4/ZpTTCeh8YnWjSyiEs0qvvmY8j755/o TAGMSG bob

When the first packet is received by the other side, they will be able to construct the session
ratchet and use it to send packets back as well.

Group sessions

For one-to-many encryption (in IRC channels), each sender creates an outbound-only ratchet. This
mitigates some scalability issues with ongoing sessions in large channels by avoiding the need to
encrypt a copy of each message separately for each recipient. First, encrypted one-to-one sessions
must be established between participants, as described in the previous section. Once these secure
channels are available they are used to share the ratchet state for the outbound group sessions.
Further details about the ratchet design can be found in the [Megolm docs].

# encrypted OlmPacket containing a MegolmSessionState
@+kiwi/olm-packet=2XA1g1ggTR6P+jorlFtkqxc8ZjvdqqP598MYtWftFikr+wDhuCYAWQGqAwogSSqvrpm9pz7w2u+CBySrcU7G5PQrNsibQ4Mpa/JfDQwSIJagDGK3zbd23eABM1Z84FnLWb3TBFbjzPjVv0ROVZo/GiBNHo/6OiuUW2SrFzxmO92qo/n3wxi1Z+0WKSv7AOG4JiLAAgMKIEpGWJSu6xndGM1kaRGaSGOIIhXMOhv8jszNhcIrm7hnEAAikAI5NEOwE6EaoLYJkb/jfKaraL9op/XQ7ooLb7c9dnuDa0pelZ01+8VdBqIB+R+RO48dnz+QrN0N3xqHcxHSfOgP8mcdT2TanLVax8DnSgaqaLOlCeIv3vA3HQCl2BVTMUoD7j0s0fQH+v2YOZvUB8IEvVe4AOYNRcRhB+P4yz5s1AQ9/vPmOo6o/Nxu8UOHl7065pplL6ngMR5IGzECVq3ohxYpF0oXXxVT9Q0X7Arm8tLA3+LBLOSAqPfYMPySWw+YXuwwNWOFNbGm4MDVWWr/nzi7GFjc5zTGtBJkBwMAp0Qt40pUUoAdbXkW4hzJrgQnVNBZdYVkg4IDllSKCdcoWPw9/NMEYf3syS+5H1LB8Kdg+gPmEP4t TAGMSG bob

After receiving the MegolmSessionState, any MegolmPackets created with that session from that point
forward can be decrypted.

# encrypted MegolmPacket containing a MegolmMessage with the text "hello"
@+kiwi/megolm-packet=2XA6hFhdAwgAEhCHnBpj2VbBf2pS5C9oV+fJhwMgb7b9IRAdE0Lstg4lSniU/Wc8FJeY5DEE+2feUocZQkaJtRk16oyTrNH+VENClcyHBpGQsnay7qVQWoXtD1oYEKSOmZcNWCBGUHuR6rck9tWqwTbFzXNX3ipREMFLdoBJq7jwot97EFggpJKNuwSzSe+dvEnxGJysH7XnfY9AYnQTmp9PL6ffhH9YQCKLjDvQNdSZVm65HOVCbEmEud3KTL+0rgFLf6M8OukBm91wnZ8+FacjAlzGFJBYYEH3PG2zOUXUSdp7SBqI3wQ;draft/msgid=bqx72n65z1921xh7 :alice!alice@example.com TAGMSG #example

All of the protocol sample codeblocks up to this point form a complete key negotiation and
conversation between two users in both one-to-one mode and group mode.

Payload types and serialization

Protocol payloads are serialized to CBOR as tagged entities with the following tag IDs and fields:

OlmPacket

• CBOR tag: 0x7035
• CBOR value: [senderKey: ByteString, type: int, body: ByteString]

The body field can contain an encrypted OlmMessage or MegolmSessionState.

OlmMessage

• CBOR tag: 0x7036
• CBOR value: text: string

A single chat message in a peer session.

OlmOneTimeKey

• CBOR tag: 0x7037
• CBOR value: oneTimeKey: ByteString

Combined with an OlmIdentity, OlmOneTimeKey is used to initialize a new peer session.

OlmIdentity

• CBOR tag: 0x7038
• CBOR value: curve25519IdentityKey: ByteString

MegolmMessage

• CBOR tag: 0x7039
• CBOR value: text: string

A single chat message in a group session.

MegolmPacket

• CBOR tag: 0x703a
• CBOR value: [ciphertext: ByteString, senderKey: ByteString, sessionID: ByteString, signature: ByteString]

Ciphertext contains an encrypted MegolmMessage.

MegolmSessionState

• CBOR tag: 0x703b
• CBOR value: [sessionID: ByteString, sessionKey: ByteString, messageIndex: ByteString]

Contains the ratchet state necessary to decrypt received MegolmPackets from a user.

Message Tag fragmentation

Because the serialized payloads can be particularly large, the message tag data will sometimes be
split across multiple IRC messages.

When a message is fragmented, it is marked with the tag @+kiwi/fragmented. When a message is a
continuation of a previous fragment, it is tagged @+kiwi/previous-frag=<previous message ID>.

Fragmentation is only allowed on the following tags' values:

+kiwi/olm-packet
+kiwi/olm-identity
+kiwi/olm-onetimekey
+kiwi/megolm-state
+kiwi/megolm-packet

The tag values should be split into chunks of as large a size as possible within the limitations of
the Message Tags spec. The chunks do not need to be of equal size, but they must be transmitted in
order.

A client must not interpret the fragmented data until it has been reconstructed, with the final
fragment being indicated by the lack of a @+kiwi/fragmented tag.

For example, @+kiwi/olm-packet=abcdefghijklmnopqrstuvwxyz TAGMSG user could be fragmented as
follows:

# receiver view:
@+kiwi/olm-packet=abcdef;+kiwi/fragmented;draft/msgid=100 TAGMSG user
@+kiwi/olm-packet=ghijklmnopq;+kiwi/fragmented;+kiwi/previous-frag=100;draft/msgid=101 TAGMSG user
@+kiwi/olm-packet=rstuvwxyz;+kiwi/previous-frag=101;draft/msgid=102 TAGMSG user

The sender will need to use a label tag and the echo-message capability to find the
draft/msgid of their sent message fragment in order to reference it with the +kiwi/previous-frag
tag.

Creating a compatible implementation

Our experimental javascript implementation makes use of the C libolm library compiled to WASM with
emscripten. Clients written in other languages should be able to use bindings to libolm to
implement the protocol in without needing to reimplement the cryptographic functions from the Olm
specs. Although the latter always remains a possibility.

Points of difficulty / Room for improvement

Tag fragmentation

1. It's unfortunate to have to reimplement layer 3 IP packet fragmentation inside a layer 7
   protocol.
2. Calculating the available space for each fragment of data is somewhat tedious because it depends
   on the length of the server's generated msgids, whether we're trying to send the first, last, or
   a middle fragment, and so on.
3. Having to use echo-message with a label to find out your own msgid adds significant latency
   since we can't predict or generate our own msgids.
4. Care must be taken to avoid DoS from yourself (if the available data space in client tags was
   very small due to other tags being present) or others (i.e. resource leaks from never completing
   the reassembly process).

Binary encoding overhead

Not having a way to directly transmit binary data causes significant overhead through base64
encoding.

Message Tags vs CBOR tagged entities

There is some impedance mismatch between the Message Tags and the CBOR serialized records. For
example, MegolmPacket packs four different values into one tag because using a separate Message Tag
for each part would be quite verbose, which eats into the space available for the actual data. The
values of our tags end up being self-describing through very efficient headers inside the CBOR
serialization, so it's tempting to only use a +kiwi/olm tag for everything instead.

The self-describing serialized values are necessary for part of the protocol due to the end-to-end
encryption itself: some of the protocol messages need to be encapsulated inside encrypted blobs, and
we might as well not leak metadata about the nature of the encrypted payload.

But I stuck with multiple separate Message Tags in an attempt to mesh with the human-readable style
of the IRC protocol to the extent it was possible.

[slingamn]

How does this relate to https://github.com/otrv4/otrv4 ?

[Alexendoo]

Covered in #ircv3: OTR is for single device-device encryption only

[jesopo]

2 issues with the Olm side of this

• don't know when the other user disconnects - you ratchet but the other side doesn't see the message (ERR_NOSUCHSICK)
• don't know when the other user disconnects - don't know you might need to renegotiate session

Both could be solved by having a way to tell the other user that you don't know the session they're using to encrypt stuff, thus triggering a renegotiation

[jesopo]

I feel it pertinent that there's some teething issues with using things like Olm wrappers.

I tried to get the python-olm lib working today and ended up having to jump through some hoops for it because Debian repos don't have libolm3 yet and the python wrapper in pip (which needs libolm3 rather than libolm2 which Debian has) can't have the C source included with it due to US crypto export control laws (this is the same reason the Olm source code is gitlab.matrix.org instead of github.com)

https://gitlab.matrix.org/matrix-org/olm/blob/b46ac91928f5fb332d04f595730e5e29164f74da/README.md#legal-notice

[SadieCat]

@jesopo This will be an issue regardless of crypto algorithm used.

American crypto export laws are widely ignored by existing IRC implementations for OTR so I don't see why this will be an issue for OLM.

[RyanSquared]

It's not that it's an issue with OLM directly, but it's an issue with encryption in general when the libraries are distributed/hosted in the US. The fact that it's not an issue with OTR is only representative of the fact that it's not noticeable by the government, right? Wouldn't this happen regardless of algorithm used so long as the distributed/hosted are published in the US?

[jesopo]

American crypto export laws are widely ignored by existing IRC implementations for OTR so I don't see why this will be an issue for OLM.

just a note about this potentially not being very pleasant for client devs to work with.

[slingamn]

My impression is that there is a full carve-out in the export regulations for FOSS:

"Publicly available" encryption source code is not subject to the EAR once the email notification per section 742.15(b) is sent. A common example would be open source encryption source code available for free online.

I think we should not allow the export regulations to deter us from standardizing OLM (or any other cryptographic algorithm).

[slingamn]

The following is a partisan/opinionated summary of some discussion from #ircv3 (not all of these ideas are mine, but any misconceptions are):

1. In the two-party case, we already have OTRvN, which is widely implemented, works without support for tags (tunnelled in the parameter of PRIVMSG, with fragmentation support), and has superior support for establishing key trust (more on that later).
2. I'm not sure what threat models make sense for multi-party chat. If I'm interpreting the Megolm spec correctly, any party can pass the ratchet state to a new participant, so in terms of key trust, an attacker only has to convince a single participant that their key is trustworthy.
3. Key trust is really the hard problem here.
4. Unlike XMPP (and Matrix?), the primary messaging target in IRC is the nickname, which is completely untrusted. This problematizes the use of trust-on-first-use for keys in the IRC setting, even where this technique has been successful in other domains.
5. account-tag is a partial fix for this problem; we might want to recommend its use.
6. OTRv3.1 and higher support the socialist millionaires algorithm for establishing key trust using low-entropy shared secrets. This is a concrete improvement on telling users to verify out-of-band.
7. pidgin-otr has a solid UI built around this protocol feature, including "shared secret" and "question-and-answer" dialogs. We should be trying for something that can be at least this good.
8. Some interesting proposals were floated for using the server (via METADATA and possibly other features) to maintain a directory of keys, and then policing the accuracy/trustworthiness of this directory, but I didn't understand them very well so I'll leave it to others to describe them.
9. In my personal opinion, the benefits of multi-party E2EE are sufficiently marginal, relative to OTRvN for two-party and TLS-everywhere for multi-party, that the priority should be on producing a very strong proposal, even at the expense of shipping in a timely fashion.

[slingamn]

I just came across a blog post about the Messaging Layer Security working group, which may have a better story about key trust and revocation:

• https://blog.trailofbits.com/2019/08/06/better-encrypted-group-chat/
• https://messaginglayersecurity.rocks/

[vith]

9. In my personal opinion, the benefits of multi-party E2EE are sufficiently marginal, relative to OTRvN for two-party and TLS-everywhere for multi-party, that the priority should be on producing a very strong proposal, even at the expense of shipping in a timely fashion.

I think there are at least two group usage modalities we should consider.

Small, invite only group chats benefit from not needing to trust a service provider to protect their privacy.

On the other hand, huge public rooms with hundreds or thousands of users don't really see the same benefits, because participants already have to expect that their communications there are not private, with or without E2EE--because without controls on who can join, you have to assume that someone malicious has. So yeah, the benefits over TLS are more marginal for that scenario.

But this difference leads to an important problem to solve: how to securely control the policy around whether to freely share the ratchet state with new users.

Perhaps a boolean promiscuous field should be added to the MegolmSessionState type.

[vith]

4. Unlike XMPP (and Matrix?), the primary messaging target in IRC is the nickname, which is completely untrusted. This problematizes the use of trust-on-first-use for keys in the IRC setting, even where this technique has been successful in other domains.
5. account-tag is a partial fix for this problem; we might want to recommend its use.

Agreed, the mutability of nicknames (well, more so, the unreliability of their ownership) is a problem. An environment where presence in a network/channel is persistent and independent from having a live network connection makes things much simpler. As far as I can tell this is related to CHATHISTORY, but not technically part of it? I wonder if it should somehow be a formal requirement for E2EE.

[slingamn]

An environment where presence in a network/channel is persistent and independent from having a live network connection makes things much simpler. As far as I can tell this is related to CHATHISTORY, but not technically part of it? I wonder if it should somehow be a formal requirement for E2EE.

I've implemented such a feature in Oragono 2.0.0 ("always-on"), but have not thought much about how to specify it or make it discoverable. How do you see this as changing the state of play, though? In a typical Oragono deployment, some clients will be always-on and others won't, and there's no way to detect whether another client is always-on.

I think if we wanted to use the account system to harden TOFU, the thing to do would be to require account-tag on the relevant handshake messages.

Perhaps a boolean promiscuous field should be added to the MegolmSessionState type.

Do you have any thoughts on megolm vs. MLS?

[GIJack]

The following is a partisan/opinionated summary of some discussion from #ircv3 (not all of these ideas are mine, but any misconceptions are):

4. Unlike XMPP (and Matrix?), the primary messaging target in IRC is the nickname, which is completely untrusted. This problematizes the use of trust-on-first-use for keys in the IRC setting, even where this technique has been successful in other domains.

I think most of the point of IRCv3 is to address this and create strong, owned, authenticated nicknames.

[RyanSquared]

Wouldn't say it's "most of the point" but it is a very strong point, that you should be able to obtain an account from a message. BitBot for the most part tracks by account name too, which is very nice.

[slingamn]

I think most of the point of IRCv3 is to address this and create strong, owned, authenticated nicknames.

I don't think there has been much systematic attention to this issue. In a typical multi-server network, if the services framework goes down, I think the rest of the network will continue functioning with reduced or nonexistent nickname protections. Oragono can be configured to have nickname protections ranging from very strong (i.e., if the ircd is up at all, then nicknames are strictly protected and the nickname and the account name are synonyms) to nonexistent, but there is no ISUPPORT token to convey to the client which of these states is in effect.

All that being said, I think the use case here is largely addressed by account-tag --- you could just require account-tag on the handshake messages that try to establish the counterparty's key. This seems peripheral to the megolm vs. MLS question.

[GIJack]

I don't think there has been much systematic attention to this issue.

Then IRC3 has already failed. This is THE big problem with IRC.

[ribosomerocker]

Doesn't something like OTR (mentioning this now would be helpful) help for some of this? I think they have some overlapping use-cases. Though, I did hear about OTR not at all being usable for public channels - but it could be a start.

[nektro]

still digesting the full conversation but wanted to mention https://saltpack.org/ which was developed by keybase

[nektro]

double ratchet and more is now an RFC https://www.rfc-editor.org/rfc/rfc9420.html