What Is a Message “Fingerprint”?

1. Why Do We Need “Fingerprints”?

When police investigate crimes, they often work with a suspect’s fingerprints. A fingerprint can determine, from a biological perspective, whether it belongs to a particular person. In that sense, a fingerprint is something unique to an individual; through it, you can identify exactly one corresponding person.

During network transmission, there may be a man in the middle. This led people to the following idea: can we find a “fingerprint” for a message? That way, we can know who sent the message and avoid man-in-the-middle attacks.

2. One-Way Hash Functions

Developers use git commands in their day-to-day work. The git diff command can compare two commits and show the differences between them. Identical files are not displayed. So how does git diff compare two files? If a file is huge, is there a simple and fast way to determine whether it has been modified?

This is where a file’s “fingerprint” becomes useful. Instead of comparing two files line by line, we now only need to compare their “fingerprint” information. If a single fingerprint can verify file integrity, that is extremely convenient!

A one-way hash function is a technique for collecting a file’s “fingerprint”. The hash value generated by a one-way hash function is equivalent to the “fingerprint” of a message. A one-way hash function has one input and one output: the input is called the message, and the output is called the hash value. A one-way hash function computes a hash value from the contents of the message, and that hash value can be used to check the integrity of the message.

The message here can be understood more broadly: it may be an image or audio. A one-way hash function does not need to care about the actual meaning represented by the message. In the eyes of a one-way hash function, there is only a stream of 0s and 1s.

The length of the hash value computed by a one-way hash function has nothing to do with the length of the message. Taking SHA-256 as an example, the hash value it computes is always 256 bits (32 bytes).

A one-way hash function has the following properties:

1. It computes a fixed-length hash value from a message of arbitrary length

2. It can compute the hash value quickly

3. Different messages produce different hash values

The last property is the most important. If two different files produced the same hash value, the one-way hash function would lose its purpose. In practice, the situation where two different messages produce the same hash value is called a “collision”. A hash function needs to ensure that, without deliberate interference, collisions do not occur. One-way hash functions used in cryptography must have collision resistance.

A one-way hash function must ensure that it is extremely difficult to find another message with the same hash value as a given message. This property is called weak collision resistance, and all one-way hash functions must have it.

It is extremely difficult to find two different messages that have the same hash value. This property is called strong collision resistance. Here, the hash value can be any value.

One-way hash functions used in cryptographic systems must have not only weak collision resistance, but also strong collision resistance.

Weak collision resistance and strong collision resistance are relative concepts here; “weak” does not mean “so weak that it has no collision resistance”!

4. One-wayness

A one-way hash function must have one-wayness, which means it is infeasible to derive the message from the hash value.

As shown above, there is no path for computing the message in reverse. This is also where the term “one-way” in one-way hash function comes from. One especially important point is that a one-way hash function is not encryption, so the original message cannot be obtained through decryption.

A one-way hash function is also called a message digest function, hash function, or digest function. The message input to a one-way function is also called the pre-image. The hash value output by a one-way hash function is also called a message digest or fingerprint. Integrity is also referred to as consistency.

For an attacker, the difficulty of breaking a hash algorithm is: strong collision resistance < weak collision resistance < one-wayness.

3. Practical Applications of One-Way Hash Functions

• Detecting whether software has been tampered with

• Password-based encryption

One-way hash functions are also used in Password Based Encryption (PBE). The principle of PBE is to mix a password with a salt (a random value generated by a pseudorandom number generator), compute its hash value, and then use that hash value as the encryption key. This approach can defend against dictionary attacks on passwords.

• Message authentication codes

A message authentication code can be constructed using a one-way hash function. A message authentication code is a hash value computed by mixing “the shared key between the sender and receiver” with the “message”. Message authentication codes can be used to detect and prevent errors, tampering, and impersonation during communication. A concrete application is in SSL/TLS.

• Digital signatures

One-way hash functions are also used in digital signatures. A digital signature generally does not directly sign the entire message content. Instead, it first computes the hash value of the message using a one-way hash function, and then applies the digital signature to the hash value.

• Pseudorandom number generators

One-way hash functions can be used to construct pseudorandom number generators. To ensure that future random sequences cannot be predicted from past random sequences, the one-wayness of a one-way hash function can be used.

• One-time passwords

One-time passwords are often used by servers to authenticate the legitimacy of clients. Using a one-way hash function can ensure that a password is transmitted only once over the communication link. Therefore, even if an eavesdropper steals the password, they cannot use it again.

4. Current Status of One-Way Hash Functions

Note: There is no necessary relationship between the output length of a hash algorithm and its computational performance. For example, the larger the data block being processed, the better the performance of sha384 compared with sha256. Be sure to pay attention to this point!

