Posted on 1 Comment

Cloud Mining and Network Centralization Explained

This post is a follow up to my Bitcoin Mining 101 post where I covered mining basics. Here I’m going to talk about a few more topics related to mining, most of which have an impact on network centralization and scalability. Those of you who have no plans to start mining should still find this post relevant to the future of bitcoin.

Cloud Mining

CloudHashingIn part one I talked about pooled mining and how it arose as a response to the extreme variance of solo mining. A potentially even more convenient solution is cloud mining. Instead of purchasing and maintaining the hardware yourself, you can essentially outsource that responsibility to a cloud mining company. These firms will purchase and maintain the hardware themselves, sometimes fabricating it themselves as well, and sell you a portion of the hash rate. For example, CloudHashing.com (seen to the right) is currently selling 250 Gh/s (gigahashs per second) for $1,000. If you purchase the Gh/s from them you are entitled to any bitcoins earned with those Gh/s. According to CloudHashing the $1,000 contract earned .29 BTC in June or about $170.

If you extrapolate $170/mo out for 12 months you get a ROI on that contract of about 100%. Unfortunately, it isn’t that easy. If you recall from part one, the total hash rate in the network is climbing rapidly.

hashrate

What this means is that the return on your cloud mining contract is going to decline pretty sharply from month to month. So just like miners who operate their own hardware, you would need to forecast the network hashrate into the future to get an estimate of what kind of return you would get on your mining contract.

Pros and Cons

As I mentioned, a major benefit of going the cloud mining route is you don’t have to operate your own hardware. Not only does this mean that people who lack the technical skills can participate in mining but you don’t have to deal with the frustration and delays of trying to acquire hardware in a timely manner. Neither do you have to worry about permanent brain damage from heat stroke when you have your miners running in your bedroom in the summer (I’m half kidding).

Additionally, mining hardware isn’t very liquid. If you decide you want to get out of mining, you usually have to try to dump your used hardware on eBay or with a friend if you have any who are interested. Mining contracts, on the other hand, are typically easier to sell. Some cloud mining companies have set up their own markets for trading cloud mining contracts. That’s an extra benefit you don’t have if you operate the hardware yourself.

But, there are some downsides to cloud mining as well. In theory you should be able to earn more by operating the hardware yourself since a portion of your return isn’t going to pay a third party to operate the hardware for you. In practice, I don’t know if this is true. Typically, large mining firms find it easier to acquire hardware from suppliers in a timely manner compared to individuals with limited resources and connections. So, all other things equal, running the hardware yourself should be more profitable, but I’m not sure all other things are equal. Perhaps a good case study could shed some more light here.

Finally, cloud mining does create some concerns about network centralization. Remember, the primary security proposition of Bitcoin is that no one person or group should be able to control more than 50% of the network hashing power. If that happens, either by a single person/group acquiring that much processing power or by separate groups colluding with each other, they could prevent transactions from confirming, double spend bitcoins, crowd out all legitimate miners, etc. In other words, it would prevent the network from being useful and would undermine confidence in the currency.

In an ideal world there would be 50,000+ individual miners, each with only a tiny sliver of the total hashing power. The existence of cloud mining, however, introduces large firms with a sizable portion of the network hashrate. It has been reported, for example, that GHash.io owns about 10% of the hashing power in the network as a result of their cloud mining operation. Unlike pooled mining for which there are theoretical solutions to the problem of centralization, there really isn’t anything stopping cloud mining companies from amassing large amounts of hardware. If you get a few cloud mining companies the size of GHash.io, they could easily collude and take over the network.

I say all this to give you something to consider if you do get into cloud mining. It’s best to go with firms that don’t own a large share of the network hashrate.

Block Size Issues

I’m going to switch gears a little bit and talk about a hot topic of late ― block size and relay times. For a while now Gavin Andresen has been working on implementing floating transaction fees into the bitcoin protocol. As it stands, miners have discretion to decide which transactions they include in their blocks and which they don’t. This implies they can set their own policies regarding how low of a transaction fee they will accept. Up until this point, however, wallets have no idea what these miner policies are and just use a hard coded default transaction fee. What this floating fee code will do is scan the block chain see how long it’s taking transactions to make it into blocks at different fees and feed that information to the user who can than use that information to decide on a fee.

In theory, so long as the fee is higher than cost to process and store the transaction on disk, profit maximizing miners should always include it in their blocks. So transaction fees should basically be negligible. However, that isn’t what we are seeing. The following is a chart compiled by Gavin after running a node and recording estimates once per day:

transaction fees

Basically it shows that transaction fees are non-negligible. What’s going on is that miners are intentionally keeping the number transactions in their blocks below the total number of outstanding transaction, foregoing the transaction fees from those additional transactions. Why would they do this? Essentially, the problem stems from situations where two miners solve in block at approximately the same time. When this happens, which ever block propagates the network quicker and reaches more nodes is more likely to be accepted earning the miner the block reward (approximately $15,000 at the moment).

As it happens, blocks which contain a smaller number of transactions propagate quicker than blocks which contain more. Rather than risk losing $15,000 for an extra couple bits in transaction fees, miners just accept a small number of transactions with the largest fees and reject the rest. This creates artificial scarcity where none exists and drives up transactions fees, eliminating part of Bitcoin’s competitive advantage in the process.

So what’s the solution? There have been a lot of ideas floating around but most of them revolve around relaying a fixed size header instead of a full block of transactions and defining some other method for acquiring the transactions in the block. Gavin alluded to something along these lines in a tweet the other day:

All in all this is a fairly serious issue. Failure to fix it will ruin one of Bitcoin’s primary value propositions. But fixing is requires a pretty drastic change to the core protocol, something which has the potential to damaging if implemented incorrectly and which requires a near consensus to implement.

My hope is it gets fixed sooner rather than later.

Original content by Chris, copyleft, tips welcome // < ![CDATA[
// < ![CDATA[
//

Posted on 1 Comment

Bitcoin Mining 101

Whenever I introduce new people to Bitcoin I tend to get asked quite a few questions about mining. What is it? Can anyone mine Bitcoin? What do I have to do to get started mining? Etc. In the next couple blog posts I’m going to answer these questions and hopefully give a fairly comprehensive intro to Bitcoin mining. Even if you don’t plan on mining yourself, chances are you’ll still come away with a good understand of what makes Bitcoin tick. So stay tuned!

What The Heck Is Mining Anyway?

BkqH8SQCcAASCSm

I think part of the problem we have when introducing people to Bitcoin is that we have all these confusing words that don’t accurately describe what’s going on. “Mining” is one of them. Bitcoin mining is essentially transaction validation. When transactions are broadcast to the peer to peer network, someone (or some computer) needs to verify that the transaction is valid and record it the public transaction database (the blockchain). That is essentially what “miners” do ― process and verify transactions and record them in the blockchain. They are rewarded for their efforts with newly created bitcoins (more on this in a little bit), which explains the origins of the term “mining”.

The process of verifying transactions is actually very easy to do. It only takes a computer a fraction of a second. Adding new transactions to the blockchain, however, is intentionally designed to be much more difficult. I’ve gone into much more detail on the reasons for this in past blog posts. To recap, trying to get millions of Bitcoin uses around the world to agree on a single version of the transaction database is no easy task. In fact, it’s a bit of miracle that it happens at all. The secret here is something called “proof of work”. The Bitcoin protocol requires that those wishing to add additional blocks of transactions to the blockchain provide proof that they expended a scare resource, in this case processing power. In this sense miners sort of “vote” with their processing power. But since there is a very real opportunity cost to expending processing power, miners will only want to “vote” for the transaction history which is supported by the majority of other miners. To vote for an alternative transaction history is to waste the processing power and risk losing reward. It’s this opportunity cost that ends up driving the network towards a consensus in regards to the transaction history.

The “work” part here consists of running the block header including a random nonce through a cryptographic hash function (SHA-256 to be exact) and checking to see if the function’s output meets the requirements set forth by the protocol. In this case the output needs to be less than a certain difficulty target. To put it another way, the output needs to start with a minimum number of zeros. For example:

000000000000002e9067f1cf7252333f7aeb619c89d220985a70ac0e015248e0

If the output does not meet the difficulty requirement, the nonce is incremented and header is run through the function again. This is done over and over until one miner in the network finds a nonce that produces a valid output. Consider the following example: Suppose we want to find a nonce such that when concatenated with “Hello, world!” produces a hash output that starts with at least three zeros. We would start with a nonce of zero and keep incrementing until we get the output we’re looking for.

"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

In this example it took 4,251 tries to produce an output hash that starts with at least three zeros. This is basically how the proof of work in bitcoin works. Miners run the block header through the (double) SHA-256 hash function over and over, incrementing the nonce each attempt in hopes of producing a hash output that meets the difficult target. The difficulty is automatically re-calibrated by the protocol every two weeks to target to target a block interval of 10 minutes. That is, since the output of the hash function is random, it should take an average of 10 minutes for one miner in the network to solve the proof of work for any given block of transactions.

The miner who finds the valid block earns the block reward ― currently set at 25 bitcoins. The protocol halves the reward every four years according to the following schedule:

37-expansion

Megahashes, Gigahashes, and Terrahashes

Bitcoin Mining

Because the rate with which bitcoins are rewarded is regulated by the protocol, Bitcoin mining is essentially a zero-sum game. That is, more total processing power in the network does not generate more total bitcoins, it only reduces the reward per unit of processing power. This means that the faster you can perform the SHA-256 calculations, the greater percentage of the total block reward you will earn. We typically measure the speed of a mining rig in terms of the number of hash operations it can perform per second (h/s).

Back in the old days, circa 2009, Bitcoin was a Windows only software and most mining was done right on your CPU using the GUI. Fairly quickly people figured out that GPUs (graphics processing units) were more efficient at calculating hashes than CPUs. Those who switched to mining on GPUs saw their bitcoin earnings increase at the expense of those who stuck with CPUs. And thus a mining arms race was born that continues to this day.

After a brief period of FPGA mining, the first ASICs (application-specific integrated circuits) hit the market in early 2013. An ASIC is a custom built computer chip designed to do nothing but perform double SHA-256 calculations very fast. As more and more ASICs were brought online, the total hashrate in the network skyrocketed driving non-ASIC miners out of the market in the process.

hashrate

Today the total hash rate in the network is around 83 petahashes/sec. That’s 83,000,000,000,000,000 hash operations per second. Way more than top 500 supercomputers in the world can do combined.

Pooled Mining

Back in the early days all miners looked for blocks individually. Given that blocks are only created on average every ten minutes miners would frequently go days if not weeks without mining a block. When a block was found, the payoff would be fairly large (50 bitcoins originally, now 25), but the variance in returns was extremely high. The solution to the variance problem came in the form of pooled mining. Basically, miners would pool their resources together to find blocks faster and split the rewards according to how much work each miner contributed.

The technicalities work like this ― in addition to looking for valid blocks, miners also look for “shares”. The difficulty for finding a share is usually set by the pool operator well below the difficulty for finding a block.

For example, a valid block may need to start with 14 zeros, say. Whereas a valid share needs only 5, say.

Block: 000000000000002e9067f1cf7252333f7aeb619c89d220985a70ac0e015248e0
Share: 00000b3709b05939f04cf2e92f7d0897fc2596f9ad0b8a9ea855c7bfebaae892

Since the difficulty is much lower for shares, miners will find these much more frequently. Each share is submitted to the pool operator and when a block is found the reward is paid out to miners in proportion to the number of shares they submit.

