headers
jrandom | 1 Nov 2005 20:40

weekly status notes [nov 1]


Hi y'all, its that time of the week again

* Index
1) 0.6.1.4 and net status
2) boostraps, predecessors, global passive adversaries, and CBR
3) i2phex 0.1.1.34
4) voi2p app
5) syndie and sucker
6) ???

* 1) 0.6.1.4 and net status

Last saturday's 0.6.1.4 release seems to have gone fairly smoothly -
75% of the network has upgraded already (thanks!), and most of the
remaining are on 0.6.1.3 anyway.  Things seems to be working
reasonably well, and while I haven't heard much feedback about it -
either positive or negative, I'm assuming y'all would complain
loudly if it were bad :)

In particular, I'd be interested in hearing any feedback from people
on dialup modem connections, as the testing I've done is only a
basic simulation of that sort of connection.

* 2) bootstraps, predecessors, global passive adversaries, and CBR

There's been lots more discussion on the list regarding a few ideas,
with a summary of the bootstrap attacks up online [1].  I've made
some progress specing out the crypto for option 3, and while nothing
has been posted yet, its fairly straightforward.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Tom Kaitchuck | 1 Nov 2005 23:55
Picon

Attack analysis on I2P

I recently describe an attack in the thread: [i2p] fwd: i2p tunnel bootstrap 
attack
in which an attacker can attempt to locate the origin of a message that it 
requested to be sent on any tunnel less then five hops, that is on the order 
of (c/n)^2. This prompted me to think about this further, and I have 
generalized this attack and created a model to determine it's effectiveness. 

First the attack: An attacker has a bunch of computers running in the network 
and is recording all traffic through them. These all operate like perfectly 
normal nodes. Then they choose one server, that they wish to identify and 
repeatedly send it a message, to which it must reply. They then have all of 
their computers flag messages that passed between them and the tunnel exit 
points between the time the request was sent and the reply was received. If 
those nodes that are connected to the tunnel end points were asked to send 
traffic to another one of their nodes, or to a node that in turn sent traffic 
to one of their nodes, they can do statistical analysis to determine the 
probability that the message they received was destined to the server in 
question, the probability that the second message they saw was the same 
message as the first one, and in turn the probability that they are talking 
with the tunnel owner. 

On the surface this sounds like a very weak attack, as all of these 
probabilities are very small. Even though that is true, the certainty with 
which they can identify the owner is quite high, because they are free to 
place thousands and thousands of requests.

Assumptions I make in my analysis:
There is only one server being attacked.
Nobody uses tunnels of length greater than 5 hops, because of latency.
False positives are not a concern of the attacker.
(Continue reading)

Permalink | Reply | 16 comments |
headers
jrandom | 2 Nov 2005 05:51

Re: Attack analysis on I2P


The numbers you're seeing sounds a bit off, but let me try to
restate what you describe with an alternate statistical anaylsis.

If I understand what you're describing correctly, rather than using
the (c/n)^2 probability of getting both a tunnel gateway and a
colluding peer next to the target and then trying to send a signal
between them, you're trying to use the (c/n) probability of having a
peer next to the target while mounting an intersection attack
against the tunnels themselves to serve as a means of detecting
participation, right?

In particular, you send a signal into the tunnel that the peer
participating can detect, and from there mount a predecessor attack.
This will only get you at most one predecessor sample for the life
of the tunnel, but since this only requires one (c/n) factor
(assuming a random distribution), over time you'll have enough
potential configurations to attack.

The question comes down to the signal being passed through the
tunnel.  The signal you describe is a straight intersection attack -
all tunnels in the network that transmit a message between t0 and
t1, where t0 is the time the e.g. HTTP request is sent, and t1 is
the time the e.g. HTTP response is received.  How many tunnels are
included in that set depends upon both the RTT and on how active
tunnels are.  If all tunnels transmit a message during that RTT,
the attack has P(success) = 0, but if only two do, it has
P(success) = 1.

Now, getting back to the specific attack, basically once every 2n/c
(Continue reading)

Permalink | Reply | 11 comments |
headers
Tom Kaitchuck | 2 Nov 2005 08:19
Picon

Re: Attack analysis on I2P

