How to steal the key of Ethereum wallet? (Part1)

Summary:

A blockchain is a public transaction book that is verified by signing and proving transaction data ownership using a public ac and private key. The popular blockchain may have hundreds of millions of transactions, including – Bitcoin, Waves, Ripple, ZCash, Monero and Ethereum (Ether Place).

Currently, there are 345 million transactions in Ethereum involving 47 million pairs of key pairs. The probability of the newly generated key being duplicated with the existing key is approximately one of the 256th power of 2, which is almost impossible.

In this paper, we studied even with this statistically small probability event, ISE found 732 private keys and their corresponding public keys, which submitted 49,060 transactions to Ethereum. In addition, it was determined that 13319 Ethereum was traded to an invalid destination address, or a wallet from a weak key. The total value of these ETHs during the heyday of the Ethereum market was $18,899,969.

In the process, we find that funds from these weak key addresses are being stolen and sent to a destination address that belongs to a working individual or group whose purpose is to crack or collect the private key and obtain these funds. On January 13, 2018, the "blockchain robber" held 37,926 ETH, valued at $54,343,407.

introduction:

The focus of this article is to crack the private key entrusted to the Ethereum transaction. As mentioned earlier, the probability of encountering a private key corresponding to another's Ethereum address is about 256 of 256.

Covering only 1% of the key space, even if the computing resources we use allow us to generate 100 trillion keys per second, it will take several years.

However, instead of trying to search for random private keys violently, we have devised ways to discover keys that might be generated using an error code, an incorrect random number generator, or a combination of the two. The following sections outline how to generate an Ethereum address and crack the private key that was not generated using the best method.

background:

Ethereum uses a cryptographic method of elliptic curves to generate a public/private key pair. A point on the secp256k1 ECDSA curve is calculated using a 256-bit private key to generate a public key. Then use the keccak256 hash function to generate the public key.

The hash value is truncated to the lower 160 bits to generate the Ethereum address. The Ethereum address cannot be reversed to the public key, nor can it be used in any way to generate its underlying private key using the Ethereum address.

Given a randomly generated private key whose valid range is 1 to the maximum value defined by the secp256k1 curve, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140, the Ethereum address can be calculated by taking the lower (rightmost) 160 bits of the keccack256 hash function of the public key.

defined as:

Figure 1 illustrates the workflow from a randomly generated 256-bit private key to generating an Ethereum address.

Figure 1: An example flow from a private key to generating an Ethereum address.

Knowing this algorithm, our research goal is to find Ethereum addresses that are not generated with a reasonably correct algorithm, or addresses that are not generated correctly from non-random private keys.

experimental design:

Ethereum allows anyone to look up an address for information such as balances, ongoing transactions, and determined transactions. This is done by querying an Ethereum node that runs locally or remotely.

For ease of use, some online services encapsulate the underlying data through a web interface. Etherscan is such a tool that can query the public Ethereum address from the above example:

l A99FDD90FF61DD08CF049155D18E086F7806641B

You can go to https://etherscan.io/address/A99FDD90FF61DD08CF049155D18E086F7806641B

For enquiry, there is no doubt that this address has 0 transactions.

Figure 2: Etherscan.io Query A99FDD90FF61DD08CF049155D18E086F7806641B Since Ethereum has recorded nearly 50 million public Ethereum addresses, due to some factors, we may encounter weak or lack of random keys. An obvious example is key truncation.

That is, a random 256-bit private key is generated, but due to the encoding/compiler/framework or other unknown errors, only a small portion of the functionality is used.

For example, a 256-bit private key with values ​​of:

l 0x47579DA2BEA463533DBFAD6FCF8E90876C2FE9760DC1162ACC4059EE37BDDB5C

If truncated to 32 bits, you will get the following key:

l 0x0000000000000000000000000000000000000000000000000000000037BDDB5C

In the experiment, we chose a private key of 1, simply because it may be the lower bound of the private key of secp256k1, and it is also in the range of 1 to 2 32 -1 of the 32-bit truncation key.

We use the private key 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

Derived Ethereum Address 0x7e5f4552091a69125d5dfcb7b8c2659029395bdf

As mentioned earlier, recall the infinitesimal probability that two Ethereum users generate the same private key. Suppose at least one user randomly generates them. The address should not coincide with a key randomly generated by another Ethereum user.

