[tor-dev] Hidden Service Scaling

waldo waldoalvarez00 at yahoo.com
Fri May 9 19:05:49 UTC 2014

El 04/05/14 07:42, Christopher Baines escribió:
> On 04/05/14 11:43, waldo wrote:
>> El 02/05/14 02:34, Christopher Baines escribió:
>>> On 02/05/14 00:45, waldo wrote:
>>>>    I am worried about an attack coming from evil IP based on forced
>>>> disconnection of the HS from the IP. I don't know if this is possible
>>>> but I am worried that if you pick a new circuit randomly could be highly
>>>> problematic. Lets say I am NSA and I own 10% of the routers and
>>>> disconnecting your HS from an IP I control, if you select a new circuit
>>>> randomly, even if the probabilities are low, eventually is a matters of
>>>> time until I force you to use an specific circuit from those convenient
>>>> to me in order to have a possible circuit(out of many) that transfers
>>>> your original IP as metadata through cooperative routers I own and then
>>>> do away with the anonymity of the hidden service.
>>> Yeah, that does appear plausible. Are there guard nodes used for hidden
>>> service circuits (I forget)?
>> No idea, according to this docs
>> https://www.torproject.org/docs/hidden-services.html.en  there aren't
>> guards in the circuits to the IP in step one(not mentioned). They are
>> definitely used on step five to protect against a timing attack with a
>> corrupt entry node.
>>   Even if they are used, I still see some problems. I mean it looks
>> convenient to try to reconnect to the same IP but in real life you are
>> going to find nodes that fail a lot so if you picked an IP that has bad
>> connectivity reconnecting to it is not gonna contribute at all with the
>> HS scalability or availability of your HS, on the contrary.
> I don't think a minority of bad IP's will do much to hurt a hidden
> service.
Hi Christopher. You are correct a minority can't do much harm, but they 
don't contribute. What's the point on keeping them? I don't meant to be 
rude, but also minority is relative. Can you please tell us what is the 
total number of IPs? I ask you because you were working there so you 
likely know better. If is 3 then one bad node is 33% of failed 
connections, If they are 50 one is only 2%.
> Clients will try connecting through all IP's until giving up,
> and this will only happen when they initially connect.
What I've had noticed is that initial connection is what causes most 
troubles. Once you establish a rendezvous with the HS things go smooth. 
Is my personal experience don't know what others experience. I've 
noticed also that usually highly used services like the hidden wiki tend 
to behave a whole lot better. No idea why. Could be related to the HSDir 
query and this http://donncha.is/2013/05/trawling-tor-hidden-services/. 
Don't know if that was fixed.
>>   Maybe a good idea would be to try to reconnect and if it is failing too
>> much select another IP.
> It currently does do this, but on probably a shorter time period than
> you are suggesting. It keeps a count of connection failures while trying
> to reconnect, but this is reset once a new connection is established.
Yes I meant measuring a larger time period and over different circuits 
as the cause of disconnection could have being the circuit failing and 
not the IP.

What happens if the HS just goes offline for a while? It keeps trying to 
connect, finds that it can't connect to the IPs and picks another set? 
You are differentiating that case?

How do they coordinate which one publishes the descriptor? Wich one puts 
the first descriptor?
> This gets complicated, as you need to ensure that each instance of the
> service is using the same introduction points,

I saw your answer to another person and seems to me is related to this 
you are saying

If the "service key"'s (randomly generated keys per introduction point)
are used, then this would complicate/cause problems with the multiple
instances connecting to one introduction point. Only one key would be
listed in the descriptor, which would only allow one instance to get the

What if the instances interchange keys and use the same? Master/slave 
for example and one of them take the master role if the master goes 
offline. Lets say master instance creates the IPs and sends a message to 
the rest to connect there.

How about changing the descriptor to host several keys per IP in case 
previous is not possible/too difficult?

Why this needs to be ensured? Does it breaks something? I understand it 
could be convenient to have at least two to avoid correlation attacks 
from the IP but why all? What would happen if one instance goes offline? 
The whole thing breaks? The desirable behavior I think in that case is 
that other instances take over and split load as if nothing happened.

I also think is highly desirable they are indistinguishable to provide 
less information (enumeration, etc).

If they use the same key, you could send the rendezvous message to all 
instances from the IP as all would have the same private key and can 
decrypt it (if the IP is not shared by different HS, don't know if this 
is possible currently). So the message doesn't gets lost in a failed 
circuit. If it is shared by several HSs some routing could be convenient 
but not necessary IMHO as they don't have the key to decrypt and 
statistics gathering could be blinded by the HS sending bogus RV 
messages that later discards.

Instances could negotiate which one is going to answer even if the one 
who is going to answer is not connected to the IP if instances talk to 
each other.

