November 13, 2011

Simplified Summary of Microsoft Research’s Bitcoin Paper on Incentivizing Transaction Propagation

Filed under: bitcoin, slashdotted — Tags: , — coderrr @ 8:51 am

Shameless Plug: Hide your IP while connected to the Bitcoin P2P network with a VPN Service.

This is a very simplified summary of the Microsoft Research paper “On Bitcoin and Red Balloons”. This summary is meant for people who already understand how the Bitcoin network and protocol function. For an overview of that see the Bitcoin Wikipedia page.

The flaw pointed out in the paper is that there is a negative incentive for miners to forward Bitcoin transactions. By not forwarding you increase the chance that you receive the transaction’s fee rather than another miner. This is not so much of an issue now as the fees usually total to much less than the 50BTC reward per block. But as the block reward diminishes in the future this negative incentive may become more of an issue.

The paper’s proposed solution is to reward nodes who forward transactions as well as nodes who solve the block in which the transaction is included. Each transaction would have a chain of its forwarding nodes attached to it. When a miner solves a block all nodes in the chains that lead the transactions in that block to the miner would be rewarded. The issue with this is that a single node can forward to itself many times to illegitimately gain more of the reward. This is called a Sybil attack.

Their solution to the Sybil attack is to give 0 reward to all nodes in a chain of forwards if the length of that chain is greater than H. This gives a negative incentive to create fake forwards to yourself in attempt to gain multiple rewards for a single transaction. Your best bet is to forward legitimately to other nodes and hope the transaction reaches a miner who solves it before the number of forwards is greater than H.

The paper determines optimal strategies in terms of values for H and the functions to divide the fee between nodes in the chain. But this is all modeled on directed trees (which have no cycles) rather than a random graph (which is what the Bitcoin network is like in reality) so it’s unknown how well it would work in practice. They leave work on random graphs for future research.

To clear up some common questions

What prevents nodes from faking/stripping the forward chain so that they can pretend as if they were the only forwarder?

The paper proposes changing the protocol so that you are must include the public key you are forwarding the transaction to and then signing it with your public key. So if the transaction was sending coins from coderrr -> sammy and the chain was coderrr, bob, alice, miner, it would look like this:

msg0 = sign_coderrr(coderrr->sammy, 1BTC, forwardto: bob)
msg1 = sign_bob(msg0, forwardto: alice)
msg2 = sign_alice(msg1, forwardto: miner)

Alice would not be able to recreate the initial message replacing alice for bob because she cannot sign as coderrr.

Please read the paper if you want details.

The goal here was just to summarize the paper to make it easier for people to get the gist of. I’m not arguing for or against the paper’s assumptions or conclusions.

Here is a bitcointalk forum discussion of how relevant this is to the actual Bitcoin network.

September 10, 2008

Get the physical location of wireless router from its MAC address (BSSID)

Filed under: network, ruby, security, slashdotted — Tags: , , , — coderrr @ 1:20 am

Shameless Plug: Protect yourself with public wifi security while connected to public hotspots with a VPN Service.

Update: Here’s a coverage map showing what areas they have data on.

A nice company called SkyHook Wireless has been war driving the country for years. Basically they’ve been paying people to ride around in cars and record the unique IDs (BSSID, aka MAC address) that your wireless routers broadcast. Doesn’t matter if your router has encryption on or not, its BSSID is still public and in their database (if they’ve driven past your house). They’ve then taken all this information and put it in a huge database. They’ve even made a nice little javascript API which given a BSSID will tell you its longitude and latitude. But it will only let you do this for yourself, only sending BSSIDs which you are in range of.

For their API to work it requires you to install a browser extension. Which contains, along with the extension source code (which is fully viewable, for Firefox at least), some compiled c++ code (loki.dll for windows). So what does the proprietary stuff do? It does the actual query to their API. And what does it send? It asks your wireless card to list all of the BSSIDs that you are in range of and sends those along with the signal strength of each.

So why can’t you just send any BSSID you want? Simple, because they don’t tell you how. The actual query is done inside of their compiled code, so it’s a secret and no one will ever figure it out. Well, only the people that try at least. After reverse engineering their code I did a google search on one of the unique-ish terms in the XML that is used as part of the API call and it seems there are others who know how to use this secret API of theirs.

