Connections between friends are encrypted.
is the crypto used.
https://github.com/irungentoo/toxcore/blob/master/docs/Tox_m...
describes the protocol used to connect securely to friends after they find themselves.
This protocol has PFS, message padding to prevent length based leaking and should be immune against replay attacks.
What makes it secure is that you know the long term public key of your friends making it really easy for the software to establish secure connections to them.
The only way to get the ip of someone from their Tox id is by knowing their public DHT key which they will only send you if they are your friend.
How this works is described in detail: https://github.com/irungentoo/toxcore/blob/master/docs/Preve...
also, if the message is encrypted, why not use a "torrent" of all the messages being shared and discarded after a while (no need for offline messages anyway) and each node decrypts its own as they please but relay all of them in the same stream? no way to know who could decode it. and it was delivered to everyone. much like a bitcoin transaction, but without the metadata.
it would probably be vulnerable to a dos by flooding it with bogus, expensive to try to read, requests... but will be the most reliable and private you can get
They have to be friends with you.
Note that being friends in this context means the users have added each other.
"Secure against bulk surveillance" is a big push in a lot of areas, it's a button Bruce Schneier and Eben Moglen have been pushing hard for the past year or so. See especially their joint lecture at Columbia Law School in December, 2013, and Schneier's presentation to Stanford Law School in April, 2014 (both are on http://FixYT.com).
Anonymized persistent IDs associated with physical / persistent IP addresses represents a different level of threat, particularly for those who are engaged in activities for which concern from a APT (advanced persistent threat) such as a state actor, with either legal impunity or significant resources, or both, is a concern. In that case, I'd want to see a system with repudiable identifiers and Onion routing such that endpoints aren't clearly determinable.
That said, yours is a crucial question.
Related: what are the threat models against which Tox is a response?
The main goal of Tox is to make it hard for a global threat to conduct mass surveillance on everyone at the same time without sacrificing performance.
If the majority of the people using Tox have "nothing to hide" and use it because it works better than skype, the minority that does need the crypto will be able to use it without being discriminated against.
NB, a comment by Peter da Silva, who's been doing networking / communications / security stuff for quite a while:
"Don't like the callback model in the API, they need a version of tox_wait() that takes a select() fd mask."
https://plus.google.com/u/0/104092656004159577193/posts/MDYU...
Connection routed over one TCP node when direct connections are impossible due to NAT issues.
Virtually all consumers are behind NAT devices.
If you can't hole punch then you will connect to your friend through a couple TCP nodes. They act like relays.
TCP nodes are pretty much randomly selected by peers and anyone can host them.
Everything is encrypted and TCP nodes are regarded as being possibly hostile so there should not be any security issues.
"NaCl library" is not a spec and it's still easy to use/apply it incorrectly.