Reports about Professor Wang Xiaoyun of Shandong University cracking MD5 and SHA-1 have attracted great attention to the security of electronic information. What is the truth?
I want to ask today's sentient beings, what is most important to you in daily life and what makes you the most headache? I believe many people’s answer is password. "Please enter your password, please enter it again." Whether you are at the bank counter or surfing the Internet, such tips are common to us. Bank passwords, login passwords, email passwords, various game passwords, and username passwords... Passwords have become an indispensable part of the world's life. Recently, reports about Professor Wang Xiaoyun of Shandong University cracking MD5 and SHA-1 have frequently appeared in the newspapers, which has made people pay great attention to the security of electronic information. Is the password really unreliable?
What is cracking
Zhai Qibin, a professor at the National Key Laboratory of Information Security and an expert in cryptography, told reporters calmly in the office: "MD5 and SHA-1 are hash algorithms. From the perspective of design principles, there is a possibility of collision. Professor Wang Xiaoyun's method shortens the time to find a collision, which is an important achievement. But what she found is a strong collision. If it is able to find a weak collision, it is considered to be a real crack and has practical significance."
According to the definition of cryptography, if the plaintext with different contents and the results obtained through the hash algorithm (cryptography is called information summary) are the same, it is called a "collision". The purpose of hashing algorithm is not to encrypt plain text so that others can’t understand, but to prevent tampering with the original text by comparing the information digest.
As the only official representative of China's annual meetings of "Crypto'2004" and "RSA 2005", Professor Zhai Qibin particularly emphasized: "Collides are divided into 'strong no collision' and 'weak no collision'. Strong no collision cannot produce original texts with practical significance, and it cannot tamper with and forge meaningful plain texts." Forging something that no one can understand through strong no collision has no practical significance. Professor Zhai also asked the reporter to browse the summary of the "RSA 2005" annual meeting. Shamir, an international cryptography expert, expressed his opinion on Professor Wang Xiaoyun's finding a pair of strong collisions at the "RSA 2005" annual meeting: "This is an important thing, but it does not mean that the password is cracked."
Reality is worry-free
"There is a fundamental difference between finding a pair of strong and non-collecting collisions with practical significance." Professor Zhai believes that the cracking statement is inaccurate. He introduced: "At the 'RSA 2005' annual meeting, experts believed that SHA-1 is currently absolutely safe and it will be fine to use it for another 5 to 10 years. It is planned to consider replacing it after 2010."
We know that if the theoretical method of cracking passwords is to be implemented in reality, it requires massive calculations from supercomputers, and the time required is generally tens of thousands of years. In practical applications, cracking time is too long, which means that cracking will lose its practical significance.
Guan Zhensheng, a technical consultant of the China Financial Certification Center (CFCA), former chief engineer of the Science and Technology Department of China Construction Bank, participated in the formulation of the Electronic Signature Law, introduced: "Currently, online banking certification uses the encryption method of multiple hashing algorithms. For example, for B to B transactions, first performs a SHA-1 summary calculation of the form of the online bank; then calculates the information filled in by the customer; finally, the bank must sign after receiving the information. If you want to tamper with the information, it must be cracked three times (assuming that it can be cracked, but it cannot be done now). Even if you crack it in a few days or months later, the transaction has been completed. At the same time, the transmission of information summary must be carried out under the PKI system (public key infrastructure). Most PKI systems now use RSA algorithms, and the security of this algorithm is safe. Therefore, for real-time systems like banks, it is absolutely impossible to tamper with information and affect the transaction process."
What if you centralize all military supercomputers to crack? Let’s think about it, if you are poor in the whole United States, what will you do if you crack a business transaction? An algorithm as weak as a hash algorithm will not be used by departments at all.
In addition, Mr. Guan also introduced: "It is also impossible to forge a digital certificate. A digital certificate contains a lot of specific content. Only if it has a series of specific information including a serial number, this certificate is meaningful. Based on the specific original content, it is impossible to forge the corresponding summary information."
We see that if you cannot find a weak and no collision, or even if you find a weak and no collision but cannot find a super-large computer, it is impossible to do some tampering and forgery. Moreover, once the management department discovers that the security of the algorithm may be risky, it is not difficult to replace a new algorithm.
Manufacturers engaged in computer security do not agree with the so-called password cracking. They believe that any product has a life cycle and the improvement of product technology is always underway. Although some people say that the password algorithm is not safe, no substantial harm occurs now. There are many precautions for information security, and the hash algorithm is just one of the weakest ones, so there is no need to worry too much.
The devil is one foot taller, and the Tao is one foot taller. With the development of technology, no means can change forever. The world today is safe, so there is no need to sleep and eat for the password.
If a collision occurs, it brings problems. Wang Xiaoyun and others discovered the problems existing in the hash algorithm currently used, which will definitely help future new hash algorithm designers consider this issue, making the new hash algorithm better secure. For example, after DES began to be unsafe, more and more powerful encryption methods also emerged. Regardless of the result of the cracking, Professor Wang Xiaoyun's achievements are enough to inspire us and promote the research of commercial passwords.
Link 1
What is strong and weak and non-collision
The hash function h is called weak and no collision, which means that for a given message x∈ X, there is almost no calculation to find x′∈ X of x and x, so that hx＝hx＇. The hash function h is called a strong collision-free means that it is almost impossible to find different x and x' in calculation, so that hx＝hx＇ . Weak collision is to calculate the same summary information for a given message x, which is the plain text you want to forge. That is to say, you can control the content of the plain text. A strong collision means that the same summary information can be found, but the fake plain text is unknown. The most digital signatures are text content, that is, human-readable content. If you create a collision that is unreadable by humans, it will not have a significant impact on the original text. Professor Wang Xiaoyun found a strong collision.
Link 2
I want to ask today's sentient beings, what is most important to you in daily life and what makes you the most headache? I believe many people’s answer is password. "Please enter your password, please enter it again." Whether you are at the bank counter or surfing the Internet, such tips are common to us. Bank passwords, login passwords, email passwords, various game passwords, and username passwords... Passwords have become an indispensable part of the world's life. Recently, reports about Professor Wang Xiaoyun of Shandong University cracking MD5 and SHA-1 have frequently appeared in the newspapers, which has made people pay great attention to the security of electronic information. Is the password really unreliable?
What is cracking
Zhai Qibin, a professor at the National Key Laboratory of Information Security and an expert in cryptography, told reporters calmly in the office: "MD5 and SHA-1 are hash algorithms. From the perspective of design principles, there is a possibility of collision. Professor Wang Xiaoyun's method shortens the time to find a collision, which is an important achievement. But what she found is a strong collision. If it is able to find a weak collision, it is considered to be a real crack and has practical significance."
According to the definition of cryptography, if the plaintext with different contents and the results obtained through the hash algorithm (cryptography is called information summary) are the same, it is called a "collision". The purpose of hashing algorithm is not to encrypt plain text so that others can’t understand, but to prevent tampering with the original text by comparing the information digest.
As the only official representative of China's annual meetings of "Crypto'2004" and "RSA 2005", Professor Zhai Qibin particularly emphasized: "Collides are divided into 'strong no collision' and 'weak no collision'. Strong no collision cannot produce original texts with practical significance, and it cannot tamper with and forge meaningful plain texts." Forging something that no one can understand through strong no collision has no practical significance. Professor Zhai also asked the reporter to browse the summary of the "RSA 2005" annual meeting. Shamir, an international cryptography expert, expressed his opinion on Professor Wang Xiaoyun's finding a pair of strong collisions at the "RSA 2005" annual meeting: "This is an important thing, but it does not mean that the password is cracked."
Reality is worry-free
"There is a fundamental difference between finding a pair of strong and non-collecting collisions with practical significance." Professor Zhai believes that the cracking statement is inaccurate. He introduced: "At the 'RSA 2005' annual meeting, experts believed that SHA-1 is currently absolutely safe and it will be fine to use it for another 5 to 10 years. It is planned to consider replacing it after 2010."
We know that if the theoretical method of cracking passwords is to be implemented in reality, it requires massive calculations from supercomputers, and the time required is generally tens of thousands of years. In practical applications, cracking time is too long, which means that cracking will lose its practical significance.
Guan Zhensheng, a technical consultant of the China Financial Certification Center (CFCA), former chief engineer of the Science and Technology Department of China Construction Bank, participated in the formulation of the Electronic Signature Law, introduced: "Currently, online banking certification uses the encryption method of multiple hashing algorithms. For example, for B to B transactions, first performs a SHA-1 summary calculation of the form of the online bank; then calculates the information filled in by the customer; finally, the bank must sign after receiving the information. If you want to tamper with the information, it must be cracked three times (assuming that it can be cracked, but it cannot be done now). Even if you crack it in a few days or months later, the transaction has been completed. At the same time, the transmission of information summary must be carried out under the PKI system (public key infrastructure). Most PKI systems now use RSA algorithms, and the security of this algorithm is safe. Therefore, for real-time systems like banks, it is absolutely impossible to tamper with information and affect the transaction process."
What if you centralize all military supercomputers to crack? Let’s think about it, if you are poor in the whole United States, what will you do if you crack a business transaction? An algorithm as weak as a hash algorithm will not be used by departments at all.
In addition, Mr. Guan also introduced: "It is also impossible to forge a digital certificate. A digital certificate contains a lot of specific content. Only if it has a series of specific information including a serial number, this certificate is meaningful. Based on the specific original content, it is impossible to forge the corresponding summary information."
We see that if you cannot find a weak and no collision, or even if you find a weak and no collision but cannot find a super-large computer, it is impossible to do some tampering and forgery. Moreover, once the management department discovers that the security of the algorithm may be risky, it is not difficult to replace a new algorithm.
Manufacturers engaged in computer security do not agree with the so-called password cracking. They believe that any product has a life cycle and the improvement of product technology is always underway. Although some people say that the password algorithm is not safe, no substantial harm occurs now. There are many precautions for information security, and the hash algorithm is just one of the weakest ones, so there is no need to worry too much.
The devil is one foot taller, and the Tao is one foot taller. With the development of technology, no means can change forever. The world today is safe, so there is no need to sleep and eat for the password.
If a collision occurs, it brings problems. Wang Xiaoyun and others discovered the problems existing in the hash algorithm currently used, which will definitely help future new hash algorithm designers consider this issue, making the new hash algorithm better secure. For example, after DES began to be unsafe, more and more powerful encryption methods also emerged. Regardless of the result of the cracking, Professor Wang Xiaoyun's achievements are enough to inspire us and promote the research of commercial passwords.
Link 1
What is strong and weak and non-collision
The hash function h is called weak and no collision, which means that for a given message x∈ X, there is almost no calculation to find x′∈ X of x and x, so that hx＝hx＇. The hash function h is called a strong collision-free means that it is almost impossible to find different x and x' in calculation, so that hx＝hx＇ . Weak collision is to calculate the same summary information for a given message x, which is the plain text you want to forge. That is to say, you can control the content of the plain text. A strong collision means that the same summary information can be found, but the fake plain text is unknown. The most digital signatures are text content, that is, human-readable content. If you create a collision that is unreadable by humans, it will not have a significant impact on the original text. Professor Wang Xiaoyun found a strong collision.
Link 2