On the interwebs, no one knows you're Satoshi Nakamoto

Several major news outlets have recently announced that Australian Craig Wright has come forward as the person behind the pseudonym Satoshi Nakamoto, inventor of the Bitcoin protocols.

I have no particular reason to doubt this, but more on that in a bit.  First, an update on Bitcoin.

In previous posts I've expressed skepticism that Bitcoin, considered as a currency, would come to supplant reserve currencies such as the Dollar, Pound or Yen.  I think that case is made by now.  The main points are

• The current Bitcoin money supply is a fraction of a percent of the dollar money supply
• The dollar value of Bitcoins actually spent in a day is an even smaller percentage of the number of dollars spent in a day
• While several major retailers have announced that you can "pay in Bitcoin", this generally means they're partnering with someone who converts Bitcoin to and from a reserve currency.
• The merchants themselves quote prices in a reserve currency and take payments in that currency.
• Bitcoin's exchange rate with reserve currencies is much, much more volatile than reserve currencies' exchange rates with each other
• As a result, there is little evidence that anyone holds on to Bitcoin except as a speculation
• All of this has been the case for years now

That doesn't mean that the whole exercise has been a waste of time or, for that matter, that a few people haven't made large piles of (reserve currency) money from it.  Bitcoin may not be a viable currency, but it's interesting considered as a payment method.  In particular, the "blockchain" used to provide a public hard-to-forge record of transactions, has seen interest from a number of players, including existing banks.

It's worth noting that the blockchain doesn't provide the anonymity that Bitcoin is rightly or wrongly known for.  After all, by design it's a public record.  But before we get to that, let's do a quick review of public key cryptography with the caveat that, although I've studied cryptography with some care, I'm far from a cryptography expert.

Public key cryptography uses a publicly known algorithm and two keys: a public key that everyone can see and a private key that only you should see.  In the usual version, RSA, the two keys are "inverses" of each other.  If you take a message and use one key to apply the algorithm, you get gibberish.  If you apply the other key to the result, you get the original message back.  This means you can use the system in two ways:

• Encryption:  If I run a message through the algorithm using your public key then (as far as we know), only you (or at least, only someone in possession of your private key) can turn the resulting gibberish back into the original message.
• Signing: If you run a message through the algorithm with your private key to get gibberish, then anyone with the public key can recover the original message but (as far as we know) only you (or at least, only someone in possession of your private key) could have produced the gibberish that you sent out.

Typically these are used together, along with a cryptographic hash function that can take any message and boil it down to a largish number -- a few hundred digits -- in such a way that (as far as we know), no one could have produced a fake message that boils down to that same number.  Putting it all together, if I want to send you a message securely, and assure you that I actually wrote that message:

• I use the hash function to boil my message down to a largish number, called the hash value, that (as far as we know) could only have been produced from my message.
• I use my private key to turn that number into a different largish number, that (as far as we know) only I (or ... you get the picture) could have produced and (as far as we know) could only have been produced from my message.  I add this "signature" to the bottom of my message.
• Finally, I use your public key to turn the whole thing¹ into gibberish that (as far as we know) only you can decrypt, using your private key.
• After you do this, you use my public key to turn the signature back into the original hash value, and you use the cryptographic hash function to verify that the message hashes to that same value.

What do I mean "as far as we know"?

All of these algorithms and protocols are widely published and widely studied by everyone from undergrads to renowned experts to the folks at No Such Agency and its counterparts.  This is a key tenet of modern cryptography.  Only private keys are private.  Everything else is public.  "Security through obscurity" is frowned upon.  While it is possible that someone has cracked one or more pieces of this system, it's unlikely for several reasons:

• The same entities that would be cracking the system are using it for highly sensitive information (they might also be using some secret system for really really sensitive information, but the information known to be secured using the widely-known systems is pretty sensitive -- military communications, money transfers ...).  If you know your system can be cracked you have to assume your enemy could figure that out as well.
• There are known ways to test whether your crypto has been hacked, mainly noting carefully who acts on what secret information (whether real information or carefully selected false information).  Military history has several famous cases of battles deliberately lost to avoid giving away that the enemy's code had been cracked.  Eventually, though, that information will be put to use.  Not long after that, the jig is up.
• No academic researcher has published a significant crack of the current "best practice".  By contrast, several no-longer-widely-used systems have been cracked in the literature (MD5, anyone?).  Cracking a widely-used system is a pretty good way to advance on the tenure track and/or line up a lucrative job and/or develop serious street cred.

If someone has cracked the current public-key encryption infrastructure, they're using that information very carefully.

OK, how about my other disclaimer, "or someone in possession of your private key".  Key management is where we separate the pros from the amateurs -- and even the pros get it wrong way more often than they'd like.

Even if you're using some sort of uncrackable-in-principle quantum cryptography, at some point you're going to want to actually read a message encrypted to you and put your signature on something you're sending to someone else, and to do that you need some sort of key.  With current technology, typically that key is a file that's been encrypted using a passphrase.  If I want to decrypt or sign something, I put in the passphrase and the crypto software decrypts my private key to use for the real task at hand.

