12:02 Plays with hashes | |
| Hello. I want to show you a little trick. To get started you will need to download an archive with two files. Both have the same size and same md5 sum. Check there is no deception. Md5 hash both equal ecea96a6fea9a1744adcc9802ab7590d. Now run the program good.exe and you will see the following. Try to run the program evil.exe. Something has gone wrong? Want to try it themselves? About heshah and kollliziyahIn fact, nothing new in all this. In fact, this effect is achieved by methods quickly find collisions for hash functions developed in the years 2004-2006. If anyone knows, the collision is two different sets of data having the same hash value. So, in 2004 a group of Chinese researchers has developed an algorithm based on differential cryptanalysis, which allows for a relatively short period of time to find two different random data block size of 128 bytes each with the same md5 sum. Although this algorithm in its time produced the effect of a bomb of his performance left much to be desired. But in 2006 the Czech cryptographer Vlastimil Climate invited to search for conflicts of a new method for finding a different pair of random 128-byte blocks a md5 sum on a personal computer less than a minute. You ask, but what will give us the possession of a pair of posts, moreover that they are short (only 128 bytes), so also, in addition, and random, ie method does not allow for a given message to pick up another, with the same hash. However, this opens up a huge scope for various kinds of attacks on an executable file. And the cause is, use the following feature of any hash function: A hash function is inherently iterative. This means that when calculating the hash of a message is divided into blocks, each block is used compression feature, depending on some variable, called the initialization vector. The result of this function will be the initialization vector for the next block. Function result after working with the last block and will be the final hash value of our message. Schematically it can be represented as follows: si +1 = f (si, Mi), where si the initialization vector for the i-th block. Climate Vlastimil method allows for any given value of si to pick up two 128-byte block of M, M `and N, N` such that f (f (s, M), M ') = f (f (s, N), N '). So, with this technique, we can construct two files with the same md5 sum, but with different 128-byte in the middle. M0, M1, ..., Mi-1, Mi, Mi +1, Mi +2, ..., Mn, M0, M1, ... , Mi-1, Ni, Ni +1, Mi +2, ..., Mn. Note that the hash of both files are identical, since different blocks Mi, Mi +1 and Ni, Ni +1 return as si +2 same value, because f (f (s, Mi), Mi +1) = f (f (s, Ni), Ni +1), as well as all subsequent data are identical to the subsequent value of the function of compression for both files will be identical. What does this leave usWe now turn from the things abstract and remote to the practical. Assume that we have an executable file M0, M1, X, X, ..., Mn. But it is based, we can create two different files M0, M1, N1, N1, ..., Mn, and M0, M1, N2, N1,..., Mn (just change the units X at N1 and N2). If the blocks N1 and N2 - this conflict is the hash sum of these files will be identical. Now imagine that this executable file has the following structure: if (X == X) then {good_program} else {evil_program} That's actually the whole secret of this focus. How to do it yourselfNow a little talk about how to do it yourself. Step One: writing a program with a double bottom. # Include <stdafx.h> # include <iostream> # include <string> using namespace std; / / variables str1 and str2 in this example are the ones most elements of X. Static char * str1 = "qwertyuioplkjhgfdaszxcvbnmkjhgfdsaqwertyuikjh" \ "gbvfdsazxdcvgbhnjikmjhbgfvcdsazxdcfrewqikolkjnhgfqwertyuioplkjh" \ "gfdaszxcvbnmkjhgfdsaqwertyuikjhgbvfdsazxdcvgbhnjikmjhbgfvcdsa" \ "zxdcfrewqikolkjnhgfq123"; static char * str2 = "qaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuy" \ "gtfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuyg" \ "tfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuygt" \ "fdeswaqscfvgyjqwertyuikja2"; int good () { int a; std:: cout <<"Good, nice programme!"; std:: cin>> a; return 0; } int bed () { int a; for (int i = 0; i <1000; i + +) { std:: cout <<"Evil, evil code!"; } std: : cin>> a; return 0; } int _tmain (int argc, _TCHAR * argv []) { / / string s and s2 contain only blocks from collisions without superfluous elements string s = str1; string s2 = str2; s.erase (0,56); s.erase (128,8); s2.erase (0,64) ; if (s == s2) { return good (); } else { return bed (); } return 0; } * This source code was highlighted with Source Code Highlighter. You to pay particular attention to variables str1 and str2. They serve to ensure that they can be quickly found in the hex-editor and replace the necessary data. The main function depending on the contents of the variable s is good or bad version. Step two: After compiling the program will need to work a little with hex-editor to find. Exe file our of str1 and str2. Copy the. Exe file. Let a copy will be called a "truncated version". Open a copy of a hex-editor and find it of str1 and str2. Delete all the data coming after the first 64 bytes of the first row. The last lines of the resulting file will look like this:. Save the file. Step Three: Building on the second step, the file will be the so-called prefix to search for collisions. To find a conflict with the specified prefix to download the program here fastcoll (Thanks to the author Marc Stevens). Sources are here. Run the program with the option-p. As a prefix, specify "trimmed version." As a result, the program will create two files "Cropped versiya_msg1" and "Cropped versiya_msg2. Step Four: create another copy of your program. Suppose that the original will be called good.exe, and a copy evil.exe. Open files msg1 and msg2 in hex editor. First, replace the unit which stores data from the block str2 str1. Now let them be the same information. Then copy the file msg1 last 128 bytes and insert them into your good file as shown in the figure. Please note that the margins must meet the following criteria: the first block is inserted directly into the place where the file ends with "truncated version", the second block is located at 96 bytes from the first. Important: insert blocks of the same. This will be a good version of the program. Save the file and open the file good.exe evil.exe. Blocks in the file evil.exe need to be inserted into the same places as in good.exe, the only difference is that we take the first block of file msg2, and the second from a file msg1. This difference will provide us with the failure conditions of the program if (s == s2), respectively, and run a malicious program version. Step Five: Profit! Compare the md5 sums of files, enjoy the results. List of Literature: 1. Great site with a description of the method 2. Site Vlastimil Klim 3. Messenger program findcoll | |
|
| |
| Total comments: 0 | |