On Wed, Feb 3, 2016 at 5:16 AM, Jack O'Connor <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
