Protecting merchants from compromised webservers

[etotheipi]

I proposed this problem on IRC, and roconner came up with a very simple answer.  I've heard the devs say that "compromised web-servers are out of scope" -- this solution very well makes it in-scope.  The availability of such solutions should be strongly considered.  

Problem:  How can we prevent the situation that a webserver is compromised, and all payment addresses are replaced with those of the attacker.  We want deterministic wallets, and we don't want to have to give every customer our entire public key chain.  Using SSL/PKI/etc is assumed necessary here, since we assume no prior relationship between merchant and customer, and communication is happening over an insecure channel (i.e. -- the internet).
Solution:  This solution has the following properties:

(1) Signing certificate (X.509, GPG, Bitcoin private key, whatever), can be offline and remain offline forever -- it is never connected, by any means to an online computer
(1a) Signing certificate is trusted because it bears a CA's signature
(2) Uses deterministic wallets without revealing the entire chain, and without signing each individual key
(3) The certificate is used only to sign the root public key of the deterministic wallet, once.  All derived/child keys can be proven to part of that public chain without revealing the chaincode.

Consider a deterministic wallet such that you have a root public key, PubKey(0), and have a deterministic way of producing a sequence of chain codes, ChainCode(i), which are not public.  Then if you use:

Code:

PubKey(i) = Hash(ChainCode(i)) * PubKey(0)
InvoiceID = Hash(ChainCode(i))

Customer is presented with (InvoiceID, certificate-signed PubKey(0), CA-signed certificate).

The customer verifies the certificate is signed by a trusted CA.  Then they verify that PubKey(0) bears the signature of that certificate.  Then they confirm that InvoiceID*PubKey(0) indeed matches the address they were requested to pay.  Since the invoice is the hash of the Chaincode, there is no way for the customer to produce any other keys (despite having the root public key, which would remain unused so it could be used for this authentication).  Privacy is preserved.

Simple, straightforward, and right down the same alley as deterministic wallets, themselves.  Even if the webserver is compromised, the only addresses it can distribute that would be accepted by the customer, would be ones derived from PubKey(0).  Granted, it could distribute addresses using arbitrary 32-byte chaincodes, but at least the attacker wouldn't have a way to insert his own address, which removes about 98% of the motivation for the attack to begin with. (and in the case of arbitrary 32-byte codes, the merchant only needs to retrieve the InvoiceID from the customer to get access to the funds).

Thanks to roconner for the straightforward-in-hindsight solution to this.


Update:    I wanted to point out that this is possible without changing anything, if you are using BIP 32 wallets.  If you look at how the address chaining works, you see that to go from Root-->Child:

Code:

I = HMAC_SHA512(RootChain, RootPubKey || ChildID)

I is 64 bytes and then split into  

ChildMult = I_left = I[:32]
ChildChain = I_right = I[32:]
ChildPubKey = ChildMult * RootPubKey

