Cryptography series: collision defense and collision attack

brief introduction

hash It is a function often used in cryptography and peacetime programs , If hash The algorithm is not well designed , Will produce hash Collision , Even a collision attack .

Today I'd like to talk about collision attack in detail .

What is a collision attack

Collision attack refers to the attack on the same hash In terms of functions , Two different input adopt hash The same result is obtained by calculation hash value . In terms of formula, it's ：

hash(m1) = hash(m2)

What's the use of this attack ？

for instance , Usually we download applications or software from the Internet , In addition to the download link , There will also be a MD5 The check code of . This check code is used to check whether the downloaded software is officially provided .

MD5 Algorithm is also a kind of hash Algorithm , If a malicious user can construct one just like the original software MD5 In terms of software , It's very likely to carry out a collision attack .

There is also a case used in digital signature . In a digital signature , Because of efficiency , If the article is very large , I usually get the articles first hash value , And then to this hash To sign .

So there are two places that can be attacked , One is hash Collision , One is the signature algorithm .

for instance , For example, Shi Feixuan wrote a letter to Xu Ziling A, It was said that there was something to tell in the bamboo forest in the early morning , But instead of giving it directly to Xu Ziling, he gave it to his good brother Kou Zhong , Kou Zhong thought that the night was too dangerous , I don't want his good brother to take risks , So I faked the letter A, Constructed and original letter A Again hash It's worth the letter B, With the signature of Shi Feixuan .

Xu Ziling received the letter B And signature , After verification, it is found that Shi Feixuan wrote it , So I didn't go to the appointment .

Collision attack depends on hash The strength of the algorithm , Like MD5 and SHA-1 these hash Algorithms have been shown to be insecure , It can be broken in a short time .

Choose prefix conflict attack

In addition to the traditional collision attack ahead , There's another one called Chosen-prefix collision attack Choose prefix conflict attack .

An attacker can choose two different prefixes p1 and p2, Then attach different strings m1,m2 front , So there are ：

 hash(p1 ∥ m1) = hash(p2 ∥ m2)     among  ∥  Represents a connector 

Let's see one SHA-1 By Gaetan . Roelen （Gatan Leurent） And Toma . Palin （Thomas Peyrin） An example of an attack found , Here are two prefixes 99040d047fe81780012000 and 99030d047fe81780011800 Example .

Two message contents can be downloaded from below ：

messageA: sha-mbles.github.io/messageA

messageB:sha-mbles.github.io/messageB

We can take a screenshot of the message ：

These two messages passed through sha1sum operation , You can get the same hash value .

sha1sum messageA ： 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

sha1sum messageB： 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

java Medium hash attack

java There is a class often used in called hashMap, stay JDK7 Before ,HashMap When storing data, if you encounter hash Conflict , The data will be inserted into this hash At the end of the node .

What are the disadvantages of this ？

So if there's a malicious attacker , All the way to hashMap Insert the same hash It's worth it key object , that hashMap It actually degenerates into a linked list .

This will greatly affect hashMap The query efficiency of . If the data is particularly large , May lead to DDOS attack .

The root cause of this problem is java in hashMap Medium hash The calculation is too simple , It's easy to find the same hash It's worth it key.

In fact, 2011 year tomcat A vulnerability solution to this problem has also been released .

Although this is java The problem of , But the last pot is made up of tomcat Come back .tomcat The way to do this is to limit maxPostSize, From the biggest 20M Changed to 10K, This can effectively reduce the number of item size .

Of course , stay JDK8 in , The original linked list structure has been changed to the red black tree structure , I believe it is also to avoid this DDOS hash The scheme of attack .

Original image attack Preimage attack

There is another attack similar to collision attack, which is called image attack .

Two conditions need to be met to resist the original image attack , The first condition is to give a hash value y, It's hard to find one x, bring hash（x）=y.

The second condition is to give a x, It's hard to find one y, bring hash(x) = hash(y).

Obviously , The defense of collision attack must satisfy the second condition , But the first condition may not be satisfied .

This article has been included in http://www.flydean.com/collision-attack/ The most popular interpretation , The deepest dry goods , The most concise tutorial , There are so many tricks you don't know about waiting for you to discover ！ Welcome to my official account. :「 Program those things 」, Know technology , Know you better ！