All MD5 hacking methods
It's no secret that cryptography has firmly entered our lives. Internet services, social networks, mobile devices - all of them store user passwords encrypted with various algorithms in their databases.
The most popular such algorithm today, of course, is MD5.
On the methods of hacking and will be discussed.
A little bit about cryptography
Modern cryptography includes three areas: private key encryption, public key encryption and hashing. Today we will talk about what hashing is and what it is eaten with.
In general, hashing is understood to mean the conversion of input data of arbitrary length into an output bit string of fixed length. Most often, hash functions are used in the process of user authentication (a 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 most well-known and widely used hashing algorithms is MD5.
The MD5 algorithm is a 128-bit hashing algorithm. This means that it calculates 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 at RFC 1321. After that, MD5 was used to solve various tasks, from hashing passwords in CMS to creating digital signatures and SSL certificates.
The fact that the MD5 algorithm can be hacked was first talked about in 1993. Researchers Bert den Boer and Anton Bossilaris showed that pseudocollisions are possible in the algorithm. Three years later, in 1996, Hans Dobbertin published an article in which he proved the existence of collisions and described the theoretical possibility of hacking MD5. It was not yet a hack, but the world began to talk about the need to switch to more reliable hashing algorithms, such as SHA1 (at the time of this writing, it was already proven that there are collisions in this algorithm, so I recommend using SHA2) or RIPEMD-160.
The immediate cracking of MD5 began on March 1, 2004. CertainKey Cryptosystems has launched MD5CRK, a distributed collision detection system. The goal of the project was to find two messages with identical hash codes. The project ended on August 24, 2004, when four independent researchers — Wang Xiaoyun, Feng Denguo, Lai Xuejia, and Yu Hongbo — discovered the algorithm's vulnerability, which makes it possible to find collisions by an analytical method in a more or less reasonable time. Using this method, it is possible to identify collisions on the IBM p690 cluster in just an hour (it’s a pity that I don’t have such a home).
An example of a collision MD5 hashes
On March 1, 2005, the first use of this vulnerability in practice was demonstrated. A team of researchers presented two X.509 certificates with different sets of keys, but with identical checksums. In the same year, Vlastimil Klima published an algorithm for detecting collisions on an ordinary laptop in a few hours. In 2006 he went further. 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 how to generate fake X.509 certificates was presented at the Chaos Communication Congress conference. In fact, this was the first case of real use of collisions in the MD5 algorithm.
MD5 Brutal Mask
Much work has also been done to hasten the hashes hacking. In 2007, Kevin Breeze introduced a program that uses the Sony PlayStation3 to crack MD5. He managed to achieve very good results: 1.4 billion MD5 hashes were generated in just one second! Two years later, in 2009, an article was published on BlackHat USA about using the GPU to search for collisions, which made it possible to increase its speed several times, especially if it was performed using several video cards at the same time.
ATI Radeon HD 4850 X2 video card allows you to generate up to 2.2 billion hashes per second! The use of the MD5 algorithm in EDS is unacceptable due to the lack of stability of this algorithm to the 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 against using it. In my opinion, this document officially put an end to MD5.
However, despite the fact that the MD5 algorithm was officially recognized as unsafe, there are thousands, if not tens and hundreds of thousands of applications that use it for storing passwords, in electronic-digital signatures and for calculating checksums of files.
By the way, on October 31, 2008, NIST announced a competition among cryptographers. The goal of the competition is to develop a hashing algorithm for the replacement of obsolete SHA1 and SHA2. At the moment, the finalists have already been determined - 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: d8578edf8458ce06fbc5bb76a58c5ca4.
To break 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 process of breaking a hash, Ighashgpu uses a GPU, so you need at least one nVidia or ATI video card with CUDA / ATI Stream support.
Modern graphics processors 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 past few years there has been a tendency to use them for ordinary computing. Getting started with the program is not easy, but very simple: unzip the archive to any place on the disk and start hacking using the Windows command line:
ighashgpu.exe -t:md5 \
We use the above method to break into one specific hash generated using the MD5 algorithm. The maximum possible password length 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 has the form d11fd4559815b2c3de1b685bb78a6283, and includes letters, numbers, underscore and has the suffix "_admin". In this case, we can use brute force by mask to simplify the program task:
ighashgpu.exe -h:d11fd4559815b2c3de1b685bb78a6283 -t:md5
Here the parameter '-u' allows you to specify the set of characters 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 “_admin” combination. Password selection is also not difficult.
Collisions - a collision in cryptography refers to two different input data blocks that, for the same hash function, give the same hash. Each output function gives a sequence of bits of a certain length that does not depend on the size of the original data. It follows that collisions exist for any hashing algorithm. However, the likelihood that you will be able to find a collision in the "good" algorithm, almost tends to zero. Unfortunately or fortunately, hashing algorithms may contain errors, like any other program. Many hash functions have either been broken or will be soon. In this case, “breaking down” 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 have a password password database in our hands. It is 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 is completed, the file ighashgpu_results.txt will appear in the Ighashgpu folder with the hacked passwords:
Hacked hashes from encrypted.dat file
Finally, let's crack the “salted” hash. Suppose that the hash is generated by 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 we got the password again 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 simply transcendental.
Hacking MD5 in turbo mode
Hacking hashes by busting even on the best hardware takes 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 disk, such a base would become a reality and the selection of any password would turn into a minute affair. However, iron developed, and the dream remained a dream. The situation changed only in August 2003, after Philip Oashlin, Ph.D. in computer networks from the Swiss Institute of Technology in Lausanne, published his work on the problem of choosing the optimal place-time ratio. It described the method of hacking hash functions using "rainbow" tables.
The essence of the new method is as follows. First you need to choose an arbitrary password, which is then hashed and affected by a reduction function that converts the hash into any possible password (for example, it can be the first 64 bits of the original hash). Next, a chain of possible passwords is built, from which the first and last elements are selected. They are recorded in a table. To recover the password, apply the reduction function to the source hash and look for the resulting possible password in the table. If there is no such password in the table, we will hash it and calculate the next possible password. The operation is repeated until the password is found in the "rainbow" table. This password is the end of one of the strings. To find the original password, you need to run the entire chain again. Such an operation does not take much time, depending on the chain construction algorithm, it 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 the 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 within 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 works on both Windows and Linux. It supports four hash algorithms: LN / NTLM, MD5 and SHA1. The program does not require installation, just unpack it somewhere on the disk. After unpacking, it is necessary to find the rainbow tables for the MD5 algorithm. Everything is not so simple here: you can either download them for free, buy them, or generate them yourself. One of the largest archives of free tables is available on the Free Rainbow Tables project site.
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 this writing, 3 TB tables for MD5, SHA1, LM and NTLM algorithms were already available on this site. If you do not have the opportunity to merge this amount of information, then on the same site you can order disks with "rainbow" tables. At the moment, there are three packages: LN / NTLM, MD5 and SHA1 - for $ 200 each. We will generate the tables ourselves. To do this, you must use the rtgen program, which is part of RainbowCrack. It takes the following input parameters:
- hash_algorithm - hashing algorithm (LM, NTLM, MD5 or SHA1);
- charset is one of the character sets contained in the charset.txt file;
- plaintextlenmin and plaintextlenmax - the minimum and maximum password length;
- tableindex, chainlen, chainnum and partindex - “magic numbers” described in the article by Philip Oashlin
Consider the last parameters in more detail:
- table_index is the index of the rainbow table, which can be used when splitting the table into several files. I used 0, because 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 the parameter that defines the beginning of the chain. The creators of the program are asked to use only a number as this parameter (I used 0). Now we start 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 table of passwords consisting of numbers and uppercase letters of the Latin alphabet and having a length of from one to seven characters. On my Eee PC with an Intel Atom N450 processor, this process took almost two days . In the end, I received the file md5loweralpha-numeric # 1-702000? 975054890.rt in the 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 yourself. First, let's try to find the 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 this 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 a file.
I generate a rainbow table
Rainbow tables vs. CPU vs. GPU
I think you paid attention to how quickly Ighashgpu is able to break through MD5 hashes by exhaustive search, and to the fact that RainbowCrack does it 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 performs a password password on the CPU (and is one of the best 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 lower than with the use of a GPU or "rainbow" tables. Moreover, most of the specialized programs allow you to create a cluster of video cards, thanks to which the speed at which the password is searched increases several times. I think you noticed that the speed of picking up 4- and 5-character passwords is lower than the speed of picking up a password of six or seven characters. This is due to the fact that the password search begins only after the table is loaded into memory. It turns out that out of sixteen seconds, on average, thirteen is spent on downloading and three on breaking a hash.
Rainbow table inside
bit.ly/vEhdir — add a new hash algorithm to RainbowCrack using the API.
bit.ly/vTSB9K - a description of the format of the "rainbow" table.
Instead of 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 thinking about using one of the cryptographic hash functions SHA2 or SHA3 (as soon as the relevant standard is published). Second, don't use hashing functions directly. Always try to use "salt" and combine different algorithms. And third, choose complex arbitrary passwords with a length of at least eight characters. Of course, this does not protect you from hacking by 100%, but at least complicates the life of intruders.