Of course, pooled mining is not without significant controversy. As I already mentioned, in the early days miners looked for blocks individually. They maintained their own copy of the blockchain, and retained control of which transactions they include in blocks. With pooled mining, miners are essentially delegating those responsibilities to the pool operator. Today most miners don’t even have a copy of the blockchain nor do they have any control over which transactions make it into their blocks. This not only creates a worrisome degree of centralization but it gives pool operators an inordinate amount of power. For example, a pool operator controlling 30% of the network mining power can double spend his own transactions with a 30% success rate. Want to tilt the odds of a gambling site in your favor? That’s how you do it. Worse, if that pool operator colluded with another pool operated with, say, just over 20% hashing power, the two could double spend transactions with 100% success, among other things. Here’s the current hashrate distribution:

hashratedistribution

The saving grace is the fact that pool operators do not actually own or control the physical hardware. So the thinking is should a pool operator(s) turn malicious, miners would quickly abandon the pool limiting the damage. It seems every few months a mining pool gets close to 50% of the hashrate and the bitcoin community panics and directs their wrath at the pool operator. Public enemy number one these days is GHash.io. The cycle looks something like this:

AX4NSyK

Developers have created several tools to address the problem of mining centralization. First is the getblocktemplate mining protocol which allows miners to retain control over the blocks they create. Unfortunately miners and mining pools have shunned it in favor of the centralized stratum mining protocol. There is work planned for a getblocktemplate 2.0 which would be even more decentralized, but it remains to be seen whether miners will actually adopt it.

There’s also P2Pool, a peer-to-peer mining pool that was developed with grant money from the Bitcoin Foundation. Yet, it only manages a meager 1% of the network hashrate, likely because it’s much more complex than stratum. If you plan on mining bitcoin, you really should do the network a favor and at minimum pick a pool with a lesser hashrate or better yet use P2Pool.

I can speak for myself, I have a couple 330 Mh/s USB miners. The total miner power is negligible and cost far more to operate than they would ever generate mining. So every now and then when I leave the house I turn them on solo mining for the off chance they will mine a 25 BTC block. It’s kind of like playing the lottery. The odds certainly aren’t in your favor, but you can’t win if you don’t play. And it supports the network, so in that sense it’s worth it.

What do I need to start mining?

You’ll need to get an ASIC for one. Unfortunately it isn’t very easy to get one, at least not within a reasonable time frame. ASIC manufacturers are notorious for long production delays. Given that the mining difficulty has been increasing at a fast pace, it’s critical to get your hardware mining as soon as possible. The longer it takes for the hardware to be fabricated and delivered to you, the more money you are losing. What’s worse is manufactures tend to prioritize orders from large mining firms that purchase hardware in bunk. This puts individuals with limited resources at a competitive disadvantage.

If you do acquire an ASIC you’ll also need to install some software. BFGMiner and CGMiner are two of the most popular. Both are command line only and will likely be difficult to use for people who are not tech savvy. Butterfly Labs has a GUI wrapper (EasyMiner) for both CG and BFGMiner. Once everything is installed, you can usually start mining with a single command. For example:

bfgminer -o stratum+tcp://stratum.mining.eligius.st:3334 -O 1CBKzGN7TkcJ9YGCxfCCMsxjhSperRcyUX

Is it a good investment?

There are quite a few variables that determine whether an investment in mining hardware will be profitable or not:

  • The cost of the hardware (including shipping)
  • The shipping delay (it will take a while)
  • The cost of the electricity
  • The difficult rate
  • The current Bitcoin exchange rate
  • The expected future value of bitcoins

To figure out if you will earn a profit or loss on the mining hardware you need to estimate all these variables and come to your own conclusion about profitability. There are profit/loss calculators you can use as well. I will say this, however ― your hardware will almost certainly start depreciating the moment you plug it in. As other miners bring additional hardware online, and as the difficulty increases, your share of the mining reward will go down. Eventually, it will get to a point where you are spending more money on electricity to operate the hardware than you are earning in block rewards. At that point you will likely want to shut the hardware down. You could continue mining at a loss and speculate that the bitcoin price will increase to cover your losses, but that adds additional risk.

What this all means for you is that your hardware likely has an expiration date. When you first plug it in, that will be the most you ever earn. The profits will continue to decline until they turn negative. Typically you can expect to get about six months out of your hardware and that’s about it. If you’ve calculated correctly, you will have earned enough in Bitcoin to cover the cost of the hardware and earn a small return on your investment. If you didn’t, you’ll take a loss. If you earn a profit, you have to decide whether to take your profits and run, or reinvest some or all of it in more hardware.

A word of caution ― there have been people who continually reinvested their mining profits in more and more hardware, amassing a large hashrate in the process. It sounds impressive, yet as the price of Bitcoin climbed towards $1,000 they found themselves with zero actual bitcoin while everyone around them were counting their riches. So you have to find a good rate to reinvest.

A final point I want to make is relate to shipping delays when purchasing hardware. Delays can be the difference between earning a positive return on your investment or a loss. To illustrate how crucial timing is, let me tell you a little story. Back in early 2013 prior to ASICs hitting the market, I was considering dropping $2,500 dollars on a 50 Gh/s ASIC. At that point I did the math and calculated that if I was able to receive the hardware within the next week or two, I would earn some ridiculous amount of money. Somewhere around $150,000/month. Not bad for a $2,500 investment. The problem was I knew the order wouldn’t ship in two weeks, more like 5 or 6 months. So I was left to try to estimate the hashrate six months out and calculate my would-be profits. Naturally, forecasting the hashrate that far out was practically impossible, but if it skyrocketed during that period, I would take a loss on the hardware. So despite the promise of $150,000/month, I declined and just purchased bitcoins with the money. And good thing! The hashrate did, in fact, skyrocket. And the shipping delays were even worse than expected. People who ordered at that point ended up waiting 8 months or more. I almost certainly would have taken a loss. Instead I earned a big profit just by buying Bitcoin outright.

This still likely hold true today. At this point there is so much hashing power in the network that I suspect most miners are operating at a loss while speculating that they can recover that loss through future increases in the price of bitcoin. If you do decide to get into mining, you need to take that into consideration and adjust your expectations accordingly.

So that’s it for now. In the next post I’m going to cover some mining topics that weren’t covered in this post. Stay tuned.

Original content by Chris, copyleft, tips welcome

Posted on 2 Comments

Beginners’ Guide To Off-the-Record Messaging

This is a sequel to my earlier post Beginners’ Guide to PGP which was the first in a series of posts aimed at introducing new bitcoiners to various encryption technologies. In this post we’re going to teach you how to use Off-the-Record messaging (OTR).

So what is OTR? Like PGP, it’s a cryptographic protocol designed to provide strong encryption of your communications. However, it shouldn’t be considered a competitor or replacement for PGP, more like a welcomed complement. Where PGP is often used to encrypt emails, files, and authenticate messages with digital signatures, OTR is an encryption protocol for real time chat. And unlike PGP, which can be a little daunting to learn and use securely, OTR is quite easy to setup and use and provides a pretty good user experience.

Under The Hood

Before showing you how to use it, let’s take a look under the hood. If you recall from the last post, PGP uses public-key cryptography. That is, one key (a public key) is used to encrypt a message and a separate key (the private key) is used to decrypt it. Public Key Cryptography OTR, on the other hand, uses symmetric key cryptography where the same key is used to both encrypt and decrypt messages. Symmetric-key cyrptography

The first question we’d like to know is how is the encryption key communicated to both parties? After all, the whole reason you’re encrypting your communications is because your communication channel is insecure. You can’t exactly send your encryption key over Facebook messenger. To solve this problem OTR uses the Diffie-Hellman key exchange algorithm. In short, two parties are able to exchange secret keys in such a way that they can derive a shared AES (Advanced Encryption Standard) key that is impossible for an eavesdropper to decipher.  The following diagram conveys the general idea.

399px-Diffie-Hellman_Key_Exchange.svg

Of course real world Diffie-Hellman doesn’t use paint, but rather some complex math that relies on the difficulty of discrete logarithm problems.

The benefit of this protocol is that it provides both perfect forward secrecy as well as deniability. By perfect forward secrecy we mean that the compromise of any long lived keys would not allow an attacker to decrypt past messages, even if he’s in possession of the ciphertext. This is because the protocol uses new keys for each message.

And since OTR doesn’t use digital signatures, it’s impossible for someone to prove that your message wasn’t forged. Using proper authentication methods, you can make sure the message wasn’t forged, but no one else can.

Finally, just like with PGP, there are no known feasible attacks on any of the algorithms used in OTR ― Diffie-Helman, AES, SHA1. That doesn’t mean someone wont find one in the future, but for right now it’s solid.

How To Use It

OTR can be used over any internet chat protocol ― AIM, Google Talk, Yahoo Messenger,etc. I my experience people find it most convenient to use it with Facebook messenger. This way you can use it with all of your existing Facebook friends and you don’t need to create a whole new buddy list. So how do you do it? First thing you need to do is download a chat client that is OTR compatible.

I use Pidgin on Linux and ChatSecure on my Android. Pidgin is available on Linux, Windows, and OS X. Mac users can also use Adium although, having never used it, I can’t vouch for it. ChatSecure is available for both iPhone and Android and can be downloaded directly from iTunes or the Play store.

MK Lords_024
ChatSecure

To set up Pidgin with Facebook messenger is easy. Visit the facebook url below and click Pidgin at the bottom of the page. It will show you exactly how to setup pidgin.

https://www.facebook.com/sitetour/chat.php

Facebook/Pidgin

A similar process is used on ChatSecure. Before you can use OTR you must activate the OTR plugin. Pidgin comes packaged with the OTR plugin pre-installed, but by default it isn’t activated. To activate it just click Tools>>Plugins and place a check next to Off-the-Record Messaging.

That’s it! Easy. You’re now setup to chat securely with your Facebook friends. Of course, you have to convince them to setup OTR as well, but that isn’t terribly difficult to do. To start an encrypted chat just click the “Not private” button in the chat window and then “Start private conversation”. Assuming your partner also has OTR running, the software will automatically perform the OTR handshake and encrypt your messages. The cool part is when you go back into Facebook after an encrypted chat secession, this is what you see…

Encrypted Facebook Chat

Authentication

The final thing you need to do to guarantee a secure connection is to authenticate your communication partner. While you don’t technically have authenticate as OTR will do its thing regardless, failure to do so could potentially open you up to a man-in-the-middle attack. This is an attack where you end up performing the OTR “handshake” with an attacker instead of your communication partner. The attacker could eavesdrop on your communications while forwarding your communications to your partner ― making you think you’re chat secession is secure. There are two ways to authenticate and prevent this from happening.

  1. You can compare fingerprints with your partner. Just like PGP, you’re encryption keys have fingerprints that look like this:
    2674D6A0 0B1421B1 BFC42AEC C56F3719 672437D8

     

    Of course, you cannot compare these over OTR, that would defeat the point. You need to find some other communication channel such as a telephone, video chat, in person meeting, etc.

  2. To avoid the inconvenience of comparing fingerprints over a separate channel, OTR incorporates a socialist millionaire protocol which allows you present a challenge question to your partner and mathematically verify the answer without actually sending the answer over the internet.

For example, you might ask your partner, “What did you order to eat when we had lunch on Monday?” As long as you both know something about each other that the NSA spook listening in doesn’t, then you can use this method to authenticate your partner. Once you’ve authenticated someone, you never have to authenticate again so long as you don’t lose control of the encryption keys (like in a computer crash for example).

