Explore nonce-misuse resistant ciphers

[zanebeckwith]

In XTT, the sequence numbers are critical to the security of the protocol: it is the assumption that sequence numbers are strictly monotonic that ensures per-packet nonces (for the AEAD protection of packets) are truly unique. Repetition of a sequence number opens up all the concerns of nonce-misuse in symmetric ciphers (e.g. all the CBC chosen-ciphertext attacks on TLS, like BEAST).

Sequence number monotonicity may be tricky for either/both servers and clients:

• (Servers) Due to the fundamental design criterion of XTT that its sessions be independent of transport-layer connections, session state is expected to be shared amongst distributed physical machines. The session sequence numbers are updated on each packet processed, making fault-tolerant sharing difficult.
• (Clients) Client implementations may not properly persist a used sequence number (send a packet -> not save its sequence number -> crash -> reuse that sequence number on restart). This may be compounded by slow access to non-volatile memory on constrained devices. Further, simply using random numbers for the nonce, rather than the sequence-number-based approach we have, is a non-starter considering many devices may have no/poor rng's.

It's hoped that the next generation of ciphers (e.g. the eventual winners of the CAESER competition) will have nonce-misuse resistance designed in. Until that time, though, we have to be careful with the expectations we place on our users with respect to nonce hygiene.

For now, in our (Xaptum's) server implementations, we have to make sure we follow good sequence number hygiene. This probably means something like making the low-order ~16-bits of the sequence number a machine-specific ID, thus ensuring that two machines never use the same sequence number (in the event of a crash, the machine that takes over may still use an old sequence number, but that will simply result in packet rejection and not in compromise of the security).

We should add a recommendation on such sequence number hygiene in the implementation notes of the spec.

For future reference, here are some thoughts on nonce-misuse resistance:

• SIV (Synthetic Initialization Vector) mode of a block cipher to give nonce-misuse resistance
  • = Keyed-hash of message fed in to create IV
  • IV = prf<Key>(nonce | addl-data | plaintext)
    • where nonce is a traditional nonce (maybe random, maybe a counter, maybe screwed up and repeated)
  • No requirement for random numbers, nor to keep state for a counter
  • Same message with same nonce gives same ciphertext
  • If different message, even with no counter or randomness, different ciphertexts
  • "Two-pass" (hash entire message, then AEAD encrypt it), so slower usually than other approaches
• Current nonce-misuse resistant encryption modes
  • XCha-cha
    • Not nonce-misuse resistant
    • Large nonce (192 bits) allows random nonces
    • But, rngs may not be reliable on constrained devices
    • No non-libsodium implementations, that I can find
  • CAESER competitors
    • Probably good, but
    • No winner(s) announced, and won't be until later this year, at the earliest
  • AES
    • In AEAD-specification, limited to 96 bits of nonce, so can't use random nonce
    • Maybe skip AEAD interface and do it by hand, with a bigger nonce?
      • Ugh
  • Maybe specify, in XTT spec, that nonce is a SIV-style IV from the message?
    • Slow
    • Requires rolling our own, not good
    • We could use this model (see paper at https://eprint.iacr.org/2015/102.pdf) with some prf and regular AES-GCM to hack an SIV?
      • WARNING!!! NSA found attacks: https://mailarchive.ietf.org/arch/attach/cfrg/pdfL0pM_N.pdf