5. The Keccak Algorithm

In 2007, NIST began the public call for SHA-3 submissions, and by 2008 it had received 64 algorithms.
In 2010, the final candidate list for SHA-3 was released, containing 5 algorithms.
In 2012, after a five-year selection process, the Keccak algorithm jointly designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche was ultimately selected as the SHA-3 standard. Joan Daemen is also one of the designers of the symmetric encryption algorithm AES.

Keccak was ultimately selected as SHA-3 for the following reasons:

• It uses a structure completely different from SHA-2
• Its structure is clear and easy to analyze
• It can be applied to a wide range of devices, including embedded applications
• Its hardware implementation demonstrates high performance
• It has a larger security margin than the other final candidate algorithms

Keccak can generate hash values of arbitrary length, but to align with the hash value lengths of SHA-2, the SHA-3 standard defines four versions compatible with SHA-2. In terms of the upper bound on input data length, SHA-1 supports up to 2^64 - 1 bits, SHA-2 supports up to 2^128 - 1 bits, while SHA-3 has no limit.

The other two SHAKE functions in SHA-3 support outputting hash values of arbitrary length. They are SHAKE128 and SHAKE256. The name SHAKE comes from the words Secure Hash Algorithm and Keccak.

Keccak uses a sponge construction that is completely different from SHA-1 and SHA-2.

1. Sponge Construction

The figure above shows the sponge construction. The entire computation process is divided into two steps. The first step is the absorbing phase, and the second step is the squeezing phase.

First step, the absorbing phase:

• Split the padded input message into input blocks of r bits each.
• First, XOR “the r bits of the internal state” with “input block 1”, and use the result as “the input value to function f”.
• Then, XOR “the r bits of the output value of function f” with “input block 2”, and again use the result as “the input value to function f”.
• Repeat the above steps until the final block is reached.
• After all input blocks have been processed, end the absorbing phase and enter the squeezing phase.

During the absorbing phase, the initial internal state is b = r + c bits of 0. Each time, an input block of r bits is absorbed and XORed with the r internal-state bits. The c bits of the internal state are not affected by the input block directly, but they are affected indirectly by function f. r is called the bitrate, and c is called the capacity. After absorption is complete, the output is still b bits. Step 2, the squeezing phase:

• First, save “the r bits from the output of function f” as “output block 1”, and feed the entire output value ((r+c) bits) back into function f.
• Then, save “the r bits from the output of function f” as “output block 2”, and feed the entire output value ((r+c) bits) back into function f.
• Repeat the steps above until the required length of output data has been obtained.

Whether in the absorbing state or the squeezing state, the logic of function f is exactly the same. Each time function f is executed, the internal state of the sponge construction is mixed once.

What the squeezing phase actually does is “mix the internal state and produce an output block (r bits)”. The data in the sponge construction’s internal state is gradually “squeezed” out in units of r bits.

Similarly, during the squeezing phase, the c bits in the internal state do not directly enter the output block. This part of the data only affects the output indirectly through function f. Therefore, the purpose of capacity c is to prevent certain characteristics of the input message from being leaked.

2. Duplex Construction

The sponge construction has one drawback: the squeezing phase cannot begin until the absorbing phase has completed. Keccak therefore improves on the sponge construction and introduces the duplex construction, as shown below:

In the duplex construction, input and output proceed at the same rate. In bidirectional communication, the mode in which sending and receiving happen simultaneously is called full duplex. By adopting the duplex construction, Keccak can be used not only to compute hash values, but also as a pseudorandom number generator, stream cipher, authenticated encryption scheme, message authentication code, and so on.

6. Keccak’s Internal State

In the previous section, we learned that Keccak’s internal state has b = r + c bits. In this section, we take a deeper look at how the internal state works.

Keccak’s internal state is a three-dimensional bit array. When b small blocks are combined in a 5 * 5 * z arrangement, they form a cube extending along the z-axis. The internal state with the three dimensions x, y, and z is collectively called the state, and the state contains b bits in total.

The xz plane is called a plane, the xy plane is called a slice, and the yz plane is called a sheet. The x-axis is called a row, the y-axis is called a column, and the z-axis is called a lane.

The entire state can be viewed as consisting of 5 * 5 = 25 lanes. It can also be viewed as a stack of slices whose depth is the lane length.

The essence of Keccak is to implement a function f that can effectively mix the state structured as described above. Since the internal state can represent all intermediate states throughout the entire processing flow, this helps save memory. Keccak uses many bit-level operations, so it can effectively resist attacks that operate at the byte level.

1. Function Keccak-f[b]