There are several weak points here.  An attacker could steal my key file and guess my passphrase.  An attacker could install a hacked version of the crypto software that sends the decrypted private key to the attacker, or encrypts the message with the attacker's public key along with the real recipient's.  An attacker could install a hacked version of the crypto software that uses a not-so-random number generator in places where we expect an unguessable random number to be used (see the footnote below for more on how those last two would work).

This is just off the top of my head.  Real experts spend a lot of time coming up with more sophisticated attacks and ways to prevent them.  The point is that no matter how strong the actual encryption algorithm, there needs to be a key of some sort, and there are plenty of ways to steal or tamper with the keys.

So if someone comes forward claiming ownership of a private key that was created years ago and used in a very visible way and that could be worth hundreds of millions of dollars, you may want to be a little careful before taking such a claim at face value.

Apparently, the only publicly available cryptographic evidence of the claim that Craig Wright is Satoshi Nakamoto is a digital signature that could have been copied from the publicly available blockchain.  This seems really odd.  You don't prove you have a private key by showing something already signed with that key.  You prove it by taking some new message of someone else's choosing, signing that and having the signature checked, ideally by yet a third person.  And anyone claiming to be Satoshi ought to know that.

On the other hand, reliable resources report that Wright has done essentially that using a different key that only Satoshi should have.  Additionally, Bitcoin experts who have met Wright claim he's the real deal -- he acts like Satoshi, he has the technical knowledge that Satoshi would have, he knows historical details that only Satoshi is likely to know, and so forth.

This is not to say that Craig Wright is lying or otherwise up to no good.  I have no reason at all to believe that or imply that.  My point is that that it would be a mistake to judge his or anyone's claim to be Satoshi Nakamoto based on cryptographic evidence alone.

So ... who knows?  At this point, we will probably never know for sure who Satoshi Nakamoto is or was, or even whether it was only one person.  Which seems somehow appropriate.

Postscript: The private key published by Craig Wright was used in an early block -- block 9 -- in the Bitcoin blockchain, in which a quantity of Bitcoin was transferred to the late Hal Finney.  As it happens, Hal Finney commented on a post on this blog.  The post was on anonymity, but his comment led me to his blog, where I saw a bunch of interesting stuff on digital rights management (DRM).   Naturally, I posted a reply to that, rather than his actual comment.  You can see the whole exchange here.

¹In practice, you don't use the public key system directly for large messages.  Rather, you use the public key system to encrypt a randomly generated key for a faster, non public-key system that is then used to encrypt the actual message.  Besides being faster, this also allows you to send a message to multiple recipients without having to generate a separate encrypted version of the whole message for each recipient key.  Instead, you encrypt the randomly generated key for each recipient.  I trust you can see why I left all this out of the main post.

"Hackers crack SSL"

[You may also want to check out this followup, and in particular the disclaimer near the top]

Well, kind of. SSL -- the protocol you use to make sure that, say, you're actually talking to your bank and that no one's listening in -- still appears safe when used correctly. What's actually happened is that Alexander Sotirov et. al. have described a way of using a long-known weakness in the MD5 cryptographic hash function to create a rogue Certificate Authority (CA) certificate. CA certificates are the "root certificates" used to vouch (directly or indirectly) for the certificates that servers use to convince your browser (and whoever else) that they are who they say they are. Certificate Authorities (CAs) are companies that -- very carefully -- issue server certificates cryptographically signed with their root certificates.

Although better alternatives (SHA1 and SHA2, for example) are known and widely available, some signing authorities were still using MD5 when Sotirov's team created their certificate. Anyone who trusted such a certificate, directly or indirectly, would be liable to be fooled by a forged certificate that looked the same as the real one as far as MD5 is concerned. Since at least one of the CAs that the major browsers trust by default still used MD5 at the time, a phisher could have used this certificate to spoof any site in the world.

Being White Hats, Sotirov and company took several steps to ensure that their particular certificate wouldn't be used that way and to give the Good Guys a chance to take preventative steps. This is standard practice. The general pattern is:

• Someone publishes a theoretical paper saying that some security measure (in this case MD5) is vulnerable to attack.
• Everyone nods thoughtfully and goes back to what they were doing.
• Time passes. In some cases years.
• Someone actually writes code to exploit the theoretical weakness. Ideally, it's a White Hat who's trying to get the major players off the dime. Less ideally, it's a Black Hat actually trying to use the exploit for ill. Quite often it's the White Hats because (we hope, and experience bears this out) the Black Hats are too busy scamming with the tools they already have to develop sophisticated new exploits.
  
• If it's a White Hat, the next step is to tell the relevant major players "Remember that theoretical paper on (some vulnerability)? I'm going to present an exploit based on it at (some conference). Here's everything I know about the problem and what to do about it." This gives the major players lead time before the cat is out of the bag and the Black Hats have access.
  
• In many cases, including the present one, the White Hats don't present the actual code they used, just the general technique and the results (in this case the bogus certificate) -- at least not until everyone's satisfied that the threat has been addressed. This means that anyone trying to do ill will actually have to have some programming skills. In the present case, it took a team of seven highly-skilled researchers six months to produce their result.
  

