What We Do
We are a research company that has received an order to conduct research and search for collisionsin common hashing algorithms: SHA-256, Scrypt, ...
We do not disclose information about our customer under the terms of our agreement with them. To solve the problem of finding collisions, we decided to use the most advanced equipment to date - cryptocurrency miners. Our developers studied the features of this equipment and wrote firmware for the control boards of some modern miner models, which allows us to solve the problem at hand with high speed and efficiency. No supercomputer is capable of performing this task as quickly as ASIC equipment does.
Collisions exist for most hash functions, but for "good" hash functions their frequency is close to the theoretical minimum. In some special cases, when the set of distinct inputs is finite, one can define an injective hash function, which by definition has no collisions. However, for hash functions that take variable-length input and return a hash of constant length, collisions must exist, since for at least one hash value, the corresponding set of inputs (the full preimage) will be infinite - and any two sets of data from this set will form a collision.
Since cryptographic hash functions are used to confirm the immutability of the original information, the ability to quickly find a collision for them is usually equivalent to discrediting them. For example, if a hash function is used to create a digital signature, the ability to find collisions for it is actually equivalent to the ability to forge a digital signature. Therefore, the computational complexity of finding a collision is considered a measure of the cryptographic strength of a hash function. Ideally, there should be no way to find collisions faster than a complete search. If for some hash function a way to obtain collisions is found that is significantly faster than a complete search, then this hash function is no longer considered cryptographically secure and is no longer used to transmit and store secret information. Theoretical and practical issues of finding and using collisions are discussed annually at international conferences (such as CRYPTO or ASIACRYPT), on a large number of Internet resources, and in many publications.
Methods for finding collisions
One of the simplest and most universal methods for finding collisions is the "birthday" attack. Using this attack, finding a collision for a hash function of n bits will require on average about 2^(n/2) operations. Therefore, an n-bit hash function is considered cryptographically secure if the computational complexity of finding collisions for it is close to 2^(n/2).Additionally, there exists a message length extension attack, which allows computing H(x∥y)=H(H(x)∥y)H(x∥y)=H(H(x)∥y) given a known value H(x)H(x).
‖‖ denotes concatenation. The extension attack for some hash functions works even if collision resistance of the first kind, collision resistance of the second kind, and the irreversibility property are ensured. It is assumed that there is no need to know X, but only its hash. In this way, one can, for example, append additional information to someone else's message. To prevent this attack, various methods are used: adding an additional round during hashing, different from the previous ones; using multiple hashing; or using a combination of the previous two methods.
But the extension attack can be viewed from the other side: if we have some message X, and the hash function is vulnerable to an extension attack, then it is easy to find a collision of the first kind: M1=X‖‖Y, M2=H(X)‖‖Y, H(M1)=H(M2), that is, the property of resistance to collisions of the first kind is violated.
Most modern hash functions have the same structure, based on splitting the input text into blocks and then an iterative process in which some function is used at each iteration
G(x,y), where x is the next block of input text, and y is the result of the previous operation. However, such a scheme is imperfect, since, knowing the function G, it is possible to analyze the data in the intervals between iterations, which facilitates the search for collisions.
Often, finding collisions of hash functions is preceded by finding its pseudo-collisions, that is, two different values of the initial buffer that give equal hash function values for the same message.