So that’s it! Pretty simple. Now that you know how to use OTR, there’s really no excuse for sending messages in the clear.

Original content by Chris, copyleft, tips welcome

Posted on 5 Comments

Reinventing Email: Update on the Dark Mail Project

I just got back from the 2014 New Hampshire Liberty Forum where I got to attend a number of great talks on privacy and security. One of the cooler parts for me was meeting Ladar Levison. Even though he wasn’t a speaker, he still took time out to speak with a number of us. For those who don’t know who Ladar is, he’s the founder of Lavabit, Edward Snowden’s email provider.

Lavabit made national headlines last year when it became the first technology firm to completely shut down rather than allow the NSA to spy on its customers. At Liberty Forum Ladar provided a little more insight into what the NSA wanted. Basically, they wanted his SSL private key so they could perform a man-in-the-middle attack on his servers. All traffic to the server would be intercepted by the NSA, downloaded, then forwarded along to the destination (with the potential for the NSA to manipulate data in the process). Of course this wouldn’t have just affected Edward Snowden, but all of Lavabit’s customers. Lavabit offered to comply with the order by giving them special access just to Snowden’s emails, but naturally that wasn’t good enough for the NSA as they wanted to spy on everyone. So Ladar made the heroic decision to shut down rather than allow his customer’s rights to be violated.

Now you can pretty much guarantee that if the NSA was demanding MITM access to Lavabit, they basically have that access for nearly all other services.

Last year Ladar and Lavabit announced a partnership with Silent Circle ― the Dark Mail Alliance. The goal of the Dark Mail project is to provide an end-to-end encrypted email protocol that not only encrypts the body of the message, but also the metadata. One of the problems with traditional encryption tools like PGP, is it can be relatively difficult for people who aren’t tech savvy to use. Studies have shown that about half of users make mistakes when using PGP, even after receiving instruction. Dark Mail doesn’t strive to be another encryption suit, but rather a new email protocol that encrypts messages by default without the user having to even think about it. It strives to be ‘Email 3.0’.

Ladar said he just hired a development team and intends start work on the project next week. He sounded a little frustrated with the Silent Circle team which has delayed release of the whitepaper, but he’s going to move forward with what he can in the meantime.

When it first launches, the Dark Mail protocol will be used by at least six different email providers, including Lavabit. You’ll still be able to communicate with non-Dark Mail email accounts, but it will put up a red banner telling you the message isn’t secure. Of course, getting every email provider to switch to this new protocol is going to be a huge challenge, but the hope is that consumer demand for secure email will drive adoption.

In my opinion this is one of the most exciting advancements in online privacy. I’m really looking forward to signing up for a Lavabit Dark Mail account.

Original content by Chris, copyleft, tips welcome

Posted on 11 Comments

MtGox Problems and Transaction Malleability

[Update below]

Watching the drama surround MtGox in recent days has been like watching a slow motion train wreck. It’s put a lot of strain on the community and has been causing the Bitcoin price to tank. If you’re not up to date on this story, basically MtGox has been experiencing severe Bitcoin withdraw issues with numerous customers claiming they never received their bitcoins. Apparently upwards of $38 million worth of bitcoin withdrawals have gone unfulfilled causing MtGox to freeze withdrawals altogether.

You can add this to the long list of problems MtGox has had over the last couple years. A trading platform that couldn’t handle high volume trades, operating without a license in the US and having a large amount of customer funds stolen by the US government, USD withdrawals taking months to clear, and strong suspicion it’s operating on fractional reserves.

Now this morning MtGox comes out and announces its problems aren’t its fault, but rather a bug in Bitcoin itself! News of this potentially catastrophic bug has sent the markets into a tizzy.

So what bug are they talking about exactly? It has to to do with something called transaction malleability. Now, this isn’t some kind of zero-day exploit. It has been known since at least 2011. Fixing it has never been high priority for the developers because, as we’ll see, it hasn’t been considered that big of a deal. Which is why it’s a bit odd that that MtGox would claim this is the source of their problems.

So what is this attack specifically? Basically it amounts to altering a transaction after it has been broadcast. A Bitcoin transaction has a number of parts:

version 01 00 00 00
input count 01
input previous output hash
(reversed)
48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81
previous output index 00 00 00 00
script length 8a
scriptSig 47 30 44 02 20 2c b2 65 bf 10 70 7b f4 93 46 c3 51 5d d3 d1 6f c4 54 61 8c 58 ec 0a 0f f4 48 a6 76 c5 4f f7 13 02 20 6c 66 24 d7 62 a1 fc ef 46 18 28 4e ad 8f 08 67 8a c0 5b 13 c8 42 35 f1 65 4e 6a d1 68 23 3e 82 01 41 04 14 e3 01 b2 32 8f 17 44 2c 0b 83 10 d7 87 bf 3d 8a 40 4c fb d0 70 4f 13 5b 6a d4 b2 d3 ee 75 13 10 f9 81 92 6e 53 a6 e8 c3 9b d7 d3 fe fd 57 6c 54 3c ce 49 3c ba c0 63 88 f2 65 1d 1a ac bf cd
sequence ff ff ff ff
output count 01
output value 62 64 01 00 00 00 00 00
script length 19
scriptPubKey 76 a9 14 c8 e9 09 96 c7 c6 08 0e e0 62 84 60 0c 68 4e d9 04 d1 4c 5c 88 ac
block lock time 00 00 00 00

The transaction is run through a hash function with the resulting output looking something like this:

81aefec8ce0fd59f5baf42096ba3e0e529dbef49d4dd3228e5f24b2acf3dd8f2

This hash serves as the transaction ID and can be referred to when referencing the transaction.

Transaction malleability makes it possible to alter the scriptSig field in the transaction in a way that does not invalidate the transaction, but does change the transaction ID.

This does NOT mean an attacker can forge a transaction. It doesn’t mean an attacker can swap out the receiving addresses or double spend bitcoins. If this attack is performed, the transaction still goes through as normal. The bitcoins still end up at the proper location. All it does is alter the transaction ID. To the sender it would look as if the transaction never confirmed, even though it did. (Note this affects all copy-and-paste altcoins as well.)

How is this affecting MtGox? Basically, MtGox logs the transaction ID for every withdrawal. They are claiming that someone is placing withdrawals then using transaction malleability to alter the transaction ID and make it look to MtGox like the withdrawal didn’t go through even though it did. Then, presumably, trying to get MtGox to reimburse them.

I should mention that this is a relatively difficult attack to pull off. An attacker would need to see to it that the altered transaction makes it into the next block and not the original transaction. Since miners accept the first transaction they receive as valid and since MtGox broadcasts the transaction to the network, it is significantly more likely the original transaction will be seen by miners first and make it into the next block.

The attacker would need to see the transaction before the vast majority of miners, then relay the altered transaction to a large number of miners and hope his transaction propagates quicker than the original. Not something your average person can do.

Now as MtGox mentions, if the altered transaction doesn’t make it into a block, the attacker can just redeposit the coins and try again.

So that’s what they claim is going on. However, from my armchair perspective I’m still a little skeptical. Let me give my reasons.

  1. Even though the transaction ID has been altered, it’s still relatively easy to tell that the transaction went through. Just look at the receiving address and check to see if it received any transactions for the same amount of bitcoins. If so, check to see if the input address matches MtGox’s address. If done correctly, transaction malleability isn’t a problem at all.
  2. AML/KYC regulations require MtGox to record the identity of all its customers. To use the exchange you have to provide a government issued ID. In other words, MtGox would know who was doing this attack. I suppose this person could plausibly claim ignorance, but would you try to scam a company using an account linked to your identity?
  3. I suppose an attacker could be doing this to other people’s withdrawals, maybe in an attempt to create chaos and drive down the price. But even here, people would still receive their bitcoins as requested. Remember we had widespread reports of people not receiving any bitcoins. It seems unlikely to me that people would complain like that if the withdrawal actually went through.

So my gut tells me there are other problems with MtGox that we still don’t know about. Transaction malleability could be a problem, but it’s an easy fix for them. Either way people need to understand that Bitcoin is not broken. These are much more MtGox problems than Bitcoin problems.

Here’s what core developer Pieter Wuille wrote this morning on the developer mailing list:

Hi all,

I was a bit surprised to see MtGox’s announcement. The malleability of
transactions was known for years already (see for example the wiki
article on it, https://en.bitcoin.it/wiki/Transaction_Malleability it,
or mails on this list from 2012 and 2013). I don’t consider it a very
big problem, but it does make it harder for infrastructure to interact
with Bitcoin. If we’d design Bitcoin today, I’m sure we would try to
avoid it altogether to make life easier for everyone.

But we can’t just change all infrastructure that exists today. We’re
slowly working towards making malleability harder (and hopefully
impossible someday), but this will take a long time. For example, 0.8
not supporting non-DER encoded signatures was a step in that direction
(and ironically, the trigger that caused MtGox’s initial problems
here). In any case, this will take years, and nobody should wait for
this.

There seem to be two more direct problems here.
* Wallets which deal badly with modified txids.
* Services that use the transaction id to detect unconfirming transactions.

The first is something that needs to be done correctly in software –
it just needs to be aware of malleability.

The second is something I was unaware of and would have advised
against. If you plan on reissuing a transaction because on old version
doesn’t confirm, make sure to make it a double spend of the first one
– so that not both can confirm.

I certainly don’t like press making this sound like a problem in the
Bitcoin protocol or clients. I think this is an issue that needs to be
solved at the layer above – the infrastructure building on the Bitcoin
system. Despite that, I do think that we (as a community, not just
developers) can benefit from defining a standard way to identify
transactions unambiguously.

UPDATE: Rick Falkvinge has provided a good summary of the problems:

Here’s the real problem: MtGox is running its own homebuilt bitcoin software, and has not cared to update and upgrade that software along with the developments of the bitcoin protocol. Recently, after a very long grace period, the bitcoin protocol tightened slightly in order to disallow unnecessary information in transaction records, and did this to fix the malleability problem that MtGox blamed.

So the problem of malleability remained at MtGox, while having been fixed in the rest of the world. This – the discrepancy itself – was the root cause of the problem, because it meant that MtGox started issuing invalid transaction records for bitcoin withdrawals. Obviously, they were rejected by the bitcoin network.[…]

What this means is that MtGox wasn’t the subject of some skilled hacking related to transaction malleability. Instead, bad code hygiene was causing MtGox to broadcast invalid transactions, which could trivially be corrected and re-broadcast, causing all these problems downstream.

Original content by Chris, copyleft, tips welcome

Posted on 2 Comments

Innovations that Enhance Bitcoin Anonymity

Articles written by both Bitcoin supporters and detractors frequently stress the fact that “Bitcoin is NOT anonymous”. Critics would like you to believe that if you use Bitcoin, your financial privacy will be totally compromised. Supporters often make a similar case to try to keep the regulators at bay. The reality, however, is that Bitcoin does provide a fairly high degree of privacy already and upcoming improvements should significantly increase the degree of anonymity. In this article I’ll provide an overview of where we are at present and talk about some up coming privacy enhancements.

Privacy Basics

As you likely know, all Bitcoin transactions are stored in a public ledger which anyone can view. It’s done like this because there simply isn’t any other way to prevent double spends without providing everyone with a copy of the transaction history. What this means is that someone can (potentially) parse this ledger and view all of your transactions. Of course, this tends to be relatively difficult since your identity isn’t recorded in the ledger, only your Bitcoin address. Someone looking through the ledger will only see that bitcoins were sent from one address to another:

