Saltpack Questions and Thoughts

[Phaiax]

Hey

From the specs:

Repudiability. It's possible for Bob to forge a message that appears to be from Alice. That means that if Bob reveals Alice's message, Alice can deny that she sent it.

It should be clarified that this is only true for a one-to-one encryption with only one recipient. As far as I understood, the repudiability comes from the fact, that this encryption ...

9 For each recipient, encrypt 32 zero bytes using crypto_box with the recipient's public key, the sender's long-term private key, and the first 24 bytes of the header hash from #8 as a nonce. Take the last 32 bytes of each box. These are the MAC keys.

... is equivalent to the encryption using the recipients private key and the senders public key With multiple recipients, one would need all private keys to fork a message. In the case of keybase.io, that would mean all own private device keys and all private keys of all other recipients.

The other thought: I think the payload key crypto_boxes order should be explicitly randomized. That would improve forkability and impede investigations. The used order of the recipients and their devices may depend on the time-grown storage structure of the client software. Sorting after public or private keys is not a good idea, since someone who wants to create a fork does not have that information.

[Phaiax]

Another thought: The sender includes its own keys as recipients. Someone who wants to fork a message can not fork these recipients keys.

[Phaiax]

PS: Maybe clarifing, that 1MB = 1000000 bytes and not a MiB

[oconnor663]

With multiple recipients, one would need all private keys to [forge?] a message.

Yes, the guarantee here is tricky. If Alice could forge a message from Bob to Charlie, that would violate authenticity. It's important that it's impossible to forge a message to anyone whose private key you don't have.

What we can shoot for, though, is that anything that Alice could reveal about a message, she can also forge. So for example, say Bob sends a sensitive message to Alice and Charlie. Alice might want to betray Bob by publishing his message to the world, along with her own secret key. However, this is not enough to prove (to anyone other than Alice) that Bob actually wrote the message (we hope). There will be two authenticators on the message, one using Alice's key and one using Charlie's. Everyone can verify Alice's authenticator, but Alice could also have forged that one. No one can check Charlie's authenticator, though, except Charlie. Charlie could also choose to betray Bob by revealing his secret key, but then there's the question of whether Alice and Charlie cooperated to forge the message.

In general, the ability to verify should be the ability to forge, but in a multi-recipient message there will be parts that each recipient can neither verify nor forge.

I think the payload key crypto_boxes order should be explicitly randomized.

That's a good idea. We don't want a recipient to be able to use the position of their (multiple) keys in the list to learn something about how the other keys are grouped. That is, whether all the other keys belong to a second recipient, or whether there are many more recipients with a smaller number of keys each. This is similar to an attack that Trevor Perrin pointed out about reusing nonces, on the Modern Crypto mailing list.

I wonder if there's a way to kinda force implementation to randomize this order, rather than just specifying that they should. I like to assume that all code is lazy and won't take any extra steps beyond the bare minimum it needs to pass tests :p

The sender includes its own keys as recipients. Someone who wants to fork a message can not fork these recipients keys.

Keybase actually does this by default, but we leave it up to the implementation. It's a choice between two incompatible features: 1) allowing the sender to decrypt their own past messages, and 2) forward secrecy against the sender leaking any of their keys.

[Phaiax]

What I wanted to say, there is a huge difference between theoretical repudiability and practical repudiability. If every single user application (e.g. keybase) of any saltpack implementation does include the senders keys as recipients, it is hard for Alice to pretend that a she did not sent that message even if she did. That means practically i can not convince an expert or a court of not having sent a message. (aka no forward secrecy as you mentioned).

Implementations can be more forward secret if they generally send encrypted messages without including own keys and encrypting a second time using only own keys for local sender storage. Then Alice can delete its own message from its own storage and deny its authorship afterwards.

I just think this should be clarified in the spec to not create a false sence of security. Because in the end, this lessens the difference between saltpack authenticators and pgp signed messages. From https://saltpack.org/pgp-message-format-problems:

There's no way to verify who a PGP message is from unless it's signed. That means that as a sender, you can't authenticate yourself without giving up repudiability. Partly because of this, authentication is off by default. In contrast, NaCl encryption authenticates the sender in a repudiable way. That makes it easy for us to enable authentication by default. It also means that we don't need special support for a "signed and encrypted" mode, because very few applications actually want that.

(As you may guess, I try to implement the saltpack format, see github.com/phaiax/rsaltpack)

[Phaiax]

Or the other way around: Even if an application uses saltpack with perfect forward secrecy it is hard for Alice to pretend not to have sent a message if bob is a noob and unable to use photoshop or temper with the stored messages. Any messenger that wants to offer repudiability should also offer a way to easily fork messages and store them in the exactly same way as real messages would have been stored. So even the noob Bob can forge messages, allowing Alice to deny authorship more confidentially.

I guess that all this is independent of the saltpack format itself. But I think these thoughts should be included in the saltpack specification to hopefully create more messaging applications that allow for real-world repudiablility.

[Phaiax]

And another proposal: Switching from sha256 to blake2b, as long as saltpack is young

https://blake2.net/ https://download.libsodium.org/doc/hashing/generic_hashing.html https://download.libsodium.org/doc/advanced/sha-2_hash_function.html

(i have not looked, but I think you probably also use libsodium instead of nacl, because it is a compatible fork but more portable)

PS to anyone reading this: I am no cryptography expert at all, I only am an interested cryptography noob, so take my words with care.

[oconnor663]

What I wanted to say, there is a huge difference between theoretical repudiability and practical repudiability. If every single user application (e.g. keybase) of any saltpack implementation does include the senders keys as recipients, it is hard for Alice to pretend that a she did not sent that message even if she did. That means practically i can not convince an expert or a court of not having sent a message. (aka no forward secrecy as you mentioned).

The scenario you're talking about is where Alice leaks her own secret key, as opposed to one of her recipients betraying her, and I think you're right that repudiability is a problem there. That said, I think this problem applies to any multi-recipient message, even if they don't include any of Alice's other keys as recipients. If Alice sends a message to 5 other people, and the attacker gets Alice's secret sender key, then the attacker can verify all the authenticators, and they know that one of two things must be true: either 1) all 5 people conspired to fake this message from Alice, or 2) Alice is the real sender. I think the 5-person conspiracy theory would be a pretty crappy defense most of the time. As far as I can tell, this is an inherent problem with authenticated multi-recipient messages. (Saltpack supports an anonymous sender mode where the sender never uses their long-term key, which doesn't have this problem, but you lose all authenticity as a result.)

I agree that all this is probably worth clarifying in the docs. Something like a Known Limitations section.

[EDIT FROM THE FUTURE (26 April 2016): I've thought about this some more. We could mitigate this problem somewhat if we both 1) avoid encrypting to the sender's own key(s) and 2) include some ephemeral DH output in the authenticators. (Credit to Trevor Perrin here.) Then it would not be possible for an attacker with the sender's compromised key to verify any of the authenticators, unless they could also compromise the recipients' keys. I don't think this is a big enough deal to make us want to omit sender keys by default at the application level, but there's certainly no reason not to get it right when we're in that mode.]

I think these thoughts should be included in the saltpack specification to hopefully create more messaging applications that allow for real-world repudiablility.

The goal of saltpack is to support old-fashioned, sent-by-hand-in-some-random-channel, PGP-style messages in a less painful way. Because of that main use case, saltpack offers very little in the way of forward secrecy, which should be a core feature of most protocols. Building a messaging application that uses saltpack over the wire doesn't feel like a very good idea to me. (For a lot of the same reasons nobody builds new protocols around PGP.)

Switching from sha256 to blake2b

We've deliberately avoided picking our own crypto primitives, and instead stuck with the NaCl/libsodium defaults (and also tptacek's advice). I think it's unlikely we'll want to change course here. But I'm curious what makes you recommend BLAKE/BLAKE2 specifically?

[oconnor663]

Rust saltpack implementation

Sweeeeeeeeeeeeeeet! Let me know if you run into any problems. I'm trying to dive into Rust myself.