All MD5 Hacking Techniques
It's no secret that cryptography has firmly entered our lives. Internet services, social networks, mobile devices - all of them store user passwords encrypted using various algorithms in their databases.
The most popular such algorithm today, by far, is MD5.
We’ll talk about methods of hacking it.
A bit about cryptography
Modern cryptography includes three areas: private key encryption, public key encryption and hashing. Today we’ll talk about what hashing is and what it is eaten with.
In general, hashing refers to the conversion of input data of an arbitrary length to an output bit string of a fixed length. Most often, hash functions are used in the process of user authentication (the password hash is usually stored in the database instead of the password itself) and for calculating checksums of files, data packets, etc.
One of the best known and widely used hashing algorithms is MD5.
The MD5 algorithm is a 128-bit hash algorithm. This means that it computes a 128-bit hash for an arbitrary set of data arriving at its input. This algorithm was developed by Professor Ronald Rivest of the Massachusetts Institute of Technology in 1991 to replace the less reliable predecessor - MD4. The algorithm was first published in April 1992 in RFC 1321. After that, MD5 was used to solve a variety of tasks, from hashing passwords in CMS to creating digital signatures and SSL certificates.
The fact that the MD5 algorithm can be hacked was first discussed in 1993. Researchers Bert den Boer and Anton Bossilaris have shown that pseudo collisions are possible in the algorithm. Three years later, in 1996, Hans Dobbertin published an article in which he proved the presence of collisions and described the theoretical possibility of hacking MD5. It was not a hack yet, but there was talk in the world about the need to switch to more reliable hashing algorithms, for example SHA1 (at the time of writing this article it was already proven that there are collisions in this algorithm, so I recommend using SHA2) or RIPEMD-160.
The direct hacking of MD5 began on March 1, 2004. CertainKey Cryptosystems launched the MD5CRK project - a distributed collision detection system. The aim of the project was to search for two messages with identical hash codes. The project was completed on August 24, 2004, when four independent researchers - Wang Xiaoyun, Feng Denguo, Lai Xuejia and Yu Hongbo - discovered an algorithm vulnerability that allowed finding collisions using an analytical method in a more or less acceptable time. Using this method, you can identify collisions on an IBM p690 cluster in just an hour (it’s a pity that I don’t have such a house).
MD5 hash collision example
On March 1, 2005, the first use of this vulnerability was demonstrated in practice. The research team presented two X.509 certificates with different key sets, but with identical checksums. In the same year, Vlastimil Klima published an algorithm that could detect collisions on an ordinary laptop in a few hours. In 2006, he went on. On March 18, 2006, the researcher unveiled an algorithm that finds collisions in one minute! This method is called tunneling. In 2008, an article on the method of generating fake X.509 certificates was presented at the Chaos Communication Congress. In fact, this was the first case of the real use of collisions in the MD5 algorithm.
Brute MD5 mask
A lot of work has also been done to speed up the cracking of hashes. In 2007, Kevin Breeze introduced a program using the Sony PlayStation3 to hack MD5. He managed to achieve very good results: 1.4 billion MD5 hashes were generated in just one second! Two years later, in 2009, BlackHat USA published an article about using the GPU to search for collisions, which made it possible to increase its speed by several times, especially if it was performed using several video cards at the same time.
The ATI Radeon HD 4850 X2 graphics card can generate up to 2.2 billion hashes per second! The use of the MD5 algorithm in EDS is unacceptable due to the insufficient stability of this algorithm to search for collisions.
This is the end?
In 2011, the IETF agreed to amend RFC 1321 (MD5) and RFC 2104 (HMAC-MD5). This is how RFC 6151 came about. It recognizes the MD5 encryption algorithm as unsafe and recommends not using it. In my opinion, this document officially put an end to MD5.
However, despite the fact that the MD5 algorithm has been officially recognized as unsafe, there are thousands, if not tens and hundreds of thousands of applications that use it to store passwords, in electronic digital signatures and to calculate file checksums.
By the way, on October 31, 2008 NIST announced a competition among cryptographers. The purpose of the competition is to develop a hashing algorithm to replace obsolete SHA1 and SHA2. At the moment, the finalists have already been identified - these are BLAKE, Gostl, JH, Keccak and Skein.
Ighashgpu: GPU hacking
But enough theory. Let's get down to business and talk directly about hacking our favorite algorithm. Suppose we had a password hash of some kind: d8578edf8458ce06fbc5bb76a58c5ca4.
To crack this hash, I suggest using the Ighashgpu program, which can be downloaded from www.golubev.com or found on our disk. The utility is distributed completely free of charge and works quietly under Windows. To speed up the hash cracking process, Ighashgpu uses a GPU, so you need at least one nVidia or ATI graphics card with CUDA / ATI Stream support.
Modern GPUs are built on a slightly different architecture than conventional CPUs, so they process graphics information much more efficiently. Although GPUs are designed to handle three-dimensional graphics, in the last few years there has been a tendency to use them for conventional computing. Getting started with the program is not simple, but very simple: unzip the archive to any place on the disk and proceed to hacking using the Windows command line:
ighashgpu.exe -t:md5 \
We use the above method to crack one specific hash generated using the MD5 algorithm. The maximum possible password is seven characters. After some time, the password will be found (qwerty). Now let's try to crack another hash, but with slightly different conditions. Let our hash look like d11fd4559815b2c3de1b685bb78a6283, but it includes letters, numbers, an underscore and has the suffix "_admin". In this case, we can use password masking to simplify the task for the program:
ighashgpu.exe -h:d11fd4559815b2c3de1b685bb78a6283 -t:md5
Here the parameter '-u' allows you to specify the character set used in the search, and the parameter '-m' sets the password mask. In our case, the mask consists of six arbitrary characters, followed by the combination "_admin". Password selection is also easy.
Collisions - a collision in cryptography refers to two different input data blocks that give the same hash for the same hash function. Each function on the output gives a sequence of bits of a certain length, which is independent of the size of the original data. It follows that collisions exist for any hashing algorithm. However, the likelihood that you can find a collision in a “good” algorithm almost tends to zero. Unfortunately or fortunately, hashing algorithms can contain errors, like any programs. Many hash functions have either been broken or will be soon. In this case, “breaking” means finding a collision in a time that is much less than the declared infinity.
Now let's try to crack several passwords at once. Suppose we got a database of password hashes. It is also known that each password ends with c00l characters:
Save the hashes in the encrypted.dat file and run Ighashgpu as follows:
ighashgpu.exe -t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_]
After the program terminates, the ighashgpu_results.txt file with cracked passwords appears in the Ighashgpu folder:
Hacked hashes from encrypted.dat
Finally, let's hack a “salted” hash. Suppose a hash is generated using the following algorithm:
var plain = password + "s41t";
var hash = md5(plain);
As a result, we got the following hash: 42151cf2ff27c5181bb36a8bcfafea7b. Ighashgpu allows you to specify "salt" in the "-asalt" parameter:
ighashgpu.exe -h:42151cf2ff27c5181bb36a8bcfafea7b \
-t:md5 -u:[abcdefghijklmnopqrstuwvxyz1234567890_] \
And again we got the password we searched for quickly and easily.
Entertaining math - For an 8-character password made up of the first 126 ASCII characters, 63,527,879,748,485,376 possible combinations are available. For 254 characters, the number of possible combinations increases to 17 324 859 956 700 833 536, which is already 2.7 billion times more than people on our planet. If you create a text file containing all these passwords, it will take millions of terabytes. Of course, in the modern world this is possible, but the cost of storing such a file will be sky-high.
Hack MD5 in turbo mode
Hacking hashes by exhaustive search even on the best hardware takes quite a lot of time, especially if the password is more than eight characters. The easiest way to increase the speed of password guessing is to create a database of all hashes for a specific set of characters. In the 80s of the last century, hackers believed that when they had more powerful hardware, 640 KB of memory and a 10 MB hard drive, then such a database would become a reality and selecting any password would turn into a matter of minutes. However, iron developed, and the dream remained a dream. The situation changed only in August 2003, after Philip Oeschlin, Ph.D. in computer networking from the Swiss Institute of Technology in Lausanne, published his work on the problem of choosing the optimal place-time ratio. It described a method for breaking hash functions using rainbow tables.
The essence of the new method is as follows. First you need to select an arbitrary password, which is then hashed and is exposed to the reduction function, which converts the hash into some possible password (for example, it can be the first 64 bits of the original hash). Next, a chain of possible passwords is constructed, from which the first and last elements are selected. They are written to the table. To recover the password, apply the reduction function to the original hash and look for the received possible password in the table. If there is no such password in the table, hash it and calculate the next possible password. The operation is repeated until a password is found in the rainbow table. This password represents the end of one of the chains. To find the original password, you need to run the entire chain again. Such an operation does not take much time, depending on the algorithm for constructing the chain, this is usually a few seconds or minutes. "Rainbow" tables can significantly reduce the amount of memory used compared to conventional search. The only drawback of the described method is that it takes quite a lot of time to build tables.
Now let's move from words to deeds and try to crack a couple of password hashes using this method.
Rainbow tables - “Rainbow” tables are a special type of dictionary that contains chains of passwords and allows you to pick up a password in a few seconds or minutes with a probability of 85–99%.
First you need to decide on the program. Personally, I like RainbowCrack, which is free and runs on both Windows and Linux. It supports four hashing algorithms: LN / NTLM, MD5, and SHA1. The program does not require installation, just unzip it somewhere on the disk. After unpacking, you need to find the rainbow tables for the MD5 algorithm. Everything is not so simple here: they can either be downloaded for free, or bought, or generated independently. One of the largest archives of free tables is available on the Free Rainbow Tables project website.
By the way, you can also help the project if you download a client from the site and join a distributed international network that generates rainbow tables. At the time of writing, 3 TB tables for MD5, SHA1, LM, and NTLM algorithms were already available on this site. If you don’t have the opportunity to merge such a volume of information, then on the same site you can order discs with rainbow tables. Currently, three packages are offered: LN / NTLM, MD5 and SHA1 - 200 dollars each. We will generate the tables ourselves. To do this, you must use the rtgen program included with RainbowCrack. It accepts the following input parameters:
- hash_algorithm - hash algorithm (LM, NTLM, MD5 or SHA1);
- charset - one of the character sets contained in the charset.txt file;
- plaintextlenmin and plaintextlenmax - minimum and maximum password length;
- tableindex, chainlen, chainnum and partindex are “magic numbers” described in an article by Philipp Oashlin
Let's consider the last parameters in more detail:
- table_index - the index of the rainbow table, which can be used when breaking the table into several files. I used 0, since my table consisted of only one file.
- chain_len - the number of unique passwords in the chain.
- chain_num - the number of chains in the table.
- part_index is a parameter that defines the beginning of the chain. The creators of the program ask to use only a number as this parameter (I used 0). Now run the generation of the rainbow table for MD5:
rtgen.exe md5 loweralpha-numeric 1 7 0 2000 97505489 0
In this case, we create a password table consisting of numbers and capital letters of the Latin alphabet and having a length of one to seven characters. On my Eee PC with an Intel Atom N450 processor, this process took almost two days. . As a result, I received the file md5loweralpha-numeric # 1-702000? 975054890.rt in size of 1.5 GB.
Next, the resulting table must be sorted in order to optimize the search for the chain we need. To do this, run rtsort.exe:
We are waiting for a couple of minutes and the table is ready! Now you can break the passwords themselves. First, let's try to find a password for one hash: d8578edf8458ce06fbc5bb76a58c5ca4. Run rcrack_gui.exe and select Add Hash ... from the File menu. In the window that appears, enter the hash and click OK. Now select the file with the rainbow table. To do this, use the Search Rainbow Tables ... item in the Rainbow Table menu. In the window that opens to select a file, look for a file with a table, I have it md5_loweralpha-numeric # 1-7_0_2000x97505489_0.rt, then click Open. After a few seconds, the password is in our hands! A similar operation can be performed on the list of hashes from the file.
I generate a rainbow table
Rainbow tables vs. CPU vs. GPU
I think you paid attention to how quickly Ighashgpu is able to crack MD5 hashes by exhaustive search, and to the fact that RainbowCrack does this even faster with a good rainbow table. I decided to compare the speed of these programs. For the purity of the experiment, I used the MDCrack program, which brutes the password on the CPU (and is one of the best among programs of this type). Here is the result for the GPU (nVidia GeForce GT 220M), CPU (Intel Atom N450, two cores) and rainbow tables:
Длина пароля | GPU | CPU | Таблицы
4 символа | 00:00:01 | 00:00:01 | 00:00:16
5 символов | 00:00:02 | 00:00:09 | 00:00:16
6 символов | 00:00:16 | 00:05:21 | 00:00:10
7 символов | 00:07:11 | 09:27:52 | 00:00:04
As you can see, the search speed using the CPU is much slower than using the GPU or rainbow tables. Moreover, most specialized programs allow you to create a cluster of video cards, so the password search speed increases significantly. I think you noticed that the speed of matching 4- and 5-character passwords is lower than the speed of matching passwords of six or seven characters. This is due to the fact that the search for the password begins only after loading the table into memory. It turns out that out of sixteen seconds, an average of thirteen is spent on downloading and three on hacking the hash.
Rainbow table inside
bit.ly/vEhdir - adding a new hashing algorithm to RainbowCrack using the API.
bit.ly/vTSB9K - description of the format of the rainbow table.
Instead of a conclusion
In the end, I would like to talk a little about protecting your passwords. First, do not use vulnerable hashing algorithms such as MD5 or SHA1. At the moment, it is worth considering the use of one of the cryptographic hash functions SHA2 or SHA3 (as soon as the corresponding standard is published). Secondly, do not use hash functions directly. Always try to use salt and combine different algorithms. And thirdly, choose complex random passwords with a length of at least eight characters. Of course, this will not protect you from hacking by 100%, but at least complicate the life of attackers.