Introduction to the

Hash is a function commonly used in cryptography and other programs. If the hash algorithm is poorly designed, hash collisions will occur, and even collision attacks will occur.

Today I’m going to talk about collision attacks in detail.

What is a collision attack

A collision attack is when two different inputs compute the same hash value for the same hash function. In the formula:

hash(m1) = hash(m2)
Copy the code

What does this attack do?

For example, when you download an application or software from the Internet, in addition to the download link, you will be provided with an MD5 check code. This verification code is used to verify whether the downloaded software is officially provided software.

MD5 is also a hash algorithm. If a malicious user can construct an MD5 software that is the same as the original software, it is likely to carry out a collision attack.

There’s another case for digital signatures. In digital signature, for efficiency reasons, if the article is very large, the hash value of the article is usually taken first and then the hash value is signed.

So there are two areas that can be attacked, one is the hash collision and the other is the signature algorithm.

For example, for example ShiFeiXuan wrote A letter to the zjmta A, say, in bamboo forest when something in the morning, but no directly to zjmta KouZhong but gave him A good brother, KouZhong considering the night is too dangerous, don’t want to let his good brothers adventure, forged the letter A, then constructed, and the original letter A letter the same hash value of B, And attached the signature of Shi Fei Xuan.

Xu Ziling received the letter B and his signature. After verification, he found that it was indeed written by Shi Fei Xuan, so he did not go to the appointment.

Collision attacks depend on the strength of hash algorithms, such as MD5 and SHA-1, which have been shown to be insecure and can be breached very quickly.

Select prefix conflict attacks

In addition to the previous traditional collision attack, there is another called select-prefix Collision attack.

An attacker can choose two different prefixes p1 and p2, and then append them to different strings m1,m2, then there are:

Hash (p1 ∥ m1) = hash(p2 ∥ m2) where ∥ indicates the concatenationCopy the code

Let’s look at one in SHA-1 by Geitan. Gatan Leurent and Toma. Two examples of attacks with prefixes 99040D047FE81780012000 and 99030D047FE81780011800, respectively.

Two message contents can be downloaded below:

messageA: sha-mbles.github.io/messageA

messageB:sha-mbles.github.io/messageB

Here’s a screenshot of the message:

The two messages are calculated by sha1sum to obtain the same hash value.

Sha1sum messageA: 8 ac60ba76f1999a1ab70223f225aefdc78d4ddc0

Sha1sum messageB: 8 ac60ba76f1999a1ab70223f225aefdc78d4ddc0

Hash attack in Java

There is a commonly used class in Java called hashMap. Prior to JDK7, a hashMap would insert data into a linked list at the end of the hash node if it encountered a hash conflict.

What are the downsides to that?

If a malicious attacker keeps inserting keys with the same hash value into the hashMap, the hashMap will effectively degenerate into a linked list.

This can greatly affect the efficiency of hashMap queries. If the data is particularly large, it can lead to a DDOS attack.

The root cause of this problem is that hash computations in Java hashmaps are too simple and it is easy to find keys with the same hash value.

In fact, in 2011 Tomcat released a bug fix for this problem.

This is Java’s problem, but Tomcat does the heavy lifting. Tomcat’s approach is to limit the maxPostSize from 20M to 10K, effectively reducing the size of the item in the request.

Of course, in JDK8, the linked list structure has been changed to a red-black tree structure, presumably to avoid DDOS hash attacks.

Preimage attack

A similar attack to the collision attack is called the preimage attack.

The defense against preimage attack needs to meet two conditions. The first condition is that given a hash value y, it is difficult to find an x such that hash (x) =y.

The second condition is that given an x, it’s hard to find a y such that hash(x) = hash(y).

Obviously, the resistance to collision attack must satisfy the second condition, but not necessarily the first condition.

This article has been included in www.flydean.com/collision-a…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!