In this article, I’ll try to explain as much as I can about hashes and collisions and my latest discovery of a triple hash collision while keeping things as simple as possible.
What Is A Hash:
It’s a cryptographic function, which takes some data as input, and generates a string, usually composed of hex characters. Now, hash differs from a checksum. Checksums are mostly made for files, to verify they’re integrity, while a hash can be both used for files and passwords(or plaintext data).
What Is A Hash Collision:
It’s when a different type of data, including plaintext, exactly matches the same hashes.
First hash collisions were theoretically predicted since the input data can be infinite and wildly different. The output is quite limited(16 bytes for MD5, 8 bytes for MySQL(64) ), but it was never proved then. Hash collisions were found for the MD5 hash, yet for file data. So, ways were found to generate files that have the same hash with different data.
Can This Be Used In A Malicious Way:
Well, it was actually used to generate a fake SSL certificate, which had MD5 hashing. Currently MD5 is never alone used for certificates, but instead mostly with SHA.
What About plaintext Hash Collisions:
MD5 hash collisions have yet to be found.
What Are Hash Collisions Good For:
Since nobody stores passwords in plaintext format, but instead in hash form, a person who can create collision passwords looks the same as the actual owner of the password to the system so the system grants access.
Double Hash Collision Discovery:
I recently discovered a plaintext hash collision for the MySQL(64) hashing algorithm. To find it, I used special hashcracking software and a Nvidia GTX 285 GPU. My first collision discovery was made on August 17th, 2010.
First Hash Collision: MySQL64(король) = MySQL64(bXBKkEHxi,i) = 745d019f415d9513
Both passwords generate the same hash. The original password is russian and translates as “king”. When I posted my discovery on the InsidePro forums, I did find out that I was not the first one to discover a MySQL(64) hash collision. XSerg found the first MySQL(64) collision, and he did it on June 26th, 2008 which at this time is more than 2 years ago!
Xserg did not spread the word but I still was not the first one to find a MySQL(64) hash collision. After discovery of the hash collision I decided to try and find collisions to three passwords and prove some things about this stuff in general. I took the password “QuantumCollision” as initial start, hashed it, and started bruteforcing it. After about 5 hours of bruteforcing the initial hash a collision was found! The password which was found was “bcSeW’!Tzu” . Now that was lovely, but I needed another password to be found, so I started bruteforcing again, but using another charset. In about 30 minutes, another password was found, which was “fxO5H23g,]” .
Triple Hash Collision: MySQL64(QuantumCollision) = MySQL64(bcSeW’!Tzu) = MySQL64(fxO5H23g,]) = 2f5b521d1ea3e566
That is the world’s first public triple hash collision.
Why Make It Public:
Well the government which has a huge amount of computing power and the tendency to buy out brilliant minds, could have found it long ago, but it was considered a “government secret”.
Triple Hash Collision Discovery Conclusions:
- MySQL(64) Analysis: MySQL(64) is now considered completely broken, worse than WEP, and it should not be used any more, so upgrade and use the more secure MySQL hashing based on SHA.
- Hash Output: I’ve proven practically that, with an infinite amount of input and limited output, some plaintext will generate the same output. However, with every new collision found, the time to generate another single one will increase.
- MySQL(64) Hash Strength: Any MySQL(64) hash can be “cracked” in matter of hours at the speed of 50T p/s.
- GPU Power: Computation on GPUs is a indeed a big step ahead, so porting even the most complex stuff to GPUs(like factoring using GNFS, ECM) is a good idea.Actually, new and more powerful graphic cards are nowadays released faster than CPUs.I consider GPUs > CPUs somewhat like SSDs > HDDs. All have they’re pros and cons.
- Hash Strength In General: Using simple hashing algorithms, without heavy iterations and salts is a bad idea in terms of security.
The World’s First 3 Plaintext Collisions Were Found Because:
- Secret Squirrel spotted a major weakness in MySQLv323 hashing algorithm and used it to create a CPU application that could bruteforce a single hash in [0;6] all-space in a matter of seconds. He published the source code to public domain.
- XSerg ported that original code to CUDA which increased the speed of bruteforcing to trillions passwords per second. The source code of this CUDA app remained open.
- Schwarzwaldhacker took XSerg’s code, rewrote, and optimized some parts of it which further increased the flexibility and speed of the bruteforcer. The source code was promised to be released some day.
- Nvidia and it’s great urge towards developing CUDA as best GPGPU language.
Thanks to everyone who helped make it possible for me to accomplish this!