So to keep things short. Here’s how to query their service to find the physical location of any wireless router whose BSSID you know.

Send an HTTPS POST request to with XML in the following format:

<?xml version='1.0'?>
<LocationRQ xmlns='' version='2.6' street-address-lookup='full'>
  <authentication version='2.0'>

You’ll receive back either this (success!):

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<LocationRS version="2.6" xmlns=""><location nap="1"><latitude>49.2422507</latitude><longitude>11.4624963</longitude><hpe>150</hpe></location></LocationRS>

or this (failure!):

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<LocationRS version="2.6" xmlns=""><error>Unable to locate location</error></LocationRS>

Here’s a dirty little ruby script which does the query based on a BSSID you pass in from the command line:

require 'net/https'

mac = ARGV.first.delete(':').upcase

req_body = %{
<?xml version='1.0'?>
<LocationRQ xmlns='' version='2.6' street-address-lookup='full'>
  <authentication version='2.0'>
}.gsub(/^\s+|[\r\n]/, '')

http ='', 443)
http.use_ssl = true

http.start do |h|
  resp = '/wps2/location', req_body, 'Content-Type' => 'text/xml'

  if resp.body =~ /<latitude>([^<]+).+<longitude>([^<]+)/
    puts "#$1, #$2"
    puts "not found"

getloc.rb aa:bb:cc:dd:ee:ff

Or here’s a one liner for UNIX thanks to George:

MYMAC=AABBCCDDEEFF && curl --header "Content-Type: text/xml" --data "<?xml version='1.0'?><LocationRQ xmlns='' version='2.6' street-address-lookup='full'><authentication version='2.0'><simple><username>beta</username><realm></realm></simple></authentication><access-point><mac>$MYMAC</mac><signal-strength>-50</signal-strength></access-point></LocationRQ>"

* note: This API is how the iPhone’s “Locate me” feature works

September 3, 2008

Google Chrome privacy worse than you think

Filed under: google, privacy, slashdotted — Tags: , , — coderrr @ 10:11 am

Shameless Plug: Anonymize your web traffic and private browsing habits. Browse anonymously with a VPN Service.

Update: Google has stated that they are working on a change to their system which will anonymize all data collected from their suggestion services (including Chrome) after 24 hours. This is exactly the sort of thing I was hoping for. Good job Google!
Update: Maybe Google’s new privacy policy isn’t good enough after all.

A friend of mine let me in on some info about Google’s secret Chrome project about 6 months ago but I didn’t get to actually try it till yesterday. I’m pretty impressed with some of their new innovative features like independent processes for tabs, compiled javascript, and the incognito mode.

But then I realized something huge. If you use Google Chrome, Google will know every URL you type into the location bar. More than that, they will know (almost) every partial URL you type into the location bar. More than that, they will know every word or phrase you type into the location bar, even if you type it and then delete it before pressing enter. More than that, all this information can be linked with your main Google account, because Google sends your cookie along with every automatic search it performs from the location bar. Chrome will use the cookie of whatever Google account you are currently logged into.

No other browser that I know of uses an automatic search/suggest feature in the location bar. The location bar is where you type the address of the site you want to navigate to. Firefox uses a suggest feature in the search bar. It makes sense to do it there. now has auto suggest on their homepage. It makes sense there too. Now it makes sense to also have it in the location bar in terms of a nice helpful feature. But in terms of privacy I think this is a new low. I think Google should, at the least, not be sending your cookie out with these searches. But even then they could be connected to you by IP.

Don’t believe me? Go download the Wireshark packet sniffer and do some tests for yourself.

Now to be fair it seems they don’t auto suggest once you’ve typed “http://&#8221; but who actually types that anymore? There are also some timing issues, if you type really quickly and hit enter the auto suggest may not be attempted.

I’m sure there’s a team of Google data mining engineers somewhere who are giddy as shit about having all this information once Chrome becomes more widespread.

Update: Google responded to a CNET story about this issue regarding their data retention policy:

