Further exploration of random risk in Bitcoin signatures

Original title: "Further exploration of random risks in Bitcoin signatures"

Original source: Babbitt

As we all know, everyone should know how important the random k value is when signing Bitcoin transactions. We can even say that the randomness of the k value is as important as the randomness of the private key. Now let's explore this topic in more depth.

An insecure random number generator may cause repeated k values ​​(and of course repeated r values), which may lead to the disclosure of private keys. So it should be okay to ensure that k values ​​are not repeated, right?
Filippo even mentioned that bitcoin-core/qt is not secure enough (the Pull-Request improvement in 2013 has not yet been merged into the main trunk), and of course blockchain.info (because it relies on the browser's random number solution). His view on the k value is "k must be secret and unique. NOT NECESSARILY RANDOM." (The k value must be confidential and unique, not necessarily random).

This statement is not very rigorous, because "confidential and unique" actually means to be as "real" random as possible, or at least cryptographically secure randomness, otherwise how can we talk about "confidential and unique"? Even the RFC6979 specification can be regarded as a specially designed, cryptographically secure random number generation method. For Bitcoin security, the most important thing is still randomness, because we are facing not only the risk of "the same private key using repeated k values ​​in different transactions", but also other potential possibilities of exposing private keys. Security engineers and Bitcoin developers need to learn about these possibilities, and hackers may be busy learning and analyzing historical blockchain data to find opportunities to steal coins.

Possibility 1:

User A and user B use the same wallet solution. Because the random number generator that the wallet relies on is not secure enough, A and B use the same k value to sign transactions. This phenomenon can be seen in the blockchain data as the same r value in transactions signed by two different Bitcoin addresses. In this case, hackers as third-party observers may not be able to do anything with these two addresses, but theoretically, if A records his own k value, he can calculate B's private key, and vice versa. Of course, because no one and no wallet software will record the k value used in the past signature (if it is recorded, it will be more problematic, because if someone obtains the k value you used before, they can reverse your private key and steal your Bitcoin), so in general, the risk of such r value duplication is much smaller than the case of r value duplication of transactions signed by the same address. However, it is not ruled out that hackers have analyzed the random number vulnerability of the wallet and tried to brute force the k value by narrowing the probability space, thereby stealing the Bitcoin assets of the wallet user.

Possibility 2:

User A and user B use the same wallet solution. Because the random number generator relied on by the wallet is not secure enough, A and B have two repeated k values ​​(not repeated with themselves, but repeated with each other), that is, A used k1 and k2, and B also used k1 and k2. In this case, any third-party hacker can reverse the private key of A and B, and the Bitcoin assets of both people will be stolen.

Possibility 3:

Because the random number generator relied on by a certain wallet solution is not secure enough, the k value used when signing the transaction is the same as the private key (wallet software generally uses the same random number algorithm to generate private keys and calculate k values). Don't worry, the coins will be lost as soon as the transaction is broadcast. If the hacker is lucky and the program runs fast, it is even possible to double spend the transaction that has just been broadcast.
Seeing the above possibilities, you should understand how important the randomness of k value is to the security of Bitcoin, in addition to the security of private keys. We all know that Bitcoin private keys can be regarded as 2^256 drawers in the universe (in fact, the range of private keys is smaller than this number). Generating a private key is equivalent to randomly pulling out a drawer and putting money in it. In this way, we can also regard the k value as 2^256 keys in the universe. Every time you spend money, you have to randomly take a key and throw it away after use. Both processes must be guaranteed to be random to avoid being reproduced by others. Repeating may lead to property loss. This is the fundamental reason why Xiao Tai said that "randomness is the lifeblood of Bitcoin."
All these problematic r values ​​have appeared in history. Among them, repeated r values ​​of a single address have directly led to the loss of coins many times (this situation is the easiest for hackers to judge). The possibilities mentioned in this article have also occurred, but it is unknown whether they really caused the user to lose coins, because even if they really lost, the user may not know why, who stole it, and how it was stolen. As mentioned earlier, the probability space of k values ​​is 2^256. Even if everyone on the earth uses Bitcoin for transactions from morning to night every day, there should be no duplication. However, the current order of magnitude of only millions of wallets and tens of millions of transactions has caused so many r value problems, which is enough to show that many current wallet solutions are "too non-random". In a historical block (322925), the r values ​​of many transactions of many addresses were repeated (brother, you used the same k value when signing a Bitcoin transaction, did you write a loop to do it?).
I would like to add one more point here. If everyone uses a cryptographically secure and as "true" random number generator as possible to generate k values, then in theory, the r values ​​on the entire blockchain should also be randomly distributed. As the number of transactions on the blockchain increases, the distribution of r values ​​should become more and more uniform statistically. However, the reality is that the distribution of r values ​​on the entire blockchain is very concentrated (probably due to the unsafe random number solutions used by some wallets). As the number of transactions continues to increase, the probability of colliding with problematic addresses is also increasing. This is also a huge hidden danger for the future development of Bitcoin, and it should be given enough attention by wallet solution providers and Bitcoin companies. Maybe hackers pay more attention to it than you do!
Finally, let me ask you a question: Are your random numbers safe?

Original link: https://www.8btc.com/article/36023