There was a lot of analysis like this back in the 1990's on this list. You could probably look for it in the archives.
In general, store and forward anonymity services, like Mixmaster, have much better anonymity characteristics than real time systems like TOR, basically for the reasons you outline.
-Lance
--
Lance Cottrell
loki@obscura.com
On Aug 12, 2013, at 7:21 AM, John Preston
Hi all,
Long-time follower, first time poster. I have an interest in darknets and saw this paper (http://www.ieee-security.org/TC/SP2013/papers/4977a080.pdf) today in a message under "Freedom Hosting Owner Arrested, Tormail Compromised, Malicious JS Discovered", which naturally got me quite worried. It did remind, however, about a few ideas I have had in the past about guarantees of anonymity in a network.
Consider a broadcast network: an eavesdropper cannot tell who a message is intended for from just the transmission itself. By using asymmetric encryption, the contents of the message can also be made unreadable to the eavesdropper and all unintended recipients, still preserving perfect single fact anonymity.
Over time, an attacker could determine the intended recipient by looking at who sent messages within a certain time frame from receiving a message: the information gain from this is increased substantially if certain information about the protocol of the messages is known (e.g. if we're anonymising a real-time protocol, timed traffic analysis can reveal an intended recipient with a high degree of certainty). This can be defeated by including noise in the network: peers constantly produce garbage packets.
I believe that this would yield information theoretically secure anonymity, as an attacker is looking for hay in a haystack, so to speak. Obviously, the problem with this protocol is that it is horrendously inefficient.
I am inclined to believe that we can preserve the anonymity properties of this protocol while reducing its network load, in exchange for reliability. The original protocol implies that the intended recipient will always get the message, but if we allow for the possibility of delivery failure we can reduce traffic.
The protocol I propose is thus as follows: peers send hop-to-hop encrypted packets to a subset of the other nodes on the network. Each packet contains the payload (encrypted for the intended recipient) and a TTL counter. If a peer cannot decrypt the payload, the message is not intended for them and so the TTL is decreased and the new message is then broadcast out to another random subset of the peers on the network. Again, we include noise packets.
For a TTL of t and a subset network ratio of s, we thus expect ts transmissions for a single packet, where we intend ts < n so as to obtain a more efficient solution.
Other possible considerations are non-fully connected networks, although I believe that a theoretically secure routing protocol must fulfil at least one of the two axioms: 1) all peers must eventually receive the message; or 2) the message is not guaranteed to reach its intended recipient.
Thoughts? Also, is there any literature on or implementations of theoretically secure networks?