Re: [GNUnet-developers] Re: TTL

[Christian Grothoff]

On Mittwoch, 11. Juni 2003 17:45 Niklas Höglund wrote:
> I sent this mail to the list more than a week ago, but it seems it was
> not accepted as I had misconfigured my mail server.

Good to know that it's not GNU 's server this time :-)

> Anyway, here it goes.
>
> On Wed, Jun 04, 2003 at 12:43:33AM -0500, Krista Bennett wrote:
> > I think the real concern over what might be leaked through TTL was
> > related to disclosing what I might be storing on my own machine. If you
> > assign a query a relatively low TTL and still get an answer from me,
> > there's a greater possibility that I have that content (or someone very
> > close to me does).  There are a few answers to this, and this is where
> > I'd really rather have Christian discussing this because he's the one who
> > hashed this out with other smart people working on PETs this Spring, but
> > I'll take a quick crack at it. Any mistakes I make here are strictly my
> > own :)
> >
> > First of all, content migration means that the content could well have
> > come from someone else and was just pushed out into the network.
> >
> > Secondly, since peers grab content floating by with a certain probability
> > and store it, me answering a query "too quickly" may well just mean that
> > the content was requested before and was indirected through me. The more
> > it's requested, the more it propagates.
> >
> > Also, if a query with a low TTL gets answered, it doesn't necessarily
> > mean the content was at an adjoining or nearby host. The locally
> > determined absolute TTL (again, TTL + Time(now)) is used to decide which
> > query entries get dropped from a full routing table, but nothing
> > guarantees a query will necessarily be dropped, especially when the
> > routing table *isn't* full. It simply determines which one should be
> > dropped if we need to drop entries. If my routing table isn't full, or
> > most of the entries already in it have lower TTLs (which can happen
> > simply by the virtue of them being long expired), AFAIK I may still
> > decide to serve "dead" queries based upon "how dead" they are. Is that
> > right, Christian? Now, granted, if the network is superbusy, these
> > queries aren't going to hang around for long, and I think this is where
> > the concern was, but that's as much as I remember about this particular
> > argument atm.
>
> If I fetch a large file, I fetch a lot of blocks. If I try to get all
> of them from a certain node, all the time using a low TTL, and get
> many replies fairly quickly, I'd say that makes it quite probable that
> that node has the entire file. As far as I can see, this could be
> because the entire file has migrated there when others fetched it, or
> it could be that that's the node where the file was inserted.  My
> guess is that a file would have to pass by a node several times for it
> to store all its blocks, so if a high proportion of a file is
> available at a node it's likely the file originated there.

What is "fairly quickly"? Peers always delay responses, typically at least by 
a couple of seconds to make it plausible that they got the response from 
elsewhere. So what would "fairly quickly" mean here? Also, what is a "low 
TTL". Remember, negative TTLs are fine. And there is no such thing as a clear 
limit where even the immediate responder would stop (or start) responding. It 
all depends on how much other traffic with with other TTLs that peer is 
routing. And note that if the responder is configured for "strong anonymity", 
it will not respond to your queries at all if it does not receive cover 
traffic. And once there is cover traffic, the TTL required depends also on 
that other traffic. 

Nevertheless, you can always play statistical tricks. Assigning probabilities 
describing how likely it is that a certain peer is the initiator is always 
possible (see also Dennis Krueger's analysis and the two papers on measuring 
anonymity from the last PET workshop where entropy (probability distribution) 
is used to evaluate anonymous systems (all were on the old GNUnet webpage, I 
still have to convert, maybe I got to it by the time you read this mail :-). 
The question is, how evenly distributed can we make the probabilities (and 
what does the adversary need to do to assess them). Active participation with 
direct probing of the responder with many blocks is a pretty strong attack. 
My best answer to this is to look at the ANONYMITY-SEND option description. 
Even if you probe the responder, you may not get any response if the 
anonymity level is set high enough (and if there is not enough cover 
traffic). But once there is cover traffic, you need to send reasonable TTLs 
in order to aquire routing table slots. So there is a good chance that the 
system will be fairly difficult to attack like that. 

> I don't really understand how gnunet works, so I could be wrong.  I
> hope I am, as that would make it more secure :)

As usual with this type of "intuitive" attack, you're not wrong per-se, it is 
just that there are a few more factors to consider that will make the attack 
much harder in practice -- and hopefully infeasible. But thinking of an 
attacker of trying this is certainly right, and I'm open for suggestions on 
how to improve. 

> It would be interesting to test the current (small) network and see if
> it can be guessed which nodes have what content.

Happy hacking...

Christian