On Tuesday 01 November 2005 10:51 pm, jrandom@... wrote:
> The numbers you're seeing sounds a bit off, but let me try to
> restate what you describe with an alternate statistical anaylsis.
>
> If I understand what you're describing correctly, rather than using
> the (c/n)^2 probability of getting both a tunnel gateway and a
> colluding peer next to the target and then trying to send a signal
> between them, you're trying to use the (c/n) probability of having a
> peer next to the target while mounting an intersection attack
> against the tunnels themselves to serve as a means of detecting
> participation, right?

No, I am assuming the following tunnel configurations are vulnerable:
Where 1 represents an attackers node, 0 represents a normal node, A Alice, M 
Malory 
For tunnels length 0-4:
AM
A1M
A10M
A11M
A101M
A110M
A111M
A1010M
A1011M
A1101M
A1110M
A1111M
	and so on for 5.
(Continue reading)

Permalink | Reply | 10 comments |
headers
jrandom | 2 Nov 2005 15:27

Re: Attack analysis on I2P


> I am making the assumption that b is both constant and a known
> value. Neither are true, but it is sufficient for an average case
> analysis.

I think its a bit of a stretch though, as unless you're a global
passive adversary, you will have no idea what b is whatsoever.
Messages out of that peer are not evenly distributed across their
peers, nor are tunnels.

> The then can infer that if they receive a message from the exit
> point, during the relevant time window, and that computer send out
> b such messages, then there is a 1/b probability that their node
> is the next one in the tunnel.

This does not follow.  The batching delay has a small but
estimatable influence upon the number of messages sent down a
particular tunnel, thats true, but it says nothing whatsoever about
other tunnels that the peer could have forwarded the message down,
or through what peer it would do so.

Receiving a message in the t0-t1 window does give you enough
information to begin to mount an intersection attack on those
tunnels, but they don't have a 1/b chance of being in the same
tunnel as the colluding gateway.  Unless you mean to imply b is the
number of  messages transmitted by *any* router on the network in
the batching period?  In which case, you need to be at least a
global passive adversary, if not also an internal global passive
adversary - the later of which is impossible, since it implies c==n.
(Continue reading)

Permalink | Reply | 9 comments |
headers
frosk | 2 Nov 2005 15:41

Re: Attack analysis on I2P

 <jrandom <at> ...> writes:

> Absolutely, there have been many discussions on irc over the last
> year with regards to Feedspace, but perhaps Frosk can explain
> further, since what matters is what he implements.  My understanding
> is that Frosk plans on getting the functional ASAP syndication going
> first, then implement the batching and mixing strategies at the
> first syndicator, who releases it into the ASAP syndication
> according to the batching and mixing strategy.

I'm just popping by to quickly confirm this ;-) The first iteration will just
use the "forward ASAP to all subscribing peers" strategy, and then we can
concentrate on batching/delaying strategies. There is some interesting
discussion at http://forum.i2p/viewtopic.php?t=622 .

> Of course, if
> someone else wants to get involved and help out with the Feedspace
> development, this stuff will be clarified faster.

As real-life concerns gradually calm down, I'll get back to feedspace hacking,
just to be clear about that. As soon as something workable exists, I'm sure
people will want to help out :-)

-- frosk
Permalink | Reply | 0 comments |
headers
Tom Kaitchuck | 2 Nov 2005 17:44
Picon

Re: Attack analysis on I2P

On Wednesday 02 November 2005 8:27 am, jrandom@... wrote:
> > I am making the assumption that b is both constant and a known
> > value. Neither are true, but it is sufficient for an average case
> > analysis.
>
> I think its a bit of a stretch though, as unless you're a global
> passive adversary, you will have no idea what b is whatsoever.
> Messages out of that peer are not evenly distributed across their
> peers, nor are tunnels.

Right, so an attacker would ether need to be able to monitor ISPs as well, or 
could just grossly overestimate b to be on the safe side.

> > The then can infer that if they receive a message from the exit
> > point, during the relevant time window, and that computer send out
> > b such messages, then there is a 1/b probability that their node
> > is the next one in the tunnel.
>
> This does not follow.  The batching delay has a small but
> estimatable influence upon the number of messages sent down a
> particular tunnel, thats true, but it says nothing whatsoever about
> other tunnels that the peer could have forwarded the message down,
> or through what peer it would do so.

I am not referring to batching in the sense that I2P uses it, but rather in 
the sense that a remailer uses it.

