I don't know how bad the bandwidth requirements would actually be. A few thousand bytes a second is an awful lot of text. Granted, you won't be able to do anything else like VOIP.
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'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.