17mJFJJcpsbEVM41QMy9gvooKJF4qJRyun ==10btc==> 1Ct9GnnCkTce65osEkXhNcq3ZArvzAjR1v

This is why Bitcoin is usually said to be pseudonymous rather than completely anonymous. However, if your identity is linked to your Bitcoin address, your privacy can be completely compromised. The ledger might as well read:

Alice ==10btc==> Bob

Given that AML/KYC regulations require exchanges like Mt.Gox or Coinbase to verify and record your identity, this gives the government a relatively convenient way of linking your identity to your address. As an imperfect workaround, you can generate a new Bitcoin address and send the bitcoins from the address linked to your identity to the new one that isn’t.

Alice ==10btc==> 1JLs7BDEfJREvGSQJUeVcBJpsiZrPeb1A1

Since Bitcoin addresses can be generated with trivial effort, you can do this as many times as you want. The new address will still be linked to the one with your identity in the blockchain, but this does give you a reasonable degree of plausible deniability. If someone were to question you about a transaction, you could plausibly claim that you sold those coins on LocalBitcoins and don’t own the address. Of course this wouldn’t prevent you from being labeled a “person of interest”, but it remains to be seen if that link would pass the “beyond a reasonable doubt” standard in court.

Address Reuse

Nevertheless, this problem can largely be mitigated by treating all Bitcoin addresses as one-time use addresses. One of the primary sources of privacy leaks is address reuse. The reasons here are two-fold:

1) Obviously, anyone who links your identity to your address can just visit blockchain.info and see your balance and transaction history. If you generate a new address for every transaction, it will be next to impossible to do this without physically compromising your wallet.

2) Even if you don’t reuse addresses personally, that fact that other people do compromises your privacy. Once identities are linked to Bitcoin addresses, it becomes trivial to link your transactions to identities through the blockchain.

WikileaksTo the right is a transaction graph for Wikileaks published in a 2011 research paper. As you can see, address resuse has negative externalitites that compromise the privacy of all users.

Now if everyone uses Bitcoin addresses only once, it becomes next to impossible to perform this type of network analysis. Consider an example: suppose Alice sends a few bitcoins to Bob, if Bob generated a new address just for this transaction, Alice doesn’t learn anything about his other addresses, only only the one she sent her funds to. When Bob sends those bitcoins to Charlie, Alice can see the bitcoins leaves Bob’s address for another, but assuming Charlie generated a fresh address for the transaction, Alice will have no idea who the bitcoins were sent to. If all Bitcoin addresses across the network spring into existence only at the moment of a transaction, and are never reused, this would make Bitcoin pretty close to anonymous.

I say pretty close because there are still some scenarios where your privacy could still be compromised. Imagine a situation where Alice receives a payment from Eve, sends the same outputs to Bob and Bob sends the same outputs back to Eve. Here Eve would be able to determine that Alice transacted with Bob. While that certainly counts as a privacy leak, situations like this tend to be extremely low probability events and wouldn’t compromise all of your transactions.

This is how Satoshi originally conceived Bitcoin to operate. Version 0.1 contained a pay-to-IP-address feature where the receiving client provided the sender with a fresh address for each transaction. Unfortunately this feature didn’t catch on and people started reusing addresses.

So despite the potential privacy gains people continue to reuse addresses. The question is why? I think there are a couple reasons. First, it’s cumbersome to manage a wallet with hundreds of Bitcoin addresses. You typically have to backup your wallet after every 100 wallet operations or else risk losing some bitcoins if you have to recover your wallet from a backup. And having a wallet with hundreds of addresses isn’t nearly as easy to back up to a piece of paper as is a single address.

Second, it’s not always possible to provide a new address for each transaction. Think of the static tip addresses that many of us post on our websites or those used by charities for donations. Fortunately there are improvements that should change our default behavior with our wallets and move people away from the practice of reusing addresses.

Deterministic Wallets

The old method of generating Bitcoin addresses was to generate each one separately from a random private key. All of the private keys would be stored in the wallet.dat file. For the reasons mentioned above managing this type of wallet is a pain in the ass.

A deterministic wallet takes advantage of the pseudorandom properties of cryptographic hash functions to generate an unlimited number of new bitcoin addresses from a single random seed. So rather than having to backup a cumbersome wallet.dat file with hundreds of addresses, you only need to securely store this seed. Every one of your Bitcoin addresses can be reconstructed from this seed at any time. So now it doesn’t take any more effort to secure the keys for a wallet with hundreds of addresses than it does to secure the key to a single address.

For those who are fans of paper wallets, there’s nothing stopping you from printing the seed to piece of paper just like you currently do with a private key.

WalletSeed

Some members of the community are in the process of developing a standard (BIP 0039) for creating a mnemonic code for the seed that looks like this:

royal despair cigarette rich huge wet pretty waist silently fail afraid passion

This has largely already been implemented in Electrum and Bitcoinj.

Also, wallets are moving away from displaying the addresses in the user interface and instead will simply handle all these addresses behind the scenes. The user doesn’t need to know she has multiple addresses in her wallet. The UI will simply display the balance and transaction history and when the user places a transaction it will automatically select an address in the wallet from which to send the funds. In other words, deterministic wallets remove the need for users to handle their addresses. This not only improves the user experience, but also moves people away from the practice of address reuse.

The Payment Protocol

Sometime in the next month or two the core developers will release Bitcoin-QT version 0.9 which will contain a new payment protocol. The goal of this protocol is to increase the security of transactions and improve the user experience. Presently, the merchant typically displays its Bitcoin address in web browser and the user copies and pastes it into his wallet. There are several problems with this practice. First, transmitting the address over the internet is relatively insecure. We’ve been lucky so far that we haven’t heard of attackers intercepting Bitcoin addresses and replacing them with their own before they reach the payer, but that certainly can happen. Secondly, alphanumeric addresses just aren’t very user friendly, especially for beginners.

The new payment protocol solves these problems. When a user goes to pay a merchant, he will be presented with a link to download a signed payment request (presumably this link will be presented to mobile wallets as a QR code). The user clicks the link and his wallet automatically downloads and loads the payment request from the merchant. The request will show the actual name of the merchant (as opposed to the Bitcoin address), the total, and a description of what the payment is for. The payment request will be signed with an authenticated X.509 certificate which will prevent an attacker from forging payment requests.

Most importantly, the default behavior of the protocol will be to generate a new address for each payment request (handled behind the scenes). This will serve to nudge people away from the practice of address reuse. As the protocol becomes ubiquitous, very few people will continue to reuse addresses.

Stealth Addresses

The payment protocol covers nearly all situations where two people can communicate in real time. It doesn’t, however, allow a user to pay someone who is offline, or who wishes post a static address on a website the way Bitcoin addresses currently allow.

The final pieces of the puzzle are “Stealth Addresses”, first discussed on the development mailing list. A stealth address allows a user to post a static address linked to his identity, but receive payments to completely separate Bitcoin addresses. Here’s how it works…

The user generates a new stealth keypair:

Secret: c8edfa93b0475d617de98643673ddbd3f25b08a98261a2b3f913ea29990ef6f6
Address: SxjHZmrj1GrtuyW8dLmtYbNsLTEUGCQzpbk6iFRHEiBiZ5Z8Nq8EVt

The sender combines the recipient’s stealth address with a random nonce and a little elliptic curve magic to generate a Bitcoin address for which only the recipient can generate the corresponding private key.

Nonce: 03f3f8509a9ac713d269670119862416f377428fa1b40119fa418c3f24a610b11f
Address: 1vTNCd9NtWS77aPsfGWMeqNP1jsfbGQZ4

The sender broadcasts a transaction to this new address and includes the nonce as an extra output. The recipient can scan the blockchain for transactions containing a nonce, check if they belong to him, and recover the private key for the Bitcoin address:

Address: 1vTNCd9NtWS77aPsfGWMeqNP1jsfbGQZ4
Private key: 5JDUsvi6bGL5M3Wk2qvgrEHvp3proSRStHakfwtsdMfauXekqR4

So in other words, stealth addresses will allow you to post a static address on a website and have each payment sent to different Bitcoin addresses which you have the keys to. Not only does this eliminate the need for address reuse, but it also makes it impossible for someone to look up your balance and transaction history on blockchain.info.

In the future it’s likely that stealth addresses will be combined with a distributed identity system such that you wont even need to type someone’s stealth address into the client to make a payment, only their real name. The corresponding stealth address will be downloaded from a blockchain and imported into your address book.

The only kinks that have yet to be worked out are making stealth addresses work with the lightweight clients used in mobile wallets. Adam Back, Peter Todd and Jeremy Spilman have been putting in a lot of work to come up with a workable solution.

Conclusion

Thanks to these innovations it seems we’re on the cusp of winning the war on address reuse. In the near future it’s likely that users wont even know what a Bitcoin address is as their wallets will just handle everything behind the scenes. This will go a long way towards making Bitcoin the anonymous currency that we all want it to be.

To get the rest of the way there we’ll need to further develop new protocols like Coinjoin, Zerocoin, and Homomorphic Encrypted Value. Until then, we can still enjoy the high degree of privacy afforded to us by the current protocol.

Original content by Chris, copyleft, tips welcome

Posted on 24 Comments

Bitcoin vs. The NSA’s Quantum Computer

Yesterday we learned from new Snowden leaks that the NSA is working to build a quantum computer. The Washington Post broke the story with the rather sensationalist headline, NSA seeks to build quantum computer that could crack most types of encryption.

Naturally, this raised much concern among the new Bitcoiners on Reddit and Facebook. The reality, however, is there wasn’t much disclosed that people didn’t already know or expect. We’ve known that the NSA has openly sponsored quantum computing projects in the past. The fact that it has an in-house project called Penetrating Hard Targets is new, but not really unexpected. We learned this project has a $79.7 million budget, but quite frankly that isn’t that much. And as The Post notes, the documents don’t reveal how far along they are in their research and “It seems improbable that the NSA could be that far ahead of the open world without anybody knowing it.”

Nevertheless, this seems like a good time to discuss the implications of quantum computing with respect to the future of Bitcoin.

Let’s start with a little primer for those who are unfamiliar with quantum computing. Today’s computers encode information into bits — binary digits, either “0″ or “1″. These bits are usually stored on your computer’s hard disk by changing the polarity of magnetization on a tiny section of a magnetic disk, or stored in RAM or flash memory represented by two different levels of charge in a capacitor. Strings of bits can be combined to produce data that is readable by humans. For example, 01000001 represents the letter A in the extended ASCII table. Any calculations that need to be performed with the bits are done one at a time.

PhotonQuantum computers, on the other hand, use the various states of quantum particles to represent quantum bits (qubits). For example, a photon spinning vertically could represent a 1, while a photon spinning horizontally could represent a 0. But photons can also exist in a rather weird state called superposition. That is, while they can spin vertically, horizontally, and diagonally, they can also spin in all those directions at the same time. Don’t ask me how that’s possible, it’s the bizarro world of quantum mechanics.

What this means for practical purposes is while a traditional computer can perform only one calculation at a time, a quantum computer could theoretically perform millions of calculations all at once, improving computing performance by leaps and bounds.