Let's say I could have a master that receives information of the load of 
slaves and receives the RV messages all instances receive. Later 
instructs the instance with less load to answer.

>   it seems to me that
> tracking connectivity failures over the long term, and changing IP on
> some threshold could break this.

Why would break it? I would create new IPs connect to them and would 
keep the old ones until the new ones become accessible (I could detect 
this by monitoring if I receive messages or by querying the HSDirs). The 
IP could act non cooperatively and send me bogus messages to try to 
confuse the HS and avoid it going away so probably checking both could 
be a good idea. I could also test if I start receiving messages through 
the new IPs. Just ideas.

>> If the IP is doing it on purpose the HS Is going to go away so the
>> control the IP has disconnecting your HS is capped for any attack known
>> or unknown. If is not on purpose the HS goes throwing away failing nodes
>> until it picks a good node as IP. I think it would cause over time, the
>> tor network re-balance/readapt to new conditions itself. For instance in
>> the case some IP is overloaded (maybe by DoS) causes the HS to go away
>> from the IP.
>> I would also rotate the IPs after using them some time. I don't think is
>> good to have one IP for too long. Doesn't sounds good to me. If for
>> instance I am big daddy and know your IPs I could go there seize the
>> computers and start gathering funny statistics about your HS. Or simply
>> censor your HS by dropping messages from clients trying to send you the
>> rendezvous point (is this possible? looks like it is if I drop introduce
>> messages and generate fake ones). You wouldn't even know cause I can
>> keep your connected and receiving fake connections. Only maybe if you
>> try to check the IP by trying to send a rendezvous point from your HS to
>> your HS (this IP quality test would be great if tor would do it
>> periodically). I somehow do it myself manually  when I notice the HS is
>> superhard to reach. Sometimes it works great, sometimes even being
>> turned on the server and online, is not visible. So you have to take
>> down tor and restart it and wait again for a while.
>> I was thinking maybe you could select new ones and inform HSDirs about
>> the change and after the new ones are known end circuits to the previous
>> IPs and with that avoid the overhead of the rotation.
>>   I would rebuild circuits to the IP from time to time (originating from
>> the HS). Multiple connections to the same IP would permit to do this
>> better since I can make a new one and afterwards kill a previous circuit
>> remaining connected all the time.
> Lots of things here, generally, some things seem quite hard to do in a
> uncoordinated, distributed manor (e.g. IP rotation).
Why uncoordinated? Looks to me it would be convenient instances could 
talk. Load balance, taking over of failed instances, etc. Would take 
work to do that for sure but doesn't seems impossible to me. I guess the 
HSDir code would have to be modified to be able to host new signed 
information coming for the same HS while maintaining the old one. Maybe 
follow signed commands from the HS. Delete this IPs, add this other IPs 
with some limit to avoid the HS attack HSDirs flooding them to store 
bogus info). New question here could anyone flood an HSDir by posting a 
zillion descriptors for a zillion bogus HSs? The HS would have to select 
new ones, publish them wait until they become available before dropping 
circuits to the old ones.

>   And I am not to
> sure that things like IP rotation and rebuilding circuits to IP's will
> even help with anonymity issues.
Regarding entry guards this is one article speaking about them, don't 
know if up to date:


Seems they are always used for all sort of circuits including HS. So if 
you reused the code they are being selected.

I am still concerned that if things stay too long in one way, big 
players (antidemocratic governments for instance) could do things. Keep 
in mind that if you have more running instances of your HS the chances 
to locate one of them increases since I only have to locate one of your 
instances to know who you are.

Ok take a look at this attack, correct me if I am wrong and some point 
is not possible (I invite anyone to proof me wrong). As I said I 
appreciate your work, but it needs to be challenged to be accepted by 
the community so it doesn't stays in a limbo of "I don't know" and is 
better to patch every possible hole before it becomes mainstream.

Suppose I am an totalitarian government and you are a dissident running 
an HS over Tor in the same country.

1 - I start introducing high availability high bandwidth corrupt nodes 
to the network across the globe (I could rent servers in case you decide 
to connect to nodes offshore or simply deploy nodes in another country), 
the more I put the higher the chances of being a stone in your anonymity 
path. To lower the budget I could host several Tor routers in one 
computer with several network interfaces and fast CPU/crypto hard for 

2 - I see you are using some IPs (I can query the HSDirs to get some) so 
If I am not lucky to be your HS's IP at start, I go flooding those you 
select to take them offline in order to force you switch so you pick 
eventually one of my corrupt nodes as IP. Is not clear to me if choosing 
them in a deterministic way gets in the way of this or helps. If is 
deterministic I could precalculate how many nodes I have to force go 
offline until you pick one of mine, so I could shutdown those nodes that 
will never be selected and lower my budget at least. I could bribe some 
ISP to rent servers with specific IP numbers(don't know if you selected 
this) or bribe the IP operator if he/she publishes the contact email. 
You can't even suspect if you don't know the flooded IP operator as is 
totally normal a node going offline. So no dust raised (there is a way 
to make a Tor router publicly publish it was attacked so other ppl can 
be warned?).

