Does using Noise asynchronously weaken its security properties?

Question

Can Noise be used asynchronously without weakening its security properties?

Specifically, there are two users, A and B, who communicate asynchronously by leaving messages for each other on an untrusted server, but they may never be online at the same time. They know each other's public static keys in advance, so the KK pattern seems appropriate:

KK:
  -> s
  <- s
  ...
  -> e, es, ss
  <- e, ee, se

It seems to me that this pattern could be used asynchronously without weakening it.

A and B both initially upload a bunch of ephemeral public keys to the server, and top up the supply when they connect at later times.

Now A wants to send a message to B:

1. Download one of B's ephemeral keys from the server, and run the first handshake step.
2. Run the second handshake step, generating an encrypted public ephemeral key (so handshake is done).
3. Run Noise again with the plain-text as a payload, generating an encrypted transport message.
4. Upload a concatenation of B's plain-text ephemeral key, A's encrypted ephemeral key, and the encrypted message.

When B comes online and downloads the message, they:

1. Discard the message if the plain-text ephemeral key is not on their list of unused keys.
2. Run the two steps of the handshake.
3. Decrypt the encrypted message.

(So in this scenario, B is the initiator and A is the responder.)

I hope this is not off-topic. I thought it was OK because I'm asking more about how to use an existing protocol rather than asking for cryptanalysis of my own design.

Edit 27 August

I found a gotcha in the above scheme today. In section 7.5 of the spec it says:

...patterns starting with K or I have the caveat that the responder is only guaranteed "weak" forward secrecy for the transport messages it sends until it receives a transport message from the initiator. After receiving a transport message from the initiator, the responder becomes assured of "strong" forward secrecy.

So my scheme will only have weak forward secrecy, which is a shame, because the whole point of using Noise was to get forward secrecy. I think X3DH (as used by Signal), gets around this by signing the prekeys (the initial shared ephemeral keys).

Answer 1

Online $\neq$ Synchronous

Yes, Noise can be used in a somewhat asynchronous setting.

Noise is initially meant to be an "online" protocol to establish secure channels, however "online" here does not really imply it requires a "fully synchronous network", but more like a "reliable channel" in which packets will come in the right order but not necessarily at a given time.

The appropriate handshake

In your case you said that:

They know each other's public static keys in advance

Which means indeed that the KK pattern is the most appropriate one. Now, it seems you'd like to have A perform what is called a "0-RTT" encryption (that is encrypting a message/payload for B without having done an interactive handshake first) and this is actually covered by Noise:

Patterns where the initiator has pre-knowledge of the responder's static public key (i.e. patterns ending in K) allow zero-RTT encryption, meaning the initiator can encrypt the first handshake payload.

So, what you want to achieve is actually already possible using 0-RTT and the KK handshake and it's actually in the spec and you don't need to run the different steps differently from what the spec says.

First notice that the lines above the ... are representing the "pre-knowledge" of the parties. They have acquired the static keys through some mean (for example by relying on a server) and then the actual protocol start:

1. -> e, es, ss means that A is sending to B its ephemeral key e and is performing a DH es using its ephemeral key and B's static key, and then it is performing another DH ss using its own static key and B's static key (of which it had pre-knowledge).
2. After having performed these 2 DH, A can already compute the shared chaining key ck which is just a hash of the 2 DH outputs
3. A can then the payload of its handshake using ck. Notice that in all Noise handshake messages, you have an implicit payload which can be zero-length or not. (And which is encrypted under certain conditions.)
4. Upon reception B will learn the ephemeral key of A and has pre-knowledge of its static key, so B is able to compute the same 2 DH as A using the e it received and its own static key and then using both static keys, so B gets the same value for ck and will be able to decrypt the encrypted payload.
5. B generate an ephemeral key, computes the DH ee between the 2 ephemeral keys and compute finally the DH se between A's static key and B's new ephemeral key and now the ck state is updated once more to its "final" state, which A will also be able to compute upon reception of <- e, ee, se. The payload to this message can directly be encrypted as well using ck.
6. Notice that at this point the final shared key ck has been computed as being the hash of first es hashed with ss hashed with ee hashed with se.
7. Subsequent messages can just be encrypted using the resulting key ck and incrementing the nonce (and ad hash) as per the spec.

We need to be careful as the spec is telling us the following:

After performing a DH between a remote public key (either static or ephemeral) and the local static key, the local party must not call ENCRYPT() unless it has also performed a DH between its local ephemeral key and the remote public key. In particular, this means that (using canonical notation):

• After an "ss" token, the initiator must not send a handshake payload or transport payload unless there has also been an "es" token.

But since we had first an es token and then a ss one, we can call ENCRYPT() on our payload. :)

So IMO you do not need to do anything differently from what the spec already allows and does. This is already possible without any change by simply exploiting the optional handshake payloads.

The alternative

Now, while I'm at it, if you really have strong asynchronous requirements, you might want to take a look at what Signal's X3DH is doing with its one-time prekeys since being asynchronous is the goal of X3DH and it's based on a server setup like yours:

X3DH is designed for asynchronous settings where one user (“Bob”) is offline but has published some information to a server. Another user (“Alice”) wants to use that information to send encrypted data to Bob, and also establish a shared secret key for future communication.