Now when journalists write things like, “In room-size metal boxes ­secure against electromagnetic leaks, the National Security Agency is racing to build a computer that could break nearly every kind of encryption used to protect banking, medical, business and government records around the world”, it naturally makes people think it’s the end of cryptography as we know it. But that isn’t the case.

Let’s consider the type attack most people think of when hear of quantum computers―a brute force attack. This is where you just keep checking different keys until you eventually find the right one. Given enough time, you could brute force any encryption key. The problem is it would take billions or trillions of years for a modern computer to brute force a long encryption key. But surely quantum computers could do this right? This is from Bruce Schneier’s 1996 book, Applied Cryptography:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.

But that’s just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be unfeasible until computers are built from something other than matter and occupy something other than space.

To recap, if you could harness all the energy from a supernova and channel it into an ideal computer, you still couldn’t brute force a typical encryption key. Needless to say, if you are going to break commercial encryption algorithms you’re going to have to attack the underlying math.

Today, most public-key encryption algorithms rely on either the difficulty of integer factorization (RSA) or the difficulty of discrete logarithm problems (DSA/El Gamal, and Elliptic Curve Cryptography). In 1994, mathematician Peter Shor demonstrated an efficient quantum algorithm for factoring and calculating discrete logarithms that would break public-key encryption when used with a quantum computer. This wouldn’t break all types of cryptography, however. Traditional symmetric-key cryptography and cryptographic hash functions would still be well out of range of quantum search algorithms.

Impact on Bitcoin

Bitcoin uses several cryptographic algorithms―The Elliptic Curve Digital Signature Algorithm (ECDSA) for signing transactions and the hash functions SHA-256 and RIPEMD160. If the NSA succeeds in developing a cryptologically useful quantum computer, ECDSA would fall while SHA-256 and RIPEMD160 would remain secure.

The good news is that ECDSA should be relatively easy to swap out if/when it becomes compromised. It would be much worse if SHA-256 were to go down. If you’re not in tune to the mechanics of Bitcoin, SHA-256 is used in Bitcoin mining. At the moment, billions of dollars have been spent on custom computer chips that do nothing but perform SHA-256 calculations. If SHA-256 were to go down, those custom chips would turn into expensive paperweights. If that happened suddenly (as opposed to allowing for a smooth transition to another hash function), it would be pretty catastrophic. The security in bitcoin relies on the fact that it would be too difficult and expensive for an attacker to command 51% of the processing power in the network. A sudden switch to another hash function would significantly compromise security and likely cause the price to tank. But as I mentioned, Bitcoiners can rest easy because SHA-256 isn’t threatened by quantum computers (although that doesn’t mean someone won’t find a feasible attack in the future).

Back to ECDSA. This algorithm generates a public/private key pair. In Bitcoin, you keep the private key secret and use it sign your transactions, proving to the network that you own the bitcoins associated with a particular bitcoin address. The network verifies your signature by using the corresponding public key. A functioning quantum computer would allow the NSA to derive anyone’s private key from their public key. So do this mean that the NSA would be able to steal everyone’s bitcoins? Not exactly.

Here’s the thing, in Bitcoin your public key isn’t (initially) made public. While you share your Bitcoin address with others so that they can send you bitcoins, your Bitcoin address is only a hash of your public key, not the public key itself. What does that mean in English? A hash function is a one-way cryptographic function that takes an input and turns it into a cryptographic output. By one-way I mean that you can’t derive the input from the output. It’s kind of like encrypting something then losing the key. To demonstrate, let’s calculate the RIPEMD160 hash of “Hello World”.

Hello World ==> a830d7beb04eb7549ce990fb7dc962e499a27230

A Bitcoin address is calculated by running your public key through several hash functions as follows:

Bitcoin AddressAll of that is a complicated way of saying that while an attacker with a quantum computer could derive the private key from the public key, he couldn’t derive the public key from the Bitcoin address since the public key was run through multiple quantum-resistant one-way hash functions.

However, you do have to broadcast your public key to the network to make a transaction, otherwise there is no way to verify your signature. What this implies is that in the face of an NSA quantum computer all Bitcoin addresses would have to be considered one-time use addresses. Whenever you make a transaction you would have to send any excess bitcoin to a newly generated address as “change”. If you didn’t remove the entire balance from your address, the NSA could steal the remainder. While this is inconvenient, it would buy the developers enough time to swap out ECDSA for a quantum-resistant digital signature scheme.

Post-Quantum Digital Signatures

This section is going to be a little technical but hopefully not too difficult for beginners to follow. There are several different types of post-quantum public-key encryption systems: lattice-based, code-based, multivariate-quadratic, and hash-based. As I already mentioned, cryptographic hash functions are presumed to be quantum-resistant. Given that, it should be possible to build a replacement digital signature scheme for ECDSA using only hash functions. Let’s take a look at these hash-based systems since they are easy to understand and the hash functions they’re based on are already widely used.

Lamport One-Time Signature Scheme (LOTSS)

To begin, we’re going to want to use a hash function with at least a 160-bit output to provide adequate security. RIPEMD160 or SHA-1 should work. To generate the public/private key pair, we’ll start by generating 160 pairs of random numbers (320 numbers total). This set of random numbers will serve as the private key.

Pair# Private Key
1 e9e515b332cf1ce01299497e9e94b7df353ff022
ce56dcfdb7038e6ab0b37c383dbfda8cb45d60ea
2 811f71c5cf7639a40df7b9b187bf768016791cf8
1094b13455a133d2d11898cfa30916e12be3e0ab
159 bc6a1eb98148850dd2b32ae632005f5472c06a70
c10f4ac3d645d891d9b5dc0fa0b7294ad14ac3df
160 585801c9da7ce0d562f375338b456ba9f10be3f6
3c3363ed7273f1ef9c1aed3fc5a7433002b668f8

To generate the public key we’ll take the RIPEMD160 hash of each of the 320 random numbers. (Note: I’m going to have to cut the numbers in half to fit them in this table)

Pair# Private Key Public Key
1 e9e515b332cf1ce01299
ce56dcfdb7038e6ab0b3
d7c3e127380fbbbe37b9
4ddf29fb200aa0fd90b1
2 811f71c5cf7639a40df7
1094b13455a133d2d118
f84a8e5a0dce682e48c5
4a88310f694329b9ab97
159 bc6a1eb98148850dd2b3
c10f4ac3d645d891d9b5
7d5c0e19c4dc9077be6c
ffbbe97612e581f073b6
160 585801c9da7ce0d562f3
3c3363ed7273f1ef9c1a
38ed36c30ee72c95c598
a546f885e8210c61767d

Now to sign a message with a Lamport signature we’ll first create a message digest by hashing the message with RIPEMD160 (in Bitcoin we would hash the transaction) then converting the output to binary. We’ll once again use “Hello World” as an example.

Hello World ==> a830d7beb04eb7549ce990fb7dc962e499a27230 ==> 1010100000110000110101111011111010110000010011101011011101010100100111001110100110010000111110110111110111001001011000101110010010011001101000100111001000110000

Next, we’ll match up each binary digit with each pair in our private key. If the bit is 0 we will add the first number in the pair to our signature, if it is 1 we’ll add the second.

Pair# Digest Private Key Signature
1 1 e9e515b332cf1ce01299
ce56dcfdb7038e6ab0b3
ce56dcfdb7038e6ab0b3
2 0 811f71c5cf7639a40df7
1094b13455a133d2d118
811f71c5cf7639a40df7
159 0 bc6a1eb98148850dd2b3
c10f4ac3d645d891d9b5
bc6a1eb98148850dd2b3
160 0 585801c9da7ce0d562f3
3c3363ed7273f1ef9c1a
585801c9da7ce0d562f3

Finally to verify the signature is valid, you’ll first create a message digest using the same process as above. Then hash each of the 160 numbers in the signature with RIPEMD160. Finally, check to make sure these hashes match the hashes in the public key that correspond with the message digest.

Pair# Hash of Signature Digest Public Key
1 4ddf29fb200aa0fd90b1 1 d7c3e127380fbbbe37b9
4ddf29fb200aa0fd90b1
2 f84a8e5a0dce682e48c5 0 f84a8e5a0dce682e48c5
4a88310f694329b9ab97
159 7d5c0e19c4dc9077be6c 0 7d5c0e19c4dc9077be6c
ffbbe97612e581f073b6
160 38ed36c30ee72c95c598 0 38ed36c30ee72c95c598
a546f885e8210c61767d

So there you have it, a quantum-resistant digital signature scheme using only hash functions. Only the person in possession of the 320 random numbers in the private key could have generated a signature that hashes to the public key when compared to the digest. However, while his scheme does in fact work, it isn’t without problems. First, as the name suggests, LOTSS signatures can only be used once. The reason for this is because you are essentially releasing half of your private key with each signature. If you were to sign multiple messages, your private key would be completely compromised. If this were used in Bitcoin, you still could only use each Bitcoin address once.

Equally problematic, the key sizes and signatures are ridiculously large. The private and public keys are 6,400 bytes compared to 32 and 64 for the ECDSA private and public keys. And the signature is 3,200 bytes compared to 71-73 bytes. Bitcoin already has issues with scalability, increasing the key and signature sizes by that much would make the problems much worse.

The Lamport private key can be dramatically reduced in size by generating the random numbers from a single random seed. To do this you would just take RIPEMD160(seed + n) where n starts at 1 and gets incremented to 320. Unfortunately, the size of the private key isn’t so much the problem as is the size of the public key and signature. There is another one-time signature scheme called Winternitz signatures that has the potential to reduce key size but at the cost of hash operations. Fortunately, we aren’t done yet.

Merkle-Signature Scheme (MSS)

The Merkle Signature Scheme combines the one-time signature scheme (either Lamport or Winternitz) with a Merkle tree (also called a hash tree). This allows us to use one public key to sign many messages without worrying about compromising security. Let’s see how this works.

We’ll start by generating a number of Lamport key pairs. The number we’ll generate will be equal to the number of signatures we want to get out of a single public key. Let’s just say eight as an example. Next we’ll calculate a Merkle tree using each of the eight Lamport public keys. To do this, the public keys are paired together, hashed, then the hashes are concatenated together and hashed again. This process is repeated until something looking like an NCAA Tournament bracket is formed.

Merkle Public Key

The hash at the very top of the tree (the Merkle root) is the Merkle public key. This massively reduces the public key size from 6,400 bytes in the Lamport signature to only 20 bytes, the length of a single RIPEMD160 hash.

To calculate a signature, you select one of your Lamport key pairs and sign the message digest just like before. This time, the signature will be the Lamport signature plus each one of leafs in the Merkle tree leading from the public key to the root.

Merkle Signature

In the above diagram the signature would be:

sig′||H(Y[i=2])||A[0]||auth[0]||A[1]||auth[1]||A[2]||auth[2]||A[3]

To verify the Merkle signature one would just verify the Lamport signature, then check to make sure the leafs hash to the Merkle public key. If so, the signature is valid.

There are several advantages of the MSS over LOTSS. First, the public and private keys are reduced to 20 bytes from 6,400 bytes. Also, you can create multiple signatures per public key. But there is still a major draw back. The more messages you want to sign with your public key, the larger the Merkle tree needs to be. The larger the tree, the larger the signature. Eventually the signature starts to become impractically large, especially for use in Bitcoin. This leads us to the final post-quantum signature schemes we’ll discuss.

CMSS And GMSS