3 - I become one of your IPs at least. This is a good achievement. From 
now on I know you are going to connect back to me using some circuit 
that can contain corrupt nodes or not when I disconnect you. When you 
connect back to me you have the counter reset so I can disconnect you as 
much as I want.

4 - I know your last node so if it is not mine I disconnect your circuit 
until you select a circuit that contains one of my corrupt nodes as the 
last one.

5 - When you do I can see the previous node in your circuit. If it is 
not mine I disconnect you and go to step 4. If it is, I learn about one 
of your guards. I stay for a while going to step 4 to enumerate your 
guards. The more you have the longer it takes, the less guards the 
easier for me. But I can continue the attack as long as I know one of 
the guards to gain time and see if I have success. I could flood your 
guard to force you select another guard and accelerate the process. Or 
globally block access to the guard.

6 - Once I learn all your guards I can do some things in front of that.

- Since your instance is going to connect to those nodes for a long 
while, I could censor your instance flooding those nodes at least until 
you notice and select new guard nodes (I can be insidious here repeating 
the attack over and over again and for each instance). I could wait to 
enumerate all the guard nodes of all of your instances since all connect 
to my IP.

- Since I am a big government and I have control of the ISP you are 
using, I could monitor incoming connections to your guard nodes. I 
record all network IP numbers connecting  to those nodes for a while. 
Maybe I could filter here some nodes with some heuristics (nodes that 
only connect to those guards since the probability of another node 
connecting to those specific guards should be low) but not necessarily 
as I am going to filter later. Notice that HSs stay connected for looong 
time periods so the connection time of a server should be longer than a 
client and I could discard nodes with that information.

   Once I have enough information I disconnect you from the net some 
small amount of time to avoid you leave my IP leaving some room for 
random failed circuits. I can tell the ISPs to do this for me. Is 
totally normal a disconnection so no dust raised. I can take my time 
too. Disconnect you today, wait some time and disconnect you again.

  I could do some things for the case of an HS hosted offshore. Bribe 
ISP employees, cause DoS to ISPs or individual computers, sell 
backdoored routers, backdoor router firmware, but that is less realistic 
and harder. Not discardable IMHO but I am going for the easy case here.

  Notice I don't care which circuit you use from now on to reconnect 
back to me even if you select new guards. I could monitor if your HS 
answers to RV messages using several preselected RV points too.

If once I disconnect those nodes, I don't see any instance go away I 
discard those nodes as hosting the HS.

If I see some of the instances go away then your node is in that subset.

I perform a binary search here disconnecting half nodes every time so 
the disconnection number it takes me is O(log(n)) where n is the total 
number of nodes I see connecting to those guards.

I repeat each of this steps several times to filter with statistics the 
casual circuit failure of your HS to my IP.

If two or more instances use the same IP I would still see some 
instances staying or going so seems it doesn't protects against the 
attack at all even if they are indistinguishable. If you close circuits 
and reopen new ones from time to time I would get noise here but maybe I 
could filter with statistics.

- I could in some cases seize a guard node or bribe the operator.

If so far there are no flaws, I can spy you to know where you are 
hosting computers and seize them without giving you time to turn them 
off and use plausible deniability crypto soft (truecrypt) and be able to 
claim you where routing instead of hosting the HS (by cloning the router 
without the HS data).

  With multiple instances seems to me now becomes desirable to host at 
least one router per instance, to be able to deny you where hosting and 
claim you were routing. As looks it won't be possible to correlate the 
router down with the HS down (other instances would hide that if they 
are indistinguishable and take over when one instance goes down).

Now if you instead rotate the IPs from time to time, I would be forced 
to go back to step 2 of the attack but on the other side your chances of 
selecting a corrupt IP or a corrupt node in your circuits increase. I as 
hosting one of your IPs would have less control since is not going to 
last forever and would be time limited.

Changing circuits could introduce noise in step 6 to some extent, on the 
other side increases the chances of selecting a corrupt node in your 

So probably all of this would have to be studied with statistics and 
current Tor network size.

Looks to me this could have more implications in other areas.

