Write specification for interaction with prekey server

[rosatolen]

This is the specification we refer to in section "Publishing prekey messages" and "Receiving prekey messages" in OTRv4.

The spec should include how many prekeys may be returned.

[claucece]

WIP here: https://github.com/otrv4/otrv4-prekey-server

[claucece]

To be taken into account:

• Deduplicate information when sending back multiple one-time prekeys i.e., if 100 prekeys get returned, don't say "version 4" 100 times

This issue should also check how it is written on the otrv4 protocol and on ADR009

[claucece]

Docs to check:

• https://signal.org/docs/specifications/x3dh/
• https://github.com/signalapp/Signal-Server/wiki/API-Protocol

[deniscostadsc]

We added first version of the diagram. When creating it, some questions came to ours minds:

• We used a DAKE as a form of authentication between Bob and server. We are not sure if DAKE itself is possible, because so far server doesn't have the same attributes as Alice (i.e. ephemeral ECDH keys). So:
  • A authentication is needed, right?
  • How can we achieve that?
• How server will check if Bob's user profile match with the user profile send from him in this prekey?

[claucece]

@deniscostadsc you use a DAKEZ with the server, not any DAKE. And you don't use this DAKEZ as defined in the otrv4 protocol (which has user profiles, instance tags, etc) but as defined in Nik's paper. It was probably wrong to call those messages 'Auth-I', etc.

[deniscostadsc]

Thanx @claucece 👍 . I got the previous paper, also this paper and the poster.

[claucece]

From discussion with Nik, ;):
So, the server can be defined depending on the client that implements the protocol and the mode they choose. In the 'otrv4-only' mode, for example, it can be the key for whoever developed that client software (there should be such a key to sign updates, for example).

The prekey server will need some OTRv4-specific prekey server software, so this software can easily generate ephemeral keys for each connection.

In the case of the other params needed for DAKEZ:

• "I" should be the identifier that participants use when they query the prekey server for a particular participant's prekey (prob the user profile).
• "R" is just something putted into the client with the long-term public key for the server, like maybe the domain name.

You can check this paper for examples of interactions with a prekey server, although this does not include a DAKE.

Some ideas can also come from 'Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)' (found here), regarding about how to generate the ephemeral keys.

Authentication is needed as if not malicious users can perform denial-of-service attacks. But this authentication should not be normal "signing" of the prekey messages, as it will break the deniability of the whole protocol. To preserve it, a DAKE must be used.

[deniscostadsc]

I added the DAKEZ part to the diagram I'd like someone to review it.

I'm not sure if the prekey should be described on on OTRv4 spec. Or we should descibe this also here.

[deniscostadsc]

So, the server can be defined depending on the client that implements the protocol and the mode they choose. In the 'otrv4-only' mode, for example, it can be the key for whoever developed that client software (there should be such a key to sign updates, for example).

How do I discover which server should I reach to get your key? You are not online and we don't know each other in person?

The prekey server will need some OTRv4-specific prekey server software, so this software can easily generate ephemeral keys for each connection.

This answer how ephemeral keys are generated, but I have another question. It's not clear for me how this communication is going to happen in the application layer. Is this going to change depending on the implementation? It's going to be a REST API?

In the case of the other params needed for DAKEZ:

"I" should be the identifier that participants use when they query the prekey server for a particular participant's prekey (prob the user profile).
"R" is just something putted into the client with the long-term public key for the server, like maybe the domain name.

Nik's paper uses I for the participant who starts the DAKEZ and R for the Responder. It seems you mean something different. For example if Bob would like to share secret with the server before put his key their Bob is "I" and server is "R".

Some ideas can also come from 'Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)' (found here), regarding about how to generate the ephemeral keys.

I think part of of my question about transport layer is going to be answer. But I'll keep it above.

[claucece]

How do I discover which server should I reach to get your key? You are not online and we don't know each other in person?

Why are you not online when you ask the server for something? When you ask to publish a prekey message, you are "online" with the server, so you can ask anything to it. When you retrieve a message, you are "online" with the server, so you can retrieve a prekey message from it. The server is known by the client you are using.

This answer how ephemeral keys are generated, but I have another question. It's not clear for me how this communication is going to happen in the application layer. Is this going to change depending on the implementation? It's going to be a REST API?

Yes. Ideally, we shouldn't be as precise as to define that on the spec, but check how TLS manages it. Or the Signal prekey server. I don't know if its going to be a REST API, but that seems something too precise to include on the spec.

