use predictable instead of random nonces

[rade]

Weave's crypto implementation goes through a lot of trouble in order to use random nonces. Alas this is completely unnecessary. It is perfectly ok for nonces to be predictable. The only requirement is that they are only used once per session.

NaCl Security Model:

Distinct messages between the same {sender, receiver} set are required to have distinct nonces. For example, the lexicographically smaller public key can use nonce 1 for its first message to the other key, nonce 3 for its second message, nonce 5 for its third message, etc., while the lexicographically larger public key uses nonce 2 for its first message to the other key, nonce 4 for its second message, nonce 6 for its third message, etc. Nonces are long enough that randomly generated nonces have negligible risk of collision.

So nonces in NaCl are 192 bits in order to permit use of random nonces, but it's fine to use predictable nonces instead.

PyNaCl requirements:

A nonce is not considered secret and may be freely transmitted or stored in plaintext alongside the ciphertext. A nonce does not need to be random or unpredictable, nor does the method of generating them need to be secret. A nonce could simply be a counter incremented with each message encrypted, which can be useful in connection-oriented protocols to reject duplicate messages (“replay attacks”). A bidirectional connection could use the same key for both directions, as long as their nonces never overlap (e.g. one direction always sets the high bit to “1”, the other always sets it to “0”).

Also, DTLS MACs employs message sequences numbers as nonces, which are also transmitted in the clear in the envelope. Note that the spec doesn't mention nonces, neither does the main TLS spec on which it builds, but the sequence numbers do evidently serve exactly the same purpose as nonces (in combination with an 'epoch', which caters for cipher suite renegotiation and thus is not relevant to us).

[dpw]

"So it seems that there is no need to generate random nonces"

#269

[rade]

@dpw well remembered (and badly not remembered by me)

I propose that weave nonces consist of 192-65=127 zeroes in the MSB, followed by a direction inidcator bit, followed by the DF bit, and a 63 bit message sequence number. The DF bit and sequence number (64 bits combined) appear in the envelope. The DF bit is present, as in the current implementation, in order to guard against routers messing with the packet headers.

NB: We still need to maintain a sliding window on the receiving side for duplicate detection, since we don't want to have to a bitset that can grow to 2^63 bits.

A 63 bit sequence number, employed to transmit ethernet-frame-sized packets (1522) over 10GigE, wraps after 356 thousand years. And weave isn't capable of transmitting at anywhere near that speed.

With the above change we can dispense with the entire nonce rolling protocol, which complicates weave crypto significantly and causes problems such as #564.

[rade]

On the subject of random vs predictable nonces

AES-GCM in TLS [...] records have an eight byte, explicit nonce. [...] But TLS already has a suitable, implicit record sequence counter that has always been used to number records. So the explicit nonce is at best a waste of eight bytes per record, and possibly dangerous should anyone attempt to use random values with it.

[rade]

Fixed by #617.