A Google representative told CNET News that the company plans to store about 2 percent of that data–and plans to store it along with the Internet Protocol address of the computer that typed it.

Update: As Rushi Vishavadia points out, the data will be sent to whatever search engine you set in the options. Of course it will default to Google but if you were to change it to Yahoo or MSN they would be receiving this data instead of Google.

Here’s an example of what Chrome is sending to Google while I’m typing the URL into the location bar:

GET /complete/search?client=chrome&output=chrome&hl=en-US&q=ww HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=www HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=www.what HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=www.whatismyip.c HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US& HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US& HTTP/1.1

Here’s an example when I’m typing the search query “how to cheat on taxes” into the location bar:

GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+t HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+to HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+to+c HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+to+cheat+on+tax HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+to+cheat+on+taxe HTTP/1.1
GET /complete/search?client=chrome&output=chrome&hl=en-US&q=how+to+cheat+on+taxes HTTP/1.1

Even if I never pressed enter to submit the above search to Google, they would still have this data and be able to link it to my account.

I should point out this feature can be disabled by going to Options -> Manage -> Uncheck “Use a suggestion …”

June 28, 2008

Detecting SSH tunnels

Filed under: network, security, slashdotted — Tags: , , — coderrr @ 6:35 pm

Shameless Plug: Use a VPN Tunnel to secure and encrypt your P2P traffic.

Italian researchers have published a paper on the Detection of Encrypted Tunnels across Network Boundaries. I came across it in a google search because I’ve been thinking of writing a program which does something similar. It doesn’t seem like anyone else has picked up on this research yet so I thought I should mention it. Here is a link to the actual paper: pdf or scribd.

They claim their technique can differentiate between “normal” ssh or scp sessions and ssh sessions which are being used to tunnel traffic (through ssh’s port forwarding mechanism). This is accomplished through a naive Bayes classifier, which they first trained with “normal” ssh sessions. The two variables used to classify a session are the size of the packets and the difference in arrival time of two consecutive packets. With just these, they can classify with 99% accuracy whether an ssh session is a tunnel. They were also able to classify the actual protocol (P2P, POP, SMTP, HTTP) of the tunneled connection with close to 90% accuracy.

Although their research is quite interesting there are a few things which limit its practicality. They can only detect tunnels going through ssh servers which they control. This is because their detection mechanism can only handle a single authentication type whereas an ssh server can (and usually does) allow multiple (e.g. public-key or password). This requires admins of the server to limit the allowed authentication options to a single consistent choice. They also require the ssh server _and_ client to disable compression. Their technique will also falsely classify a second login attempt (after a failed login) as a tunnel and drop the connection. In their words: “However, this should not be a major problem: simply, if the user is entitled to connect, they will try again.”

So it seems the use of a tool like this would be limited to an extremely controlled environment where users are limited to a white-list set of network protocols (so that they can’t use a different tunneling mechanism, stunnel for example) and only allowed to ssh to servers under the control of the censoring party. In which case you would wonder why the admin wouldn’t just set the ssh servers’ AllowTcpForwarding option to false.

It sounds like this is just preliminary work so maybe their future research will solve all these problems. If perfected this technology could be used by ISPs to block or throttle even encrypted P2P traffic.

I’d also like to note that it would probably be easy to create a tunneling mechanism which thwarts their detection attempts. Knowing that they use packet size and inter packet intervals you could easily manipulate these to match whatever protocol type you wanted.
Update: This actually might not be that easy with P2P traffic since you’d need to mimic another protocol where there is a large amount of uploading going on at the same time as downloading. This is pretty hard to speculate on without actually trying it out. But if you could limit a bit torrent connection’s upload to 5% of the download and still get reasonable speed you might be able to mimic a tunneled HTTP connection.

While looking around one of the researchers web pages (Franceso Gringoli) I found a pretty cool Linux/OSX utility called sshgate. It allows you to transparently tunnel all your connections over ssh. This is great for programs which do not give you the option to use a socks server and which do not play nice with socksification. I haven’t tested it out so I’m not sure if it actually works.

Bookmark and Share

The Silver is the New Black Theme. Create a free website or blog at


Get every new post delivered to your Inbox.

Join 31 other followers