Thank you for the reply!
In that case, how would you store the salt? Because suppose I'm logging in. To compare my password to the stored hash, the system has to know exactly the salt that was added to the hash. But well... if you store the salt in your db as a string, it's basically the same as not salting it. And you can't hash it or you won't be able to recover it.
Well, we're talking about very technical topics, and especially theoretical.
Lets say that at the mathematical level, what I can I say is only a small part of the concept.
Yes indeed, because the function for a cryptographic hash is a one-way compression function, it is not a one-way trapdoor function. One-way trapdoor function is instead used in public encryption.
A one-way trapdoor function is something that becomes easy to invert if you have an extra knowledge. An hash encryption function is defined one way and "compression" (obviously lossy, indeed, a fundamental characteristic is to map the space of strings of any length to strings of a given length). Nothing prevents you to ask for that is also one-way trapdoor (of course that does not allow for a true reversal, in view of the poor injectivity of a hash function), but this is done only for very specific applications (e.g. reducing the time of the online computation for RSA signatures) and none of the standard hash functions has a trapdoor (or at least I hope).
However, I've heard that taking the salt from usernames can be a bad idea, and instead, the salt should be completely random and long enough. Then how would you know what the salt is? I thought about encrypting the salt table, that's the only approach I can remember. But that seems weirdly complicated (where would you store the encryption key?), and in my head, it doesn't sound as good as scrambling the username to get the salt.
Am I missing something? Do you know how that would work?
The fact is that the "password+salt" system is assigned forcibly. It may not be a function of the password, because otherwise it would be part of the same hash.
You consider that there are many precomputed hash database (rainbow table), and so it is not too difficult to find out what is the hidden password with the MD5 hash. Salt makes the creation of rainbow tables more difficult.
You try to imagine: you want to do all the hashes of all the passwords of only 8 characters, with an alphabet of 26 characters, you have to calculate 26^8 possibilities, each of which requires 8 bytes + 16 bytes for a hash 128 bits: in total, a database from 10^13 bytes, about 4 Tera.
Adding even just 2 bytes of salt, however, the same calculation leads to a DB of 3081 Tera!