Yes, if you manually and wisely choose your own guard nodes, then you can avoid these attacks. You should be sure that those guards can't themselves be linked to you, either.
340 karma · joined September 20, 2010
[0] http://www.hackerfactor.com/blog/index.php?/archives/868-Dea...
1. S is at an IP address that is not a public Tor relay as listed in the Tor consensus. It's not impossible that S is a bridge (i.e. private Tor relay), but statistically unlikely because using a bridge isn't all that common.
2. During circuit construction, S extends the circuit beyond R two times. I don't see why Tor couldn't easily create dummy circuit extensions to fool R, but it doesn't (probably because there are so many other indicators that this change alone wouldn't solve the problem).
3. R observes what appear to be HTTP-level request-response pairs between it and S at about the same round-trip time (RTT) as the RTT R observes between it and S at the TCP layer, which should only happen if there were no more hops beyond S.
If I recall correctly, Kwon et al. [0] describe several more statistical indicators of being a guard for an onion service.
Also, you are right that a client doesn't tell the guard node the destination (e.g. the onion service) of its traffic. The guard node is not trusted with that because it already directly observes the client, and so giving it the other side would deanonymize the connection.
[0] https://www.usenix.org/conference/usenixsecurity15/technical...
1. The biggest improvement is that (in 2014 or 2015?) they reduced the number of entry guards from 3 to 1 [0], reducing the risk of a malicious guard by a factor of 3.
2. The time until a guard choice expires was increased from 2–3 months to 3–4 [1] (this maybe happened 3 years ago?). This increases by ~40% the expected time an adversary would need to passively wait to have his relay selected as a guard by a victim.
3. The bandwidth threshold to become a guard relay was raised from 250KB/s to 2000KB/s [2] (looks like in 2014). However, 2000KB/s=16Mbit/s is still a very low bar, and, moreover, for an adversary that can run relays above the threshold, this change increases the adversarial guard fraction as there are fewer guards above the threshold to compete with.
4. A new guard-selection algorithm was implemented that prevents a denial-of-service attack from forcing a large number of guards (i.e. > 20) from being selected in a short period of time [3]. I believe this merged in 2017. If an adversary can force guard reselection by an attack, you are still extremely vulnerable, though, as a limit of 20 still provides a 20x risk multiple.
[0] https://trac.torproject.org/projects/tor/ticket/12688
[1] https://trac.torproject.org/projects/tor/ticket/8240
1. Each hidden service chooses a "guard" relay to serve as the first hop for all connections.
2. A server running multiple hidden services has a guard for each of them. Each new guard is another chance to choose a guard run by the adversary.
3. An adversary running a fraction p of the guards (by bandwidth) has a probability p of being chosen by a given hidden service. A hosting service with k hidden services is exposed to k guards and thus has ~kp probability of chosen an adversary's guard. With, say, 50 hidden services, an adversary with only 2% of guards has nearly 100% chance of being chosen by one of those 50 hidden services.
4. The adversary can tell when it is chosen as a guard by connecting to the hidden service as a client and looking for a circuit with the same pattern of communication as observed at the client. Bauer at el. [0] showed a long time ago this worked even using only the circuit construction times.
5. The adversary's guard can observe the hidden service's IP directly.
The risk of deanonymization with onion services in general (i.e. even not using an onion hosting service) is significant against an adversary with some resources and time. Getting 1% of guard bandwidth probably costs <$500/month using IP transit providers (e.g. relay 8ac97a37 currently has 0.3% guard probability with only ~750Mbps [1]). And every month or so a new guard is chosen, yielding another chance to choose an adversarial guard. Not to mention the risk of choosing a guard that isn't inherently malicious but is subject to legal compulsion in a given jurisdiction (discovering the guard of a hidden service has always been and remains quite feasible with little time or money, as demonstrated by Øverlier and Syverson [2]).
[0] "Low-Resource Routing Attacks Against Tor" by Kevin Bauer, Damon McCoy, Dirk Grunwald, Tadayoshi Kohno, and Douglas Sicker. In the Proceedings of the Workshop on Privacy in the Electronic Society (WPES 2007), Washington, DC, USA, October 2007.
[1] <https://metrics.torproject.org/rs.html#details/014E24C0CD21D...
[2] "Locating Hidden Servers" by Lasse Øverlier and Paul Syverson. In the Proceedings of the 2006 IEEE Symposium on Security and Privacy, May 2006.
I see that the delay from one ballot batch to the next is set to a uniformly-random time between 10 and 60 seconds. I also see that the ballot batch size is 10.
Let's assume that you have fixed the problem of the ballots being submitted in the clear and that they are instead send through a proxy on different TCP connections (or through Tor on different circuits). Let's also say that the news reports are correct and Brave has 4 million active users, and moreover that all have enabled payments (this is generous). Furthermore, assume that (1) there is no reason payments would start being submitted on any particular day or time, and (2) say, 20 publishers are paid 20 tokens each on average. Then the average number of users uploading ballots in any given minute - let's call them "neighbors" - is roughly (20 ballots/user / 10 ballots/batch)(20 publishers/month)(4e6 users)/(30 days/month)/(24 hours/day)/(60 minute/hour) = 3704 neighbors. That's not a very big anonymity set, but it's not nothing. Early adopters got screwed, though.
However, it gets worse. Based on BatClient::prepareVoteBatch() (bat_client.cc), it looks like each batch has ballots for a single publisher (if I'm wrong, privacy erodes even further). How many of those 3704 simultaneous uses are uploading to the exact same domain? I don't know how to guess (to be conservative, we should assume none). Moreover, unless the last batch happens to be a multiple of 10, that one will be unique in being a size less than 10. Both of these things make it easy in many cases to determine when you are finished uploading ballots for one publisher and are moving onto the next. If many of your neighbors have split a publisher's votes across multiple batches, then it seems unlikely that they will move to the next publisher at the same time, making your ballot submissions more linkable across publishers, exactly the problem we were worried about.
In addition, the time of each batch isn't independent because the delay is applied after the last one. For example, if one batch appears is sent quickly by chance, then the next one is more likely to be sent at a time close to the initial batch. Thus, to link two batches, you only need to consider the batches that end in the 10-60 seconds preceding the start of the second one. How many of your 3704 neighbors ended a batch then? The longer a batch upload takes, (due to latency & bandwidth), the less likely that the batch of any other user has ended in that short time frame.
There is also the issue of semantic linking. If I'm a relatively rare group, the sites I visit are likely to be linkable to each other as distinct from those of my neighbors. For example, suppose I speak Catalán and am involved in regional politics, or that I am a teenage boy in Iceland. How many of my sites are linkable based on those characteristics? And this linking can happen across "gaps" in the ballot-upload stream, where there is uncertainly about how the uploads are linked together, allowing you to get the inference "back on track".
Fortunately, the timing stuff seems fixable. Hiding the IP and separating ballots across connections is an essential first step, of course. but to handle timing issues after that, simply do the following: (1) submit all ballots individually; (2) schedule each ballot upload independently of the other ballots and at a uniformly-random time over, say, the next week or two, and if the user isn't online, reschedule.
The semantic issues with small populations seems harder. I think Brave should prevent itself from learning about votes for publishers unless enough people vote for the publisher. I don't see how to do this without a more powerful cryptographic protocol (it is absolutely doable, though, using MPC for example).
You'd be surprised how far you can get. For example, protocol design exist that provide strong message anonymity: mixnets, DC-nets, and secure multiparty computation (MPC). Tor is great at its goals, but it accepts weaker security for low latency that Brave doesn't need. Tor is also unfortunately blocked in many companies and countries by technology and/or policy. Mixnets are freely available [0]. MPC is sold commercially [1]. (I have no personal or professional connection to either project.)
> On road, will get you links to code for randomizing time between ANONIZE sessions as soon as I can.
Looking forward to it.
Many thanks for the serious engagement. I look forward to recommending Brave to my friends and colleagues in the not-distant future!
[0] <https://katzenpost.mixnetworks.org> [1] <https://www.unboundtech.com/>
Even using a privacy-enhanced blockchain isn't necessarily sufficient. Blockchains do not provide anonymous messaging. Therefore, a recipient R of a transaction can identify the sender S if R can observe S sending the transaction. Yes, this problem affects Bolt, Zcash, Monero, etc.
I am reasonably familiar with the contents of GDPR, having looked into it more after attending a lecture on the subject [0].
> We cannot use IP address except for antifraud, so it is not legally viable for us to try to link zero-knowledge proofs into a profile based on IP address.
If your users must rely on you obeying a policy, then please just say that. Right now, it seems to me that you claim to use technical means to prevent Brave from learning browsing histories [1].
> my home AT&T IP address wanders often, so do many others; mobile even more variable.
IP addresses can be so identifying that they have been ruled as personally-identifiable information by the European Court of Justice [2].
> I think you are mistrusting prematurely. But as noted in my item 1, we are talking to PIA about using an IP relay (not full VPN). This got delayed by their work on handshake.org but we're restarting it.
Thank you for stating clearly that you aren't using PIA (aka "IP masking") at the moment for Brave Payments. You might consider your users who are worried about data breaches and compromised servers as much as they are worried about Brave's intentions. Please don't take my criticisms personally.
> Putting these through separate Tor circuits is possible, as we also randomly space them out in time.
Oh, you do randomly delay ballot submissions? I have not been able to find any such logic in the code but would be happy to be pointed to it. The specific way in which you choose delays is, of course, crucial to it providing security.
[0] <https://petsymposium.org/2018/program.php>
[1] <https://brave.com/faq-payments/#anonymous-contributions>
[2] <https://www.irishtimes.com/business/technology/european-cour....
Suppose I understand you correctly and you do see the network IPs and timestamps of submitted tokens and ballots. Is your argument then that you can be trusted to follow your privacy policy? If we rely on trusting you to follow policy, then why not get rid of your zero knowledge proofs entirely?
By saying that you "have two options", it sounds like you are saying that there are two mitigations for the privacy problem that you could use but do not yet.
(1) is the one-hop proxy, which used to be used in the form of Private Internet Access service, but it seems like it is not currently being used by Brave. If you did use such a service and encrypted the publisher identities under Brave's public key, then that would be a improvement, although still not really private because Brave would receive the results in a batch from Private Internet Access. Browsing histories are essentially fingerprints for each user. The ten sites I visit each week are almost certainly not shared by any other Brave user on the planet, and moreover they are frequently identifiable (consider sites for individuals, companies, sports leagues, scohols, etc.). From [0]: "Our results show that for a majority of users (69 %), the browsing history is unique and that users for whom we could detect at least four visited websites were uniquely identified by their histories in 97 % of cases."
(2) has the same batching problem as (1). It would be superior, though, because it would be harder for Brave and the proxy system to collude or (more likely) be forced to cooperate with some authority.
To handle the batching problem, you should at least choose to upload each Anonize ballot at a uniformly random time in each month and on a separate connection (i.e. TCP connection or Tor circuit). You should also explain how this works in a technical document to give people the ability to understand what exactly they are signing up for when they enable payments in Brave. Ideally you would use a cryptographic protocol more suited to strong anonymity than a proxy network, such as a verifiable mix network or a secure-multiparty-computation protocol.
[0] Olejnik et al., "On the uniqueness of Web browsing history patterns", 2014, <https://link.springer.com/article/10.1007/s12243-013-0392-5>
I think it works like this: (1) Brave Browser submits its transactions to a Brave server to exchange a BAT for an Anonize ballot (anonize.org), (2) each ballot has the name of a site you visited randomly added by the browser with probability proportional to the frequency of site visits, and (3) the ballots are sent to a Brave server. Key here is that the token and ballot submissions are sent directly (e.g. not through a proxy or Tor). In addition, I believe the ballots may be submitted as a batch (i.e. at one point in time). Therefore, it is easy for Brave to see your votes for your visited websites, all coming at once, all from your IP address. That IP address may well be the same one used to exchange the BAT for ballots as well.
There are additional problems regarding visits to unusual and identifying websites that I feel like Brave hasn't begun to consider, either. Suppose that every and only time that Brave receives a ballot for your personal website, they also receive a ballot for some unpopular and sensitive website. They can then conclude that the owner of the website also visits that sensitive site.
These problems must be addressed before Brave can be considered seriously by privacy-conscious users.
I think that Tor does already implement some padding protections, specifically against correlation via NetFlow records. See the spec at <https://gitweb.torproject.org/torspec.git/tree/padding-spec.... and an implentation history at <https://trac.torproject.org/projects/tor/ticket/16861>.
The effectiveness of further padding protections aren't clear unless you go to full padding, which is very expensive (probably impossible for mobile clients, for example). Tor is successful, in my opinion, because it understands that reducing performance reduces users and thus actually harms anonymity.
And the sentences you cite make perfect sense to me: the legislature may be relatively functional and courteous, but it still has many irrational members who are ignorant and backwards.
But I think your original point has been effectively rebutted: there are several notable onion services other than Silk Road, and some of these are quite beneficial.
Other "notable" onion services include OnionShare [0], which sets up an onion service to enable simple anonymous file sharing, Ricochet, which is a P2P anonymous chat service that sets up an onion services for each chat participant, and SciHub [2], which provides most academic papers for free. Each of these has been widely reported in the mainstream press.
[0] https://onionshare.org/ [1] https://ricochet.im/ [2] https://scihub22266oqcxt.onion
Here's why it's worse: they inserted a plaintext encoding into the response from the onion-address lookup relay, and so anybody observing the user (e.g. the ISP) could detect what onion address the user was connecting to. This applies after the fact to recorded traffic as well. Thus the researchers had no control over who got deanonymized, to whom they were deanonymized, and when they were deanonymized.
> I do wish both sides would acknowledge this is a tricky issue. On the one hand, if I run a tor exit node or relay, it is my node and it seems like I'm allowed to do with it as I please.
You actually are not allowed to do with your relay as you please. At least in the US, the legal theory protecting relay operators (i.e. safe harbor) also makes it illegal to observe user traffic content except in certain cases (e.g. to improve network performance).
> One other thing to keep in mind here is that SEI is a DoD funded center.
This doesn't seem very relevant. All researchers have an obligation to consider and mitigate possible harms that occur during their research (source: I work in a military research laboratory). These researchers clearly did not fulfill that obligation, and I'm sure their institution is reviewing or has reviewed their procedures to make sure it doesn't happen again.
[0] https://gitweb.torproject.org/torspec.git/plain/dir-spec.txt
1. Allow relays to apply individual hidden service (HS) blacklists: HS addresses are not necessarily public, can require authentication to connect to, and are trivial to generate (these are all extremely important properties for anonymous publishing in general). So these CP sites will go even more "dark" once the relay blacklists start being an annoyance. Not to mention that relay blacklists open up an obvious DoS opportunity.
2. Require credentials for HSes and revoke them if they are discovered to be serving CP: There is no apparent way to make identity creation costly in an anonymous world where we must be able to support relatively poor users (e.g. without much CPU, memory, bandwidth, money).
3. Allow authorities to selectively deanonymize certain users or service: There is no way this is going to work in a world where nobody agrees on who the authorities are or what constitutes a legitimate request.
The Tor Project is doing one thing about this problem that is consistent with their mission. They are making accessible safe but useful information about the world of hidden services. In fact, they have a whole funded project on it <https://trac.torproject.org/projects/tor/wiki/org/sponsors/S.... Note that this project includes such useful things as improved crawling support, global HS statistics, and discovering public .onion addresses.
> That's human self–incrimination. As long as this is safe for an one–time user... I have some basic semblance of security
So this is not anonymous reddit, then. That is much less useful, and it had better be extremely clear to users that they should only use it in that way.
> > There is an easy so-called "intersection attack"... The actual author will always be present,... and so eventually only the author will remain in the intersection.
> The actual author won't always be present. The posts start at a point, but they do not need the author to be present to continue distribution.
In this attack, the adversary would need to be one of Alice's peers most of the time. If he isn't, though, because Alice only connects to a few peers consistently, then he can at least identify one of those consistent peers. That serves as a focus for attack, say by denial of service.
> > Tor will not solve the problem here if users have to be able to receive incoming connections.
> The users do not need to accept incoming connections. There are some very restrictive routers that refuse to be UPNP port mapped, and Aether works fine on them.
So to actually be undetectable as using Aether, you can't accept connections. Then you have to hope that enough users are connecting for the anonymity and not the undetectability, or you'll have to provide some infrastructure nodes.
> > and so an adversary can just connect to the network to discover who to block or punish.
> For this, the roadmap is to have a 'protected' node which refuses all connections from nodes except those who are explicitly marked as trusted.
Great, if you promise undetectability, then this should be the default. Of course, that makes connectivity a challenge (what if everybody you trust doesn't accept connections because they also want to remain undetectable?).
> > The bootstrap IPs can obviously be easily blocked.
> It does not rely on the bootstrap IP. If you have installed the application, it asked you in the onboarding process IP and port of a friend
Sounds good!
> > The votes are not anonymous, which is unlikely to be clear to users and which are nearly as sensitive as authorship itself.
> They point to node id's, which are not users, but machines.
I don't understand the distinction being made here. In any case, the upvote is observed as coming directly from some IP. That is the identifier to worry about. As far as privately gauging the popularity of the post, I don't exactly understand what you need here, but they may be some crypto solutions that could work. Unfortunately, post popularity seems easily spoofed to me.
> > Denial-of-service here is as simple as flooding the network with "forwarded" posts and votes.
> Well, those posts won't get upvoted, and will get stuck in spam filters and upvote thresholds of users. None of those are implemented yet, of course, but this doesn't seem to be a structural problem.
What about the mechanism to prevent extinction of a post? Doesn't that spread a post without upvotes? And why can't I create a network of Sybils to upvote my spam posts? Also, spam filters are a UI mechanism, if I understand what you mean. I am talking about consuming network and memory via protocol flooding.
I do worry that "usable" has gotten more thought than "security", and providing a system that doesn't deliver the security it promises could be worse than not having the software at all. It may end up conveniently serving up those at most risk to their adversaries.
As others have noted, anonymity is hard to get right, and the approach here has some serious flaws:
1. It seems that the pseudonymous author of posts can easily be determined by connecting a bunch of Sybils (i.e. multiple clients) to as many other peers as possible and observing who is the first to send new posts by the target pseudonym. And you really can't have a forum without pseudonyms. Users will create them on their own (by including a nickname in their posts) even if you don't build it in.
2. There is an easy so-called "intersection attack" in which the sets of users that are connected at any given time a pseudonymous entity posts are intersected. The actual author will always be present, and the other participants won't be static, and so eventually only the author will remain in the intersection.
3. There is no apparent protocol obfuscation. Despite the use of TLS, the protocol traffic patterns of this new protocol are likely to be highly identifying. They can then be easily confirmed by an active attacker directly connecting to the suspected participant. In addition, it doesn't seem that the list of participants is protected, and so an adversary can just connect to the network to discover who to block or punish. Tor will not solve the problem here if users have to be able to receive incoming connections. And if you're using Tor, then you are relying on an external system that has censorship issues of its own (e.g. access from China is currently extremely limited) and does rely on servers.
4. The bootstrap IPs can obviously be easily blocked.
5. The votes are not anonymous, which is unlikely to be clear to users and which are nearly as sensitive as authorship itself.
6. Denial-of-service here is as simple as flooding the network with "forwarded" posts and votes.
Here are some suggestions for designing a system that is secure and that people can trust as being secure:
1. Write a white paper describing the design! This is not a detailed protocol spec - it's a description of how the protocol works at a higher level along with arguments establishing its security properties. This allows others to understand and critique the design.
2. Check out some of the related system designs [0-6]. They have had to deal with the same issues, and you can learn from them. You can get all these papers and more at <http://freehaven.net/anonbib/>. As you can see at that site, people have been thinking about these issues for a while and have figured out a lot!
3. Submit your white paper to a computer security conference. Even if it doesn't get in, you will get feedback from experts.
As it is currently, I wouldn't trust my communication to this system. You really need a large and diverse user base to provide anonymity, and so you will have to work at convincing people that this is something they can trust. Good luck!
[0] "Membership-concealing overlay networks" by Vasserman et al. CCS09
[1] "Crowds: anonymity for Web transactions" by Reiter and Rubin. TISSEC 1998.
[2] "Freenet: A Distributed Anonymous Information Storage and Retrieval System" by Clarke et al. PET 2000.
[3] "Traffic Analysis: Protocols, Attacks, Design Issues and Open Problems" by Jean-François Raymond. PET 2000.
[4] "ScrambleSuit: A Polymorphic Network Protocol to Circumvent Censorship" by Winter et al. WPES 2013.
[5] "Drac: An Architecture for Anonymous Low-Volume Communications" by Danezis et al. PETS 2010.
[6] "Tor: The Second-Generation Onion Router" by Dingledine et al. USENIX Security 2004.
1. Anonymity is provided as long as there is a single trustworthy member, regardless of how many phony members there are.
2. Denial-of-service resistance is provided even against many Sybils - eventually they will all be kicked out of the group and communication can proceed.
This is in contrast to protocols (e.g. onion routing, Aqua[0]) that only provide their security properties when the adversary doesn't control too much of the system. I think it is a fair claim to make and in particular is clear to people familiar with this area of research.
[0] "Towards Efficient Traffic-analysis Resistant Anonymity Networks" <http://www.mpi-sws.org/~stevens/pubs/sigcomm13.pdf>