## Boring Protocols

One of my favorite movements in cryptography in recent years has been the trend
towards "boring cryptography": protocols built on well-understood building
blocks, tightly constrained to remove common sources of vulnerabilities. Boring
cryptography prioritizes:

* Data-independent control flow: to avoid side channels & cache attacks
* Very large security margins: to avoid caring about incremental attack gains
* One True Cipher Suite: agility expands attack surface & lets attackers choose
                         the weakest available target suite
* Correct software: especially automated validation & formal correctness

A boring *protocol* should therefore be one composed of simple building blocks,
and in which:

* Attacks are detected and rejected as early as possible, to reduce attack
  surface
* Concerns that do not have to be handled at the cryptographic layer are handled
  at other layers - especially flow control, buffering, and similar

Here's a sample boring protocol, which allows for bidirectional communication
of ordered messages of up to a fixed length between a client C and a server S.

### Goals

This protocol has these goals:

G1. Privacy: Nobody other than the protocol participants should be able to
    learn the contents of messages.
G2. Integrity: Nobody should be able to modify or forge protocol messages and
    have them accepted by any participant.
G3. Liveness: Nobody should be able to usefully replay a previous instance of
    the protocol, to either client or server.
G4. Reflection resistance: The protocol should not admit "reflected" DoS
    attacks, in which a server is tricked into sending a reply to a forged
    client address much larger than the client initially sent.
G5. Stealth: There should be no "fixed" signatures of the protocol on the wire,
    either as specific bitstrings that are always present, or as long-lived
    values (public keys, etc) that are sent in the clear. Furthermore, it should
    not be possible for an attacker to prove that the protocol is being
    executed.

G4 and G5 are not strictly necessary for a lot of uses, but complying with them
is an interesting extra constraint.

### Syntax & Primitives

Let's define some primitives:

* m is a plaintext message, of no particular structure
* c is a ciphertext, of no particular structure
* (Up, Pp) are a fixed public-private key pair that identify the *protocol*, not
  any given participant in it (!)
* (Us, Ps) are a public-private key pair for the server
* (Uc, Pc) are a public-private key pair for the client
* a || b means "append b to a"
* a ^ b means "bitwise exclusive-or a and b"
* "abc" is a byte string, without terminating null byte
* nonce() generates a random bit-string of length 256
* skey() generates a random bit-string of length 256
* knownclient(Uc) returns whether Uc is an allowed client key
* box(Ux, Py, n, d) is a PKAE[1] function that encrypts d with a nonce n, such
  that:
    * Only the posessor of Px can decrypt it
    * Having done so, if they have Uy, they can verify that it was encrypted
      by a holder of Py
* unbox(Uy, Px, n, d) is the inverse of box(), so it:
    * Decrypts d using Px and nonce n
    * Verifies that d was produced by a holder of Py
* enc(k, n, d) performs authenticated encryption of d with key k & nonce n
* dec(k, n, d) performs authenticated decryption of d with key k & nonce n

### Key Exchange

Let's assume that all clients and servers are statically aware of each other -
i.e, every client and server are aware of the full set of Uk for every k. This
is a big assumption to make, but it significantly simplifies the protocol. There
are ways to augment the protocol to design this assumption out, which I'll talk
about at the end, but for many uses this assumption actually holds true.

Let's also assume that clients always contact servers first. Note that servers
can also act as clients of other servers (with their own client key pair) if
that's convenient, but that is outside the scope of this protocol.

When a client C wishes to exchange messages with a server S, for which it
already possesses Us:

       C: N = nonce(), Kc = skey()
       C: Bc = box(Us, Pp, N, "1ch" || Uc || N || Kc)
  C -> S: N || Bc                                           "client hello"
       S: (N, Bc) = unbox(Up, Ps, N, Bc)
       S: if (!knownclient(Uc)), end the protocol
       S: Ks = skey(), K = Kc ^ Ks
       S: Bs = box(Uc, Ps, N, "1sh" || N || Ks)
  S -> C: Bs                                                "server hello"
       C: K = Kc ^ Ks
       C: discard N, Kc
       S: discard N, Ks

After key exchange is complete, both C and S posess K, which is a shared secret
key.

One remark about Up/Pp: using a fixed, static key pair for this allows for two
goals:
1) The client can produce an unauthenticated "client hello" box, which otherwise
   requires sending the client's public key on the wire so that the server can
   open the box
2) This uniquely identifies the protocol without including any cleartext version
   number or header, to help meet G5

Does this part of the protocol meet the goals listed above? Let's see:

#### G1 - Privacy
Only N, a random bit string, is sent in the clear. Bc is boxed to Us, so only
the holder of Ps (the server) can open it. Bs is boxed to Uc, so only the holder
of Pc (the client) can open it.