Nik's paper uses I for the participant who starts the DAKEZ and R for the Responder. It seems you mean something different. For example if Bob would like to share secret with the server before put his key their Bob is "I" and server is "R".

On DAKEZ, XZDH, Spawn, etc, there are some parameters which are called "I" and "R" which are not the same as I and R. "I" and "R" are the identifiers for I and R. In the case of the otrv4 spec, this is the user profiles. In the case of the DAKEZ with the prekey server, it can be the what was stated. The "I" and "R" I stated will probably depend on who starts the DAKEZ: if it is the server, then the server is I and has what I stated as "R" as "I"; if the participant starts it, then the participant is I and has what I stated as "I" as "I".

I think part of of my question about transport layer is going to be answer. But I'll keep it above.

Check how they define it.

[deniscostadsc]

How do I discover which server should I reach to get your key? You are not online and we don't know each other in person?

Why are you not online when you ask the server for something? When you ask to publish a prekey message, you are "online" with the server, so you can ask anything to it. When you retrieve a message, you are "online" with the server, so you can retrieve a prekey message from it. The server is determined by the client you are using, so your client knows.

My question was really miswritten. Here it goes again:

Bob uses CoyIM as OTRv4 client
Bob publish his prekey to the server specified on CoyIM
Bob goes offline
Alice uses a random OTRv4 implementation
Alice sees Bob is offline

How Alice knows which server to reach, if the information is described on a client she doesn't use?

[olabini]

In general, the way a prekey server is discovered will need to be defined in a protocol specific way. For example, I think we need to make it so that an XMPP server will make it possible to say what prekey server to use for that xmpp server. The other alternative, which might be better, is that an xmpp-user has an attribute that can be fetched, that contains the prekey server to use for that user. For example, it might possible to use XMPP pubsub to set a persistent value on a node, associated with a JID, so what you do when wanting to contact a person would be to lookup the "otr_prekey_server" node on the JID you're looking for. But in general, this is going to be different for different networks.

[olabini]

Also, about naming of messages and participants - it might help reduce confusion if we can rename both the packet names, and the I/R thing

[claucece]

Also, about naming of messages and participants - it might help reduce confusion if we can rename both the packet names, and the I/R thing

Yeah, it was only to explain how it is in Nik's paper. But on the spec it should be different (maybe: Alice - Server - Bob). And the identifiers for each one, should state what they are, rather than "I" or "R".

I'm not sure if the prekey should be described on on OTRv4 spec. Or we should descibe this also > here.

The OTRv4 should only state when you need to interact with the server, basically. The otrv4-prekey-server spec, on contrary, will give the details. When needed, the otrv4 spec can maybe put a link to the prekey-server spec.

[deniscostadsc]

I'm not sure if the prekey should be described on on OTRv4 spec. Or we should descibe this also > here.

The OTRv4 should only state when you need to interact with the server, basically. The otrv4-prekey-server spec, on contrary, will give the details. When needed, the otrv4 spec can maybe put a link to the prekey-server spec.

Perfect!

[deniscostadsc]

Also, about naming of messages and participants - it might help reduce confusion if we can rename both the packet names, and the I/R thing

Yeah, it was only to explain how it is in Nik's paper. But on the spec it should be different (maybe: Alice - Server - Bob). And the identifiers for each one, should state what they are, rather than "I" or "R".

Yeah I agree. @olabini, @claucece and me already have this discussion and we agreed to leave like that while we have no decision on how this identification ("i" and "R") should be on OTRv4. This confusion prone is already mapped. 👍

[deniscostadsc]

In general, the way a prekey server is discovered will need to be defined in a protocol specific way. For example, I think we need to make it so that an XMPP server will make it possible to say what prekey server to use for that xmpp server. The other alternative, which might be better, is that an xmpp-user has an attribute that can be fetched, that contains the prekey server to use for that user. For example, it might possible to use XMPP pubsub to set a persistent value on a node, associated with a JID, so what you do when wanting to contact a person would be to lookup the "otr_prekey_server" node on the JID you're looking for. But in general, this is going to be different for different networks.

OTR is suppose to be agnostic to communication protocol. I think this is a tight coupled to XMPP solution that goes against the agnostic feature.

[olabini]

Yeah, @deniscostadsc - you are completely right. However, the prekey server is the one thing that really can NOT be agnostic. That's one of the reasons why we have it as a separate specification. I have also been thinking about the possibility of making specific specs for each integration - ie "prekey XMPP integration", "prekey Skype integration" etc.

