[noise] RFC: Encrypted sliding window transport layer

[Tiffany Bennett]

# RFC: Encrypted sliding window transport layer

I have been talking to Tony Arcieri and others recently about
developing a transport protocol for sending messages in an unordered,
at-least once fashion. I have been suggested, and I am likely to use,
the noise protocol to achieve this.

I have read through the mailing list archives and I have seen some
discussion of unordered protocols, such as ZeroMQ, DTLS. These have
comparable scopes to what I'm attempting, and I believe it's important
that noise support them.

## Sliding window layer

There is a distinction between messages and packets. There is only one
window per packet, but multiple messages can be included in one
window, and a large message can be split over multiple windows.

Each window contains a sequence number, and some number of messages,
and the entire payload of the window is encrypted, rather than
individual messages. I believe this prevents selective dropping of
messages in some cases, subject to the following assumptions:

* The attacker only wishes to drop certain messages.
* There are multiple messages to be sent in the first place, to be
  confused for the message which is to be dropped.
* Extra latency for the sender will not compromise the sender due to a
  race condition.
* The message is not larger than a window, which would mean it is the
  only message in that window.
* That there is always another message being sent whenever the desired
  message is. For example, if the desired message is A, and there are
  other messages are B, C, ...; A series of windows consisting of {A,
  B, C}, {A, C, D}, {B, C, D} repeating in a similar fashion, then it
  is possible that A will never be delivered, if the attacker always
  knows which messages are included in which windows, because they can
  simply drop any message containing A, and the other messages will be
  delivered as soon as a window not containing A is sent.

Messages to be sent are placed into a queue, and whenever a window
needs to be sent, it selects a set of messages which are to be sent,
until it fills the reserved space for the window. Messages which have
a high priority cause a window to be constructed immediately, whereas
low priority messages will wait some period of time until before a
window will be constructed. As long as the queue has more than a
single window worth of messages, a window will always be sent
immediately. Whenever a window is ACKed, all of the messages which
were contained in it are removed from the queue.

Replay attacks will be mitigated by tracking sequence numbers and by
having the sequence number be authenticated by the MAC.

## Problems

Because the noise protocol does rekeying for every message, this
enforces strict ordering for windows when there is none. There are a
few solutions in mind, in increasing levels of preference:

1. Enforcing strict ordering, and essentially recreating TCP
2. Modify noise so as to keep the handshake, but then use the
   resulting keys as session keys, rather than rekeying for every
   message. This breaks the forward secrecy guarantee that if the keys
   are compromised, past messages will not be. If this solution is
   used, there should be a special message type which can force a
   rekey, which is done periodically; or simply closing and
   re-initiating the connection.
3. Only iterate the cipher context when an ACK of a window
   happens. This way, multiple windows will be encrypted with the same
   key, but it will be a small number of windows, and only for a
   roundtrip time if there is no packet loss, which I find
   acceptable. There are some downsides to this approach, however:

   * An attacker can force a client to continue to use the same key
     until it reaches a timeout (or possibly indefinitely) if it simply
     drops any ACKs, or any messages at all from the other peer.
   * The rekeying needs to be able to 'skip' arbitrarily far, which
     could lead to a DoS vector if a peer receives a sequence number
     which is over a million higher than the previous one, forcing a
     huge number of KDF calculations.
   * Each window must contain the ID of the iteration of the chain of
     keys for the other peer to know which one to use, and each peer
     must contain the key from the highest ID of any received message.

   In this way, instead of rekeying on each message, we rekey on each
   roundtrip, which does seem strange, but I believe to be a workable
   approach.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: noise-rfc.md.sig
Type: application/pgp-signature
Size: 543 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20150622/4d5a210c/attachment.sig>