On 7/6/15 12:00 PM, Trevor Perrin wrote: > I think the question here is: if Alice sends Bob a message via some > metadata-hiding system (e.g. anonymous remailers, or Pond), how does > Bob know which key to decrypt with?
I was thinking about quantifying the "how many keys do I need" question. I suppose the solution space includes questions like: Q1: do senders get to know they're talking to the same person? Q2: does it use interactive (ratchet) key rotation? Q3: does it use non-interactive (k=H(k)) key rotation? Q4: what are the responsibilities of a "mailbox server", if any? Q1 is probably the most influential. If you choose to hide the recipient this way, you need pairwise keys, which has deep effects on addressbook management: you must interact with someone, to get the key, before you can send anything to them, so you can't just type in something from a business card or a search lookup (using forward-secure keys imposes a similar constraint). Likewise to introduce two of your friends requires your agents to make a couple of roundtrips. On the other hand, pairwise is the only case where you could use symmetric keys. OT3H, that makes forward-secrecy less reliable, since you must depend upon the *sender* erasing a key too. Petmail currently hides the recipient from senders (with pairwise current+next pubkeys), but I'm increasingly uncertain that the operational/UI challenges are worth it. I like the "default to unlinked, but link if you want to" approach over "default to linked", but there are too many ways to accidentally link your supposedly-distinct personas when you use them in the same agent. Trevor has convinced me that it's safer and just as easy for Carol to run two separate instances of her agent (one for the persona she presents to Alice, and a second for Bob). Pairwise keys also make the key rotation easier: you know the state of the sender, so you can use (current+next) keys and rotate them immediately each time you see evidence that the sender knows about the new one (which is every message, if the messages don't overlap). If you use the same keys for all senders, then this style of rotation could be held up by *any* sender falling behind. I think you'd need epoch-based rotation, where you deliver e.g. one pubkey for each of the next 5 days, and messages which gets stalled for too long are just lost. Or use Puncturable Encryption as a fancier variant. The mailbox server might be responsible for: * rejecting spam from unknown senders * rejecting spam from recently-removed senders * rejecting duplicates * rejecting out-of-order messages * *not* recognizing distinct senders Rejecting messages is pretty easy if the server is allowed to distinguish senders (you effectively just have a layer of encrypt-on-the-wire to the server). If not, things are harder, and you need a stash of tokens, or ring signatures, etc. Petmail currently uses re-randomizable ElGamal encryption to let the senders produce a unique per-message token. The server allocates a queue id and a keypair, keeps the decryption key for itself, and sends the queueid and encryption key to the recipient. The recipient randomizes the queueid to get a base token for each sender, and gives them the encryption key too. Each sender randomizes it *again* for each new message, and the server decrypts that to get back the queue id and figure out who the recipient is. Revocation is a drag, though, so I'll probably be switching to a token stash too: much simpler to explain and implement. > so I wonder if tags could more directly indicate message decryption > keys. I guess the simplest and most forward-secure approach would be to give each sender a stash of single-use pubkeys, and the mailbox server H(pubkey) for each. Pros: recipient does a simple table lookup instead of trial-decryption. Cons: fast message exchange could exhaust the supply quickly, server must be updated frequently, server must learn about the new token before it's safe to give it to the sender. Maybe we'd send larger batches to the server ahead of time. There's probably a hybrid Axolotl-ish approach where each pubkey can be used multiple times, with k=H(k) -style rotation in between. In fact, maybe we could skip the inter-ratchet rotation: I think I'm ok if the forward-secrecy interval is larger than a single message, maybe up to a couple of days long. Remember that we can't expire the key until the user has read the message anyways. That doesn't help figure out what the server-visible tokens should be, though. The two agents must keep each other informed about their remaining keys, and ask for a refill while they still can. Back in 2004 (in the original Petmail) I drew up a scheme to do this with Mixminion's SURBs (Single-Use Reply Blocks), where the threat of giving someone too many was that they could send a big burst of messages to you and use the resulting traffic pulse to trace your location. These days, if the stash is merely being used to avoid DoSing the server, then handing out too many doesn't matter so much, especially since the agent can cancel them by talking to the server, and thus limit the total outstanding. As a fallback, it might be useful to have a set of non-rotating keys which are never used for human-authored messages, but can be used to ask for new keys even after the stash has been exhausted. cheers, -Brian _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