Post Quantum CryptographyMSS has been known for over 30 years and has remained essentially unscathed despite extensive cryptanalysis. However, most of the improvements to it have come in the last five years or so. In my brief survey of the literature, it seems a couple signature schemes by Buchmann, Dahmen, Klintsevich, et. al., are the most promising of the lot. These are the Improve Merkle Signature Scheme (CMSS) and Generalized Merkle Signature Scheme (GMSS) (Links to the academic papers can be found here and here). Two of the cryptographers behind this signature scheme are authors of a textbook on post-quantum cryptography.

Both CMSS and GMSS offer substantially improved signature capacity with reasonable signature lengths and verification times. GMSS in particular offers virtually unlimited signature capacity at 280 signatures but with slower performance in others areas compared to CMSS. They accomplishes this by breaking the system up into separate Merkle trees of 2n leafs. A signature from the root tree is used to sign the public key of the tree below it which signs the tree below it and so on.

Generalized Merkle Signature Scheme

So it seems to me that either of these signature schemes would be a serious candidate to replace Bitcoin’s ECDSA in a post-quantum world. But why not just go ahead and implement it now and rather than wait until the NSA springs a surprise on us? Let’s do a little comparison and take a look at the time (t) and memory (m) requirements for each. CMSS variants have signature capacities of 220, 230, and 240 while GMSS has signature capacities of 240 and 280. I would assume that 240 if not 230 would be plenty for Bitcoin as I can’t imagine someone would make more than a billion or trillion transactions from a single address. Also, GMSS can be optimized for faster verification times but at the expense of a 25% larger signature.

mPrivKey mPubKey mSig tKeygen tSign tVerify
ECDSA 32
bytes
64 bytes 71-73 bytes 9.6 ms 100 ms 8.53 ms
CMSS20 1900 bytes 46 bytes 2128 bytes 4.1 sec 12.5 ms 2.0 ms
CMSS30 2788 bytes 46 bytes 2328 bytes 2 mins 17.0 ms 2.0 ms
CMSS40 3668 bytes 46 bytes 2528 bytes 62.3 mins 21.7 ms 2.0 ms
GMSS40 1640 bytes 20 bytes 1860 bytes 723 mins 26.0 ms 19.6 ms
GMSS40′ 1680 bytes 20 bytes 2340 bytes 390 mins 10.7 ms 10.7 ms

So from the table we can see that CMSS and GMSS actually perform better than ECDSA in public key size and signature time. However, in the critical variable that will affect scalability, signature size, they don’t perform nearly as well. Verification time for CMSS is actually better than ECDSA which would actually improve scalability and the optimized variant of GMSS is relatively close, but signature size for both would definitely be an issue. Consider some very rough estimates: the average transactions size is currently about 500 bytes, either CMSS or GMSS would push it up over 4000 bytes. That means you could be looking at an increase in the size of the block chain of upwards of 700%. The block chain is currently at 12.7 gigabytes. Had Bitcoin employed either of these signature schemes from the beginning, it would be over 100 gigabytes right now. Signature and key size isn’t a problem that is unique to hash-based signature schemes either, most of the others are in the same ballpark.

Also, note the insane keygen time for GMSS. If you left your computer running for 24 straight hours you would have only generated 3 bitcoin address and that’s using the optimized variant with larger signatures! I suspect, however, that an ASIC hardware wallet would significantly improve that performance. Keygen for CMSS isn’t that bad.

So in other words, Bitcoin can’t adopt one of these signature schemes at the moment if we want to scale beyond present capacity. However, by the time quantum computers become viable, Moore’s law will likely have brought the cost of storage and processing power down to the point where CMSS, GMSS or one of the other types of post-quantum signature schemes could easily be merged into Bitcoin. Until then, let’s not lose any sleep over Penetrating Hard Targets.

Original content by Chris, copyleft, tips welcome

Posted on 16 Comments

Beginners’ Guide To PGP

If you are new to Bitcoin it’s likely you’ve heard some terms thrown around by Bitcoiners that you have no idea what they mean―PGP, Tor, VPN, OTR, etc. In most cases these are referring to various technologies that people use to protect their data and communications.

This is the first installment of what will likely be a series of articles aimed at introducing new Bitcoiners to these and other technologies that you can use to enhance your privacy and keep sensitive information away from the prying eyes of governments and data thieves.

We’re going to start off this series by introducing you to PGP, which is by far the most widely used encryption software available and a critical component to online privacy. Whether you’re purchasing drugs from Silk Road or just sending emails to friends and family, it’s something with which even casual internet users should familiarize themselves.

What is PGP?

PGP stands for Pretty Good Privacy. At it’s core, it is an internet standard (called OpenPGP) used for data encryption and digital signatures. Software that employs this standard is available in both a free, open source version produced by the Free Software Foundation called the GNU Privacy Guard (or GPG for short) as well as a low-cost commercial version.

Let’s take a moment to understand some of the basics of how it works. In conventional encryption, a secret key is used to transform plaintext (the unencrypted data) into unreadable ciphertext. The same key is also used to decrypt the ciphertext and reveal the plaintext. While this process works well for encrypting data stored on your hard drive, it has its drawbacks for use in communication. For one, you need to somehow communicate the secret key to the other party. But how to do this securely? After all, the reason you are using encryption is because you don’t believe your communication channel is secure. You could meet in person and exchange the secret key offline, but that isn’t very convenient. Protocols have been developed to allow for secure exchange of keys across insecure communication channels, but they tend to work better for real-time chat than, say, sending encrypted emails.

PGP makes use of public-key encryption. One key (a public key) is used to encrypt the data and a separate key (the private key) is used to decrypt it.

Public Key Cryptography

As a new user, you will generate a new public-private key pair. Just like the names suggest, you’ll share your public key with others so that they can send you encrypted messages or files, while keeping your private key secret so that you can decrypt the data. The process by which the key pair is generated makes it impossible (given current technology and knowledge of mathematics) for an attacker to derive your private key from the public key.

Use Cases

The most obvious use case for this type of encryption is email. Anyone who has your public key can send you encrypted emails which only you can view. Likewise, you can send encrypted emails to your contacts by first downloading their public keys. In a future post we’ll provide a more thorough tutorial demonstrating how to set up an email client to work with PGP. What you need to keep in mind, however, is only the body of the email will be encrypted. The subject and metadata (to, from, cc, and timestamp) will still be visible to anyone snooping on your emails.

You aren’t limited to just encrypting emails either. Buyers at anonymous marketplaces like Silk Road frequently download their merchant’s public key and use it to encrypt their shipping address so that only the merchant view it. Edward Snowden persuaded journalist Glenn Greenwald to set up PGP prior to leaking the top secret classified documents that revealed the depths of the NSA’s spying operation. You can encrypt whole folders and files with your own public key to protect them from attackers who may gain access to your hard drive. In other words, PGP can be used in just about every conceivable case where strong encryption is needed.

Digital Signatures

Another feature of public-key cryptography is it allows for the creation of something called digital signatures. Much like your real life signature, a digital signature can be used to authenticate data but with the added benefit of being completely unforgeable (again given the current state of cryptography).

A digital signature is created by a mathematical algorithm which combines your private key with data you wish to “sign”. The validity of the signature can by verified by anyone simply by checking it with your public key.

Digital Signature

In the above diagram you see that the plaintext is run through a hash function to produce a message digest which is then signed with your private key. What this process ensures is that a signed document cannot be altered without invalidating the signature, allowing people to not only check the document’s authenticity but also the integrity of the data. Just to give an example, suppose you sign a 10,000 word document. If someone were change even a single punctuation in that document, the signature would show as invalid. To see why digital signatures are useful let’s consider a few examples:

Returning to Edward Snowden, suppose the NSA had intercepted the classified documents before they reached Glenn Greenwald. The NSA could have removed the sensitive data, replaced it with disinformation, then forwarded it along to Greenwald. The reason this didn’t happen is because Snowden signed the data with his private key before sending it along. This allowed Greenwald to use Snowden’s public key to verify the files were unaltered. If the NSA tried to switch out some information, the signature would have shown as invalid.

Digital signatures are also extremely useful in verifying the integrity of software. A great example here would be Bitcoin wallets. Given the security implications, you want to be able to trust that the wallet you download is legitimate and wont leak information that would allow someone to steal your bitcoins. While all Bitcoin wallets are open source, unless you check and compile the source code yourself, you will most likely download a pre-compiled version that could contain malicious lines of code. Software developers will typically sign the software and provide a link to download the public key used for signing. With Bitcoin-Qt, lead developer Gavin Andresen signs new versions with his PGP key. Simply by checking the signature with his public key you can guarantee you’ve downloaded a legitimate copy.

How Secure Is It?

If all of this is new to you, you’re likely wondering how secure is the encryption used in PGP. Can we really trust it to protect us from from the NSA and its $52.9 billion black budget? All I can really say is that the cryptographic algorithms used in PGP are all part of the public domain have been heavily vetted by the community of experts. At this point in time there are no feasible attacks known to the general public or academia. It’s certainly possible that the NSA has access to highly advanced math that isn’t publicly known, but even there the best attacks typically don’t reveal the plaintext, rather they just make the keys slightly easier to brute force. The fact that the NSA has pressured Google, Microsoft, Apple etc. into giving them backdoors into their systems seems to be prima facie evidence that they can’t break commercial cryptographic algorithms.

Getting Started

The first thing you need to do to get started is download and install GPG. If you use the Ubuntu operating system you’re in luck, you already have it. It can be found in the apps menu as “Passwords and Keys”.

Windows users can download Gpg4win here.

And Mac users should download the GPG Suite for OS X from here.

Ubuntu

Ubuntu

Windows

Windows

OS X

OS X

In each of these operating systems you can access GPG as well as a number of advanced options from the command line, but as a new user, you’re better off learning to use the GUI for now.

Generating A New Certificate

In PGP a “certificate” is essentially a public key with extra data attached to help others verify that the key really belongs to you. In practice this is usually your name, email address and one or more digital signatures from others (more on that later).

Depending on your operating system, you’ll generate a new certificate by clicking “New”, “New Certificate”, or “New PGP Key”.

At minimum you will have to enter your name, email address, and a strong password that you will use for decrypting and signing data. In the advanced options menu you can select your encryption algorithm (RSA, DSA/ElGamal), key size (in bits), and an expiration date if you want your certificate to expire. The defaults here should suffice for our purposes. The differences are technical and unlikely to affect your overall security (just don’t reduce to the key size).

Once this process is complete you will have generated a new certificate and private key. You can click on “export” to save your public key to a .asc file for distributing to others, or you can copy the text of the key block and share it with people that way. A typical public key block will look like this:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: PGP Universal 2.9.1 (Build 347)