#### G2 - Integrity
An attacker could edit N, Bc, or Bs in transit. Editing N would cause Bc not to
unbox, which will cause the server to end the protocol. An attacker could edit
Bc and N, but does not possess Kc, so they can make:

  N' || box(Us, Pp, "1ch" || Uc || N' || Kc')

which will cause the server to reply with:

  box(Uc, Ps, N', "1sh" || N' || Ks)

however, without Uc, the attacker can't open this box to get Ks, and therefore
can't compute K' = Kc' ^ Ks.

Obviously an attacker can substitute their own Uc' (for which they possess Pc')
in:

  N' || box(Us, Pp, "1ch" || Uc' || N' || Kc')

but the server will reject this message, since Uc' is not a known client key.

#### G3 - Liveness
An attacker could replay a previous client hello, to which the server would
respond with a new server hello. However, the new server hello would include
a fresh Ks, which the attacker would be unable to recover, so they would be
unable to complete the key exchange.

An attacker can't replay a previous server hello, because the server hello
includes a nonce supplied by the client.

#### G4 - Reflection Resistance
The server hello is strictly shorter than the client hello.

#### G5 - Stealth
The client hello is indistinguishable from random bytes: it is composed of a
nonce, then a box an attacker can't open (and hence can't verify as a valid
box). The server hello is a box an attacker can't open, and hence can't verify
as a valid box.

### Steady-state protocol

Once key exchange has concluded, the protocol is in "steady state": the client
and server have authenticated each other, and both parties can exchange messages
in either direction and any order until one party wishes to end the protocol.
The steady-state message protocol uses three values:

  K: a symmetric key, computed as part of key exchange
  Nc: a nonce, beginning at zero, incremented by 2 for each client message
  Ns: a nonce, beginning at one, incremented by 2 for each server message

To send a client message m, the client does:

  C -> S: enc(K, Nc, m)
  C: Nc = Nc + 2

and upon receipt the server does:

  S: m = dec(K, Nc, enc(K, Nc, m))
  S: Nc = Nc + 2

To send a server message m, the server does:

  S -> C: enc(K, Ns, m)
  S: Ns = Ns + 2

and upon receipt the client does:

  C: m = dec(K, Ns, enc(K, Ns, m))
  C: Ns = Ns + 2

It's easy to see that this also meets the protocol goals:
G1: all messages are encrypted under K, so an attacker cannot recover any of it
G2: all messages are authenticated under K, so an attacker cannot modify them.
    additionally, since Nc never equals Ns, an attacker can never "reflect"
    a C -> S message into an S -> C message or vice versa.
G3: each message has a unique nonce and nonces increment on the receiver side
    automatically, so a replayed message will not have the correct nonce and
    will not decrypt correctly.
G4: there is no specified reply to any given message.
G5: message data on the wire is solely encrypted messages, which are indistinct
    from random data

If we wanted to make the protocol extensible here, we would do so by prepending
data of known, fixed length to m before encrypting it, and checking for /
processing that data on decryption. In this case we've avoided that, because it
is not necessary for a protocol this simple; if we wanted to support re-keying,
re-authentication, protocol switches, or similar, we would need to do so.

### Termination

Either side is free to close the transport-layer connection at any time. There
is no in-band way to terminate the protocol.

### Removing The Static Key Set

One part of the protocol that I glossed over was this:

  knownclient(Uc) returns whether Uc is an allowed client key

The simplest way to do this is for the server to have a priori knowledge of all
valid clients. However, that can be unwieldy if there are a lot of clients.
There are a few ways to deal with that:

1. Push authentication to a higher layer: allow any client key to perform key
   exchange, then have a higher-level protocol do authentication in any way
   it desires (or not at all). "Anonymous" HTTPS does this.
2. Introduce a secret token that the client provides in the client hello, to
   identify itself, and accept any client key. IRC and some older protocols do
   this.
3. Introduce a notion of "authorities" that can validate the identities of
   clients, and reduce the problem to servers having static knowledge of all
   authorities, rather than all clients. HTTPS with client certificate auth
   does this.

We now need to introduce two new primitives:
* sign(Px, m) signs a message m with Px
* verify(Ux, m) verifies that a message m was signed by the holder of Px

And provide the client with a certificate Cc, which is:

  Cc = Ua || sign(Pa, "client" || Uc)

Then in the client's hello, instead of:

  Bc = box(Us, Pp, N, "1ch" || Uc || N || Kc)

the client computes:

  Bc = box(Us, Pp, N, "1cha" || Cc || N || Kc)

and the server, when opening Bc, receives Bc and checks:

  verify(Ua, sign(Pa, "client" || Uc)) == "client" || Uc

to get Uc.

### References

[1]: "Authenticated Encryption in the Public-Key Setting: Security Notions and
     Analyses" by Jee Hea An