Hacking hashes¶
Hash functions, like MD5, SHA-1, SHA-256, SHA-3, and BLAKE2, are used in digital signatures, public-key encryption, integrity verification, message authentication, password protection, key agreement protocols, and many other cryptographic protocols.
Security goals¶
Hash functions in applied cryptography are constructions that were originally defined to provide three specific security properties:
Pre-image resistance ensures that no one should be able to reverse the hash function in order to recover the input given an output.
Second pre-image resistance: given an input and the digest it hashes to, finding a different input that hashes to the same digest should not be feasible.
Collision resistance: one should not be able to produce two different inputs that hash to the same output.
This definition has changed over time, and is often meaningless on its own; it all depends on how the hash function is used.
In addition, hash functions are usually designed so that their digests are unpredictable and random. This is useful because one cannot always prove a protocol to be secure.
Many protocols are instead proven in the random oracle model, where a fictional and ideal participant called a random oracle is used. In this type of protocol, one can send any inputs as requests to that random oracle, which is said to return completely random outputs in response, and, like a hash function, returns the same output when given the same input twice.
Proofs in this model are sometimes controversial as it is not known for sure whether these random oracles can be replaced with real hash functions (in practice). Yet, many legitimate protocols are proven secure using this method, where hash functions are seen as more ideal than they probably are.
Finding collisions¶
Naive birthday attack¶
Compute \(2^{n/2}\) hashes of \(2^{n/2}\) arbitrarily chosen messages and store all the message/hash pairs in a list.
Sort the list with respect to the hash value to move any identical hash values next to each other.
Search the sorted list to find two consecutive entries with the same hash value.
This method requires a lot of memory (storing \(2^{n/2}\) message/hash pairs), and sorting lots of elements slows down the search, requiring about \(\frac{n}{2} \cdot 2^{n/2}\) basic operations on average using even the quicksort algorithm.
The Rho method¶
The Rho method is an algorithm for finding collisions that, unlike the naive birthday attack, requires only a small amount of memory:
Given a hash function with \(n\)-bit hash values, pick some random hash value (\(H_1\)), and define \(H_1 = H'_1\).
Compute \(H_2 = Hash(H_1)\), and \(H'_2 = Hash(Hash(H'_1))\); that is, in the first case apply the hash function once, and in the second case twice.
Iterate the process and compute \(H_{i+1} = Hash(H_i)\), \(H'_{i+1} = Hash(Hash(H'_i))\), until reaching \(i\) such that \(H_{i+1} = H'_{i+1}\).
Advanced collision-finding techniques work by first detecting the start of the cycle and then finding the collision, without storing numerous values in memory and without needing to sort a long list.
Cracking hashes¶
Given a hash value, recovering the data it came from has no unique solution in general. For short objects like passwords, there is. If someone uses an MD5 function to obscure a password (done by some old web applications still existing in the wild), then it can be reversed by guessing passwords until finding a match. There is no mathematical way to undo a hash function, so the practical route is a lookup of known hashes.
Windows passwords¶
The hash used by, for example, Windows Server is the NT Hash. If two users have the same password, they have exactly the same hash.
The algorithm Microsoft uses takes the password and encodes in Unicode instead of ASCII, to allow for passwords in languages such as Chinese and Japanese that do not encode with 8-bits per character but 16-bits per character. Then it is run through MD4 (an algorithm even older than MD5) to produce the NT hash value.
Because password hashes have no variation and any two users with the same password will have the same hash, all the hackers who have cracked wordlists over the decades have put their results on the internet. For example, crackstation or hashes.com can be used. This availability has even resulted in a situation where frequently used password hashes can simply be Googled.
When the passwords cannot be cracked, guessing can be tried using hashlib. Make a series of guesses (or use a passwordlist), hash them, and hunt for the answer.
import hashlib
hashlib.new("md4", "password".encode("utf-16le")).hexdigest()
Linux password hashes¶
In Linux, the hashes can be found in the /etc/shadow file.
username:$6$ligE06T/QLQMANm9$8GDajwZJahwNnnW/OtfwLUGZHYcmTd9RByNz2e32iJAx37fSu7R1mpxTwWOqwlc4etyR/SLBkfiksitUHXRVV.:18961:0:99999:7:::
After each username comes $6, which indicates it is a type 6 password, then there is a random string of characters that goes up to the next dollar sign, the salt, and then an even longer random string of characters, which is the actual password hash itself.
When users have the same password, they have completely different hashes, because a random salt is added before hashing them, to obscure the fact that these passwords are the same.
Besides salting, stretching is also used. Calculating the hash uses 5,000 rounds of SHA-512, which takes much more CPU time. This might slow down attackers trying to make dictionaries of password hashes.
Make a series of guesses (or use a wordlist for a dictionary attack), hash them, and hunt for an answer.
from passlib.hash import sha512_crypt
sha512_crypt.using(salt="ligE06T/QLQMANm9", rounds=5000).hash("password")
This will be very, very time-consuming. Hashcat or John the Ripper can also be used.
Security¶
Despite their apparent simplicity, hash functions can cause major security troubles when used at the wrong place or in the wrong way, for example, when weak checksum algorithms like CRCs are used instead of a crypto hash to check file integrity in applications transmitting data over a network. However, this weakness pales in comparison to some others, which can cause total compromise in seemingly secure hash functions.