Pseudo-Random Number Generator Vulnerability in Bitcoin

Private the Bitcoin keys is an integer value from 1 to 115792089237316195423570985008687907852837564279074904382605163141518161494337 or in HEX 1 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. In the main network of Bitcoin there are addresses beginning with 1: compressed, unpressed; Addresses on 3: SigScript and backward compatible with SegWit, as well as native SegWit addresses beginning with bc1. Besides, there are already about seventy forks, having other prefixes, but the same roots as the main Bitcoin.

Bitcoin addresses are calculated by the cryptographic signature function ECDSA () based on an elliptical curve.

So, let ‘s consider generating a Bitcoin address from a private key.

Private key d – number
The public key Q is an elliptical curve point equal to dG
Where G is the base point of the curve.

  • A random number k, in the range [1, n-1], is selected for the signature.
  • Calculates curve point (x1, y1) = k * G
  • R = x1 mod N is calculated, where N is the order of the curve.
  • Calculated is s = k-1 (H (m) rd) mod N, where k-1 is a number inverse of modulo N to k.
  • H (m) is the hash of the message to be signed.

The signature is pair (r, s).

The variable “k” is randomized and is derived in the ECDSA algorithm from standard operating system libraries.

Thus, only this variable can be affected throughout the function. Which gives two vectors of attack:

Embedded vulnerability in pseudo-random number
And universe luck in which a random number falls out twice

Pseudo Random Number Generator Attack

The first to investigate this problem was published by Nils Schneider in January 28, 2013 on his personal page. But the problem has survived and moreover, has acquired a new scale.

The program attack on the GPS is divided into three types:
Direct cryptographic attack based on algorithm output analysis.

Input-based attacks can be divided into attacks with known input, attacks with reproducible input, and attacks on selected input.

Attacks based on the opening of the internal state in which the attacker knows the initial or initial state of the generator.

This can also include – bookmarks in software, in which the creator of the algorithm knows any of the hashed pseudo-random numbers and subsequent in the chain. Such an algorithm is difficult to determine from the outside as the numbers look evenly distributed over the entire range.

Program vulnerabilities also include weak generation of pseudo-random numbers in individual libraries. Such as SSL, OpenSSL, some Java libraries, JavaScript, etc. Detailed material was repeatedly described in break-in periodicals and over time became examples in cryptography textbooks.

What is the scale of the threat to Bitcoin?

With a complete Bitcoin nodu, 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 number of more than 170 million addresses, and signatures 447 million. Scanning vulnerable addresses into ten streams took a week.

As a result, 1,327 vulnerable addresses with the same signatures were found! The address list can be found at the end of the article.

This means that you can calculate a private key to these addresses, which means you can gain control of the money.

The largest leak occurred in the summer of 2015. JavaScript purse for several hours gave the same value of the variable “k.” Which led to the theft of about 200 Bitcoins!

If you remove the human factor of software vulnerabilities, the probability of matching is about 0.000296868%. Not much at all, but I would very much hate to become such a “lucky man” and lose my money.

How do you fight it?

As we described above, this vulnerability works only when you send payments and generate the same K variable on at least two transactions. Therefore, if you do not create or minimize outbound transactions, there is no threat. Such an idea has long been implemented in Bitcoin protocol BIP 32 (Hierarchical Deterministic Wallets, HD wallet) Hierarchical Deterministic Wallet.

His idea is that a private key is used from which an endless chain of Bitcoin addresses can be obtained. You can use a one-time address to receive each individual transaction. At the same time, the amount of HD wallet balance is the sum of all address chain balances. And in the outgoing transaction, coins are collected from these addresses, making up one outgoing transaction for each Bitcoin address. The delivery will be directed to the new Bitcoin address from the chain of addresses.

Such a scheme of work significantly increases the safety and anonymity of the wallet.

Leave a comment

Your email address will not be published.

Translate »