The internal function in Keccak is actually called Keccak-f[b]. The parameter b is the total bit length of the internal state, referred to here as the width. According to the design specification, b can take 7 values in total: 25 (5 * 5 * 2^0), 50 (5 * 5 * 2^1), 100 (5 * 5 * 2^2), 200 (5 * 5 * 2^3), 400 (5 * 5 * 2^4), 800 (5 * 5 * 2^5), and 1600 (5 * 5 * 2^6). SHA-3 uses the largest of these widths, namely b = 1600. The reason all of them are multiples of 25 is that one slice contains 25 bits. b / 25 = the number of slices = the length of a lane.

In Keccak, changing the width b changes the bit length of the internal state. However, no matter how it changes, the size of a slice remains 5 * 5; only the length of the lanes changes. Therefore, changes in Keccak’s width do not affect its basic structure. This structure is also called a nested-doll structure.

Each round in Keccak-f[b] consists of 5 steps: θ (theta), ρ (rho), π (pi), χ (chi), and τ (iota), repeated for a total of 12 + 2ι rounds. (Define 2^ι = b / 25.) SHA-3 uses the Keccak-f[1600] function, where b = 1600 and ι = 6, so the total number of rounds is 12 + 2 * 6 = 24.

2. Step θ

This step takes the 5 bits from each of two columns at different positions, combines them via XOR, then XORs the result with the target bit of the permutation and overwrites that target bit.

3. Step ρ

This step shifts bits along the z-axis.

4. Step π

The figure above shows step π being applied to one slice. In practice, the same bit-movement operation is applied to all slices across the entire lane.

5. Step χ

The figure above shows step χ being applied to one row. The diagram includes logic-circuit symbols: the inverted triangle denotes the logical NOT operation, and the inverted letter D denotes the logical AND operation.

6. Step τ

This step XORs all bits of the entire state with a fixed round constant, with the goal of giving the internal state asymmetry.

Of the 5 steps above, except for the parity processing in step θ and the NOT and AND operations in step χ, the remaining operations can all be implemented purely with hardware circuits.

7. Attacks on Keccak

All one-way hash functions before Keccak generated hash values by repeatedly executing a compression function. For example, almost all traditional one-way hash function algorithms such as MD4, MD5, RIPEMD, RIPEMD-160, SHA-1, and SHA-2 are based on the MD (Merkle-Damgard construction) structure.

To prevent SHA-3 from being affected by the MD structure, SHA-3 abandoned the MD structure from the very beginning of its design. Instead, it adopted the completely different sponge construction. This is why attack methods against SHA-1 are ineffective against SHA-3.

So far, no attack has emerged that can pose a threat to the Keccak algorithm in practical use.

7. Attacks on One-Way Hash Functions

1. Brute Force

By exploiting the redundancy of a file, an attacker can brute-force modifications to the file, slightly changing the message each time and computing the hash values of these messages. Once a hash value matches a previous hash value, the brute-force attack is considered successful. This is equivalent to an attack that attempts to break the “weak collision resistance” of a one-way hash function.

Attacks that try to find a message with a specified hash value fall into two categories: a Pre-Image Attack means that, given a hash value, the attacker finds any message with that hash value; a Second Pre-Image Attack means that, given a message 1, the attacker finds another message 2 whose hash value is the same as that of message 1.

2. Birthday Attack

A birthday attack or collision attack does not look for a message that produces a specific hash value. Instead, it tries to find two messages with the same hash value, where that hash value may be arbitrary. This is an attack that attempts to break the “strong collision resistance” of a one-way hash function.

The principle behind the birthday attack comes from the birthday paradox; that is, it exploits the property that “the probability of any two hash values being equal is higher than one might expect.” Taking a 512-bit hash value as an example, the number of attempts required to brute-force a one-way hash function is 2^512, whereas the number of attempts required to perform a birthday attack against the same one-way hash function is 2^256. Therefore, compared with brute force, a birthday attack requires far fewer attempts.

In 2005, the collision attack proposed by Professor Wang Xiaoyun’s team required 2^69 attempts for SHA-1, already far fewer than the 2^80 attempts required by a birthday attack. In the same year, Professor Wang Xiaoyun’s team further improved the method, reducing the number of attempts again to 2^63.

8. Problems One-Way Hash Functions Cannot Solve

A one-way hash function can detect “tampering”, but it cannot detect “spoofing”. For a message, it is necessary not only to confirm the integrity of the message, but also to confirm who sent it. Integrity checking alone is not enough; message authentication is also required. Authentication technologies include message authentication codes and digital signatures.

A message authentication code can assure the communication peer that the message has not been tampered with. A digital signature can not only assure the communication peer that the message has not been tampered with, but can also provide the same assurance to all third parties.

References：

Illustrated Cryptography
SHA-3 Wikipedia

GitHub Repo: Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/one_way_hash/