[p2p-hackers] Pirate Pay

[Raphael Manfredi]

Quoting "Vijay K. Gurbani" <vkg at bell-labs.com> from ml.p2p.hackers:
:This looks like Pirate Pay is injecting multiple sybils into the
:DHT with node-IDs close to the info-hash of the file, thus making
:the sybils responsible for the file.  This assures that all queries
:are sent to the sybils, allowing the sybils to sent out false
:information to the other peers.

See:

	"Efficient DHT attack mitigation through peers's ID distribution" by
	Thibault Cholez et al., published in June 2010.

This is a protection that can be added to every DHT nodes and which will
significantly increase the cost of widespread Sybil attacks.

This DHT protection algorithm has been implemented in gtk-gnutella, with
a few enhancements of mine (transmitted back to the author of the above
article).

Here's my summary of the article, as C comments within gtk-gnutella:

	/* 
	 * The idea is that Sybil attacks will necessarily change the statistical
	 * distribution of the KUIDs surrounding the target.  By comparing the
	 * actual KUID prefix distribution with the theoretical one, we can detect
	 * that something is unusual.
	 *
	 * The divergence between the theoretical distribution of prefixes and
	 * the actual one is measured by computing the Kullback-Leibler divergence
	 * (K-L divergence for short).
	 *
	 * The measured distribution of prefixes sharing "i" leading bits with the
	 * target is M(i).  For instance, if 6 nodes from the 20 closest share
	 * 13 bits with the target, M(13) = 6/ 20 = 0.3.
	 *
	 * The prefix length b_min at which we start looking is the theoretical
	 * k-ball furthest threshold, which dht_get_kball_furthest() gives us.
	 * It is computed as:
	 *
	 *    b_min = E[log2(estimated_DHT_size / KDA_K)]
	 *
	 * with E[x] being the integer part of x.
	 *
	 * The maximum prefix length we consider, b_max, is computed as:
	 *
	 *    b_max = b_min + KDA_C
	 *
	 * where KDA_C is the "closeness factor", an arbitrary amount of extra
	 * bits we allow to have in common with the key before looking suspicious.
	 *
	 * Starting at b_min, the theoretical distribution of prefixes, T(i) is
	 * computed as:
	 *
	 *	  T(i) = 1 / 2^(i - b_min + 1)
	 *
	 * So if b_min is 13, T(13) = 1/ 2, T(14) = 1/2^2, T(15) = 1/2^3, etc...
	 * Up to T(b_max) = 1 / 2^(KDA_C + 1).
	 *
	 * The K-L divergence of T from M is given by:
	 *
	 *    Dkl(M|T) = SUM(M(i) * log2(M(i) / T(i))
	 *            i = b_min to b_max
	 *
	 * Intuitively, the larger M(i)/T(i), the larger the divergence added
	 * by the i-bit prefix.  Given that an attack will focus on getting close
	 * to the KUID target, T(i) will get smaller and smaller as "i" increases
	 * and a large M(i) will indicate a potential attack.
	 *
	 * Since Dkl is a summation, we can determine which prefix length
	 * contributes the most towards the divergence and therefore remove these
	 * nodes from the path as a counter-measure.
	 *
	 * The beauty of that protection is that the more efficient the Sybil
	 * attack is designed to be, the more we'll spot it and defeat it!
	 */

Raphael
_______________________________________________
p2p-hackers mailing list
p2p-hackers at lists.zooko.com
http://lists.zooko.com/mailman/listinfo/p2p-hackers

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE