[messaging] saltpack spec and library

[Trevor Perrin]

On Wed, Feb 3, 2016 at 5:16 AM, Jack O'Connor <oconnor663 at gmail.com> wrote:
>
>> (1) If two recipient public keys are identical, this fact would leak
>> in the ciphertext.  If I'm one of the recipients I could possibly use
>> this to confirm guesses as to other recipients, by providing their
>> public keys as mine.
>
> Good catch, we should totally fix that. It looks like there's two
> places where sharing a nonce among the recipients causes this problem:
> 1) when we box the payload encryption key for each recipient, and 2)
> when we compute each recipient's MAC key. I think we could fix both
> cases by putting a 4-byte counter at the end of each of the nonces.

Makes sense.  Good point on (2).


> Out of
> curiosity, since we're relying on random nonce #2 to avoid nonce reuse
> between two static keys, is there a size that's generally considered
> safe for that? This change would drop us from 24 random bytes down to
> 20.

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.


> Thinking about this attack brought up a related problem: currently
> there's no way for Keybase users to publicly prove that they own a
> particular encryption key. [...] How risky would
> it be to use an approach like https://github.com/dchest/ed2curve-js to
> convert a Curve25519 encryption key into an Ed25519 signing key, just
> one time when the key is created, to sign a statement about who owns
> it?

Might be easier to solve by having the encrypted message bind the
recipient's signing key.  I.e., include that in a key derivation or as
authenticated data somewhere.  Then have recipients reject messages
not bound to their correct signing key.

(A somewhat related point:  if the recipients are anonymous, you don't
bind the recipient's exact encryption public key.  Curve25519 public
keys have a few equivalent values that calculate the same DH output.
Not a big deal, but you might want to ensure that the sender is seeing
the exact same value as the recipient.)

I actually think converting a Curve25519 key and signing with it is
fine under some conditions, and have some code and a
(not-yet-published) spec for that.  I think Tor is doing it or
considering it, too.  But you'd need to think about it a little
carefully, and consider how you're using DH and the assumptions you're
making.  Plus this is more computations and data to send around.


>> (2) The MAC keys only depend on the static-static DH output, not the
>> ephemeral-static DH output.  So if I compromise Alice's private key, I
>> can tamper with the ciphertext of messages she's previously produced.
>> This would be easy to avoid, if the ephemeral-static DH outputs
>> contributed to the MAC keys.
>
> Could you help me picture the attack here? If I've stolen Alice's
> private key, I can always generate entirely new messages that appear
> to be from her. Is there a situation where reusing one of Alice's old
> message headers / ephemeral keys is required?

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.


>> (3) On a similar note, it wouldn't hurt if the static-static DH
>> outputs contributed to the key used for encrypting payloads.  That
>> *might* help in the case where a weak RNG is generating bad ephemeral
>> private keys, but somehow the sender's static private key was good.
>> But that's a pretty weird case.
>
> The static-static DH outputs are unique for each recipient, but the
> payload encryption key needs to be shared. Is there a way to make that
> work?

Good point.  It's possible if the two DHs are combined first, *then*
used to decrypt the final payload key.

E.g., currently the format is something like:

  1 ephemeral public key
  N encryptions of symmetric-key K with ephemeral-static DH
  1 encryption of sender static public key with K
  KA = static-static DH
  1 encryption of payload with K, N authentications with KAs

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

I.e. the two DHs are mixed into a per-recipient "KA" which derives the
MAC key, but also decrypts the single payload encryption key.

This unfortunately enlarges the message header.

To plug my own thing (sorry!), Noise [1] was designed to accumulate DH
results like this.  If you used "Noise_X" handshake messages to
encrypt K, you'd have N copies of:

  1 ephemeral public key
  1 encryption of sender static public key with ephemeral-static DH
  KA = ephemeral-static DH + static-static DH
  1 encryption of K with KA

But you wanted a single ephemeral, which is stretching Noise a little
bit - you'd have to compensate by using Noise's "PSK" option to add a
nonce to each Noise message.  Then you'd have a header like:

  1 ephemeral public key
  N Noise messages of:
    1 encryption of sender static public key with ephemeral-static DH
    KA = ephemeral-static DH + static-static DH
    1 encryption of K with KA
  1 encryption of payload with K, N authentication with KAs


Trevor

[1] https://github.com/trevp/noise