Tuesday, May 03, 2016

Satoshi: how Craig Wright's deception worked

My previous post shows how anybody can verify Satoshi using a GUI. In this post, I'll do the same, with command-line tools (openssl). It's just a simple application of crypto (hashes, public-keys) to the problem.

I go through this step-by-step discussion in order to demonstrate Craig Wright's scam. Dan Kaminsky's post and the redditors comes to the same point through a different sequence, but I think my way is clearer.

Step #1: the Bitcoin address


We know certain Bitcoin addresses correspond to Satoshi Nakamoto him/her self. For the sake of discussion, we'll use the address 15fszyyM95UANiEeVa4H5L6va7Z7UFZCYP. It's actually my address, but we'll pretend it's Satoshi's. In this post, I'm going to prove that this address belongs to me.

The address isn't the public-key, as you'd expect, but the hash of the public-key. Hashes are a lot shorter, and easier to pass around. We only pull out the public-key when we need to do a transaction. The hashing algorithm is explained on this website [http://gobittest.appspot.com/Address]. It's basically base58(ripemd(sha256(public-key)).

Step #2: You get the public-key


Hashes are one-way, so given a Bitcoin address, we can't immediately convert it into a public-key. Instead, we have to look it up in the blockchain, the vast public ledger that is at the heart of Bitcoin. The blockchain records every transaction, and is approaching 70-gigabytes in size.

To find an address's match public-key, we have to search for a transaction where the bitcoin is spent. If an address has only received Bitcoins, then its matching public-key won't appear in the Blockchain. In that case, a person trying to prove their identity will have to tell you the public-key, which is fine, of course, since the keys are designed to be public.

Luckily, there are lots of websites that store the blockchain in a database and make it easy for us to browse. I use Blockchain.info. The URL to my address is:

https://blockchain.info/address/15fszyyM95UANiEeVa4H5L6va7Z7UFZCYP

There is a list of transactions here where I spend coin. Let's pick the top one, at this URL:

https://blockchain.info/tx/8c4263d864d4f36e4eb4065a877e3e9a68cbe1de63a7b1fda70096e1e209cbbb

Toward the bottom are the "scripts". Bitcoin has a small scripting language, allowing complex transactions to be created, but most transactions are simple. There are two common formats for these scripts, and old format and a new format. In the old format, you'll find the public-key in the Output Script. In the new format, you'll find the public-key in the Input Scripts. It'll be a long long number starting with "04".

In this case, my public-key is:

04b19ffb77b602e4ad3294f770130c7677374b84a7a164fe6a80c81f13833a673dbcdb15c29857ce1a23fca1c808b9c29404b84b986924e6ff08fb3517f38bc099

You can verify this hashes to my Bitcoin address by the website I mention above.

Step #3: You format the key according to OpenSSL


OpenSSL wants the public-key in it's own format (wrapped in ASN.1 DER, then encoded in BASE64). I should just insert the JavaScript form to do it directly in this post, but I'm lazy. Instead, use the following code in the file "foo.js":

KeyEncoder = require('key-encoder');
sec = new KeyEncoder('secp256k1');
args = process.argv.slice(2);
pemKey = sec.encodePublic(args[0], 'raw', 'pem');
console.log(pemKey);

Then run:

npm install key-encoder

node foo.js 04b19ffb77b602e4ad3294f770130c7677374b84a7a164fe6a80c81f13833a673dbcdb15c29857ce1a23fca1c808b9c29404b84b986924e6ff08fb3517f38bc099

This will output the following file pub.pem:

-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEsZ/7d7YC5K0ylPdwEwx2dzdLhKehZP5q
gMgfE4M6Zz282xXCmFfOGiP8ocgIucKUBLhLmGkk5v8I+zUX84vAmQ==
-----END PUBLIC KEY-----

To verify that we have a correctly formatted OpenSSL public-key, we do the following command. As you can see, the hex of the OpenSSL public-key agrees with the original hex above 04b19ffb... that I got from the Blockchain: 

$ openssl ec -in pub.pem -pubin -text -noout
read EC key
Private-Key: (256 bit)
pub:
    04:b1:9f:fb:77:b6:02:e4:ad:32:94:f7:70:13:0c:
    76:77:37:4b:84:a7:a1:64:fe:6a:80:c8:1f:13:83:
    3a:67:3d:bc:db:15:c2:98:57:ce:1a:23:fc:a1:c8:
    08:b9:c2:94:04:b8:4b:98:69:24:e6:ff:08:fb:35:
    17:f3:8b:c0:99
ASN1 OID: secp256k1

Step #4: I create a message file


What are we are going to do is sign a message. That could be a message you create, that you test if I can decrypt. Or I can simply create my own message file.

In this example, I'm going to use the file message.txt:

Robert Graham is Satoshi Nakamoto

Obviously, if I can sign this file with Satoshi's key, then I'm the real Satoshi.

There's a problem here, though. The message I choose can be too long (such as when choosing a large work of Sartre). Or, in this case, depending on how you copy/paste the text into a file, it may end with varying "line-feeds" and "carriage-returns". 

Therefore, at this stage, I may instead just choose to hash the message file into something smaller and more consistent. I'm not going to in my example, but that's what Craig Wright does in his fraudulent example. And it's important.

BTW, if you just echo from the command-line, or use 'vi' to create a file, it'll automatically append a single line-feed. That's what I assume for my message. In hex you should get:

$ xxd -i message.txt
unsigned char message_txt[] = {
  0x52, 0x6f, 0x62, 0x65, 0x72, 0x74, 0x20, 0x47, 0x72, 0x61, 0x68, 0x61,
  0x6d, 0x20, 0x69, 0x73, 0x20, 0x53, 0x61, 0x74, 0x6f, 0x73, 0x68, 0x69,
  0x20, 0x4e, 0x61, 0x6b, 0x61, 0x6d, 0x6f, 0x74, 0x6f, 0x0a
};
unsigned int message_txt_len = 34;


Step #5: I grab my private-key from my wallet


To prove my identity, I extract my private-key from my wallet file, and convert it into an OpenSSL file in a method similar to that above, creating the file priv.pem (the sister of the pub.pem that you create). I'm skipping the steps, because I'm not actually going to show you my private key, but they are roughly the same as above. Bitcoin-qt has a little "dumprivkey" command that'll dump the private key, which I then wrap in OpenSSL ASN.1. If you want to do this, I used the following node.js code, with the "base-58" and "key-encoder" dependencies.

Base58 = require("base-58");
KeyEncoder = require('key-encoder');
sec = new KeyEncoder('secp256k1');
var args = process.argv.slice(2);
var x = Base58.decode(args[0]);
x = x.slice(1);
if (x.length == 36)
    x = x.slice(0, 32);
pemPrivateKey = sec.encodePrivate(x, 'raw', 'pem');
console.log(pemPrivateKey)

Step #6: I sign the message.txt with priv.pem


I then sign the file message.txt with my private-key priv.pem, and save the base64 encoded results in sig.b64.

openssl dgst -sign priv.pem message.txt | base64 >sig.b64

This produces the following file sig.b64 that hash the following contents:

MEUCIQDoy6K0xQ1cAPg7fXbQcmfbtK4VJ5wlMTzG4DaUV3zF9gIgLNbJw0oqj3lQf7lhe7TtPzse
PXf8GB3q4IhCiWVxTJ8=

How signing works is that it first creates a SHA256 hash of the file message.txt, then it encrypts it with the secp256k1 public-key algorithm. It wraps the result in a ASN.1 DER binary file. Sadly, there's no native BASE64 file format, so I have to encode it in BASE64 myself in order to post on this page, and you'll have to BASE64 decode it before you use it.

Step #6: You verify the signature


Okay, at this point you have three files. You have my public-key pub.pem, my messagemessage.txt, and the signature sig.b64.

First, you need to convert the signature back into binary:

base64 -d sig.b64 > sig.der

Now you run the verify command:

openssl dgst -verify pub.pem -signature sig.der message.txt

If I'm really who I say I am, and then you'll see the result:

Verified OK

If something has gone wrong, you'll get the error:

Verification Failure


How we know the Craig Wright post was a scam


This post is similarly structure to Craig Wright's post, and in the differences we'll figure out how he did his scam.

As I point out in Step #4 above, a large file (like a work from Sartre) would be difficult to work with, so I could just hash it, and put the binary hash into a file. It's really all the same, because I'm creating some arbitrary un-signed bytes, then signing them.

But here's the clever bit. If you've been paying attention, you'll notice that the Sartre file has been hashed twice by SHA256, before the hash has been encrypted. In other words, it looks like the function:

secp256k1(sha256(sha256(message)))

Now let's go back to Bitcoin transactions. Transactions are signed by first hashing twice::

secp256k1(sha256(sha256(transaction)))

Notice that the algorithms are the same. That's how how Craig Write tried to fool us. Unknown to us, he grabbed a transaction from the real Satoshi, and grabbed the initial hash (see Update below for contents ). He then claimed that his "Sartre" file had that same hash:

479f9dff0155c045da78402177855fdb4f0f396dc0d2c24f7376dd56e2e68b05

Which signed (hashed again, then encrypted), becomes:

3045022100c12a7d54972f26d14cb311339b5122f8c187417dde1e8efb6841f55c34220ae0022066632c5cd4161efa3a2837764eee9eb84975dd54c2de2865e9752585c53e7cce

That's a lie. How are we supposed to know? After all, we aren't going to type in a bunch of hex digits then go search the blockchain for those bytes. We didn't have a copy of the Sartre file to calculate the hash ourselves.

Now, when hashed an signed, the results from openssl exactly match the results from that old Bitcoin transaction. Craig Wright magically appears to have proven he knows Satoshi's private-key, when in fact he's copied the inputs/outputs and made us think we calculcated them.

It would've worked, too, but there's too many damn experts in the blockchain who immediately pick up on the subtle details. There's too many people willing to type in all those characters. Once typed in, it's a simple matter of googling them to find them in the blockchain.

Also, it looks as suspicious as all hell. He explains the trivial bits, like "what is hashing", with odd references to old publications, but then leaves out important bits. I had to write code in order to extract my own private-key from my wallet in order to make it into something that OpenSSL would accept -- I step he didn't actually have to go through, and thus, didn't have to document.


Conclusion


Both Bitcoin and OpenSSL are just straightforward applications of basic crypto. It's that they share the basics that made this crossover work. It's by applying our basic crypto knowledge to the problem that catches him in the lie.

I write this post not really to catch Craig Wright in a scam, but to help teach basic crypto. Working backwards from this blogpost, learning the bits you didn't understand, will teach you the important basics of crypto.


Appendix


To verify that I have that Bitcoin address, you'll need the three files:

pub.pem

-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEsZ/7d7YC5K0ylPdwEwx2dzdLhKehZP5q
gMgfE4M6Zz282xXCmFfOGiP8ocgIucKUBLhLmGkk5v8I+zUX84vAmQ==
-----END PUBLIC KEY-----


message.txt
Robert Graham is Satoshi Nakamoto

sig.b64
MEUCIQDoy6K0xQ1cAPg7fXbQcmfbtK4VJ5wlMTzG4DaUV3zF9gIgLNbJw0oqj3lQf7lhe7TtPzsePXf8GB3q4IhCiWVxTJ8=

Now run the following command, and verify it matches the hex value for the public-key that you found in the transaction in the blockchain:

openssl ec -in pub.pem -pubin -text -noout

Now verify the message:

base64 -d sig.b64 > sig.der
openssl dgst -verify pub.pem -signature sig.der message.txt




Update:


The lie can be condensed into two images. In the first is excerpts from his post, where he claims the file "Sartre" has the specific sha256sum and contains the shown text:


But, we know that this checksum matches instead an intermediate step in the 2009 Bitcoin transaction, which if put in a file, would have the following contents:


The sha256sum result is the same in both cases, so either I'm lying or Craig Wright is. You can verify for yourself which one is lying by creating your own Sartre file from this base64 encoded data (copy/paste into file, then base64 -d > Sartre to create binary file).

AQAAAAG6kcHV5VqeL6tOQfVbhipzskcZqtE6Un0WnB+tO2O1EgEAAABDQQQR25Ph3NuKAWtJhA+MU7wetoo4LpexSC7K17FIppCaXLLg6t37hMz5dERk+C4WC/qbi2T51MA/mZuGQ/ZWtBKjrP////8CAMqaOwAAAABDQQS+2CfTdHS+/7N+/lM3AawffGAJV6RIe+izcTRvAWgm7m9XujDYikcqDk7NLwdZmnlfHwHeeNeRs4LmXuHFi0UIrADSSWsAAAAAQ0EEEduT4dzbigFrSYQPjFO8HraKOC6XsUguytexSKaQmlyy4Ord+4TM+XREZPguFgv6m4tk+dTAP5mbhkP2VrQSo6wAAAAAAQAAAA==

I got this file from https://rya.nc/sartre.html, after spending an hour looking for the right tool. Transactions are verified using a script within the transactions itself. At some intermediate step, it transmogrifies the transaction into something else, then verifies it. It's this transmogrified form of the transaction that we need to grab for the contents of the "Sartre" file.

10 comments:

Unknown said...

Da major [in "Do the right thing"] paraphrased Tao Te Ching with the immortal words: "those that'll tell don't know, and those that know won't tell". Your analysis shows the accuracy of this once again.
Thanks for the code based explanation.

pjb said...

Do we know that Satoshi is a single person? I have the impression it could very well be a group. Therefore I would request that you write he/she/they and his/her/their!

Unknown said...
This comment has been removed by the author.
Jim said...

I agree with pjb, this is a Homer or even Shakespeare like character with more then 1 (code) writer involved. Or died with Hal Finney or David Kleiman.

Unknown said...

Technically, your proof has a hole because you are using your private half of the key and refusing to disclose it. :-)

Personally, I would love it if you worked this as an example where you ginned up a new key pair and used that - then we can see the whole thing, and it's really easy to share far and wide so anyone can see without requiring much of them.

I care about security, but I don't 'do' security now. So I don't understand the players - what is this all about ? We're agreed on the fundamentals. if you don't have the pair, you can't fake having it, and using digests to fool the unobservant won't fool the system. Who the hell is this guy ? Haven't we been clear enough about a primary point of crypto being 'you cannot forge stuff.' Weird and stupid are the only two terms I have at present....

aferron said...

https://twitter.com/a_ferron/status/727695099711250432

.NetDeveloper said...

Why doesn't he just encrypt another short file (or ideally one the community gives him) and use that as proof?

anantk said...

@.NetDeveloper: because he isn't Satoshi

bigtruck01 said...

As an alternative, create a new wallet with a new private/public key pair and disclose both for the example.

IOGAMES said...

nicest piece of logic against this scammer not attacking his personality or motives but his knowledge :)