This is irrelevant whether the key space is explored from the lower bound, the upper bound, or a key using a π-bit key, and a random number.

Instead, using Etherscan.io to query the transaction data at the above address from the 0x01 private key, we will see evidence that there is a conflict with the key we intentionally generated. (For example: this key is already in use)

Figure 3: Etherscan.io query 7e5f4552091a69125d5dfcb7b8c2659029395bdf

ISE shows that there are 592 transactions on the Ethereum address derived from the private key of 0x01, and there is currently no ETH on this address. If a private key is randomly selected, the chances of others generating the same key are about one of 256 powers of 2, which is actually a 0% chance.

Since the probability of randomly generating a private key of 0x01 is approximately zero, we must assume that this value was chosen deliberately or due to an error. The following sections detail our research to understand and investigate how widespread weak key generation is in Ethereum.

area of ​​research:

Research attempts to locate Ethereum addresses based on the use of weak keys and to study the use of these addresses. While it is unlikely that the appropriate code will be used to generate weak keys in a normal environment, it is still assumed that weak private keys may be generated by coding errors or operating system, device, and execution environment errors, and these problems are common. In addition to key truncation, other common errors that can weaken a 256-bit key include:

  • Code logic error
  • Type confusion
  • Entropy error
  • Random strategy error
  • Handling exceptions
  • Memory reference error
  • Memory leak
  • Seed reuse
  • Compromise on malware

Due to the limited computing resources, it is not feasible to enumerate all keys even in a smaller 64-bit key space.

So instead turn to the achievable goal: enumerate the keys that will appear in the smaller 32-bit subset of the 256-bit private key. This is equivalent to 4,294,967,295 private keys, for which you need to calculate the corresponding public Ethereum address and query the blockchain.

method:

To perform a batch scan of possible Ethereum addresses, it is impractical to query online services such as Etherscan and even abuse resources.

Instead, a hash map of all public Ethereum addresses is generated in memory, and the data structure of each enumerated key is queried in this memory.

In a mid-range notebook, its performance is about 15,000 keys per second per core and its query. The bottleneck is the generation of the ECDSA private key to the public key.

Focus on the eight 32-bit "sub-regions" in the 256-bit key space, where it may be observed that the Ethereum address being used is derived from the weak private key.

It is expected that the lower 32-bit portion of the ciphertext space is most likely to contain a weak key. In order to take into account the byte order, the higher 32-bit portion is also scanned, and for the sake of completeness, each different portion of the 256-bit key space is tested using a 32-bit window that may generate a key.

To illustrate the scanned area, Figure 4 below depicts each area identified for the enumeration. When enumerating the 32-bit key space of each area (A to H), the remaining 224 bits of the 256-bit key are set to 0x00.

Figure 4: The 256-bit key space is represented by the H to A part.

This gives eight possible areas, each with a combination of 2 and 32 minus one (about 4.3 billion). Converting the zone definition to an explicit private key range, scanning and testing these key ranges for trading activities on the Ethereum blockchain:

Group A:

0000000000000000000000000000000000000000000000000000000000000001 to

00000000000000000000000000000000000000000000000000000000FFFFFFFF

Group B:

0000000000000000000000000000000000000000000000000000000100000000 to

000000000000000000000000000000000000000000000000FFFFFFFF00000000

Group C:

0000000000000000000000000000000000000000000000010000000000000000 to 0000000000000000000000000000000000000000FFFFFFFF0000000000000000

Group D:

0000000000000000000000000000000000000001000000000000000000000000 to

00000000000000000000000000000000FFFFFFFF000000000000000000000000

Group E:

0000000000000000000000000000000100000000000000000000000000000000 to 000000000000000000000000FFFFFFFF00000000000000000000000000000000

Group F:

0000000000000000000000010000000000000000000000000000000000000000 to 0000000000000000FFFFFFFF0000000000000000000000000000000000000000

Group G:

0000000000000001000000000000000000000000000000000000000000000000 to 000000000FFFFFFFF000000000000000000000000000000000000000000000000

Group H:

0000000100000000000000000000000000000000000000000000000000000000 to FFFFFFFF00000000000000000000000000000000000000000000000000000000

Although the above ciphertext space constitutes an infinitesimal part of 256-bit ciphertext space, the random key may affect the randomness of 256-bit ciphertext due to errors or other factors, so the private key may exist in these areas.

Source: Gemi chain