Multi-signature and correlated risks: the case of Bitfinex


BitFinex has not yet provided a detailed account of the recent security breach that resulted in loss of 120000 bitcoins from the exchange. Much of what has been written about the incident is incomplete, speculation or opportunistic marketing . Fingers have been pointed at seemingly everyone, including strangely the CFTC, for contributing to the problem. (While casting regulators as villains seems de rigueur in cryptocurrency land these days, that particular argument was debunked elsewhere.) Others have questioned whether there is a problem with the BitGo service or even intrinsic problem with the notion of multi-signature in Bitcoin.

Some of these questions can not be answered until more information about the incident is released, either by Bitfinex or perhaps by the perpetrators- it is not uncommon for boastful attackers to publish detailed information about their methods after a successful heist. But we can dispel some of the misconceptions about the effect of multi-signature on risk management.

Multi-signature background

In the Bitcoin protocol, control over funds is represented by knowledge of cryptographic secrets, also known as private keys. These secrets are used for digitally signing transactions that move funds from one address to another. For example, it could be moving funds from a consumer wallet to a merchant wallet, when paying fora cup of coffee in Bitcoin. Multi-signature is an extension to this model when more than 1 key is required to authorize the transaction. This is typically denoted by two numbers as “M-of-N.” That refers to a group of N total keys, of which any quorum of M is sufficient to sign the transaction.

Multisig achieves two seemingly incompatible objectives:

  • Better security. It is more difficult for an attacker to steal 3 secrets than it is to steal a single one. (More about that assumption below.)
  • Higher availability & resiliency. Theft is not the only risk associated with cryptographic secrets. There is also the far more mundane problem of plain losing the key due to hardware failures, forgotten credentials etc. As long as N > M, the system can tolerate complete destruction of some keys provided there are enough left around to constitute a quorum.

Multi-signature with third-party cosigners

Bitfinex did not have a cold-wallet in the traditional sense: storing Bitcoins on an offline system, one that is not accessible from the Internet even indirectly. Instead the exchange leveraged BitGo co-signing engine to hold customer funds in a multi-signature wallet. This scheme involves a 2-of-3 configuration with specific roles intended for each key:

  • One key is held by the “customer,” in this case Bitfinex (Not to be confused with end-users who are customers of Bitfinex)
  • Second key is held by BitGo
  • Third key is an offline “recovery” key held by Bitfinex. It is the escape-hatch to use for restoring unilateral control over funds, in case BitGo is unable/unwilling to participate

In order to withdraw funds out of Bitfinex, a transaction must be signed by at least two out of these three keys. Assuming the final key is truly kept offline under wraps and only invoked for emergencies, that means the standard process involves using the first two keys. Bitfinex has possession of the first the key** and can produce that signature locally. But getting the second one involves a call to the BitGo API. This call requires authentication. BitGo must only co-sign transactions originating from Bitfinex, which requires that it has a way to ascertain the identity of the caller. The parameters of this authentication protocol are defined by BitGo; it is outside the scope of blockchain or Bitcoin specifications.

Correlated vs independent risks

The assertion that multi-signature improves security was predicated on an assumption: it is more difficult for an attacker to gain control of multiple cryptographic keys compared to getting hold of one. But is that necessary?

gate_multiple_padlocks.jpg

Consider a gate with multiple padlocks on it. Did the addition of second or third padlock make it any harder to open this gate? The answer depends on many factors.

  • Are the locks keyed the same? If they are, there is still a “SPOF” or single-point-of-failure: getting hold of that key makes it as easy to open a gate with 10 locks as it is one protected by a single lock.
  • Are the locks the same model? Even if they have individual keys, if the locks are the same type, they may have a common systemic flow, such as being susceptible to the same lock-picking technique.

The general observation is that multiple locks improve security only against threats that are independent or uncorrelated. Less obvious, whether risks are uncorrelated is a function of threat model. To a casual thief armed with bolt-cutters, the second lock doubles the amount of effort required even if it were keyed identically: they have to work twice as hard to physically cut through two locks. But a more sophisticated attacker who plans on stealing that one key ahead of time, it makes no difference. Armed with the key, opening two locks is not substantially more difficult than opening one. Same holds true if the locks are different but both keys are kept under the doormat in front of the gate. Here again the probability of second lock being breached is highly correlated with the probability that first lock was breached.

When multi-signature does not help

Consider Bitcoin funds tied to a single private-key stored on a server. Would it help if we transferred those funds to a new Bitcoin address comprised of multisig configuration with 2 keys stored on the same server? Unlikely— virtually any attack that can compromise one key on that server is going to also get the second one with equal ease. That includes code execution vulnerabilities in the software running on the box, “evil-maid” attacks with physical access or malicious operators. The difficulty for some attacks might increase ever slightly: for example if there was a subtle side-channel leak, it may now require twice as much work to extract both keys. But in general, the cost of the attack does not double by virtue of having doubled the number of keys.