> Receiving a message in the t0-t1 window does give you enough
> information to begin to mount an intersection attack on those
> tunnels, but they don't have a 1/b chance of being in the same
(Continue reading)

Permalink | Reply | 7 comments |
headers
jrandom | 2 Nov 2005 21:43

Re: Attack analysis on I2P


> > I think its a bit of a stretch though, as unless you're a global
> > passive adversary, you will have no idea what b is whatsoever.
> > Messages out of that peer are not evenly distributed across their
> > peers, nor are tunnels.

> Right, so an attacker would ether need to be able to monitor ISPs
> as well, or could just grossly overestimate b to be on the safe
> side.

An external global passive adversary will not know a tunnel message
from a data message from a netdb message from a piggybacked ACK.
And as mentioned before, an internal global passive adversary cannot
exist with c < n.

> I am not referring to batching in the sense that I2P uses it, but
> rather in the sense that a remailer uses it.

Well, some remailers are timed threshold mixes too, the difference
is I2P's timer and batch size are both miniscule ;)

But basically, to do what you propose, you'd need to have access to
the message counts and timing of all tunnel messages entering and
leaving all peers.  If they're a global passive adversary, they'll
only get SSU packet counts which may offer statistical suggestions
of tunnel messages, with (c/n) peers exposing nonstatistical data.

If they're not a global passive adversary, if they only control
(c/n) nodes, they have *no information whatsoever* with which to
even estimate any particular b.
(Continue reading)

Permalink | Reply | 6 comments |
headers
Tom Kaitchuck | 2 Nov 2005 22:51
Picon
Favicon

Re: Attack analysis on I2P

On Wednesday 02 November 2005 2:43 pm, jrandom@... wrote:
> > > I think its a bit of a stretch though, as unless you're a global
> > > passive adversary, you will have no idea what b is whatsoever.
> > > Messages out of that peer are not evenly distributed across their
> > > peers, nor are tunnels.
> >
> > Right, so an attacker would ether need to be able to monitor ISPs
> > as well, or could just grossly overestimate b to be on the safe
> > side.
>
> An external global passive adversary will not know a tunnel message
> from a data message from a netdb message from a piggybacked ACK.
> And as mentioned before, an internal global passive adversary cannot
> exist with c < n.

True. 

> > I am not referring to batching in the sense that I2P uses it, but
> > rather in the sense that a remailer uses it.
>
> Well, some remailers are timed threshold mixes too, the difference
> is I2P's timer and batch size are both miniscule ;)
>
> But basically, to do what you propose, you'd need to have access to
> the message counts and timing of all tunnel messages entering and
> leaving all peers.  If they're a global passive adversary, they'll
> only get SSU packet counts which may offer statistical suggestions
> of tunnel messages, with (c/n) peers exposing nonstatistical data.
>
> If they're not a global passive adversary, if they only control
(Continue reading)

Permalink | Reply | 5 comments |
headers
jrandom | 2 Nov 2005 23:34

Re: Attack analysis on I2P


> > Every router will also always be the last hop in their own tunnels.
> > The analysis requires sampling only situations where the right
> > tunnel is being tested, otherwise you're going to be gathering
> > predecessor samples from other tunnels, each of which will expose
> > an equal probability of being next to the end of a tunnel initiated
> > by a different peer.
>
> Yes, and I don't know how fast this will be. But we do know how
> fast Alice's probability grows. And based on the analysis of the
> standard Predecessor attack by Michael we can see that in most
> cases, that Alice will come up more than other random nodes.

The predecessor attack doesn't have that conclusion - it requires
you to differentiate between samples in a path and samples not in a
path.  If you can't differentiate Alice's path from Bob's path,
you're just as likely to get Bob's router as the predecessor as
you'd get Alice's.

On the other hand, I think what you describe *could* differentiate
Alice's path from Bob's path, but at a rate much slower than the
O(1) described.  It'd depend upon the RTT as well as the network's
activity for the method I described (intersecting active paths with
t1-t0).  If there is an O(1) method of discovering whether the peer
is in the targetted tunnel however, that'd make this more mountable.

> However I don't regard False positives as an issue, as to avoid
> them the attacker could simply conduct the exact same analysis on
> both their incoming and outgoing tunnels, at the same time,
> without using any more resources, and discount the probability of
(Continue reading)

Permalink | Reply | 4 comments |

Gmane