Off-chain anonymous transactions by secure transfer of private keys

[drazvan]

Hello everyone,

I've posted a message on the Project Development thread at https://bitcointalk.org/index.php?topic=319146.0 but it didn't get much attention, but there's a technical side to it that I'd like to submit to you and hopefully get some feedback.

To summarize, I'm in the process of developing a system called OtherCoin that allows anonymous off-chain payments by transferring private keys between tamper-proof smartcards. The private keys are either generated internally by the smartcard or received over an RSA-encrypted channel from a similar smartcard. The smartcard just certifies that any key it sends over the RSA-encrypted channel has never left the card in unencrypted form and has never been revealed to the wallet. The smartcard can reveal the private key to the wallet at any time - when it does that, it removes it from its secure storage, effectively making it a plain Bitcoin private key.

A short whitepaper is available at http://www.othercoin.com/OtherCoin.pdf . It explains more than I can do in a single post here.

The system has been designed to work in the absence of trust (you do not have to trust the smartcard, you always combine the public keys it generates with a second set generated by the wallet, so that the card has no idea what your actual Bitcoin public key / address is). And since it's a smartcard, it obviously can't communicate to the outside world by itself, so it cannot leak information. It never signs transactions, its purpose is to only generate private keys and store them securely, then either fully reveal them to the wallet or securely transfer them to the storage of a similar card.

I would appreciate some comments from the more crypto-knowledgeable developers here. I think it's currently the only off-chain payment system that does not rely on a central service/server - the issuer of the cards could go out of business and the system could continue to work indefinitely. And since transactions never touch the blockchain, they are invisible to the Bitcoin network (and your friends in law enforcement) - they are strictly point to point between the payer and the payee, no record is written in the blockchain or anywhere else.

Any ideas, comments and criticisms are welcome.

Thank you,
Razvan

[gmaxwell]

tamper-proof

Please say tamper-resistant.

Otherwise you are overselling the possible.

