Bitcoin Pseudo Random Number Generator Vulnerability
Private keys Bitcoin - is an integer from 1 to 115792089237316195423570985008687907852837564279074904382605163141518161494337 or HEX 1 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. In the main Bitcoin network, there are addresses starting with 1: compressed, uncompressed; 3 addresses: SigScript and backward compatible with SegWit, as well as native SegWit addresses starting with bc1. In addition, there are already about seventy forks with different prefixes, but the same roots as the main Bitcoin.
Bitcoin addresses are calculated by the cryptographic signature function ECDSA () based on an elliptic curve.
So, consider the generation of a Bitcoin address from a private key.
The private key d is the number. The
public key Q is the point of the elliptic curve, equal to dG,
where G is the base point of the curve.
The signature is a pair (r, s).
The variable “k” is random and is obtained in the ECDSA algorithm from the standard libraries of the operating system.
Thus, only the variable can be affected in the entire function. What gives two attack vectors:
This problem was first investigated and published by Nils Schneider on January 28, 2013 on his personal page. But the problem persists and moreover, has acquired a new scale.
The program attack on the PRNG is divided into three types:
Direct cryptographic attack based on the analysis of the output of the algorithm.
Attacks based on input data can be divided into attacks with known input data, attacks with reproducible input data, and attacks on selected input data.
Attacks based on the opening of the internal state in which the attacker knows the initial or initial state of the generator.
Also here it can be attributed - bookmarks in software, in which the creator of the algorithm knows any of the hashed pseudo-random numbers and the subsequent ones in the chain. Such an algorithm is difficult to determine from the outside, since the numbers appear to be evenly distributed over the entire range.
Software vulnerabilities also include weak pseudo-random number generation in individual libraries. Such as SSL, OpenSSL, some Java libraries, JavaScript, etc. Detailed materials have been repeatedly described in periodicals on hacking and eventually became examples in cryptography textbooks.
Having a full Bitcoin node, you can compare and group all network transactions. It is enough to compare the variable "k" in all transactions at each address and find duplicates.
The first time we did the reconciliation at the end of 2016, then the database was more than 210 million addresses, transactions with a total of more than 170 million addresses, and signatures 447 million. Scanning vulnerable addresses in ten streams took a week.
As a result, 1327 vulnerable addresses were found with identical signatures! A list of addresses can be found at the end of the article.
This means that you can calculate the private key to these addresses, and therefore get control of the money.
The largest leak occurred in the summer of 2015. JavaScript Blockchain.info wallet several hours issued the same value of the variable "k". What led to the theft of about 200 Bitcoins!
If the human factor of software vulnerabilities is removed, the probability of coincidence is approximately 0.000296868%. Not much at all, but I really wouldn’t like to become such a “lucky man” and lose my money.
As we described above, this vulnerability only works when sending payments and generating the same “K” variable, in at least two transactions. Therefore, if you do not create outgoing transactions or minimize their number, then there is no threat whatsoever. Such an idea has long been implemented in the Bitcoin protocol BIP 32 (Hierarchical Deterministic Wallets, HD wallet) Hierarchical Deterministic Wallet.
His idea is to use a private key from which you can get an endless chain of Bitcoin addresses. You can use a one-time address to receive each individual transaction. At the same time, the HD wallet balance amount is the sum of all balances of the address chain. And for an outgoing transaction, coins are collected from these addresses, making up for one outgoing transaction for each Bitcoin address. The handover will be sent to the new Bitcoin address from the address chain.
Such a scheme of work significantly increases the security and anonymity of the wallet.
References:
[1] ECDSA - Application and Implementation Failures, Markus Schmid, UC SANTA BARBARA, CS 290G, FALL 2015.
[2]Nils Schneider: Recovering Bitcoin private keys using weak signatures from the blockchain, Blog entry, 28 January 2013.
[3] Private Key Recovery Combination Attacks
[4] List of vulnerable addresses and total balance
Bitcoin addresses are calculated by the cryptographic signature function ECDSA () based on an elliptic curve.
So, consider the generation of a Bitcoin address from a private key.
The private key d is the number. The
public key Q is the point of the elliptic curve, equal to dG,
where G is the base point of the curve.
- To sign a random number k is chosen, in the range [1, n-1].
- Calculate the point of the curve (x1, y1) = k * G
- Calculate r = x1 mod N, where N is the order of the curve.
- Calculate s = k-1 (H (m) + rd) mod N, where k-1 is the number inverse of the modulus of N to k.
- H (m) - hash of the message being signed.
The signature is a pair (r, s).
The variable “k” is random and is obtained in the ECDSA algorithm from the standard libraries of the operating system.
Thus, only the variable can be affected in the entire function. What gives two attack vectors:
- pseudo-random number vulnerability
- and universal luck in which a random number drops twice
Pseudorandom number generator attack
This problem was first investigated and published by Nils Schneider on January 28, 2013 on his personal page. But the problem persists and moreover, has acquired a new scale.
The program attack on the PRNG is divided into three types:
Direct cryptographic attack based on the analysis of the output of the algorithm.
Attacks based on input data can be divided into attacks with known input data, attacks with reproducible input data, and attacks on selected input data.
Attacks based on the opening of the internal state in which the attacker knows the initial or initial state of the generator.
Also here it can be attributed - bookmarks in software, in which the creator of the algorithm knows any of the hashed pseudo-random numbers and the subsequent ones in the chain. Such an algorithm is difficult to determine from the outside, since the numbers appear to be evenly distributed over the entire range.
Software vulnerabilities also include weak pseudo-random number generation in individual libraries. Such as SSL, OpenSSL, some Java libraries, JavaScript, etc. Detailed materials have been repeatedly described in periodicals on hacking and eventually became examples in cryptography textbooks.
What is the scale of the threat to Bitcoin?
Having a full Bitcoin node, you can compare and group all network transactions. It is enough to compare the variable "k" in all transactions at each address and find duplicates.
The first time we did the reconciliation at the end of 2016, then the database was more than 210 million addresses, transactions with a total of more than 170 million addresses, and signatures 447 million. Scanning vulnerable addresses in ten streams took a week.
As a result, 1327 vulnerable addresses were found with identical signatures! A list of addresses can be found at the end of the article.
This means that you can calculate the private key to these addresses, and therefore get control of the money.
The largest leak occurred in the summer of 2015. JavaScript Blockchain.info wallet several hours issued the same value of the variable "k". What led to the theft of about 200 Bitcoins!
If the human factor of software vulnerabilities is removed, the probability of coincidence is approximately 0.000296868%. Not much at all, but I really wouldn’t like to become such a “lucky man” and lose my money.
How to deal with it?
As we described above, this vulnerability only works when sending payments and generating the same “K” variable, in at least two transactions. Therefore, if you do not create outgoing transactions or minimize their number, then there is no threat whatsoever. Such an idea has long been implemented in the Bitcoin protocol BIP 32 (Hierarchical Deterministic Wallets, HD wallet) Hierarchical Deterministic Wallet.
His idea is to use a private key from which you can get an endless chain of Bitcoin addresses. You can use a one-time address to receive each individual transaction. At the same time, the HD wallet balance amount is the sum of all balances of the address chain. And for an outgoing transaction, coins are collected from these addresses, making up for one outgoing transaction for each Bitcoin address. The handover will be sent to the new Bitcoin address from the address chain.
Such a scheme of work significantly increases the security and anonymity of the wallet.
References:
[1] ECDSA - Application and Implementation Failures, Markus Schmid, UC SANTA BARBARA, CS 290G, FALL 2015.
[2]Nils Schneider: Recovering Bitcoin private keys using weak signatures from the blockchain, Blog entry, 28 January 2013.
[3] Private Key Recovery Combination Attacks
[4] List of vulnerable addresses and total balance