What a normal web developer needs to know about cryptography. Part 1: hashing
Another writing in the "let's squeeze a book into an article" format.
Cryptography knowledge among web developers tend to gravitate towards the extremes: from complete cluelessness on one side to being a cryptography professional on the other. An average dev that doesn't work in infosec tends to know nothing about the subject matter. How much cryptography knowledge is actually necessary in the day-to-day SWE job?
Not much, actually. A bit about hashing, a bit about symmetric and asymmetric encryption, a bit about digital signatures. This modest package is enough to carry 80% of web developers through the whole career. We'll cover these things here. What we won't cover: specific details of encryption algorithms and ways to defeat them. Thoughtful people that are much smarter than me publish whitepapers on this topic and collect government grants for them. This is a field guide, not a whitepaper. It's split into three parts:
- Hashing (you are here)
- Encryption (currently WIP)
- The rest: non-cryptography and some common misconceptions
What is hashing?
Hashing is an important concept in computer science for many reasons, both in the cryptography context and beyond it. Namely, it's a go-to way to securely store passwords.
Hashing is the process of taking some input, processing it according to a hashing algorithm and producing some output (also known as "digest"), with these additional constraints:
- Output size is fixed;
- Hashing works only one way and is irreversible;
- Same input produces the same output.
Let's take a closer look at them, because they are important.
Rule 1: output size is fixed
If a hashing function supposed to produce 32 bytes worth of output, it will produce exactly 32 bytes every single time, regardless of the input length. You feed it War and Peace, or you feed it number 4 - it will be the same output length.
Example: this is the result of hashing of the input string "crypto is easy" using the MD5 hashing algorithm:
b030d6554ddff1821761ead7f832de38
And this is the result of hashing of the number 42 using the same algo:
a1d0c6e83f027327d8461063f4ac58a6
As you can see, both hashes have the same length, even though the input lengths are different.
Rule 2: Hashing works only one way and is irreversible
In a good hashing algorithm, it should be impossible to infer the input by looking at the output. This "one-wayness" does not stem from some secret formula: hashing algorithms are usually well-documented and everybody can see how they work.
— If we know what an algorithm does, why can't we reverse it?
Some things work in just one direction. You know the algorithm of cooking an omelet. Still, you can't take an omelet and convert it back to raw eggs.
A more concrete example:
Imagine an app that requires user passwords to consist of six numbers. The app then multiplies all these number, and saves the result. If the password is 426269, the result would be 4 * 2 * 6 * 2 * 6 * 9 = 5184.
Now, I'm giving you this result: 1680. Despite knowing the formula, there's no way for you to reliably infer the input numbers.
This example is oversimplified, but it demonstrates the idea: in math, some things work one-way only.
Real hashing algorithms use much more robust formulas, with much better prevention of reversing. Sometimes reversing happens nevertheless, and that's a reason to consider the algorithm insecure and immediately stop using it for anything security-related.
As mentioned before, hashing has many uses besides cryptography. Sometimes a cryptographically insecure algorithm is still good enough to be used for non-cryptographic purposes, such as checksum calculation. A well-known example is MD5. It was cracked in 2004, but still used for checksum calculation or data integrity verification, because it's cheap and simple.
Here's a hash of a very secretly secret string:
51b4e0e3bf34bed94b115512449b2a235b1961adc46b34a15ab8b97fd3d4a462
It's produced using SHA-256 hashing algorithm. You cannot infer what string is hashed here by just looking at the hash. If you can, you're entitled to a hefty monetary prize, and the industry will be in shambles.
Rule 3: same input produces the same output
You take a string and hash it a million times, the resulting hash must be the same a million times. No randomness.
Hashes and passwords
In a typical web application, hashing is used to securely store passwords. Consider this simplified example:
A user registers with an email "john@example.com" and a password "Password123" and the app stores both the email and the password in a database. A hacker then somehow gains access to the database. If passwords are stored as plain text, the attacker sees every email/password pair and is able to log in on behalf of any user.
Now, imagine that instead of storing plaintext passwords like "Password123", we hash them, and store their hashes, like this: 008c70392e3abfbd0fa47bbc2ed96aa99bd49e159727fcba0f2e6abeb3a9d601. Remember the rule #2: hashing is a one-way process. Even if an attacker steals the hashed string, there is no way for them to get the actual password from it.
— But it also means that we can't see the actual password ourselves. Then how we verify passwords on user logins?
Surprisingly, you don't have to know a password to verify if it's correct. Remember the rule #3: same input produces same output. When a user tries to log in with a password, you hash it and compare the hash with the value in your database. If they are the same, the provided password is correct. This is the technique that is used in vast majority of web apps.
— I still need to see the original passwords sometimes! I log in on behalf of my users.
You don't need to know a password to log in on behalf of your users. See the impersonation chapter in my other article.
— I _still_ need to see original passwords for other reasons.
Sigh... Alright, there is a relatively secure way to do that without storing passwords in plain text. We'll get to it in the Symmetric Encryption chapter. But keep in mind that it's still not a good idea, and your infosec colleagues will hate you.
Hashing algorithms worth knowing
General purpose hashing:
SHA-256- the current default for general purpose hashing.SHA-512- rarely seen, but sometimes used in performance-critical paths. Because, surprisingly, it could be faster than SHA256.SHA-1- was considered a default before, but mostly discontinued. In 2005, some theoretical work was published, that demonstrates some theoretical ways to find collisions (two different inputs with the same hash), and the algorithm fell out of favor by 2010. Still used to this day sometimes. Notably, git versions before 3.0 use SHA-1.MD5- not cryptographically safe since circa 2004, still used for other things.
Password hashing:
Argon2id- modern default;PBKDF2- most widely used, and often the only allowed choice in regulated environments (government, finance, healthcare);bcrypt;scrypt.
Password hashing vs general-purpose hashing
— Wait, why there are separate algos for password hashing?
Because password hashing has additional requirements, and general-purpose algorithms are not a good fit.
When we talk about algorithms in the context of software development, we usually want them to be effective. We want our hash maps and checksum calculations to be as fast and cheap as possible. A good password hashing algorithm, counterintuitively, must be slow and expensive. The algorithms from the second category are special wrappers around general-purpose algorithms, purposefully created to be slow and expensive.
Brute force attacks
If a hacker steals our database with password hashed with just SHA256, they can't get source passwords from the hashes, but we're not out of trouble yet! The hacker can generate SHA256 hashes for possible passwords, and look for those hashes in the stolen database. If some of that hashes match, the attacker knows the original password for that hash.
SHA256 is very fast, on modern hardware it's possible to generate billions of combinations. Specialized password hashing algorithms, such as bcrypt, are thousands of times slower, thus making brute-force iteration thousands of times slower. They are still fast enough for legitimate usage.
bcrypt and PBKDF2 make brute-force CPU-expensive. Newer algorithms, such as Argon2id and scrypt, in addition to being CPU-expensive, also consume much more RAM, making the brute-forcer's life even harder.
Rounds of hashing
I promised not to go into technical details in this article, but "rounds of hashing" is seen often enough to be explained.
Secure algorithms, such as bcrypt, hash input many times, sometimes - many thousand times.
A simplified example:
Take plaintext password -> hash it -> hash the result again -> hash the result of previous step again -> repeat again -> ...
By performing multiple rounds of hashing, we effectively raise the time required to complete hashing. Ten rounds of SHA256 will take ten times more that one. This is still fast enough to check passwords for legitimate users trying to log in, but make life of brute-force attackers much more difficult.
Over time, the recommended number of rounds rises. In 2000, a thousand iterations was considered good enough. Today, OWASP recommends 600,000 for PBKDF2-HMAC-SHA256, 600x increase. Hardware (esp. GPUs) has surely made a lot of progress since 2000.
It's worth noting that real password hashing algorithms do more things than just hashing input multiple times. Don't try to manually re-implement them, the result will be less secure than a stock solution.
Dictionary attacks
Instead of going through all possible combinations alphabetically, an attacker can instead try to check the most popular ones first. This is called dictionary attack. Turns out, people are very predictable when choosing passwords. There are many lists of the most popular passwords that have much higher chance to be picked over some random strings.
Rainbow tables
Another popular attack method is called rainbow table attack. In the brute-force attack, an attacker generates hashes on the fly. Alternatively, they can purchase or generate a table of pre-calculated hashes, like this one:
| Plain text | Hash |
|---|---|
| Password | e7cf3ef4f17c3999a94f2c6f612e8a888e5b1026878e4e19398b23bd38ec221a |
| Password1 | 19513fdc9da4fb72a4a05eb66917548d3c90ff94d5419e1f2363eea89dfee1dd |
| Password2 | 1be0222750aaf3889ab95b5d593ba12e4ff1046474702d6b4779f4b527305b23 |
| Password3 | 2538f153f36161c45c3c90afaa3f9ccc5b0fa5554c7c582efe67193abb2d5202 |
| ... | ... |
| Password123 | 008c70392e3abfbd0fa47bbc2ed96aa99bd49e159727fcba0f2e6abeb3a9d601 |
| ... | ... |
Tables like this are called "rainbow tables". They contain millions of hashes pre-calculated for millions of common passwords. The attacker can use them to find matching hashes in the stolen database without wasting time on hash generation.
Rainbow tables have practical size limits, because the number of possible password variants grow exponentially with length. A rainbow table that contains all hashes of all possible alphanumeric passwords with the length up to five characters can be generated in a split second. Same table, but for 30-symbol passwords, would take centuries to generate. Therefore, a long, high quality password will probably not be there. Unfortunately, users tend to pick short, trivial and predictable passwords. Even if your app enforces some minimal password complexity (min 8 characters, uppercase-lowercase-numbers etc.), chances are these measures are not good enough. Luckily, there are ways to harden the security, and for that we'll need some seasoning.
Cryptographic salt and pepper
We want our passwords to be long and complex enough to be absent from rainbow tables. At the same time, we don't want to inconvenience our users demanding 30-characters passwords with numbers and special symbols. To solve this dilemma, we can use cryptographic salt.
Cryptographic salt is a random string that is concatenated with a password before hashing. An example: a user has a password "Password123", and we define a salt string "SaltString456". When a user registers, we store the salt alongside the password:
| UserId | Salt | HashedPassword |
|---|---|---|
| 1 | SaltString456 | hash of "SaltString456Password123" |
| ... | ... | ... |
Many modern hashing algorithms store salt and other metadata, such as algorithm version or # of hashing rounds, concatenated with the hash string itself, not in a separate column. That's OK, because this information is not considered secret, and will not help an attacker in any meaningful way.
The user later wants to log in and provide the password Password123. In our app, we concatenate it with the salt to get SaltString456Password123 and then get a hash of this "salted" string. If a hacker steals our DB, they will see the salt and the hash, but it would not help them. There is a high chance that the hash of Password123 is already in their rainbow table, but a much lower chance that the hash of SaltString456Password123 is. This way, by adding a salt string, we can drastically improve resistance against rainbow table attacks. Just make sure that the salt is long enough. Many modern crypto libraries take care of that automatically.
Salt should be unique per password. Do not repeat it. Remember rule #3: same input produces same output. So if you have five users with the same password Password123, they all will have the same hash in the DB. If an attacker somehow knows one password (e.g., by using social engineering), all five will be compromised. If the salt is unique, all five hashes will be different, reducing the attack surface to just one password.
Cryptographic pepper is largely similar to the salt and uses the same principle: it's a string that is concatenated with the password before hash calculation. Unlike salt, pepper is not stored alongside the hash. It should be stored securely and separately. Sometimes it's a static string that is reused for every password, sometimes it's randomized. Generally, pepper is an additional security measure that comes after the salt.
Don't roll your own cryptography
One common advice universally agreed on: don't try to reinvent the wheel. If you're not in infosec business, your homemade solution is guaranteed to be less secure that trusted open-source libraries. If you are in infosec business, you already know this.
Conclusion
Congratulations for making it this far! In the second part we'll talk about another important concept: encryption. By the way, the secretly secret hash mentioned earlier is a SHA256 of this paragraph. Go check it!