[messaging] saltpack spec and library

[Jack O'Connor]

> Likelihood of a random collision on 20 bytes is low (2^160).  If an
> attacker could see the rest of the header and then choose some header
> value (like their recipient public key) they could search for a
> collision on the first 20 bytes of the header hash with 2^80 work
> (birthday collision), thus causing a MAC key reuse.  I think that's
> not possible because the header hash always includes some
> unpredictable ciphertext, but worth keeping in mind.  An explicit
> 20-byte nonce might simplify this.

Now that you mention it, I wonder if we need randomness in the MAC key
nonce at all. (This may be a holdover in the design from when we were
considering tricky things with Poly1305.) Even if the MAC key were
static, using it with multiple messages would never produce the same
authenticator twice, because the header hash that we were exploiting
for random nonces is an HMAC input too. The only worry then would be
the attack you mentioned, where we leak that some recipients are
identical within a single message, which either way we need to solve
with a counter. So maybe the right nonce for the generating the MAC
key would be "some_constant_bytes_XXXX", where XXXX is a counter equal
to your position in the recipients list.

> That's true, but tampering with old messages is potentially a worse
> attack than forging new ones.
>
> For example, if you can send tampered ciphertexts to some party that
> tries to decrypt them, you can often observe timing, error messages,
> or other behavior to learn some plaintext contents.
>
> So being able to break authentication on old messages might reduce
> their forward-secrecy in case of a sender private-key compromise.

Ah, I see my confusion now. For Keybase saltpack messages, the sender
adds their own keys to the recipients list by default, for convenience
reasons similar to why we make the recipients list public by default.
So compromising a sender's key means you can probably read messages
they've sent. But other applications or non-default-modes might not
want sender decryptability, even if they do want sender authenticity
(and so can't use fully ephemeral keys), and in that case past
messages ought to stay private and un-tweakable even if the sender
leaks their key.

I think we're saved here by the payload secret box. Decrypting a
payload chunk happens in two steps: 1) you verify the MAC that was
made with your per-recipient MAC key, which the attacker knows in this
scenario, but then 2) you open the payload secret box using the shared
payload key, which this attacker does not know. The second step
implicitly verifies NaCl's Poly1305 authenticator. Any tampering done
by an attacker who doesn't have the shared payload key should fail
that second step. Before you brought this up, I was thinking about
that second authenticator as a waste of 16 bytes, but we kept it
because we didn't want to require implementers to have access to the
lower level crypto_stream functions. If I'm understanding this right,
it's nice to see that those bytes actually do something for us.

I think mixing ephemeral-static DH output into the MAC keys actually
might not be enough to prevent this attack by itself, without that
Poly1305 tag on the ciphertext. An attacker with the sender's stolen
key could generate an entirely new header, with a new ephemeral
keypair and new MAC keys/authenticators, reusing only the payload
ciphertexts from the original message. The per-recipient MACs would
look good, and the recipients would have no way of knowing that their
MAC keys weren't the original ones that went with that payload.

> You could consider something like:
>
>   1 ephemeral public key
>   N encryptions of sender static public key with ephemeral-static DH
>   KA = ephemeral-static DH + static-static DH
>   N encryptions of K with KA
>   1 encryption of payload with K, N authentications with KAs

Do I have it right that the goal is to contain the damage of a weakly
generated ephemeral keypair? My worry would be that, if the ephemeral
keypair is weakly generated, then K is presumably also weakly
generated. Adding extra security around K might not buy us much if K
itself is guessable?

One idea Max was thinking about was that senders could hash their own
static private keys together with the random bytes they get from the
OS, as insurance against generating weak keys, assuming their static
keys are strong. An upside would be that this sort of thing wouldn't
require any changes on the recipient end. Maybe downside is that it
would violate the Thou Shalt Not Use Userspace RNGs rule, and that if
an implementation screwed this part up it would be difficult to
detect?

- Jack