I've been thinking of ways to combat this as well, and I admit it's an interesting problem. You either have to do some kind of Tor-like onion protocol (which has its own problems), or send every message to every client in the world. Sending your message to [your friend] + X random people would still allow an attacker to eventually gather a very detailed map of your friends by looking at which come up most often.
That's what I do, as I can't think of any alternative that is equally analysis-resistant
> A few thousand bytes a second is an awful lot of text
I was planning for ~500 bytes / sec so that traffic spikes wouldn't block up the send queue, but now that I think about it you're probably right -- even at 50 bytes/sec, the network speed cap would still be a fairly small factor compared to the amount of time spent typing...
I wonder if the broadcast approach would help there? Be constantly throwing out GPG encrypted data to the entire network, anyone with the private key can pick it up. No "to" or "from" headers, and traffic analysis is hard since the flow of traffic is constant:
https://github.com/shish/firehose (Very alpha)
The main downside there is that bandwidth requirements are huge, you can only have a few thousand people on each shard :<