mQMuBFG3x4URCACZ/c7PjmPwOy2qIyKAYRftIT7YurxmZ/wQEwkyLJ4R+A2mFAvw
EfdVjghAKwnXxqeZO9WyAEofqIX5ewXD9J4H6THaWNlDeNwnIUhbVsSEgT6iwGEG
arXvkrMyy+U5KA0x2dcsYRKAPMM1db+4zSQkWTWzufLU7lcKi3gU3pNTxSA0DjCn
wfJQspiyWchSfgZ59+fKaGZJVSElrS2i2ok5mK3ywCXRWvnAC/VxA3N6T4jvkX/+
1gS/oUgdocP31TeV0L20JH9QgmFYC3jMbErAATo2x9Y8g4NofdvSnntbZk9Giycc
cgOWsa8aFtTjvcBp8hkCl3dK5xTZiY0gLSaDAQCXSHI7zw4LiNFfCV+PbO9BEqDA
i4JFV/qX7TgfBNX7nwf/fEFu18V16lVCsRzeuhMsHHzAQ7PZJfdfhyOubq0fnjkk
2RdcleosnP22zP5LoRs1fvIDdL3wnkg1ZUwfICP0HWRzRYcVBaIv9HcqSVBWriJj
uscni5QtX3fIU2wqSyP90wquWPkO7jObT0hWihhWPFXiFA6996i/rTZiJH+eFPSW
afxVlRAqH4kaUBen5fSMbBSsfc+GkuuQH7gIYQC2k88soPLuFZGsibDwBqvdUqFG
S39ifNf/2MUx8DrM8bbIPPwiuTelAFVPu7GGzyzAF3yhk/Cdd/YmWlwrwAd4Psev
WpXNSApzSgh/HhY3wVdj9skItQBISXJSVkMD4DLvhwgAh/Ur5JEgtx5dYGpU/nEr
LGEDUgPeBnewReA8wurAnYeOHGVSu84kXceO2tJvnbLn5y1L0dML/u3+S9pDXOfR
1TR9QxWd3QIBUY68lfa+DiXHSVcfrTPz3q+CHMLj7917hfATWwRTemccp6n8al68
tfGXih9t+lAwuq4KuRk0NkGEKrqeRU3sdGVLdIZ8IteikyYgWcZTYG7oxcj7qpif
ixl0DsI1HXfXQrFVnjOyQuiS8z06+ZuC/8dgi7UBpUkgQLZYosE0fUAdeiAVPGv0
LanXwHRQPDlmBiorge1c1jpbna2K9EyQ1Jbkyn6nkg8OaetO9brLBMk916mn6mQD
ebQfQ2hyaXMgUGFjaWEgPGN0cGFjaWFAZ21haWwuY29tPoh6BBMRCAAiBQJRt8eF
AhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAKCRC4lW2/7nwQXJ/dAP42O7se
mHDqZnxl4Slrf8AxgCI0DowpBcNxWRM8hNHS2QD/TkbCvy4QNq2QNrP26m183eJM
y6PNCncuwsB5TdoLgYqJASIEEAECAAwFAlKqHEQFAwASdQAACgkQlxC4m8pXrXyE
oAf+JusFcRHVGXDYOlRLwQYUJt9q3czp4cinwdheR24VUZVoE9pibogJcc2Oh4aS
5cpMg3EbmuoyVeLunxp01qpFDfVnfGJ3ZpdPDPlFu6Wy1iM7rVafcSR7CxI+oGRH
DKH0fZLhKKffujevM0Y7lFA80wjItq5Ewqy2UBxI6Vtdzo/ouAJ+EPmJsDOjclwe
Ayx4d/0g1kzf7DIGjUs6loV74zMqruPSPHGC6zFSz6jdA4xkzrlSV5U44TAkTz+1
I65j6I+doTcCmkzv4V8NU9wQ5LblE/flfTVCpnHNH4z4jAN2N8MyGNjAnbd2q752
yG3t651VmyOxa+XPffZ+F06GMbkCDQRRt8eFEAgAg+tZGxFVO3eeEn7R3KBCNCzL
DH3AwxcQs52k6ZbPzfyS59HTbvz1vkNNE/aoSb6HKZ95t3jaSBqbYIs8G3cXqN7h
kc/WJpYGeyKEokELg6Fr5vdaPxQakf63q2Ly+hCFCAorsc2iR50xVFB1befMFPWn
sptPIsel1P47wpRd2HmEwE+vGA90HcYUfdAA7eGCxZeRl8wc0DHbgAb+iKa1bmAY
vMO8FDTBAV9aayLL5qHxCGhR3VHRQi0Pq8P2nYjwwA+eF4M7gTXrB3L8Cf/mTXKi
rEF36kAAKegMmlPBH8/bLsWg7loJcxbPll4qhuJM7ErFF+hpmWbvYUqksFMjrwAE
Cwf7B63AelE+pT1qOFITFQPV30kvbQbIMz70yAurUBDRTRQ4L45DnUvZurS0Uojr
nczueK6sHufdsKdI0DKxG2REOz9hZ64+NoZRzB+cYCt0g93M3Wtg3zt6x1q8MwEj
uFcaO0gTKlh1fKSg7cV+VYm0nMo7/kOgupVxtcy65te6EM6KAtRCugqBeY/FxKXN
G4tps+KbzwmDq5G5lAZOLH3kVmSJxOHdTr/jwPlHnq8J+AYlXANEJMmbG3s6Eaf2
/du8FAy4025UUPZdLsJBM3HKoIqR7lsl2T9cCB9Un4fXlF8axb7PojRO6Y68dfSU
to3UsZXERO4NtVI0IT0uhLXh+IhhBBgRCAAJBQJRt8eFAhsMAAoJELiVbb/ufBBc
QjgA/j1J7nN42zDMJxoAKQDvp+H3dErZVY7hJ8qHeGVbExWGAP97G/jWhl6FEg7M
2vOMWRC5GQUM8TU1YkCeAuhsxSj3ew==
=dgnf
-----END PGP PUBLIC KEY BLOCK-----

Key Servers

You might want to consider uploading your public key to a key server such as the MIT Key Server or PGP Global Directory. These are searchable directories from which other people can download your public key without first asking you for it. This functionality comes in especially handy when using email. Some email clients can be configured to search the key servers for the PGP keys of your contacts or anyone who has sent you an encrypted email and import them automatically.

Just keep in mind that once you upload a key to a server, you typically can’t remove it. It’s probably a good idea to play around with PGP first, get used to it, then once you’ve created your permanent key, upload it. That way you don’t litter the key server with multiple keys bearing your name.

Importing Keys

In order to encrypt files to send to others, you will first need to import their public key into PGP. You can do this by downloading the .asc file containing their public key (either directly from others or from a key server), clicking “Import” or “Import Certificate”, and selecting the file. In Linux you can import a key simply by double clicking the .asc file. In Windows you have the option to copy the public key block and import it directly from the clipboard.

The software will typically let you view, edit and sign the public keys on your keyring. More on signing other people’s keys later.

Encrypting Data

You have two options for encrypting data in PGP ― you can encrypt a plain text message from the clipboard or encrypt whole files. Let’s start with encrypting plain text messages. The first thing you need to do is pull up your plain text editor (Notepad in Windows, GNU Emacs works well for this in Linux). You’ll have to forgive me for not being familiar with OS X, but I assume you can encrypt from the clipboard in that operating system (though I’m not positive).

Type whatever message you want and copy it to the clipboard. In Windows, you’ll need to right click on the Kleopatra tray icon and click Clipboard>>Encrypt. The software will prompt you do select a public key from your keyring with which to encrypt the message. The encrypted ciphertext will replace the unencrypted plaintext in your clipboard.

Kleopatra

 

In Emacs you’ll need to highlight the text, click Options>>Encryption/Decryption>>Encrypt Region. Or you can simply save the file to disk and right click and click encrypt.

GNU Emacs

Right Click/Encrypt

The resulting encrypted message will look like this:


-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.14 (GNU/Linux)

jA0EAwMCNUyTD6Yu1QtgyemPt3ysidtpK5AXDobS2mB5+ym7/zNqMe4u/fli9pPV
PakBAwNtRCE45qIFUpCj3Pjh3jRoPVmiQOb8n5PuhipuIP4v6ANCboWnCUam7NGd
VHuU2OLX36QWOoPI5Ewl9xto+3iqjlclTaiRlHo0JHU8EOv75BpjahzKhDCV2lMQ
q9QOHBESsU9xhk/t7gnT2EfhxzPHTb2N7fkPRFqItMU949hSvaYtN3AA80qxjkic
jpEbftLI1brvEK2WpyMPDt+YPnIvJ2mHfsmB41VNlr14BS5zpfWTEDjkTJALRWVj
MRARwU8/iE/hh9FMkYb8mB2cmJh6TgqpYF45qtacdKOKVqQBToPwS0dFf5Pw25Qx
jaRKTzfoP9mhD1nkHuNP79zhj9+uTMwRp00d117CuopnTeaTMQTYJeHNpsX79Jx3
EF6QQjrw38UNz2IZGplKHFKT39laI7NywviI7LmfJYHMoIFhdz97Woad1MCMPq/G
qqlA/QRrheMz90NG9OQRtc6q2hNCsQUI7kRV7kTrgPCrzKepLwZ3EBcSea8vyQcH
f43blJP1VucaTf9jvGPX1qgisOFHBYcZKv1+1I4sRIFcSWpKr3VeCr76bq+vMk1D
7+rT8SaYs0efFkfF/Y6+yOoporP0HsxVxAIUZ7zPXIH2UxtGfcfcu/pWxNQ1WrM5
dwWFasQaXg==
=tfo5
-----END PGP MESSAGE-----

Some things to keep in mind, once you encrypt something with someone else’s public key, you can’t decrypt it. You can, however, encrypt a message using multiple public keys and the message can be decrypted with any of the corresponding private keys. So you could encrypt a message with someone else’s public key and your public key, then you can both decrypt it at a later date. Also, if you encrypt data using only your public key, it basically works like symmetric key encryption in that only you will be able to decrypt it.

To encrypt an entire file select “Sign/Encrypt File” from the menu and select the file you want to encrypt. Just like before, you’ll need to select a public key(s) from your keyring with which to encrypt the file.

Decrypting Data

To decrypt either a message or a file, you need to do all of the above in reverse. Just this time use the decypt option from the menu. Here you will be prompted to enter your password for your private key that you created along with your key pair. This is what prevents an attacker from stealing your private key and decrypting messages intended for you.

Keep in mind, if you are decrypting data on your normal computer, you could be running the risk that malware could copy and upload the data after you’ve decrypted it. This might be an acceptable risk for everyday communications, but if you’re dealing with extremely sensitive data you should probably transfer the encrypted data to a secure viewing station prior to decryption.

Any air gapped computer (one permanently disconnected from the internet) would work for this purpose. Or you could boot into a Linux live system (such as Tails) from a USB stick to isolate your work environment from preexisting malware.

Signing Data

Just like with encryption you can either sign a message from your clipboard or sign whole files. The process is just as straightforward as before except this time you will select “sign” rather than “encrypt”. Here you will again be prompted for your password. The resulting output will look like this:


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

This is an example of a PGP signed message.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)

iF4EAREIAAYFAlK5pacACgkQuJVtv+58EFxiXgD/QGwQVCZMAlE7fL6V1Kbv4Ogq
Sa9VTEw+s9mWwiBInp4A/3guc2PvZb8iIdrCyWGwIMJIOQS8OuhWfjtN3CBhOSA1
=S+B+
-----END PGP SIGNATURE-----

 

Notice that the message is at the top under the header, while the signature is at the bottom. If you chose to sign an entire file, the software will generate a separate .sig signature file that you will need to send along with the original file.

Also keep in mind that encrypting and signing are not mutually exclusive. You can opt to both encrypt and sign data to protect the message from eavesdroppers and allow the recipient to verify the message came from you.

Verifying Signatures

To verify a signature on a signed message or file you will obviously have to first download and import the corresponding public key. Just like with decryption, you can either verify the signed message from your clipboard or by selecting the file. If you’re verifying a signed file, you’ll likely be prompted to select both the file and the detached signature (.sig) file.

If you’ve done it right you will see a response that looks something like this:

