Silk Road forums

How does running 'Spend' immediately after 'Mint', "greatly reduces the user’s anonymity by decreasing the number of coins in C and leaking some information about when the coin was minted" if 'Spend' doesn't broadcast something to the network, and if it does, why is this not detailed in the paper?

Even blind mixes are vulnerable to traffic analysis. If someone obtains 1000 zerocoins and immediately after that somebody gets 1000 bitcoins for zerocoins, there is a correlation there.

Quote from: kmfkewm on June 10, 2013, 05:46 pm

Also 1 gigabyte per second really isn't that much bandwidth. A quick search of hosting providers shows 1 gigabit per second unmetered packages averaging around $700 a month. I believe there are 8 gigabits in a gigabyte, so that means $5,600 a month to have enough bandwidth to fuck hidden services and their clients. It would take 60 days for all clients (and hidden services) to rotate entry guards enough to probabilistically select one of the bad entry nodes. That puts the price for massively breaking Tor anonymity at about $11,200 dollars. It would take about $11,200 and 60 days to deanonymize any hidden service and the majority of the clients connecting to the hidden service. I could afford to carry that attack out. I don't want to use a network that I can defeat with traffic analysis.

It's not that simple. Buying 8 servers with 1 gigabit ports doesn't mean all 1 gigabit will be used. In fact, from discussions I've seen, that's guaranteed not to be the case.

But my objection has more to do with the fact that adding 50% bandwidth to the network in a week, or even a month, would be noticeable. An attacker would have to spread it out over several months, greatly increasing the cost of the attack.

And you have to factor in the 12-18 servers needed for HSDirs, and the computational cost of brute forcing their fingerprints to be closest to the descriptor ID.

Even if it takes 12 servers with 1 gigabit ports, and they are added one at a time once per month:

$700 for the first month
$1,400 for the second month
$2,100 for the third month
$2,800 for the fourth month
$3,500 for the fifth month
$4,200 for the sixth month
$4,900 for the seventh month
$5,600 for the eighth month
$6,300 for the ninth month
$7,000 for the tenth month
$7,700 for the eleventh month
$8,400 for the twelfth month

