Lack of Randomness: Why Hackers Love It

Random numbers, perhaps have different analogues among the humans and machines. Tossing a coin is assumed to be truly random for humans with the uniform distribution and probability of 0.5 to get heads or tails. However it’s a different story for machines.

Determinism vs. Randomness

Machines are created in a way to get an input, process the input and release the output. They only follow the patterns that are programmed.

“Machines are deterministic, which means that if you ask the same question you’ll get the same answer every time,” says Professor of Computer Science and Engineering at MIT’s Computer Science and Artificial Intelligence Laboratory, Steven Ward. “In fact, such machines are specifically and carefully programmed to eliminate randomness in results. They do this by following rules and relying on algorithms when they compute.”

Ward then raises a very important question:

 “So what happens to our random number then when it comes to a machine? In fact many things are built based on the idea of generating a random number. Consider casinos using old-fashioned slot machines. Can they work without generating a random number? How can these machines generate random numbers then?”

In fact, a simple answer to the latter question is that they do not. Machines do not generate truly random numbers yet. However, instead of taking an input (seed) from users to generate a random number, machines can get that from many other unpredictable processes such as thermal or atmospheric noise, rather than from human-defined patterns. That is why we always call any machine generated random number a pseudo random number. There are plenty of interesting random number generation techniques that can be used at the random.org website.

Unfortunately, having an element of randomness (entropy) might cause some problems. Elliptic curve digital signature algorithm (ECDSA), which is the core of cryptography in Bitcoin, suffers from this pseudo random number generation by its nature.

Every transaction in Bitcoin is required to be signed by the owner who owns the private keys. Apart from the private keys in each signature in ECDSA, the user should generate a random number k, which should really be generated randomly for every single transaction that the user makes. In fact, if the same private key of a user with the same random number k is used twice, anyone can calculate his private key and eventually spend his money. This applies to any wallets in Bitcoin including offline storages.

Security holes

This lack of randomness has caused the Bitcoin community a lot of loss. Bitcoin exchange Bitstamp confirms the loss 18,866 BTC earlier this year and Blockchain.info, one of the most reputable bitcoin wallet providers, has lost some of its customer’s money in December 14 due to this very simple issue.

Generally this issue has not only affected the Bitcoin users but also many other applications and certificates, which use ECDSA. In December 2010, Sony announced a hack to its PS3 users. Sony was actually using the same random number for each signature, which was a big failure in the implementation of ECDSA. The next year in 2011, OpenSSL suffered from the same issue by timing attacks.

Moreover, any linear relation between the two random number k1 and k2 in two different signatures compromises the user’s private key. Stephan Verbucheln in January of 2015 released his paper on how an unreliable service can make a random number generator, which generates random numbers that are indistinguishable where only the service provider can recover the random numbers.

Solution

So how does a user make sure that this number is generated randomly?

The answer is that as long as there is a random number generator in the process, user can’t trust any random number generator.

So does this mean that Bitcoin is not secure since it uses ECDSA?

I’m glad to say that there is a solution for this issue and it’s using the RFC 6979 standard to generate deterministic random numbers. A deterministic random number is created deterministically, just what a machine likes. Input goes through a function and gives you an output, generating the random number.

The reason that a hacker can’t generate this deterministic random number is that the input for generating this number consists of the user’s private key and the function is a hash function, which is irreversible. Therefore, we can say that the output k is random and this mechanism is safe.

Services such as Trezor and Mycelium have already implemented RFC 6979 standard into their systems, which makes them resistant against randomness attacks. Hopefully, with greater awareness of people, we are not going to see any more incidents caused by a careless random number generation of ECDSA in future.

Did you enjoy this article? You may also be interested in reading these ones:

Self-Owning Computers Can Beat ‘Skynet’ – Mike Hearn on the Internet of Things (Op-Ed) Blockchain Technology Could Have Prevented Louisiana’s Deadly Bacteria Leak