>> In some previous messages about the subject I saw that HSDirs provide
>> all the HS IPs. I don't like this way of doing things since let's say I
>> have 6 IPs to my HS available to everyone. To cause a DoS to your HS
>> seems to me all I have to do is cause a DoS to the IPs. And there is no
>> need for everyone to know all the IPs of one HS all the time. All one
>> user needs to connect is just some maybe for redundancy but not all.
>> Is there some way to only provide part of the IPs of one HS to one user?
>> Avoid enumeration? Maybe distribute partial information to HSDirs? Don't
>> know, just thinking. Maybe "abuse" some caching effect on HSDirs and
>> publish partial IP information on one end and partial in another end
>> that only reaches all users in entirety over time.
> As the set of IP's is so small,
   Again small is relative. Earlier you mentioned some nodes failing 
where not going to affect too much the service so seems contradictory to 
me. Can you please mention numbers? Can't this number be increased?
> I cannot think of any practical way to
> do this without it being trivial to break.

This is not directly related to your work but could be worth discussing. 
I was thinking that one property that maybe could be exploited could be 
the fact that the whole Tor network has lots of computational power that 
is hard to match by a single player (unless the player is really big). 
This is a rough idea that could contain flaws and maybe could be improved.

What if lets say the IP information is encrypted by the HS,  doesn't 
provides the key and makes Tor clients "bruteforce" them to open the 
encrypted message containing the IP. All IP keys scattered through the 
keyspace that could be larger or shorter depending on the time I want 
you to spend looking for it. So any IP would have equal chance of being 
found. Passing the key through an ASIC resistant function and then 
encrypt with the result so big players  would have to use at most GPU 
and somehow equalize different CPU powers through memory bandwidth. All 
Tor clients start looking at a different random position of the keyspace 
until they find one key to desencrypt one IP.

 From there they start to communicate with the IP if available and keep 
looking for the rest of the IPs (to be able to reconnect if the RV and 
the initial used IP go offline). Maybe re-connection to the RV could be 
desirable too to some extent to improve availability of HS in case the 
circuit fails. Don't know if currently possible.

Maybe adding 1 bit of the key inside the encrypted message for another 
encrypted IP so finding through a route of decryption makes it more 
feasible than starting from zero (this could be a good idea or not). 
Therefore forcing anyone to follow a decryption path depending on where 
they start decrypting IPs information.

To explain the idea better lets say I have 3 introduction points A B and 
C, but I don't see why there couldn't be more specially since the bulk 
of the traffic goes through the rendezvous and not through the IP, IPs 
could be shared by several HS and since is harder to cause a DoS to more 
nodes than just a few.

lets say one Tor client starts looking at a random position and finds 
the key for B (now it can connect to B if available and pass the RV message)
once decrypted it gets one bit for the key of C
so starts looking for the key of C as is easier to find than the key for A.
Then gets C and that gives it bits for A.

Another Tor client starts random finds A and gets 1 bit for B (now it 
can connect to A and pass the RV message if available)
goes to B and gets the bit for C.
finds C.

After a while the HS rotates IPs and the process starts again (not 
necessarily all at once could be a flow in a way some get replaced 
maintaining part of the old ones). So anyone trying to cause a DoS would 
have to perform all of that work again and be very quick to find all of 
the IPs before they are rotated again by the HS in order to flood all of 
the IPs. So at most all they could do is turn the HS intermittent (if 
enough CPU power and enough bandwidth). On the other side the Tor swarn 
would be very efective at finding them all.

The big question that remains to me here is how much this causes a big 
player waste a load of resources without pushing out of the network 
small players (mobile devices for instance). The memory hard functions 
equalizes somehow devices by the memory bandwidth limit but still can 
make large differences. Seems to me that the more IPs are selected for 
an HS the more this can be achieved.

One option I was thinking to fix that problem is for instance the HS 
could function normally if everything is running smooth, and if it 
detects that can't create circuits to the IPs switch to protective mode 
in a way that things work as usual if there is no attack but the system 
changes to defensive mode if there is an attack.

Let me explain better. I as an HS work as normal. Suddenly I see all the 
circuits to my IPs can't be established (or router operator of my IP 
publish they are being attacked). I create new ones and see again that 
eventually I can't connect. That probably means someone is attacking my 
IPs. I switch to defensive mode and publish encrypted IPs. Clients 
notice they are encrypted and start each on their side to look for the 
IP keys.

I could have degrees here and increase computational complexity to do 
away with the attack. Lets say maybe that only mobile devices get pushed 
away from the net but CPU and GPU nodes could still connect so the 
attack is only to a part.

   One problem could appear here is the time it takes the information 
published to HSDirs to reach clients. I ignore a lot of information 
about that part and I beleive is under active research ATM.

The scheme doesn't pushes away big players with large computational 
power and bandwidth but can push away some medium players. Also it 
doesn't protects to other attacks for instance flooding through a RV 
(could puzzle solving be applied here? Let's say the harder the puzzle 
the more bandwidth I give to you)


> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20140509/e5aeaa26/attachment-0001.html>

More information about the tor-dev mailing list