[deniscostadsc]

Yeah, @deniscostadsc - you are completely right. However, the prekey server is the one thing that really can NOT be agnostic. That's one of the reasons why we have it as a separate specification. I have also been thinking about the possibility of making specific specs for each integration - ie "prekey XMPP integration", "prekey Skype integration" etc.

It makes sense! So I'm going to work with XMPP in mind.

[deniscostadsc]

One thing I realized reading this paper is that Signal users publishes many prekeys (usually 100). This helps to mitigate the problem of all offline communication using the same prekey. If this prekey leaks all offline communication are compromised. Probably we should do something similar.

[deniscostadsc]

Another point about Signal protocol is that they use HTTP-REST API, what increases the complexity of the prekey server. You need at least a HTTP server serving this API. With the mind set of "less code as possible" that could be a problem, Although I like the idea of REST API, because is a common pattern these days. Of course this complexity brought by REST isn't a big problem because this server suppose to holds only public information.

[deniscostadsc]

Do we need a authentication with Alice when she tries to retrieve the prekey message?

[claucece]

Looking at Offline Conversation Initialization section on OTRv4 specification, I realized that the prekey message is generated the same way as as identity message (maybe this section is duplicated, if not, explain me the difference).

The difference between an Identity message and a Prekey message is that the latter specifically needs a shared prekey and a siganture of it (which is the same, right now, as the signature of the user profile). As discussed with @olabini on the IRC chat, the format (structure) of the prekey message now is going to change because the prekey message will have an user profile and a "prekey-profile" (or whatever its name). An identity message will only have an user profile.

At this moment is not clear how a prekey message is generated. Here says we need a user profile, a ephemeral ECDH key pair, a the ephemeral DH key pair and an intance tag. If I'm a server and Bob is going to send me 10 prekey messages, is he going to send me {profile_0, echd_keys_0, dh_keys_0, instance_tag_0, profile_1, echd_keys_1, dh_keys_1, instance_tag_1, ... , instance_tag_10}?

A user profile has an expiration date. There is only one profile during that time until it expires (or there can be two when the first is closed to get expired). Shared prekeys expire with the user profile, long term public keys do not.

The prekey message is generated as this:

1. Assembly (prior) an user profile.
2. Assembly (prior) a prekey profile, as discussed with Ola.
3. Generate ephemeral keys.
4. Generate an instance tag for the location you are using.
5. With all of this, create a prekey message.
6. Publish it to the server.

There should always be valid prekey messages on the prekey server, meaning, prekey messages that do not contain an expired user profile. Nevertheless, this can be on storage:

{id, profile_0 (with x expiration date), echd_keys_0, dh_keys_0, instance_tag_0 (for an specific location)}
{id, profile_1 (with a different x expiration date), echd_keys_1, dh_keys_1, instance_tag_1 for an specific location)}
{id, profile_0 (with x expiration date), echd_keys_2, dh_keys_2, instance_tag_0 (for an specific location)}
{id, profile_1 (with a different x expiration date), echd_keys_3, dh_keys_3, instance_tag_0 for an specific location)}

etc.

An user requesting for prekey messages check for the expiration of the user profile in them. If it is expired, the prekey message is invalid.

The user profile section says that it has a Public Shared Prekey (Ed448 Public Key), and that prekey is used in multiple prekey messages. How?

A shared prekey has an expiration date (it expires when the user profile expires). Therefore, it can be used for multiple prekey messages (until it expires).

Are those ephemeral keys above derived from this key? Reading this I'd say the answer is no.

The ephemeral keys are not derived from the shared prekey. The private part of it is generated randomly and then the public part is generated by multiplying the private part by the generator.

You need a shared prekey because:

XZDH (without a shared prekey and a signature) can be vulnerable to an attack where an active adversary modifies the first flow from I to use an adversarially controlled ephemeral key, captures
and drops the response from R, and then compromises I’s long-term secret key. I will never see
the message, and the adversary will be able to decrypt it.

You mitigate this attack by using a signed shared prekey (signed by long-term secret keys) that is reusable and has an expiration date.

[claucece]

Do we need a authentication with Alice when she tries to retrieve the prekey message?

No. Anyone can request prekey messages from the prekey server, because anyone can produce a non-interactive-auth message from it.

[olabini]

It might be useful to have some kind of deniable authentication anyway, just to make it possible to do rate limiting - but I'm not sure that's a good idea.

[claucece]

This still needs some internal revision, but it is done for now.