There is absolutely a place for that kind of system, but having a reasonable dialog requires being frank about precisely where the security breaks down.  E.g. if the tamper resistance is compromised, or the issuer cheats and issues fake cards or leaks their key, the result is a class break which renders all othercoin smartcards insecure and only useful for direct redemption to Bitcoin (because you couldn't trust if they were doublespends otherwise).

In general, it sounds like a fantastic idea.  I think it would also be neat if future Bitcoin hardware wallets had a smartcard slot that enabled them to host an othercoin card. (bitcoin hardware wallets are not as tamper resistant, but have important UI elements that protect you from compromise of your host).

[drazvan]

My apologies, tamper-resistant is more accurate. The cards we plan to use are certified at the EAL 5+ level (http://en.wikipedia.org/wiki/Evaluation_Assurance_Level) which I understand to be fairly high - maybe not high enough for military apps but definitely designed to withstand casual hacking attempts.

Thank you!
Razvan

[drazvan]

Also, the plan is to eventually get more than 1 entity certifying/signing the device key - in order to keep everyone honest. For instance, one of the entities signing the cards could be the Bitcoin Foundation or one of the large mining organizations. We would also obviously share the sources with them (but that would have to happen under NDA given the strict requirements of our NDA with NXP - without that we wouldn't have access to hardware-accelerated crypto and everything would be painfully slow, plus that we would have to add SPA/DPA (http://en.wikipedia.org/wiki/Power_analysis) countermeasures ourselves).

[gmaxwell]

Petertodd would probably recommend bonding the cards in some (or multiple ways).

One way would be to make every card contain a shared bitcoin private key (same key in all cards) for some large amount of Bitcoin, visible sitting in the chain. The card could prove that it contains the key by being willing to do a bitcoin-signmessage for the key.

If someone can compromise your tamper resistance, they can obtain the coin and in doing so would alert everyone that the tamper-resistance has been compromised at least once.

[drazvan]

There is an alert mechanism already built into the system - basically, the wallet gets a list of the public keys that the OtherCoin card claims to have secure private keys for, then monitors the blockchain for any transactions involving those addresses. If funds ever move out of any of them, it triggers an alarm and then we know the security has been breached somehow since the private key is supposed to have not been released to anyone (the current user can actually prove it by showing the OtherCoin card with the private key inside, in its "secure/unreleased" status).


I'll look into the bonding idea as well, thank you!

[gmaxwell]

There is an alert mechanism already built into the system - basically, the wallet gets a list of the public keys that the OtherCoin card claims to have secure private keys for, then monitors the blockchain for any transactions involving those addresses. If funds ever move out of any of them, it triggers an alarm and then we know the security has been breached somehow since the private key is supposed to have not been released to anyone (the current user can actually prove it by showing the OtherCoin card with the private key inside, in its "secure/unreleased" status).

I'll look into the bonding idea as well, thank you!

Thats kinda bad for privacy.  You could use a cryptographically secure bloom filter to improve privacy, but it's probably asking too much for your CPU power.

Interesting, done right you could probably make it so your alert mechnism wrote a cryptographic proof that could be showed to other people.

[adam3us]

I was also thinking of something similar (draft post sitting in another tab), not skimmed your paper yet though.  I think I can get it to work, pseudonymously, somewhat online verification, but with untrusted open spec hardware, that anyone would be invited to produce and load bitcoins onto.  So the design parameters are a bit different.  But I share your excitement for physical electronic non-clonable coins (though I did not try to increase bitcoins privacy model in my idea) and encourage you if you're an operational guy who actually builds things go go for it

Specifically about your proposal and question the perf requirements of your card, I think you are not taking advantage of existing known technology.  Read about Stefan Brands observer protocol, chapter 6 (whole book online as pdf in chapters):

http://www.credentica.com/the_mit_pressbook.html

[EDIT: its long and full of crypto, but read 6.5.1 last para or two; and 6.5.4 shows you what he's thinking this is good for "bearer certificates" = offline transferable pseudonymous ecash.]

In short it gives you a way to have a smart card that does something very cheap (like one 256-bit mod mul and 256-bit mod add to compute cx+w mod n (a contribution to the signature)  Because of the inflow/outflow security arguments the card has no visibility into your privacy, its tamper resistance only protects double spending.  

Furthermore its offline spend compatible using limited-show protocol, which allows things like retep's comments about good behavior bonds.  You can put the private key for a high value coin (eg $10,000) in the private key certificates in such a way that if a single double spend occurs (which can only happen as a result of hacking a card) a simultaneous equation is released that allows recovery of the $10,000 private key (that is the basis of the limited-show protocol).

Brands protocols are defined on Schnorr signatures (or ECSchnorr) and of course bitcoin uses ECDSA.  It might be within the realms of possibility that you could achieve something analogous though DSA is a complexification of Schnorr that does nothing for security and just limits flexibility.  Brands also has an RSA group variant but that doesnt help the compatibility.

Adam

[adam3us]

[EDIT: its long and full of crypto, but read 6.5.1 last para or two; and 6.5.4 shows you what he's thinking this is good for "bearer certificates" = offline transferable pseudonymous ecash.]

In short it gives you a way to have a smart card that does something very cheap (like one 256-bit mod mul and 256-bit mod add to compute cx+w mod n (a contribution to the signature)  Because of the inflow/outflow security arguments the card has no visibility into your privacy, its tamper resistance only protects double spending.  

btw I its not so clear in the book, and I reinvented it in my 1995-2005 pre-bitcoin attempts to find a way to deploy a decentalized anonymous ecash, as specified what he is saying is actually not offline respendable, only offline spendable; ie after you've done your spend, before you can respend, you have to deposit the funds in an issuer bank.  (And in bitcoin or zerocoin or the 1999 Ta-Shma & Sander "auditable anonymous electronic cash" paper there is no central bank, but you have to send it to the blockchain/zerocoin mix/shared blackboard respectively, but the dependency is still present).

What I figured out is you can offline respend without deposit (without going online) using 0-value coin collection as the initial witness.  Very excited when I figured out that in 2000, and I asked Stefan about it, but it turns out there was a masters thesis on this topic and its mentioned in a footnote somewhere in Brands PhD thesis/book referenced above.

Anyway it seems to me you're more interested in offline re-spendability so you need to use that follow-on invention/re-invention.

Why I did nothing with this protocol (eg like rush off and implement it with B-money) is I was thinking it was not good enough - its necessarily, like bitcoin, pseudonymous, and publicly linkable, which I considered, and still do consider to be a privacy problem (and in bitcoin whether you believe in privacy or not, a fungibility problem in addition, hence all the debate about zerocoin, coinjoin, mixers and taint, whether you actually even want anonymity or not, those security concerns of fungibility and anonymity are actually orthogonal - you can have fungibility (via coin anonymity) with pseudonymity, or escrowed identity and other variants just fine).  Btw there is a difference between payment confidentiality and pseudonymity/anonymity also, you can have payment confidentiality with or without pseudonymity/escrowed identity pseudonymity/anonymity.  Bitcoin has limited payment confidentiality (you have to work hard with wallet control, which is not implemented, and disciplined fund separation, and mixes/coinjoining is of apparently statistically weak value according to the data analysts who have looked at the network flow statistics.  And thats a problem.  If nothing else we need to make bitcoin payment amounts confidential (eg homomorphic value encryption).  And even payees is extremely invasive if you think about it.  Oh the public can see you bought an ebook from this publisher.  Or you bought a condom pack from this supplier.  etc  Its ridiculously invasive as is, and if your credit card issue or bank account put your statements online like the block chain there would be a public outcry.

Also I have to say I am not someone convinced by the offline respendability security argument.  Even if there is a fidelity bond, the problem is offline respendable card is a license to print money, and people will just spend a multiple of the fidelity bond or try to.  One somewhat defense is that if multiple people have offline respenable money flowing around, some of them are going to convert it to online ("deposit" it) and as soon as that happens the double-spend hw hack is blown.  You want to pass a "this key and card series hacked" protocol revocation cert through the network, and switch to the ciphersuite/keyset B while working on deploying card C or firmware upgrade C.

Adam

[Peter Todd]

Petertodd would probably recommend bonding the cards in some (or multiple ways).

One way would be to make every card contain a shared bitcoin private key (same key in all cards) for some large amount of Bitcoin, visible sitting in the chain. The card could prove that it contains the key by being willing to do a bitcoin-signmessage for the key.

If someone can compromise your tamper resistance, they can obtain the coin and in doing so would alert everyone that the tamper-resistance has been compromised at least once.

Yup. There are more sophisticated ways of doing bonding, but I think for OtherCoin just doing the above is the way to go for v1.0 if you're pretty confident in the hardware. Just be clear to market this stuff for low-value, low-security-required applications initially and go slow with your expectations.

Regarding trusted hardware in general, people have this mistaken idea that the idea is fundamentally flawed because the secrets will always be possible to exploit. What they don't realize is that 60 years ago you would have made the exact same argument about cryptography: "This encryption business will never work because mathematics will always be broken eventually." In the case of trusted hardware we're still not there, but it certainly in theoretically possible to build hardware systems that impossible to extract secrets from, simply because at some point you've built a circuit whose physical dimensions are so small that the only way to probe it is with the physical structures already built into it. I work in analog electronics myself, and there's lots of situations where its physically impossible to probe a circuit and determine what state it is in because physics simply does not allow you to do so.  These limitations are every bit as real as the mathematical limitations that prevent someone from spending a Bitcoin they don't own, and future hardware designs that use them fully can and will be secure.

[piotr_n]

It's a nice idea, but as you say yourself "The only trusted authority is the issuer of the OtherCoin card".

So first of all you need to trust an authority.

Second, you need to have some kind of making sure that the card is not just pretending to be issued by an authority - this I guess you can do by putting the authority's private key inside the card and telling it to sign messages with it.

But the third problem is (and I had worked with smart cards for awhile) that basically every smart card can be hacked - it is only a matter of time and money.
So eventually someone will manage to get the authority's private key out of it and then will be able to make his own, fake cards.

And on top of that, there is always tha ever lasting: how can you even trust an authority?

But the idea is appealing and probably worth exploring.

[Mike Hearn]

In practice, secure hardware seems to be secure enough for many transactions. EMV is a successful system and AFAIK all the attacks against it are protocol attacks, or exploiting flaws in the terminal hardware or banking backend software (like poor RNGs). I've yet to hear about criminals decapping chips en-masse and exploiting the system that way, despite massive incentive to do so.

If you could obtain that trust, then I think a MintChip style secure hardware platform is a great way to do off-chain, off-line transactions. I hope it won't be necessary due to the increasing prevalence of internet connections and smartphones, but if it does prove useful, I think it'll work fine.

[piotr_n]

I've yet to hear about criminals decapping chips en-masse and exploiting the system that way, despite massive incentive to do so.

I would not call the guy a criminal, but... http://www.youtube.com/watch?v=Qk73ye2_g4o

For the application we are talking about, all it takes to extract the authority's private key is to successfully hack one card.
You might destroy hundreds of thousands of them, on the way there, but all you need is the master key that is shared among all of them.
So one is enough and you can make millions of fake ones ever since that moment.

[drazvan]

Piotr_n, there is no private key that all the cards share. They all share the public key of the issuer in order to be able to verify other cards and ensure that the Bitcoin private keys are only transferred to cards issued with the same restrictions and running the same software.

Each card comes with its own "device key" (I think this is called an "endorsement key" in TPM world - see http://en.wikipedia.org/wiki/Trusted_Platform_Module ). The root private key (used to sign the endorsement keys) is definitely not present on any of the cards.

As I've described earlier, the plan is to raise an alarm when we detect a doublespend (meaning one of the cards was compromised). We also plan to have a CRL (http://en.wikipedia.org/wiki/Revocation_list) that we can use to mark a card as compromised.

Right now, the OtherCoin cards do not keep track of where they got the keys from (I mean they do verify the sender but they don't store it), but they could - they could create a chain of public keys indicating the previous owners of that Bitcoin private key (stored securely in the card, not released to the wallet). When the wallet detects an external spend for a key stored in its OtherCoin, it can essentially ask the card to release this chain and we can then blacklist all the cards in the chain (blacklisting would not mean locking them out of their funds, but forcing them to go through the blockchain for their transactions). Since we cannot tell exactly which card from the chain has been broken (but one definitely has been broken if we ended up with a key that has been spent externally), we blacklist them all.

I'm still reluctant to implement something like this since it would give quite a bit of power to the entity controlling the CRL - if implemented, each blacklist would have to be properly documented.

[drazvan]

Thats kinda bad for privacy.  You could use a cryptographically secure bloom filter to improve privacy, but it's probably asking too much for your CPU power.

Interesting, done right you could probably make it so your alert mechnism wrote a cryptographic proof that could be showed to other people.

That's actually the plan, but we need to make sure that the person reporting the hack is not the person that has actually hacked the card. If we have a physically intact card that contains a private key that we've seen a spend operation for on the blockchain and the card can keep track of the previous owners of that private key, it can be asked to reveal that chain of previous owners. If two or more physically and logically intact OtherCoins report this, we can compare the chains and find the actual card that has performed the double spend.

The wallet will most probably employ Bloom filters to monitor the blockchain - but most wallets already do that, don't they? The wallet knows the public keys / addresses to look for and it's up to it to fine tune the Bloom filter to not reveal the exact addresses it's looking at. I wouldn't want to implement that on the smartcard.

[piotr_n]

Piotr_n, there is no private key that all the cards share. They all share the public key of the issuer in order to be able to verify other cards and ensure that the Bitcoin private keys are only transferred to cards issued with the same restrictions and running the same software.

Each card comes with its own "device key" (I think this is called an "endorsement key" in TPM world - see http://en.wikipedia.org/wiki/Trusted_Platform_Module ). The root private key (used to sign the endorsement keys) is definitely not present on any of the cards.

Oh, OK.
So each card would have a unique private key and its corresponding public key, that would be signed by the issuing authority?

Now it starts making much more sense.
This can indeed work - as long as the private key used to sign the public keys of the cards they manufacture does not leak out of the authority.
Which is again: usually only a matter of time and money...
But OK - let's assume that it won't leak out.

In such case I have another concern.
From what I understand moving bitcoins from one card to another means sending the key from card A to B - storing it in card B, while destroying it in card A.
But is there some reliable method to avoid destroying the key in A too soon, or too late?
If you destroy it too soon, the coins will get lost - if you do it too late, you might end up with the same key being owned by two cards.

[drazvan]

Piotr, the way it works is that there are two separate operations. The first one (called REVEAL) takes the Bitcoin private key out of the secure storage, encrypts it with the RSA-2048 public key of the recipient, then moves it to a public buffer (no longer in secure storage) that the wallet can read it from as many times as it wants. Once the wallet has successfully forwarded that encrypted key to the other end, it issues a second command called REMOVE that clears the public buffer. The Bitcoin private key is erased from secure storage as soon as REVEAL is called, but it is still available in its encrypted form (decryptable only by the recipient) in the public buffer until REMOVE is called.

So in the case of a communication breakdown, the sender can keep reading it from the buffer (or just cache it internally since it's encrypted) and retry sending it to the recipient that is now the only entity capable of recovering that Bitcoin private key.

The scheme also does replay protection by using a nonce sent together with the RSA public key (preventing you from resending an old recorded payment message to a recipient to convince him to reimport the key into its private storage).

[piotr_n]

Cool - thanks for explaining.

So REVEAL removes the Bitcoin from the card's balance storage, though keeps it in the card's NVM, encrypted with the recipient's RSA.
The recipient can request this RSA encrypted key as many times, as it wants - until it gives the REMOVE command, which essentially frees the memory in card A.

Yeah, I like this idea.
And sorry for not reading through carefully, at the first time, asking these questions instead.
But it's all clear now and I like it - I think it can work.

[Crowex]

What is the protocol to establish an authenticated and encrypted channel between the smart cards that is resistant to MITM attacks?

[gmaxwell]

What is the protocol to establish an authenticated and encrypted channel between the smart cards that is resistant to MITM attacks?

Presumably the cards must present a certificate signed by a trusted (by the card) authority.