sonic-servant

I would suggest that at least a little bit of thought be given to this issue though. Maybe allow a recipient server to specify the number of PBKDF2 rounds that have to be applied to the hash of the message, as a proof-of-work / rate-limit thing? (So if I don't care much, 10 rounds. If I'm sick of spam, 10,000. Or whatever. But let the recipient choose.)

This might be nerding into this too much, but you probably don't want an intentionally slow hash algorithm like PBKDF2 for proof of work, because then it requires just as much work to verify that the work was done as it does to do the work. This would make opening your email slow.

Instead, you can use a fast hash algorithm (like SHA256) and require that the sender provide a salt which, when appended to the message header (timestamped and containing the receiver name, so it's unique) produces a hash with certain properties (for example, the resulting hash must have three 1s at the beginning).

The way this works is this: the chances of a result coming up 1 is 1/16 (in hex) so starting with three 1s has a 1 in 16³ (1 in 4096) chance of occurring. So it will take on average 4096 tries for the sender to find a salt which produces a hash starting with three 1s (those 4096 tries are the work). However, to verify the work, the sender only needs to append the salt produced by the receiver and verify that the resulting hash starts with three 1s. That way verifying proof of work takes 1/4096th as much work as doing the work.

You can also scale up the work necessary (by increasing the number of 1s required) without increasing the difficulty of verification.

This solution still presents problems for people running legitimate mailing lists. That problem can be solved by allowing users to whitelist certain sender public keys and allow a signature with a whitelisted public key as an alternative to the proof-of-work. This solution exposes the sender mailing list to the server, however, so people could tell which mailing lists you subscribe to (that would be possible anyway if the sender is not using an anonymized connection such as through Tor).

I'm assuming (perhaps incorrectly) that Darkmail will use public key cryptography, with users able to generate and keep their own keypairs so that even a central authority can't get at the keys via a secret warrant.

How do you plan to solve the problem of distributing and verifying the public keys?

To my knowledge the only solution which doesn't depend on a central authority (which we must assume to be compromised) for key verification is a web of trust, which depends a lot on users. If this is the solution you're using, what kind of tooling are you planning for allowing users to manage their web of trust?