Skip to content

Instantly share code, notes, and snippets.

@substack substack/keypair.js
Last active Mar 3, 2019

Embed
What would you like to do?
bittorrent proximity attack calculations
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;
}

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.

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;
}
@whyrusleeping

This comment has been minimized.

Copy link

commented May 6, 2015

Interesting stuff, that salt really screws things up

@lmatteis

This comment has been minimized.

Copy link

commented Jan 5, 2016

I'm wondering why then this sort of attack isn't used against regular DHT keys that are serving the list of peers downloading specific content.

@paulkernfeld

This comment has been minimized.

Copy link

commented Jan 11, 2016

@lmatteis that is a good question. I can't find anything on why that doesn't happen. Perhaps no one cares to do it? I think it might require a lot of network bandwidth, since nodes should decide which keys to retain based on the ones that are most frequently looked at. I.e. you couldn't just write each fake key once, you'd have to keep writing and reading them constantly in order to keep the real key DDoS'ed. Now that I think of it, this attack sounds pretty expensive.

@substack my understanding of the DHT security extension was that it restricts the IDs that a node can choose by incorporating the IP address of node into that node's ID. I don't think it restricts you from generating data with particular IDs.

@davidnicol

This comment has been minimized.

Copy link

commented Apr 27, 2016

@paulkernfeld @lmatteis @substack Breadth-first search instead of depth-first would weaken or eliminate the attack, especially combined with some kind of blacklisting beyond marking non-responding nodes "bad" as in BEP5. I'm not 100% clear on how DHT discovery works but I have presumed there are multiple pending peer location requests at any one time. The worst thing the attack should be able to do is create a situation equivalent to a "local maximum" in a heuristic search, just slowing down peer discovery slightly, until a different branch of the search finds nodes not participating in the attack and aware of the goal. Generating even an adjacent hash shouldn't "move responsibility for a hash onto nodes the attacker controls" with breadth-first search. BEP5 states "The original node iteratively queries nodes that are closer to the target infohash until it cannot find any closer nodes. After the search is exhausted, the client then inserts the peer contact information for itself onto the responding nodes with IDs closest to the infohash of the torrent" but it does not state if the iterative querying is done breadth first or depth first. I may have merely optimistically misread BEP44 to imply that a node publishing BEP44 data (either mutable or immutable) is supposed to have a much larger routing table than one that isn't, because every BEP44 DHT entry, being the actual goods, deserves treatment as an alternate "node ID" in BEP5 terms, as, the node having the data, the nearby nodes by ID should be able to direct queriers to it as well as to nearby BEP5 nodes.

In the event that we're trusting the network not to do "hash matching attacks" and therefore using depth-first search, here's pseudocode for a breadth-first variant:

function breadthfirst_node_search(target_id){
      var doneflag = false;
      var found_peer; 
      var seen_peers = {}; 
      var done_here = function( p ){doneflag = true; found_peer = p};
      var peer_list = [ first eight good BEP44-participating router table entries sorted by distance metric from target_id  ];
      var peer_distance_limit = distance_metric(target_id, peer_list[7]);
      while ( peer_list ){
                // ideally, the find_node gets backgrounded or other async mechanism is used,
                // so queries could happen in parallel as long as we don't have too many open channels
                var p = shift peer_list;
                seen_peers{p}++ and next;
                distance_metric(target_id, p) > peer_distance_limit and next; // prune our tree
                push peer_list, [ the result of the find_node operation on p, looking for target_id, with callback to done_here on found ];
                if (doneflag) { return found_peer };
      };
      return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.