$54,600 to obtain an adequate amount of servers / bandwidth then + $8,400 * 2 to maintain it for two months (which wouldn't be required as many would be deanonymized up to this point) = $71,400 and 14 months. That does make it a lot more unrealistic for me, although in my *ahem* glory days I did have $50,000 in cash once . On the other hand I know big vendors who have stacks of hundred thousand dollars sitting on their kitchen tables. I don't feel comfortable using a network that they can defeat with traffic analysis in a year.

Also 1 gigabyte per second really isn't that much bandwidth. A quick search of hosting providers shows 1 gigabit per second unmetered packages averaging around $700 a month. I believe there are 8 gigabits in a gigabyte, so that means $5,600 a month to have enough bandwidth to fuck hidden services and their clients. It would take 60 days for all clients (and hidden services) to rotate entry guards enough to probabilistically select one of the bad entry nodes. That puts the price for massively breaking Tor anonymity at about $11,200 dollars. It would take about $11,200 and 60 days to deanonymize any hidden service and the majority of the clients connecting to the hidden service. I could afford to carry that attack out. I don't want to use a network that I can defeat with traffic analysis.

warning: I am really just brainstorming here and in the process of writing this post I came to the conclusion that some of the trains of thought I was following would not work very well. I didn't originally plan to, but several times I sort of had my train of thought abruptly diverge in the process of writing this. Most people will probably be very bored reading this, I am going to post it anyway on the off chance that anybody reads it and gives it any thought. I find that when I talk things out as if I am talking to people that I can think more clearly about a subject, I don't care if anybody actually is listening .

I am thinking something along these lines:

A. Native / default support for layering with Tor

This will pretty much be required to get a user base to start with. People trust Tor already, and Tor is already big enough that it can provide some anonymity. Layering Tor with another network can only help anonymity, and Tor already has put a lot of focus on blocking resistance / membership concealment, features that seem silly to try to reproduce in a new network when they are already provided adequately by Tor.

B. P2P network

I definitely think that all nodes should route by default. If all nodes run as hidden services we can get around the issue you pointed out of not all users being able to route due to being behind NAT. I suppose it would be H2H, hidden service to hidden service. Normally I would strongly advise against anything where users run as hidden services, but if we can add plausible deniability and protection from timing attacks to the picture, it should be acceptable. I think the only way we are going to be able to add plausible deniability is if all nodes route for all nodes. I also like the idea of all nodes providing some hard drive space to all nodes, this will allow for distributed content that is very resistant to censorship. 

C. Support for multiple use cases: exiting to clearnet, centralized hidden services, distributed content storage, internal E-mail

By being designed for as many use cases as possible, we may be able to attract a large number of users. The primary issue will be designing the system such that all of the different sorts of traffic blend in together, and do so while consuming reasonable amounts of bandwidth. I will need to give more thought to how these different sorts of traffic can be made to blend together.

I have some basic ideas for how traditional hidden services could be provided by a mix network. Utilization of single use reply blocks (SURBS) seems to be an acceptable way to obtain this. Single use reply blocks were introduced by mixminion. When a user sends a forward message through a mix network, first they need to construct a layer encrypted cryptographic packet that securely routes the message payload through the network, starting from the closest node to the message sender and then with layers of encryption being removed as the message is routed forward all the way to the furthest node from the message sender. SURBS are cryptographic packets that route towards the person that constructs them. Essentially Alice creates a SURB and sends it through the mix network to Bob, as described previously. After Bob obtains the SURB, he can attach it to an outgoing message and the message is routed to Alice. From a SURB Bob only learns the closest node to himself, all of the other nodes are only known by Alice and neighboring nodes. One primary difference between normal forward routing and routing with a SURB is that in the case of the former the payload has a layer of encryption stripped from it at each mix, whereas in the case of the later usually a layer of encryption is added to the payload at each mix.

It seems to me that a hidden service could create SURBs that route data to it and then publish them somewhere. After clients obtain a SURB for the hidden service they want to access, they can establish a connection to the hidden service with it, sending their own SURB for the hidden service to send replies to them. Essentially this is the same exact way that remailer networks use SURBs, but instead of applying it to E-mail it would be applied to a client <-> centralized hidden service model. This is not a well thought out idea at this point, primarily we would still need to think of a way for clients to obtain the SURBs in the first place, and for hidden services to refresh the supply of SURBs available to clients.

Another issue is that SURBs are not particularly secure as they are usually used. With SURBs, global passive adversaries can usually link two communicating parties together after only several dozen to thousand messages are exchanged between them. Due to the limited anonymity of SURBs, state of the art theoretical remailers have ditched them all together in favor of Private Information Retrieval (PIR). In the case of remailers that use PIR instead of SURBs, there is a mix network as well as a nymserver network and a PIR network. Users register an address at a nymserver through the mix network, and can control their account through the mix network as well. When Alice sends a message to Bob, she sends it through the mix network to the nymserver of Bob. Bob's nymserver then batches Alice's message to Bob together (adds them to a bucket) with all other messages to Bob that arrived in a given time period (called a cycle). After each cycle completes, Bob's nymserver distributes all of its users buckets to the PIR network. Every cycle Bob engages in the PIR protocol with some number of the PIR nodes in order to obtain his bucket (hundreds of cycles worth of buckets can be stored at a time, and Bob can go through them at his leisure, so long as he always engages in the PIR protocol once for each completed cycle). This system enormously strengthens the anonymity of bidirectional communications through a mix network as it removes a limit on the number of messages Alice and Bob can exchange before their anonymity suffers in the face of a global passive adversary. This comes at the expense of requiring a massive infrastructure to support it (mix network + nymserver network + PIR network), and having semi-trusted intermediaries (the Nymserver). 

For E-mail type systems I would definitely be in favor of using something based on PIR, and PIR based systems are widely recognized as being greatly more anonymous than SURB based systems. However, for a traditional hidden service I don't think it is possible to use PIR. This does bring up a bit of a problem with integrating E-mail and Hidden services into the same network, in the case of E-mail it would be better to use PIR but then it would be using a different mechanism than the hidden services. Perhaps by having plausible deniability due to all nodes routing for all nodes, we can use SURBs for E-mail messages without the traditional weakness to GPA long term intersection attacks. Let's break down the risks of SURBs, here is a quote from a paper that discusses the problems with them:

Nym servers based on reply blocks (discussed in Section
2.1 above) are currently the most popular option for re-
ceiving messages pseudonymously. Nevertheless, they are
especially vulnerable to end-to-end traffic analysis.
Suppose an adversary is eavesdropping on the nym server,
and on all recipients. The attacker wants to know which user
(call her Alice) is associated with a given pseudonym (say,
nym33). The adversary can mount an intersection attack,
by noticing that Alice receives more messages, on average,
after the nym server has received a message for nym33 than
when it has not.6 Over time, the adversary will notice that
this correlation holds for Alice but not for other users, and
deduce that Alice is likely associated with nym33.
Recent work [19, 43] has studied an implementation of
these intersection attacks called statistical disclosure, where
an attacker compares network behavior when Alice has sent
to network when she is absent in order to link an anonymous
sender Alice to her regular recipients Bob1 ...BobN . Against
pseudonymous recipients, however, these attacks are far eas-
ier: in the anonymity case, many senders may send to any
given recipient Bobi , but with pseudonymous delivery, only
one user sends or receives messages for a given pseudonym.
To examine this effect, we ran a version of the attack simu-
lations described in [43], assuming a single target pseudonym
and N non-target pseudonyms providing cover. In order to
make the attack as difficult as possible (and thus establish
an upper bound on security), we assume that users behave
identically: they receive messages with equal probability ac-
cording to independent geometric distributions in each unit
of time (receiving no messages with probability 1 − PM );
they use identical reply blocks with path length through
mixes in a steady state that delay each message each round
with probability PD .
We ran the simulated attack with different values for PM ,
PD , and , against a nym server with N = 216 active pseudo-
nymous users. (This is probably an overestimate of the num-
ber of users on typical nymserver today [45].) We performed
100 trials for each set of parameters. In the worst case (for
the nym holder), when PM = 0.5, = 1, PD = 0.1, the lack
of mix-net delay variance allowed the simulated attacker to
guess the user’s identity correctly after the user received an
average of only 37 messages. In the best simulated case
(PM = 0.5, PD = 0.9, = 4), the user received an average
of only 1775 messages before the attacker guessed correctly.
For an active user, this is well within a month’s expected
traffic.
Although there are ways to use dummy traffic to resist
statistical disclosure attacks, these are difficult to implement
perfectly in practice (due to outages) and even slight imper-
fections render users vulnerable to attack [43].

So in summary, the risk of SURBs is that Alice can obtain X reply blocks for Bob and then use them to send X messages to Bob, and then watch to see if any of the IP addresses using the network have X more messages arrive at them than usual. It is possible to protect from this if the nymserver stores SURBS for Bob, and only sends messages out in fixed cycles, but in such a case the nymserver is still capable of attacking Bob's anonymity by not respecting the cycle scheme. There are some fundamental differences of the PIR based systems that protect from this attack: Alice (or the nymserver) pushes messages to Bob with SURBs, whereas with the PIR designs Bob pulls messages from the PIR network. With the PIR systems, Bob only pulls X bytes of data per cycle in all cases, with SURBs Bob has as much data pushed to him as people with SURBs for him desire to push.   

In the case of everybody gets everything PIR this attack is protected from even if data is pushed rather than pulled. For example, with BitMessage, if somebody sends Bob x messages, every node on the network receives X additional messages, making the intersection attack impossible to carry out. So the fundamental mechanism leading to the insecurity attributed to SURBs is that they can be used by an attacker to cause Bob to receive unique amounts of data. It seems that it is possible to use SURBs with nearly the same security as PIR if Bob receives messages to a nymserver and then sends the nymserver SURBs in fixed duration cycles, with the network itself enforcing the size of all routed messages (a timestamp enforcement mechanism would also be required). Since Bob determines when the nymserver has a SURB for him, and since the nymserver can only route X bytes to Bob per SURB, it seems that this avoids the specific attack attributed to SURBs. Of course using SURBs for message retrieval still lowers the anonymity to that which can be provided by a mix network, whereas PIR can guarantee anonymity unless all of the utilized PIR servers are compromised (or even if they are all compromised, in the case of everybody gets everything).

Anyway, I am getting a little bit off topic because a hidden service could not utilize a nymserver like this and still serve hundreds of clients. The original goal was to determine if all nodes routing for all nodes protects from this weakness of SURBs. The answer is obviously that it does to an extent, but probably not enough of one. If the attacker is a GPA they will see several nodes get X messages after spamming Bob, but they will be able to follow the flow and it will end at Bob. Bob will maintain plausible deniability from a local internal attacker, after all he could be forwarding the X messages on himself. However, a local external attacker will be able to defeat his plausible deniability. The only way Bob could protect from this is by sending out a number of dummy messages equivalent to the number of legitimate messages he obtains for himself. However, this will only create a crowd size, and unless it is an everybody gets everything PIR like BitMessage, the attack will still be possible for narrowing in on Bob. Of course it is probably asking to much to protect a nearly-low-latency network from a GPA, and this would still allow to protect from a local internal attacker.

Also, if you want to allow access to clearnet sites, you should not allow arbitrary newbs to be exit nodes. Some people will unwittingly get in a lot of trouble and that will drive everyone away from the network.

Would definitely make it so people need to select to be exit nodes, after being given a warning about what it means to be an exit node.

I think it's a combination of the network requirements and the lack of clearnet access that makes I2P users a very selective group. No offense to them, I think they are great people, but they are very homogenous. Almost all of them know how to code. Almost all of them are professional technologists or very tech savvy hobbyists. That works well for them now, because there isn't a lot of controversial content on the network. There are no major drug or CP sites. But if I2P was invaded by those groups, that situation would change. Not only might technical weaknesses be revealed by serious adversaries, but it would become obvious that they lack the cover you get from mixing with very diverse crowds. If there was a major CP invasion, then everyone using I2P would be a suspect, whereas I'm quite comfortable using Tor even if someone sees me using it, because of the plausible deniability of the very diverse crowd.

I think it is primarily the lack of clearnet access. Let's face it, most hidden services are boring. I have never looked at the I2P eepsites but my guess is that they are about as boring as Tor hidden services tend to be, if not more so. I guess there are some I2P torrent sites but I have heard torrenting through I2P is still pretty slow.

So for these many reasons, I don't think people should be required to relay, and the size and diversity of the user base should be maximized.

In the case of Tor you may have a larger user group to blend into, but the thing is that this will not protect you if an attacker is positioned to do a timing attack against you. If you use Freenet there might be a 90% chance that you are trading CP, but actually proving that somebody is trading CP on Freenet is arguably a lot harder than proving somebody is trading CP on Tor. In the case of Tor, if the attacker owns your entry guard and can observe your traffic arrive at the destination, you are screwed. In the case of Freenet the attacker can be your 'entry node' and indeed the entry node always can see the content they pass to you, but they can still not easily prove that you requested the content.

Well, if you believe the network is going to be crippled by mass arrests, that's a good reason to start designing a robust alternative.

Just look at the recent HSDIR attack. An attacker is capable of being all HSDIR servers for a hidden service. That means they have the ability to constantly be positioned for 1/2 of a timing attack against any hidden service, and the clients accessing any hidden service. If they own 33.3333% of the bandwidth of the (I think?) 900 or so entry guards, they can deanonymize close to 100% of people who access the targeted hidden service within 60 days. That is the level of an attacker that can deanonymize almost all users of a targeted hidden service: if they can do the HSDIR attack and if they contribute 33.3333% of the entry guard bandwidth for 60 days. Even if they contribute less bandwidth and wait for 30 days, they are still going to be able to do some serious damage. Even if they own only a fraction of the entry guard bandwidth, they will be able to do serious damage over many months.

I still wonder if adding features like layered, permanent entry guards is not worth doing in the short term.

Layered entry guards could be good for hidden services, but as it stands the attacker doesn't need to own the hidden services entry guards to do an edge timing attack against clients connecting to the hidden service. The attacker only needs to own the HSDIR nodes of the hidden service, or the introduction nodes of the hidden service. Permanent entry guards would also be a good idea, but I doubt the Tor developers ever implement that because it would lead to a lack of resource balancing.

One thing I've thought about, especially since I've been hanging out with the I2P folks lately, is a trans-proxy. Similar to the onion.to and i2p.us in-proxies, or exit nodes and I2P out-proxies, but trans-proxies would proxy connections between anonymity networks. For example, to access eepsite whatever.i2p from Tor, you would go to whatever.i2p.transproxy.onion, and to access hidden service whatever.onion, you would go to whatever.onion.transproxy.i2p. You could chain these things together, so if you want to use an exit node from I2P, a modified dot exit URL like  www.google.com.RelayName.exit.transproxy.i2p would get you there. Ok, that's a bit confusing for newbs, but you could access and enjoy the properties of different networks at the same time. Somehow, Freenet could be integrated into this too, so you can the plausible deniability of accessing files from Freenet, but through a hidden service, and thus a Tor connection that doesn't expose you as a Freenet user.

I have used a transproxy to do Tor -> I2P once before actually. Actually I used Tor to connect to Freenet myself in the past, no transproxy involved . Transproxies are neat but I don't think that they will offer the anonymity required unfortunately. Tor to Freenet is probably pretty good though.

Essentially I think that Tor is the RSA-1,024 of anonymity networks. In 2004 it was more than good enough. In 2013 it looks like it is probably already breakable by the most powerful attackers. Data retention laws are becoming more prevalent, NSA is monitoring as much of the internet as it can, the FBI is well past carnivore, more and more sophisticated attacks are being discovered, etc. Tor is roughly as untraceable as a single hop proxy. If the attacker is monitoring the site you visit, the middle and exit nodes are all but worthless. If the attacker owns your entry node, you are fucked. Entry guards rotate every 30 to 60 days. We need a network that protects from edge timing attacks, and we need a network that provides deniability in the event that an edge timing attack is successful. The only way we can obtain this, that I am aware of, is via time delayed mixing, uniform padding, variable path length and all nodes routing. 

Great write up!

First, I want to point out, as you probably know but didn't mention, that hidden services can be multihomed, you simply publish the descriptor from two or more boxes. It isn't common, but I have talked to people who do it. Also, I2P has a hidden mode that is similar to entry guards and Freenet's darknet mode. So the features of Tor and I2P overlap more than is usually considered.

I did know that it was possible to multihome Tor hidden services, but I didn't mention it because I have never heard of anybody actually doing it before. Also, the I2P scene is much more focused on multihoming, their community has been very involved in working on forks of tahoe-lafs for multihoming dynamic Eepsites, whereas the Tor community generally ignores multihoming all together. You are right though that multihoming is possible with Tor as well, and I should have mentioned this rather than give the impression that this feature is unique to I2P. Speaking of rarely used Tor features, it also supports authenticated access to hidden services such that clients without a specific cookie can not even determine if the hidden service is up or not. 

I also am aware of the hidden mode with I2P, this is also a rarely used configuration for I2P. the primary problem with operating in hidden mode is that afaik you no longer route traffic for other peers. I am not an expert in regards to I2P, but from what I can gather the developers generally suggest against running in hidden mode due to it damaging some of the anonymity providing properties of I2P. Of course it also protects from some attacks, such as intersection attacks and obviously membership enumeration.

One of the most important properties of an anonymity network is the size of the user base. A high latency mix network with one user offers no anonymity. Similarly, I would feel a lot safer using I2P if it had a million concurrent users. Unfortunately, it only has 10,000 to 20,000 users. The main reason of course is that Tor offers easier access to clearnet sites, and it doesn't require you to be a relay. So those are the most important properties for an anonymity network with a large user base.

Yes definitely allowing exiting to the clearnet is required to gain a substantial user base (and all of the delicious cover traffic they bring with them). I am really torn between having all users route by default or not.

Advantages of all users routing:

A. The network can scale much more easily (Tor is constantly running into resource problems, I2P has an abundance of resources)
B. It makes it much easier to add plausible deniability
C. It opens up the possibility of having a distributed data store like Freenet, which I find very attractive
D. The abundance of resources allows for heavier use of dummy traffic and other anonymity increasing, bandwidth intensive techniques
E. The network is likely to grow much larger (20,000 routing nodes versus 3,000 routing nodes) which makes it harder for an attacker to monitor a large % of it

Disadvantages of all users routing:

A. Not as many people want to make resources available as want to consume resources. Having users route by default could lead to a much smaller overall user base, even if the number of routing nodes is larger.

B. If all users route it is very likely that it will open the network up to client enumeration, and this will likely lead to weakness to various sorts of intersection attack

C. If mixing is utilized, having a very large network will dilute the number of messages that mix together at any one hop, potentially significantly reducing the anonymity that can be provided by mixing

But to address your ideas, are you brainstorming a theoretical network, or something actually worth building? Because I think any competitor network will suffer the same problem that competitor darknet markets suffer. Everyone is on SR, so everyone will use SR, regardless of how good the alternatives are from a technical standpoint. Right now, 90% of anonymity network users are on Tor. It's doubtful a significant number of people would bother to use another anonymity network, even if was much more robust. Tor is "good enough" for most people.

Well my interest in anonymity networks predated SR and the massive SR user base by many years, so I am not really concerned with SR being the primary destination of people who use the darknet. Tor is definitely by far the most popular network though, and any new comer will have trouble even growing to the same size as Freenet or I2P. So I would say that I am brainstorming a theoretical network, but a theoretical network that would be worth building. I really do love Tor but I am entirely convinced that it is not capable of continuing to provide anonymity as the scrutiny against it increases. Simple analysis of Tor reveals that a fairly modest attacker can cause enormous damage to those who use it. We have not seen this carried out in practice yet, and we never will until we do. But looking at the theoretical strengths and weaknesses of Tor, the only conclusion I can come to is that Tor is just not something I want to continue trusting with my life. After the first wave of Tor arrests comes, and in my opinion this will be sometime in the fairly near future, perhaps in a year or two, people will look for alternatives because they will realize that Tor is actually no longer good enough. But I am interested in anonymity networks theoretically and practically, and even if nobody ever uses a superior network it is interesting enough in itself to make one.

So if you're describing a theoretical network, your ideas are good. If you want to build something that people would actually use, why not layer it on top of Tor? Route it through Tor but with additional properties that enhance anonymity. Since Tor clients control their circuits, they can easily build variable length paths. Adding timing delays would require modification of relays, and thus cooperation of others, but it might be easier to convince the Tor developers and relay operators to do that than to build a useful competitor network.

I can see merit to layering some things on top of Tor (for example a remailer network), but I think that something that is fundamentally an alternative to Tor would not make much sense to layer through Tor. I also doubt that the Tor developers have much interest in fundamentally changing their network. Right now we have low latency anonymity networks a la I2P and Tor, deniable file sharing networks a la Freenet, and high latency mix networks a la Mixminion and Mixmaster. I think that the remailer networks are so slow and unreliable and E-mail specific that hardly anybody will ever use them, that I2P and Tor are so fundamentally insecure that they will not withstand attack for much longer, and that Freenet is so unique that it files sort of a niche market (it can't be used for surfing the internet, it can't be used for E-mail to people on the clearnet, it can't be used for hosting a traditional website, etc). I think that the anonymity network of the future will be a mixture of all of these things: fast enough to surf the internet but slow enough that timing attacks can be somewhat protected from (0-3 minutes of delay total), incorporating plausible deniability as much as possible while still allowing for the clearnet to be surfed, allowing hidden services that are stored distributed through out the network like Freenet or multihomed like I2P and sometimes Tor, etc.

Pretty much I think it will be Freenet in that plausible deniability will be a primary focus (because this offers strong protection and is easier to obtain than actual anonymity), Tor in that exiting to the clearnet will be possible, and Mixminion in that it will look like a greatly watered down remailer network (using the same techniques as the remailers, but to a much smaller degree, to allow for reasonable latencies).

Also, I do believe that a userbase would be attracted. Now more than ever before people are taking an interest in stuff like this. Look at how quickly BitMessage got over 100 nodes. When the earliest academic papers analyzing Tor started coming out it only had a few dozen nodes.