(I changed the thread's Subject, since "Anon Mus"'s attack is not the same as the attack described on it.wikipedia.)
On Fri, Feb 15, 2008 at 12:42:59PM -0800, Anon Mus wrote: > F. Fox wrote: > > Anon Mus wrote: > >> 3. Attacker has a list of known public/private key pairs. These are > >> generated over the years by government security service supercomputers > >> and their own secure network computers (around the world). Such lists > >> are > >> regularly swapped between 'friendly' countries and are fro sale on the > >> black market. Given any tor nodes public key, the attacker looks up > >> that > >> key in the list and it returns the tor nodes genuine private key, where > >> it > >> has it in its list. (Interesting note: here you have to imagine that > >> there is software of out there, like the tor network itself, which > >> could > >> be used for generating and acquiring billions of key pairs a year over > >> millions of networked computers world wide. You only need to store the > >> key pairs such networked software generates after they have finished > >> with them.) > > > > Umm... unless you're talking about lists of *compromised* keys (i.e., > > stolen, like via malware), then this is pure FUD. Trying to figure out > > the private key by other means, is pretty infeasible. I agree with others here that this particular item from Anon Mus is bogus. The math simply doesn't work this way: 1024 bits is really big, and enumerating and storing products of 512ish-bit primes is going to fill up your disk way before you have a non-trivial fraction of them. > I must say, I feel that 3 very deliberate and clumbsy attempts have > been > to shoot down such a VERY obvious and sound scenario. > > Why so? Probably the reason they all misinterpreted your attack is the thread you posted it in (which describes a similar-sounding attack that *is* bogus), plus the above "A.3" which sounds like it's straight out of some conspiracy theory. Now that we've cleared that up (if we have), let me rephrase your attack and we can see if it makes sense to more people here. Imagine an adversary who can observe any connection attempt from Alice and fail any of them that he wants. Imagine this adversary also runs, say, 10% of the Tor network, including some guard nodes and some exit nodes. Alice starts up, learns about the Tor network, picks her entry guards, and tries to connect to some. Our adversary keeps tricking her into thinking she picked bad nodes, until she picks an adversary-controlled entry guard. Then he lets all connections to that entry guard succeed, but when Alice picks a second hop that isn't adversary-controlled, he claims that next hop is down. Until eventually he picks an adversary-controlled second hop. Repeat for the exit node. Ignoring bandwidth weightings, exit policies, etc, Alice would need to try (.1*.1)^-1 = an estimated 100 circuits before she makes three bad hops (assuming she's already happened across the bad entry guard). For a more reasonable 1% of the network being bad, that changes to 10000 circuit rebuilds. See http://freehaven.net/anonbib/#ccs07-doa for a related paper here. Mike Perry also brought up an attack like this when he was working on SoaT. Alas (or perhaps fortunately), he's been working on Torbutton-dev lately instead. The number of competent anonymity programmers and designers in the world is still woefully small. Note that to make this attack work, you really do need to be able to reject any connection from Alice that you want. Otherwise, if she picks some bad guards and some good guards, she'll switch to using her good guards as soon as the bad guards demonstrate themselves to be flaky. And if you're in that powerful a position for Alice, I'm not too worried about this attack; or to say it differently, I worry a lot about other attacks too, and I'm not sure I can help Alice much. --Roger