Now consider the same multi-signature arrangement, except the second private-key is stored in a different server, loaded with a different operating system and wallet software, located in a different data-center managed by a different group of engineers. In this scenario the cost of executing attacks has increased appreciably, because it is not possible for attacker to “reuse” resources between them. Breaking into a data-center operated by hosting provider X does not allow also breaking into one operated by company Y. Likewise finding a remote-code execution vulnerability in the first OS does not guarantee identical vulnerability in the second one. Granted the stars may align for the attacker and he/she may discover find a single weakness shared by both systems. But that is more difficult than breaking into a single server to recover 2 keys at once.

Multi-signature with co-signers

Assuming the above description of Bitfinex operation is correct, Bitfinex operational environment that runs the service must be in possession of two sets of credentials:

  • One of the three multi-signature keys; these are ECDSA private keys
  • Credentials for authenticating to the BitGo API

These need not reside on the same server. They may not even reside in the same data-center, as far as physical locations go. But logically there are machines within Bitfinex “live” system that hold these credentials. Why? Because users can ask to withdraw funds at any time and both pieces are required to make that happen. The fact that users can go to a web page, press a button and later receive funds indicates that there are servers somewhere within Bitfinex environment capable of wielding them.

Corollary: if an attack breaches that environment, the adversary will be in possession of both secrets. To the extent that correlated risks exist in this environment- for example, a centralized fleet management system such as Active Directory that grants access to all machines in a data-center- they reduce the value of having multiple keys.

Rate-limiting

BitGo API designers were aware of this limitation and attempted to compensate for it. Their API interface supports limits on funds movement. For example, it is possible to set a daily-limit in advance such that request to co-sign for amounts greater than this threshold will be rejected. Even if the customer systems were completely breached and both sets of credentials compromised, BitGo would cap losses in any given 24 hour period to that limit by refusing to sign additional Bitcoin transactions.

By all indications, such limits were in effect for Bitfinex. News reports indicate that the attack was able to work around them. Details are murky, but looking at BitGo API documentation offers some possible explanations. It is possible to remove policies by calling the same API, authenticating with the same credentials as one would use for ordinary transaction signing. So if the adversary breached Bitfinex systems and gained access to a valid authentication token for BitGo, that token would have been sufficient for lifting the spending limit.

This points to the tricky nature of API design and the counter-intuitive observation that somethings are best left not automated. Critical policies such as spending limits are modified very infrequently. It’s not clear that a programmatic API to remove policies is necessary. Requiring out-of-band authentication by calling/emailing BitGo to modify an existing policy would have introduced useful friction and sanity checks into the process. At a minimum, a different set of credentials could have been required for such privileged operations, compared to ordinary wallet actions. Now BitGo did have one mitigation available: if a wallet is “shared” among 2 or more administrators, lifting a spending limit requires approval by at least one other admin. The documentation (retrieved August 2016) recommends using that setup:

If a wallet carries a balance and there are more than two “admin” users associated with a Wallet, any policy change will require approval by another administrator before it will take effect (if there are no additional “admin” users, this will not be necessary). It is thus highly recommended to create wallets with at least 2 administrators by performing a wallet share. This way, policy can be effective even if a single user is compromised.

One possibility is Bitfinex only had a single administrator setup. Another possibility is a subtle problem in the wallet sharing API. For example, documentation notes that removing a share requires approval by at least one other admin- ruling out the possibility of going from 2 to 1 unilaterally. But if adding another admin was not subject to same restriction, one could execute a Sybil attack: create another share which appears to be another user but is in fact controlled by the attacker. This effectively grants adversary 2 shares, which is enough to subvert policy checks.

Multi-signature in perspective

Until more details are published about this incident, the source of the single point of failure remains unknown. BitGo has went on the record stating that its system has not been breached and its API has performed according to spec. Notwithstanding those assurances, Bitfinex has stopped relying on BitGo API for funds management and reverted to a traditional, offline cold-wallet system. Meanwhile pundits have jumped on the occasion to question the value proposition for multi-signature, in a complete about-face from 2014 when they were embracing multi-signature as the security silver bullet.  This newfound skepticism may have a useful benefit: a closer scrutiny on key-management beyond counting shares and better understanding of correlated risks.

CP

** For simplicity, we assume there is just one “unspent transaction output” or UTXO in the picture with a single set of keys. In general, funds will be stored across hundreds or thousands of UTXO, each with their own unique 2-of-3 key sets that are derived from a hierarchical deterministic (HD) key generation scheme such as BIP32.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s