Bringing Cryptocurrencies to the Next Stage Through Formalizing Their Cryptographic Security Models
Insight from our technical advisor Dr. Zhen Liu.
As the word ‘cryptocurrency’ implies, cryptographic primitives are the fundamental components of cryptocurrencies. In particular, as far as it goes, all cryptocurrencies are using some sort of Digital Signature schemes for authorizing and authenticating transactions, and combine the application of some Hash functions for enforcing order and timestamp on transactions and/or blocks. More specifically, while Bitcoin and Ethereum, and many other conventional cryptocurrencies, are using a standard signature scheme, say ECDSA, to achieve the preliminary authorization and authentication, some new cryptocurrencies are using more advanced and complicated cryptographic primitives to achieve stronger privacy and/or security. For example, Monero’s cryptographic tools include Linkable Ring Signature, Commitment Scheme, and non-interactive Diffie-Hellman Key Exchange; while Zerocash uses ZK-SNARK, Key-private Public Key Encryption, Commitment, etc.
When only a stand-alone cryptographic primitive is used, like in Bitcoin and Ethereum, we have relatively high confidence on their security due to their simplicity and the ordinary application of the cryptographic primitive. However, when multiple cryptographic primitives are put together and work in a tightly-coupled fashion, a natural question to ask is whether their security properties, which are analyzed separately, still hold? For example, many cryptocurrencies use Stealth Address mechanism to derive the verification keys and corresponding signing keys from master keys, and then use these derived keys to sign and verify transactions. This might triggernew security vulnerabilities or concerns, as the underlying signature scheme’s security is analyzed only in the setting that the signing and verification keys are generated independently from each other by running the Key-Generation algorithm. From the views of both cryptography and cryptocurrency, we cannot be too careful of the security, since any minor security vulnerability may incur devastating consequences.
We have to consider the security properties in a uniform model where the cryptographic components of the cryptocurrency are analyzed as a whole. This includes two steps:
- formalize the security model, and
- prove the security of a concrete scheme.
Below are two examples of the security of some widely used deterministic wallet algorithm and stealth address algorithm.
A Potential Vulnerability in Deterministic Wallets
In a Deterministic Wallet, all public verification keys and secret signing keys can be deterministically derived from a `seed’. Fig. 1 shows the essence of the deterministic wallet, which has been accepted as Bitcoin standard BIP32. Deterministic Wallets are common in the community due to its appealing applications, including ‘trustless audits’ and ‘treasurer’ use cases.
In particular, if the owner of a deterministic wallet reveals his master public key to a third-party auditor, the auditor can identifyall the transactions related to the corresponding wallet, since the auditor can compute all the public verification keys in the wallet by using the master public key and some indexing information. The user is also assured that his coins are secure since the master secret key or derived signing keys could not be computed from the master public key and derived public keys.
The `treasurer’ use case means that in a large company, the treasurer can create child key pairs for each department within the company, so that the treasurer will have the master public/secret key, while each department will only have the key to their own part of the funds.
The community has noticed that the deterministic wallet algorithm cannot be used to simultaneously implement the treasurer and the auditor use cases, since otherwise, the auditor (with the master public key MPK) may collude with some department manager (with a derived secret key, say ski) to compute the master secret key as s=ski — H(MPK||i) and steal all the funds of the company.
A Potential Vulnerability in Stealth Addresses
The goal of stealth addresses is to send coins to a certain publicly visible master key in such a way that this key does not appear in the blockchain at all, and hence a user’s privacy can get ensured. Fig.2 shows the stealth address algorithm which is widely used in cryptocurrencies, for example, in Monero.
This algorithm also suffers from a vulnerability, which may cause fatal damages. Consider the example in Fig. 2, the payer Bob derives two public verification keys
and
for the same payee Tom with master public key (A, B). Suppose Bob somehow compromises one of the two secret signing keys, say
Note that Bob knows the value of
he can compute the value of b by
So, Bob can compute the secret signing key corresponding to
by
since he also knows the value of
Furthermore, if Bob colludes with other payers who sent coins to Tom, they can compromise all the secret signing keys for the related coins.
For example, through colluding with Alice in Fig.2, Bob can compute the secret signing key corresponding to (R,S) by
where r is provided by Alice. In fact, as long as one derived secret signing key is compromised, the corresponding master secret key is not safe, and all coins to the public verification keys derived from the corresponding master public key in the past and the future are in danger of being stolen.
When such a stealth address algorithm is used, users must be very well aware of that, they not only need to keep their master secret keys safe, but should also keep all the derived signing keys for their coins safe, even after the coins have been spent, since leaking one derived signing key may result in leading towards the complete leakage of all the signing keys derived from the same master key. However, in practice keeping all the derived signing keys safe is a difficult task, since signature computation is frequently performed on insecure devices (e.g., mobile phones) operating in an environment where the private (signing) key is likely to be exposed.
A Secure Signature Scheme for Secure Deterministic Wallets and Stealth Addresses
It is worth mentioning that, while the aforementioned vulnerability in deterministic wallet has been widely noticed in the community, the above vulnerability in stealth address is not noticed until a recent work (“Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key”, published in the proceedings of EuroS&P 2019).
It is indeed not easy to identify this vulnerability intuitively, until a security model is formalized for signature schemes with keys generated using the stealth address mechanism.
When formalizing the security model for a cryptographic primitive, a basic assumption is the famous Kerckhoffs Principle, which says that the system should be considered to be completely known to attackers and only the key is secret.
In the setting of stealth addresses, we can assume that the master secret key is safe, but we must consider the possibility that the derived signing keys are compromised somehow. Formalizing the security model is not only a requirement for security, but is also a powerful methodology to facilitate us in capturing possible attacks, and result in practically secure systems.
In the aforementioned work, a new signature primitive is formalized, where anyone can derive an arbitrary number of verification keys from a master public key without requiring any interaction, while only the owner of the master public key can generate the corresponding signing keys, also without interactions. On the privacy, neither the verification keys nor the corresponding signatures leak any information about the corresponding master public key.
On the security, for any specifically derived verification key DVK, even if an adversary compromises all other derived signing keys, the adversary cannot forge a valid signature with respect to DVK. As a result, a signature scheme, which is proven secure and satisfies the underlying security model can then be used to implement a SECURE deterministic wallet and the stealth address.