Therefore, the child public key can be derived from the root public key using a multiplier which is not related to the chain code.  This means that you can sign RootPubKey with your offline certificate (but don't give out the chaincode!) and then I_left can be used as the "InvoiceID" above.  It fits perfectly into BIP 32.

[thanke]

The availability of such solutions should be strongly considered.  

Great idea, and totally agree with this statement.

What exactly is the difference to what is being discussed in the other thread? (https://bitcointalk.org/index.php?topic=130456)

[Mike Hearn]

Indeed, it seems to be the same as what was proposed by thanke. Great minds think alike, right

It suffers from the same practical problem I raised on the other thread: if an entity has an SSL cert, it's unreasonable to expect them to not use it for SSL. In that case, hacking the server lets you obtain the SSL keys and you gain nothing.

To fix this we'd need to find a way to achieve the following. This is what we have today:

Code:

Root CA -> Intermediate CA -> foo.com certificate (X)

We sign payment requests and SSL handshakes with the key for X. What we need is this:

Code:

Root CA -> Intermediate CA -> foo.com certificate (X) -> child foo.com certificate (Y)
Root CA -> Intermediate CA -> foo.com certificate (X) -> bitcoin-specific certificate (Z)

The key for X would then be held offline. The key for Y is online and would be used to set up SSL sessions. The key for Z would be kept offline too and used to sign a payment request that uses deterministic wallets. Bitcoin software would understand the Bitcoin specific cert format and how it chains onto the bottom of an X.509 chain, and the spec would require that the Bitcoin cert cannot be chained onto a chain that ends in two foo.com certs, so if Y is compromised, the following chain would be rejected by wallet software:

Code:

Root CA -> Intermediate CA -> foo.com certificate (X) -> child foo.com certificate (Y) -> bitcoin cert (Z2)

I don't know off hand whether this is possible, it'd need an SSL expert to comment. I might try and get Adam Langleys attention on it, I'm sure he would know.

Is it clear why this would be needed for the scheme to be practically deployable?

[Mike Hearn]

Well that was fast. Adam replied to my question. It turns out that the kind of chaining we'd need is technically supported by the spec (at least recent versions, he said only major browsers) ..... but CAs won't enable the magic bits for you unless you give them absurd piles of money. What a surprise.

More problematic is something I suspected but didn't mention yet - some CAs check you control the domain by checking to see if you control the web server, not DNS. So if you obtain control of the merchants server, you could get a new SSL cert issued to the merchants identity.

Apparently DNSSEC keys can be held offline in the way we'd need. DNSSEC is rolling out now, but almost nobody has practical experience with it, and only Chrome supports SSL-with-DNSSEC (no certificate authorities), and only then with custom extensions and tools checked out from Adams git repo. So it's not a mature solution yet.

There is another solution, but again, it's not really mature. Modern x86 CPUS support trusted computing extensions. Your SSL key could potentially be stored in a secure world. It would set up SSL sessions and sign payment requests, but could not be exported. In this construction, signing can still be online (so no protocol extensions needed) but obtaining root on the machine would not allow you to steal the key.

The toolkit here can be used to implement it: http://xmhf.sourceforge.net/doc/

The problem is that not all servers support this (I don't think you can use virtualized platforms like Linode), and the whole trusted computing system is kind of rough around the edges. Not to mention that the programming complexity is enormous (usage should be straightforward though).

[Gavin Andresen]

CAs will issue you multi-domain certificates for not a WHOLE lot more than a single-domain certificate, which suggests to me a possible short-term workaround/hack until DNSSEC/DANE is widely deployed.

Get a certificate that is valid for these subdomains:
   merchant.com
   www.merchant.com
   BaseBitcoinAddress.merchant.com  (e.g. 1gavinR2Y6RiHnEbf3sJBGbbKTc5t66do.merchant.com )

(in X.509 speak: Subject Alternative Names)

Payment requests from the merchant would include that certificate and the full public key (or script) that corresponds to 1baseBitcoinAddress.

Bitcoin clients would have to notice that the merchant's SSL certificate included a bitcoin address as one of the top-level domains, and would need to reject any payment requests that didn't include the full public key/script (and would always pay to BaseBitcoinAddress*hash(payment_request) where '*" is whatever hierarchical deterministic wallet scheme we decide we like).

Reasons not to do this or why it might not work:

* It is a hack.
* domain names are not case-sensitive (GOOGLE.com and google.com are the same); bitcoin addresses are.
* The extra cost to the merchant for the multi-domain cert might not be worth the incremental security benefit; if they have good monitoring (which they should), then they should detect an attacker's intrusion within minutes and so their potential loss might be tiny.

Edited, to add references to relevant standards:

X.509 certificates for the Internet:
http://www.rfc-editor.org/rfc/pdfrfc/rfc5280.txt

Subdomain names must be less than 63 characters and start with a letter:
http://www.rfc-editor.org/rfc/pdfrfc/rfc1034.txt

[Mike Hearn]

Also, it complicates rollout still further. Currently people can re-use their existing certs, so integrating payments is just an hours work or so with good docs. If new certs are required far fewer merchants will use it and users will be trained to expect unsigned payments, which means if I hack the server I can simply vend unsigned invoices for a while and many people will accept them.

I think the original plan still looks like the best one for now.

[etotheipi]

My apologies for "reposting" thanke's idea.  I read through 2/3 of the paper and a lot of the comments and apparently I didn't have the attention span to recognize that they were essentially the same solution (clearly related, though).  If nothing else, this is a much-more-concise version of it.  I had posed this question to roconner and he came up with a nice clean solution, so I thought it should be posted.

The extra cost to the merchant for the multi-domain cert might not be worth the incremental security benefit; if they have good monitoring (which they should), then they should detect an attacker's intrusion within minutes and so their potential loss might be tiny.

I'm not convinced that the incremental security is tiny.  Visa and Mastercard and Paypal, all have fairly locked-down systems that provide lots of information about anyone who is registered with the system, and the funds may be recoverable depending on how soon you detect it.  But in Bitcoin, you're talking about pseudo-anonymous, irreversible transactions -- every dollar lost to this kind of attack is really gone.  And this isn't just profit, this is gross income -- you can be sure that the customer will still expect their stuff, since they didn't do anything wrong.

Also, maybe resourceful/large companies can pay to have a good monitoring of their own webserver.  But maybe some smaller companies can't.  Or their IT team isn't that good -- a lot of companies get by with mediocre support.  It wouldn't surprise me if such a small company went a full business day without noticing.  Hardware devices are cool, and I think they offer a lot of potential but not nearly as versatile as a SW solution.  First, the HW solution proprietary and not everyone can make one, so it costs extra money.  And the physical security becomes more vulnerable having to keep the HW with the server -- with this method, the business owners could keep the cert/key in their safety-deposit box (or at home?).   

Unfortunately, I don't know that much about the X.509 infrastructure (other than the low-level cryptography aspects), and did not know that the certificates were restricted in what they could sign.  This is why I haven't contributed much to the payment protocol discussion, because I'm not sure I have anything to contribute (but lots to learn).  I was intrigued by the concept that a signature on the root key could be proven in the child keys, and was hoping someone else would answer about the feasibility.  If truly was feasible, I'd hope that we'd consider folding it into the currently-discussed payment protocol somehow...

[thanke]

CAs will issue you multi-domain certificates for not a WHOLE lot more than a single-domain certificate, which suggests to me a possible short-term workaround/hack until DNSSEC/DANE is widely deployed.

Get a certificate that is valid for these subdomains:
   merchant.com
   www.merchant.com
   BaseBitcoinAddress.merchant.com  (e.g. 1gavinR2Y6RiHnEbf3sJBGbbKTc5t66do.merchant.com )

(in X.509 speak: Subject Alternative Names)

Payment requests from the merchant would include that certificate and the full public key (or script) that corresponds to 1baseBitcoinAddress.

Bitcoin clients would have to notice that the merchant's SSL certificate included a bitcoin address as one of the top-level domains, and would need to reject any payment requests that didn't include the full public key/script (and would always pay to BaseBitcoinAddress*hash(payment_request) where '*" is whatever hierarchical deterministic wallet scheme we decide we like).

Reasons not to do this or why it might not work:

* It is a hack.
* domain names are not case-sensitive (GOOGLE.com and google.com are the same); bitcoin addresses are.
* The extra cost to the merchant for the multi-domain cert might not be worth the incremental security benefit; if they have good monitoring (which they should), then they should detect an attacker's intrusion within minutes and so their potential loss might be tiny.

Since Mike laid out the advantages of moving to DNSSEC for the PKI as soon as possible (in the other thread), an SSL "hack" may just be what we need for know, rather than designing anything "serious" based on SSL which is then later discarded. I like this hack and don't see any problem with it. Bitcoin pubkeys can be encoded case-insensitive in base32. And the merchant can decide if the security benefit is worth it for him or not. Small merchants won't have that kind of monitoring.

[Gavin Andresen]

Since Mike laid out the advantages of moving to DNSSEC for the PKI as soon as possible (in the other thread), an SSL "hack" may just be what we need for know, rather than designing anything "serious" based on SSL which is then later discarded. I like this hack and don't see any problem with it. Bitcoin pubkeys can be encoded case-insensitive in base32. And the merchant can decide if the security benefit is worth it for him or not. Small merchants won't have that kind of monitoring.

I'm liking the hack the more I think about it, too. Encoding a compressed public key (257 bits) in base32 would be 52 characters, which is comfortably less than the 63-character domain name limit.

Anybody buying a multi-domain (not wildcard) certificate sometime soon? I'm curious to find out if CA's blink if you ask them to issue a certificate valid for something like BTC8df4rfkbmeopl49vvfgkjgtimb84k9gtredsxfr9fekspclen493.mydomain.com

[pinnpe]

Protecting merchants from compromised webservers? Solution: http://www.youtube.com/watch?v=C0k_EMf2qqw (but then a bitcoin community version of this)

Certificate Auth??? Solution: Replace the CA http://convergence.io/

This might also be interesting http://www.youtube.com/watch?v=Z7Wl2FW2TcA (a got to see if your talking about dnssec)

[thanke]

I'm liking the hack the more I think about it, too. Encoding a compressed public key (257 bits) in base32 would be 52 characters, which is comfortably less than the 63-character domain name limit.

The more I think about it, I feel that a single pubkey is not enough, at least two are required. Frequently, if someone sets up a business, there will be business partners. Any derived certificate shall require the signature of all partners. This is only possible if the business' root certificate contains more than one key.

The situation for SSL certs is not comparable, because they are not equally sensitive. Even multinational corporations have SSL certs with a single key. But a bitcoin cert is comparable to the corporation's main bank account, which surely requires more than one signature to spend from it (or to license an agent to spent part of it with his own signature).

[etotheipi]

I'm liking the hack the more I think about it, too. Encoding a compressed public key (257 bits) in base32 would be 52 characters, which is comfortably less than the 63-character domain name limit.

The more I think about it, I feel that a single pubkey is not enough, at least two are required. Frequently, if someone sets up a business, there will be business partners. Any derived certificate shall require the signature of all partners. This is only possible if the business' root certificate contains more than one key.

The situation for SSL certs is not comparable, because they are not equally sensitive. Even multinational corporations have SSL certs with a single key. But a bitcoin cert is comparable to the corporation's main bank account, which surely requires more than one signature to spend from it (or to license an agent to spent part of it with his own signature).

I was just about to post about how this would seem to be solved using a combination of multi-sig/linked wallets (like described here) and the derived signatures like described in this thread.  But I just realized this doesn't work with P2SH. 

In the case you're talking about, your multi-national corp would probably have something like 5 wallets linked all using 4-of-5 transactions.  But it is expected that all "addresses" given out would be P2SH scripts.  The P2SH scripts would not be verifiable in the same way, since they are just strictly a hash.

You could supply the customer with all 5 root public keys (all five of which are signed) and let them create the P2SH script for you.  As long as the client includes all public keys in lexicographic order (which I think should be a divinely decreed for all M-of-N P2SH scripts, regardless of application), then all parties automatically know what the P2SH script would look like.   

It would technically work, but it's kinda messy.  The messiness can be hidden, but still complicates the payment protocol quite a bit.  But if you did have this, or were okay without P2SH (using regular multi-sig), then it would seem to solve the issue:  The multiple keys are all individually signed, and the customer client will verify all root keys before multiplying them by the per-invoice scalar, and then combining them into a TxOut -- in a deterministic way.

[khal]

You can store a hash (or a part of it) in the certificate, like abcdef01234567890, that points to a file anywhere, like :
- http://abcdefg01234567890.yourdomain.com/bitcoin.data (no need to even use ssl, you just have to verify if the hash of the file matches the hash in the certificate
- any p2p system that can provide data from a hash (namecoin, dht,etc)

The file can contain any amount of data, any amount of addresses.

Here is an example :
- ssl domain : abcde01234.mydom.com
- ssl file : http://abcde01234.mydom.com/bitcoin.cert
Hash of the file must match hash in the ssl certificate.

Example 2 :
- domain in ssl cert : bitcoindata.mydom.com
- name of the entry in namecoin : cert/bitcoindata
- value of the entry in namecoin : pubkey1,pubkey2,etc
You have the advantage to be able to update the addresses/pubkeys without to change the ssl certificate.

[thanke]

I'm liking the hack the more I think about it, too. Encoding a compressed public key (257 bits) in base32 would be 52 characters, which is comfortably less than the 63-character domain name limit.

The more I think about it, I feel that a single pubkey is not enough, at least two are required. Frequently, if someone sets up a business, there will be business partners. Any derived certificate shall require the signature of all partners. This is only possible if the business' root certificate contains more than one key.

The situation for SSL certs is not comparable, because they are not equally sensitive. Even multinational corporations have SSL certs with a single key. But a bitcoin cert is comparable to the corporation's main bank account, which surely requires more than one signature to spend from it (or to license an agent to spent part of it with his own signature).

I meant this as a general remark that applies to all kinds of payment protocols, not only and not specifically to the one proposed in this thread. In fact it was a remark about the PKI. I wanted to say that a PKI suitable as a foundation of a bitcoin payment protocol needs to allow more than one pubkey in its certificate. This applies even if the payment protocol uses only single keys (in a conceivable use case the multi-key corporation root cert signs a temporary single-key payment cert, say for some agent). Indeed a hash pointer suffices.

In the case you're talking about, your multi-national corp would probably have something like 5 wallets linked all using 4-of-5 transactions.  But it is expected that all "addresses" given out would be P2SH scripts.  The P2SH scripts would not be verifiable in the same way, since they are just strictly a hash.

Why not? If the unhashed scripts are verifiable then so are the hashed ones.

[etotheipi]

In the case you're talking about, your multi-national corp would probably have something like 5 wallets linked all using 4-of-5 transactions.  But it is expected that all "addresses" given out would be P2SH scripts.  The P2SH scripts would not be verifiable in the same way, since they are just strictly a hash.

Why not? If the unhashed scripts are verifiable then so are the hashed ones.

I meant, one of the reasons for P2SH was to give users the ability to use complicated scripts without sending such the script to the person paying.  Because such scripts could be long and annoying to copy, and it's really unnecessary for the payer to know/care about what is in the script.  Also it has the advantage of moving the bulky script itself into the TxIn script, which can then be pruned (though that particular advantage is still preserved, here).

It makes sense that linked wallets only create P2SH scripts and distribute those, thus using P2SH as it was intended.  However, in this case, the other party is forced to care about the innards of this P2SH script, because it must see each individual root key, and verify it before accepting the script -- unnecessarily complicating the protocol and kind of defying the original intent of P2SH.

It's workable, just suboptimal.

[etotheipi]

Since Mike laid out the advantages of moving to DNSSEC for the PKI as soon as possible (in the other thread), an SSL "hack" may just be what we need for know, rather than designing anything "serious" based on SSL which is then later discarded. I like this hack and don't see any problem with it. Bitcoin pubkeys can be encoded case-insensitive in base32. And the merchant can decide if the security benefit is worth it for him or not. Small merchants won't have that kind of monitoring.

I'm liking the hack the more I think about it, too. Encoding a compressed public key (257 bits) in base32 would be 52 characters, which is comfortably less than the 63-character domain name limit.

Anybody buying a multi-domain (not wildcard) certificate sometime soon? I'm curious to find out if CA's blink if you ask them to issue a certificate valid for something like BTC8df4rfkbmeopl49vvfgkjgtimb84k9gtredsxfr9fekspclen493.mydomain.com

I was thinking about this hack last night, and I think it's not as bad as it sounds -- perhaps not really a hack, but just a simple extension of the existing systems.  It's because the string in the subdomain doesn't have to be the full address, it just has to be identifiable.

-- My business creates a super-secure offline wallet.  The wallet root private key has the address:  1ArmoryXcfq7TnCSuZa9fQjRYwJ4bkRKfv.
-- I create a subdomain of bitcoinarmory.com:  1armoryxcfq7tncsuza9fqjrywj4bkrkfv.bitcoinarmory.com
-- I get a cert for that domain (all lowercase) verifying that I actually control that domain. 

When I send out a payment request, I include:

-- A cert verifying that 1armoryxcfq7tncsuza9fqjrywj4bkrkfv.bitcoinarmory.com is verified
-- The actual root public key (but not chaincode)
-- The "InvoiceID" which will be used to multiply that public key
-- The amount to send (and all the other stuff that needs to be included)

Then user's software can verify that 1armoryxcfq7tncsuza9fqjrywj4bkrkfv.bitcoinarmory.com belongs to me, and that hash160(publickey).lower() matches the subdomain.  Then they mulitply the verified public key by the "InvoiceID" and pay that address.  This works, because the address is 160 bits.  Throwing out the casing removes at most one bit of that information.  Even if my address is all letters (like the one in my signature), you still have at least (160-33)=127 bits of "entropy", which is more than enough to be collision resistant.  And I haven't actually added anything here: you have to send them the public key anyway.  I'm just pointing out that the signed data in the subdomain doesn't have to to be be a full address, just a "fingerprint" of such an address.

This has been on my mind recently, because I'm enjoying potential simplicity of this solution, and think it would be technically usable right now... besides the availability of a standardized, compatible wallet format (but BIP 32 will work).  A company only has to get another subdomain included on their cert each time they change their wallet.  Or the solution could be extended so that they can actually use the verified address, to ECDSA-sign other addresses/wallets to be used to collect funds for the company.

[thanke]

Good point, any 128 bit hash is indeed enough to authenticate the root public key.

Here are some reasons that this hash shouldn't be some (case insensitive) hash of the root public payment key itself, but rather, as you suggested, a hash of a public key (ECDSA or not) that is used to sign the root public payment key.

You want to put as little additional information as possible into the cert that you pay the CA for and keep that information as static as possible (never update). So let's just place one single hash in the form hash.main-domain.com, which is the hash of a bitcoin-specific cert that we define. The bitcoin-specific cert can contain

• more than one root key (e.g. different types, singlesig and multisig)
• keys for purposes other than payment, like
  
  • signing derived weaker certs (e.g. for agents)
  • signing payment root keys valid for certain periods of time
• keys from other cryptosystems than ECDSA

This would allow for great flexibility. Regarding other cryptosystems than ECDSA, specifically group signature schemes is something we need if several natural persons want to set up a business and don't fully trust each other. This issue doesn't come up in SSL certs because they are not powerful enough - they don't control money after all. But it comes up for bitcoin-specific certs. We do, of course, have a group signature available in the form of multisig scripts, and the P2SH address of such a script could indeed be placed directly in the CA cert. But any scenario where group signatures are needed is almost certainly complex enough to also require derived certs, so again, the multisig address wouldn't end up in the CA cert directly.

Yes, it would be technically usable right now. I made an attempt (https://github.com/bcpki/bitcoin) at defining a bitcoin-specific cert (protobuf) and implementing the payment address derivation (among other things), which is usable. Of course, the final link from the bitcoin-specific cert to the CA cert is missing. Not sure if BIP32 can be used because it does significantly more than what we need here. Not sure if we need a "compatible wallet format" at all. We can just handle this as an import into the existing wallet (an RPC doing exactly that is implemented in the above mentioned project). It seems the only things we need to agree on is the derivation function (two choices: additive or multiplicative) and endianess of "InvoiceID". And probably also on the format of "Invoice" (text or binary) and the hash function that produces "InvoiceID" (probably Hash160).

For compatibility with the currently developed payment requests I suggest to sign (this happens offline) the current root public payment key with some key that's defined for that purpose in the bitcoin-specific cert, and then store this root public payment key (in explicit form, not its address) online and ship it with every PaymentRequest message.

[EDIT] I just realized that with "Invoice" and "InvoiceID" I had something different in mind than the OP, which led to some confusion on my part and to my scepticism that BIP32 could be used as is.
What if InvoiceID is entirely customer generated (unlike in the OP)? Then it doens't fit in BIP32 anymore. Since there are strong use cases for customer generated InvoiceIDs, we should definitely allow those.
[/EDIT]