Good signature from B8956DBFEE7C105C Chris Pacia  (trust ultimate) created at 2013-11-16T12:05:37-0500 using DSA

When verifying the signature on software, the developer will typically provide a link to a .sig file for you to download. However, when releasing software on multiple platforms, it’s not uncommon for a developer to provide a single signed message containing the hashes of the files rather than a separate signature for each version. Consider the following release notes for Bitcoin-QT:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

73495de53d1a30676884961e39ff46c3851ff770eeaa767331d065ff0ce8dd0c  bitcoin-0.8.6-linux.tar.gz
ec85816e6cd034230ec5dc83c105334aa91bfa38fd959ba3d1d3bd5d4df3208b  bitcoin-0.8.6-macosx.dmg
baac30350a721472bd34e811f16bd68c4e4672cfb47df73aee12376b2adcae8d  bitcoin-0.8.6-win32-setup.exe
582fcb973a29e1a6e44ddc6602400e77fc85b53f6f54a1105d22d84d992e3c83  bitcoin-0.8.6-win32.zip
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.20 (Darwin)

iQIcBAEBCAAGBQJSpjKpAAoJEBt7+0V79uISEvgP/2T2Pt1wO2WMaK3DL4D/uFq6
xcuhCjrV1FHt1UoYTdohl112dO3q6qsakguBxvaGMe80KCJS85JT7B2Sbs/goyYT
2WxkEv+ttQFVnB32MlFeGYrPt9I7xmNQqYoQMGsV+VeCfqSDElxVpPCLDYFbBLUk
lkHa4LTkXsGI351iIEjUB4jXSKeJvWQQ6HdxKOIUaxA6AZX8qGKuGbSYUMNy/pBi
lqZNOTWtFjRkPR+qhhjjpx9J9A9l4dFYvH6lJDS9mj2jOUCTtg3hKwYg3KvSOtjl
6Mkm6qkJtf0SxJpx3tQjH4rav7G1WY0Y546X2+uF9BuFKvhDVY74fe8pAh+ASF18
lq4pbpg6pElk94CESPEDxIIB1wgozKBidLSzCtKfqgTDPQtFDny1nA3Km+FGQX5Y
HATPB0EeuB5juJs7rHpO/OhweI1cORPPfhaTiA6Cf6Tioyl+FX/ZmVXclUUYEF1M
fXS8JsAIZxIdDgjeo6xTwI2llN5Gs3JmypGM0dggNslMUEeCX/O5uciyoZ6y+TUZ
TZLRVY4WsS0FpsA07UuYuasi1B1WzGm8BW4Akt3XO7awVwyHSUfePS02qGdUwfDS
sDzf5SoBphnBUcRiVoHL1lhn8bfW0henksL6YUJIfY4w5q5S9vM/5uk+vxghWGRk
K6o6VP8xT/1yRhWbR0Yp
=DYos
-----END PGP SIGNATURE-----

So what is going on here is that the installation files for Linux, OS X, and Windows (.exe and .zip) were run through the SHA-256 hash function and the outputs were then signed. To verify the integrity of the Bitcoin-QT for Windows (say), you would first verify the signature on this message then hash the bitcoin-0.8.6-win32-setup.exe file with SHA-256. The output should look like this:

baac30350a721472bd34e811f16bd68c4e4672cfb47df73aee12376b2adcae8d

Then just compare this output with the hash in the signed release notes. If the two match, you know you have a good file.

You may be asking, how in the world do I calculate a hash function? Some operating systems will let you do this from the terminal. For example in Linux you can just type:

user@users-desktop:~$ sha256sum [FILE]
user@users-desktop:~$ sha1sum [FILE]
user@users-desktop:~$ md5sum [FILE]

Otherwise, you could easily use an online hash calculator.

Key Management

Finally, we should probably talk a little about key management. One of the downsides to PGP is susceptibility to something called a man-in-the-middle attack. This attack works like this: Let’s say you want to securely communicate with someone using PGP. The first thing you would do is download their public key. However, it may be possible for an attacker to intercept your internet communications before they reach the server containing the public key. The attacker could send you one of his own public keys and make you think it’s the public key of your communication partner. Not knowing any better, you would encrypt your messages with the attacker’s public key allowing him view all your communications. Even worse, the attacker could re-encrypt the message with the correct public key and forward it along it the destination. Neither you nor your communication partner would know the message was intercepted.

Man-In-The-Middle Attack

Obviously, a critical part of security in PGP is the ability to trust that the public key belongs to its purported owner. While complete trust is difficult to achieve, there are a few methods you can use to increase your level of trust.

    1. Meet in person. If someone physically hands you their public key, then obviously this eliminates the problem of trust. Of course, this is very inefficient.
    2. Verify the fingerprint. Each PGP certificate has a unique fingerprint which is calculated as the hash of the certificate represented in hexadecimal. It looks like this:
      0150 2502 DD3A 928D CE52 8CB9 B895 6DBF EE7C 105C

      If you can get the key’s owner to verify the fingerprint, possibly by reading it over the phone, then you can be fairly confident in the validity of the certificate. Obviously, finding an appropriate communication channel to verify the fingerprint can be tricky.

    3. Download the key from multiple IP addresses/devices/servers A MITM attack is difficult to pull off as it is. It becomes much harder if the attacker has to watch the communications of multiple IP addresses and servers. To this end you can increase the trust in the public key by downloading it from multiple locations (home, work, the library, Starbucks, over Tor, etc), from multiple devices, and from multiple servers. Gather up all the keys and check to make sure they are all they same. If so, you can be reasonably confident the key is valid. It would be extremely difficult to pull off a MITM attack after all that.
    4. Web of trust. In PGP you have the ability to use your private key to sign the someone else’s public key. This creates the opportunity to introduce a sort of six degrees of separation trust model. Let’s say you’ve downloaded Charlie’s public key but don’t know if you can trust it. Charlie’s key is signed by Bob, who you also don’t trust, and Bob’s key is signed by Alice, who you do trust. Because you trust Alice, this gives you chain of trust that goes all the way to Charlie, allowing you to trust Charlie’s key. The only downside to web of trust is that it can be difficult to get started and make enough connections to link you to all the keys you wish to download.

So that’s it for now. While we could go much more in depth, what we covered should be enough to get you started using PGP. Just remember, given the revelations about U.S. government spying and depths to which it is sinking to destroy your online privacy, there is really no excuse for not familiarizing yourself with PGP and using it on a regular basis. In a future installment of the series we’ll talk about how to set up an email client to automatically encrypt and decrypt your emails. Until then, stay safe and feel free to email me with questions.

Part two: Beginners’ Guide To Off-the-Record Messaging

Original content by Chris, copyleft, tips welcome

Posted on 9 Comments

Bitcoin, the Greater Fool’s Gold

In a recent blog post, Bob Murphy succinctly asks a question that seems to get at the heart of the disagreements between Bitcoin proponents, and Bitcoin haters like me:

There are people claiming that Bitcoin’s non-monetary price is zero, and hence if it’s trading for anything at all, it is in a bubble. But by that logic, gold’s non-monetary price might be (say) $250, and so if it’s trading right now for $1,250, then $1,000 of that is clearly just due to a self-fulfilling prophecy, where people are willing to pay $1,250 for gold because they think that’s how much (at least) it will be worth in the future. If something were to shatter that expectation, then the price of gold would plummet back down to its fundamental value of $250

He similarly quotes a hypothetical proponent’s position, which I believe captures my point of view quite fairly. I would recommend reading his whole post, it’s not very long. I’ve touched on this particular argument before, but I think I should expound on it, given the opportunity to respond directly to Dr. Murphy’s careful layout of the proponent’s position. Murphy, at least for the purposes of this article, accepts the premise that bitcoin has no value as a consumer good, whereas gold has some. I will counter-argue with that premise as well. He also makes some of the same distinctions in categories of valuation that I like to make: consumption, store of value, and speculation. However, I think that Greater Fool speculation is a separate entity. But let’s start with the beginning.

He gives $250 as a hypothetical market value for gold in a pure consumer market today, and of course $0 for bitcoin. For simplicity, let’s suppose that this hypothetical $250 market price is absent any major lapses in knowledge on the part of vendors, so we can safely take as a given that there is no bubble in this market. In reality, a price of $250 doesn’t mean that all consumers are willing to buy at exactly $250, there will be a range of prices at which potential consumers are willing to buy. Suppose this range is between $100 and $1000. We arrive at the price of $250 because anybody only willing to spend $249 is out-bid by people willing to spend $250 or more. The number of people willing to pay $250 or more roughly matches the amount vendors are willing to sell at the same price (basic supply and demand).

Supposing then, that people start deciding to buy gold as a store of value. Many of them are willing to spend more than $250 an ounce, thus they outbid many of the potential consumers in the market, bringing the price up to, say, $300. In buying for a store of value, they expect the price to stay roughly the same, at worst. As such they are speculating on price stability (as Mises said, all action is speculative). Is this a bubble? Not necessarily, because we said that there are potential consumers going up all the way to the $1000 range. It might be a bubble, since these holders may be overestimating the demand at those higher prices, but not necessarily, because they might be right. In contrast, if the same is done with bitcoin (again, taking the $0 pure-consumer market assumption) they can’t possibly be right, so it must be a bubble.

Okay, so what brings gold all the way to $1200 today? It is probably the result of speculation, but the sort of longer-term speculation on effects of inflation of the dollar, in which the gold is priced. Is this a bubble? Again, not necessarily. If the feared outcome of inflation comes to fruition, consumer goods will skyrocket in price, and gold is a consumer good. The hypothetical pure-consumer market, may rise, say, to $1100. If we then account for the store-of-value speculators of that future date, those who speculate on price stability, perhaps the stable price post-inflation will be $1500. Now, the long-term speculators could be wrong that impending inflationary effects will increase the consumer + store-of-value price of gold to that degree, in which case this mentality and the resulting price would be a bubble. But in doing the same with bitcoin, taking the opening assumptions of no consumer market, they are surely wrong.

I’d like to note here that store-of-value speculation on price stability, alone, can increase the price of gold, but it cannot (without being a bubble) rise above the hypothetical price that the highest bidding consumer is willing to pay. That is, this cannot raise it above $1000 in the initial example. But speculating on price increase, as in the case of inflation speculators, the price can be well above today’s entire consumer market, without (necessarily) being a bubble. That said, this is not even the case today; gold-tipped RCA cables are still on the market. I like to point to this example because even jewelry can be a convenient store of value, whereas it seems implausible for RCA cables.

Finally, none of what I’ve described thus far is actually what I would consider “Greater Fool” speculation. All of the above forms of speculation, as I have described them, are based on the expectation, correct or not, of certain consumer prices at a certain point in the future. Greater Fool speculation, on the other hand, is speculation based on the assumption that another trader will always be around to keep the price afloat, in spite of the fact that there is no expectation of consumers. I don’t believe that it is correct to describe every price above the consumer price of gold to be a Greater Fool price. I’d gladly concede that some of gold’s price is due to it, maybe a whole lot of it, like in any market. But to say that everything holding gold so high above the hypothetical pure consumer market price is Greater Fool pricing is incorrect. A lot of speculation is quite legitimate, and as such, it is not necessarily a bubble (again, there could still be bad data). However if we assume that bitcoin has no potential for a consumer market, we must conclude that it is purely a bubble, either via bad data by those who believe bitcoin does have a consumer market, or of the Greater Fool variety for those who do not.

Original content by Dan, CC0 (attribution appreciated), tips welcome