> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
