[messaging] saltpack spec and library

[Trevor Perrin]

On Thu, Feb 4, 2016 at 1:13 PM, Jack O'Connor <oconnor663 at gmail.com> wrote:
>> 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.

Sounds right, though depending on uniqueness of the header hash like
that is pretty subtle.  A future modification to the format might
change that property without realizing it mattered.


>> 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.

Good summary.


> 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.

I hadn't realized the payload is being authenticated twice, once with
Poly1305 based on the payload key, and once with HMAC based on the
static-static DH.

I think you're right that prevents this issue.  What I was proposing
(mixing ephemeral-static DH output into the MAC key) is more
efficient, because you don't need the Poly1305.


> 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.

I don't think that's right.  If an attacker creates a new ephemeral,
they won't be able to encrypt the original payload key.  All they'd
accomplish is forging a message that decrypts to gibberish.

That wouldn't affect security of the original message.


>> 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.

That was one goal, but the other was to strengthen the authentication
key with ephemeral-static DH, per previous point.

You're right that it's not very plausible an RNG would generate a weak
ephemeral but a strong payload key, so encrypting the payload key N
times with DHES+DHSS, instead of just once with DHES, doesn't gain
much.

You could strengthen the payload key by hashing all DHSS outputs into
it, but then you could also just...

> 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.

do the "NAXOS trick" to generate ephemeral private keys, as Max
mentions.  Or just accumulate some RNG output in a file off to the
side, and re-use it.


> 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?

That's a fair summary of some pros and cons.

Trevor