So ... it's highly unlikely that anyone will be able to use the Sotirov & co.'s certificate to steal your bank details. It's only a matter of time before someone else forges a bogus certificate that could have been so used, had the CAs not taken proper steps, but by that time the MD5-based CA certificates will have been taken down. In particular, Verisign has already taken down the one under their direct control and has said that those controlled by resellers should be gone by the end of January.

There's an interesting wrinkle in Sotirov's blog post that I linked to. Thanks to the recent legal wrangling over a paper detailing an attack on the Mifare Classic subway card system, people have become more skittish about giving a heads-up to just anyone.

Most hackers (in the older sense) believe strongly that suppressing useful information is counterproductive. Mifare is a case in point, particularly since Mifare Classic had already been successfully attacked, and the paper Mifare was trying to suppress is publicly available right here. But I digress.

Back at the storyline, Sotirov's team was concerned enough about dealing directly with CAs that "did not have a significant track record of responding to public security vulnerabilities in their systems" and so might "overreact and attempt to stop or delay our presentation through legal or other means" that they took the extra precautions of getting non-disclosure agreements from the browser vendors and using Microsoft as an intermediary in talking to the CAs.

The net effect was the same: The team was able to alert the geeks at Verisign and elsewhere without giving any trigger-happy suits anything to go on, and Verisign in turn acted quickly to deal with the problem. Sotirov closes his post on an encouraging note:

Cryptographic algorithms can become broken overnight, so it is important for CAs to demonstrate the ability to react quickly to such issues. I'm happy with the reponse from Verisign and the other affected CAs. Based on our experience with them, I would not hesitate to work with them directly on any vulnerabilties I might discover in the future.

Trusted computing: What could be better?

The fundamental tension behind trusted computing is over programmability. Someone sending out protected content wants to be sure that it can only be accessed on a restricted set of particular devices. This is a lot easier of the devices in question are not highly programmable. In the case of a portable music player or set-top box, the keys involved can be kept in special tamper-resistant hardware and otherwise protected from exposure or modification.

If your playback device is a general-purpose computer, the game becomes a lot harder. I could send you a player application with a key branded into it, but there are any number of ways to get such a player to yield up its secrets, or yield up the unprotected content without having to uncover the secrets themselves.

The trusted computing model tries to combat this by restricting access to the information on a given computer and tightly controlling all modification to such an otherwise-programmable device. In other words, the vendor asserts control over programmability. It is this idea, not the idea that the creator of content should have control over the content, that fundamentally conflicts with the ideas (and ideals) of personal computing in general and free software in particular.

The TC model, depending on tight control of all possible modifications, is inherently fragile. Compare it to the models used in modern cryptography (on which it heavily relies). In modern cryptography, one makes extremely pessimistic assumptions about what will happen in practice.

For example, in designing a cipher, one typically assumes an adaptive chosen-plaintext attack. This means that the attacker can repeatedly choose a message to be encrypted, look at the resulting ciphertext, choose another message to be encrypted and so on. This did not come about by accident. There are various ways a real-world attacker can perform such an attack on a real-world cipher.

Cipher design, and robust engineering in general, assumes that anything that can go wrong will. This generaly means minimizing the number of dependencies and moving parts. The RSA cipher, for example, consists of raising a number representing the message to a known power and taking the remainder against a large number, called the modulus. The modulus (along with a second exponent used to decrypt the message) is derived from two large, randomly-chosen prime numbers by a simple recipe.

That's it. That's one of the most secure ciphers known. But even with that simple recipe there are known subtleties in choosing a good key and in preparing messages for encryption in order to avoid various attacks.

Trusted computing relies on five key technologies, which interact in various ways to provide the full model. You need hardware support in several places to even have a chance at making it all work. There are legitimate questions about how all this will affect basic system functions like backup. It's quite clear that any TC system will be actively attacked by hackers in both senses (I shouldn't get started on this, but I still like to think of "hacker" as meaning someone who does clever things with technology for the sake of learning and having fun; the more popular meaning is someone who tries to break into systems).

It doesn't seem like a good bet.

Trying to prevent or control modifications to a general-purpose computer is swimming upstream. The main driver here is to protect content like music and video. That requires a tamper-resistant decoder (and faith that this is a worthwhile exercise, despite analog reconversion). From this point of view, TC tries to enable general-purpose computers to become decoders by first making them tamper-resistant.

The alternative is not to try to make general-purpose computers into decoders. If my computer has an encrypted-bits-to-sound-and-video decoder attached to it, then I can reprogram my computer all I want, and I can make as many copies of protected content as I want. When I want to play a song or video, I send it to my decoder, which has all the attributes TC wants: it's tamper-resistant, non-programmable and has a private key embedded in it as tightly as modern technology will allow.

I can use my favorite software to index the content that I've bought the rights to, to sequence it, to dispatch it to the various decoders I own and so forth. I can use my favorite non-media software without having to worry about what measures my OS vendor is taking to control my use of the content I bought the rights to.

This is not to far from how current content-delivery systems like cable and satellite boxes work, as I understand it. Given that, it's not clear to me how much farther we need to go down the TC road.