Finding collisions in SHA-256 on the Node.js platform using Bitcoin Hasher
Before starting reading, I want to warn you that all the definitions described below and the research I have done are for informational purposes only and are incomplete or inaccurate.
While writing this article, many important aspects have been omitted or not supplemented due to the magnitude of the topics that were covered. Based on the information I have provided, a list of materials will be given that can be consulted for a deeper dive into such sciences as data protection and cryptography.
To understand the operation of the Bitcoin Hasher application, the content of the article was divided into small sections:
- A bit of theory
- A little about SHA-2
- A little about Blockchain
- Bitcoin Hasher
- Useful materials
1. A bit of theory
An encryption algorithm is a function that accepts a string of arbitrary length as input, which, using a certain mathematical algorithm, converts an INPUT (a string of arbitrary length) into an OUTPUT (a string of fixed length). This conversion process is called hashing or encryption. The end result of encrypting any input information is called a digital fingerprint (digest).
The goal of any algorithm is to compress, scatter and shuffle the input information. Because how much it is converted, not only the security of this very fingerprint, but also the hashing algorithm through which the fingerprint was formed, will depend. An illustrative conversion process is shown in the diagram:
When transferring confidential information, it becomes necessary to ensure effective protection of input data from an attacker, therefore, regardless of the method of its implementation, any modern cryptographic information protection system must comply with a number of requirements:
- As a result of the transformation, the resulting fixed key must provide reliable information protection
- With a slight change in the input information passed through the hash function, a significant change in the output value must be observed
- Absence of any dependence between input and output information
- Difficulty or inability to select an input value for a digital fingerprint
The purpose of encrypting information when choosing the most stable and new standard is to preserve and irreversibly transform the original data, which, in my opinion, is one of its most important advantages. The disadvantage is the appearance of inevitable collisions during conversion. Suppose there are two input blocks (x) that differ in information, which need to be "passed" through the hashing function (H) and get a fixed length of the fingerprint (y). If the blocks (x) passing through the functions (H) will have the same fingerprints (y), then a collision is formed as a result of the work performed:
2. A little about SHA-2
At the time of this writing, one of the most efficient hashing algorithms is the SHA-2 (Secure Hash Algorithm Version 2) family of cryptographic information security systems.
All functions that are included in this "family", namely: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 and SHA-512/224 are built on the basis of the Merkle-Damgard structures, which affects their real resistance to various types of attacks. The principle of operation of the absolutely above information algorithms is to split the input parts of the same size, each of which is subjected to a selected one-way compression function. The key advantage with this approach is algorithmic one-sidedness, that is, the impossibility of recovering any initial data based on the result obtained without the presence of a generated key.
This elegant solution was introduced to replace the outdated SHA-1 by the US National Security Agency in 2002 for more secure encryption of sensitive data. One of the most applicable algorithms today is SHA-256; it gained its popularity for its implementation in various systems thanks to such large-scale projects as Bitcoin and Blockchain (we will dwell on Blockchain in more detail below). All presented functions work well and are used to this day.
Below is the result of the work of each of the algorithms that are part of the SHA-2 family:
SHA-224:
Hello World ! -->
2c8abaa6a94a76fe9c6005994567d67a1631bc90dfca267099dc750f
SHA-256: Hello World ! -->
07f2bdef34ed16e3a1ba0dbb7e47b8fd981ce0ccb3e1bfe564d82c423cba7e47
SHA-384: Hello World ! -->
67e60f9ce837caa3ca82550f0dfcbde1b8b8a7c1605fa8d115bcc2314204fd95f5f607306622c38c0205de7df6d426d8
SHA-512: Hello World ! -->
feab0028f1142d420a1425d1dd5b518225b4523aa1cff63385ece3411318819f5ec83042ccb79d81f20e4a243866886ca3ae3026153acff8e126c0e89631502e
SHA-512/256: Hello World ! -->
a70e1d1268e729e90db4c0834214f449c8e7b652777f40a8a0d26f2372e39ca7
SHA-512/224: Hello World ! -->
7cc0d174b7ce522eff7d7ee59789e420d75d0244f006ef8ce0f4efb7
3. A little about Blockchain
To understand how the application works, I must write a few words about the Blockchain network, since it is it that is based on working with the SHA-256 algorithm and is also an important "input information provider" for Bitcoin Hasher.
Blockchain is a decentralized, continuous, sequential chain of blocks, built according to certain rules, containing information about all transfers of means of payment in digital currency that were made using this network.
Having plunged into the history of the formation of technology, the work and research of scientists for convenience were divided into several stages:
- (1991): Reflections on Blockchain as a secure repository of digital documents without the possibility of forging or returning them was described in the works of Stuart Hubber and W. Scott Stornett in 1991. Such a brilliant and persistent idea was formulated long before the advent of the Blockchain network.
- (1992): For the reliable operation of the Blockchain, the so-called Merkle tree was incorporated into the design of the future network, which subsequently led to the establishment of connections between all data records in the entire chain of the global Blockchain ecosystem.
- (2008): A certain person or organization under the pseudonym Satoshi Nakamoto publishes a document titled: "Bitcoin: a peer-to-peer electronic cash system". This document will subsequently become the starting point for the creation of the current Blockchain for the Bitcoin currency.
- (2009): In an alternative to the current financial system, Satoshi Nakamoto implements a decentralized, uncontrolled network of one state unit, Blockchain to work with the world's first digital currency, Bitcoin.
The software solution of the product was designed in such a way that any interference in its work will lead absolutely nowhere, since the paradigms that were laid in the Blockchain from its very foundation remain persistent, relevant and applicable to this day.
All information about transfers in the Blockchain is stored in the form of blocks, each of which is an object and has the following form (Example of block number 685466, created 2021-05-30 08:05):
{
"hash": "00000000000000000009fde417c010d7ec9ffb25a268f4b0667681ed9b74cf65",
"ver": 536870916,
"prev_block": "00000000000000000007b7241ee4748769266870bdab4e5306379739db07c466",
"mrkl_root": "8d620000ab7ba942a165ed49be563a31c33269ce8f2d40b8317784475a543fe7",
"time": 1622351111,
"bits": 386752379,
"nonce": 3069945434,
"n_tx": 996,
"size": 1602081,
"block_index": 685466,
"height": 685466,
"tx": [
"--Array of Transactions--"
]
}
Reliable information about all blocks and transactions can be obtained on the Blockchain website, in the API section: https://www.blockchain.com/ru/api/blockchain_api.
Having gone from ideas and reflections to an independent technology, Blockchain has become what we know it today. The remaining stages of further development and formation, up to the present day, are brought together in the constant support of a stable and uninterrupted work process for all users of the decentralized network.
4. Bitcoin Hasher
Bitcoin Hasher is a small collision detection application for the SHA-256 encryption algorithm.
The search is performed by creating the so-called "double encryption" of digital fingerprints. That is, from the previously encrypted information received from the Blockchain, the application generated a similar fingerprint for each of the transactions using SHA-256.
The work algorithm was as follows:
- On the JavaScript client, I made a new XHR request to the Blockchain API of the following form: https://blockchain.info/rawblock/ (a unique block identifier entered into the input of the application).
- After sending a request to the Blockchain servers, in response, Bitcoin Hasher received detailed information about the block, an example of which I have already described.
- From the "tx" field, the application "took" an array of digests of confirmed transactions in a specific block, and based on them, Node.js generated exactly the same digital fingerprint for each of the transactions.
- In parallel with the generation from the "prev_block" field (which includes the value of the identifier of the previous block) on the JavaScript client, it created a new XHR request of the following form: https://blockchain.info/rawblock/ (unique identifier of the previous block). This process was looped until all blocks and transactions were processed.
- When a client-server application is running in parallel, all INPUT-OUTPUT data is written to the db_blocks / block-NUMBER_BLOCK.txt folder.
- It remains to find INPUT, which is the key to the OUTPUT fingerprint you are interested in.
Useful materials to familiarize yourself with the application:
- Repository Bitcoin Hasher: https://github.com/ArtCODE-web/Bitcoin-Hasher
- An example of the formation of "double encryption", for a block with a height of 665862 in the Blockchain: https://github.com/ArtCODE-web/Bitcoin-Hasher/blob/master/db_blocks/block-665862.txt
- Bitcoin Hasher workflow:
5. Useful materials
- Applied Cryptography - Book, Bruce Schneier
- Blockchain Basics: A Non-Technical Introduction in 25 Steps - Book, Daniel Drescher