There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(dated 1979), and suffers from length extension attacks. New hashes might opt for the sponge construction, as it is immune to that particular attack.
As for how they work, they both contain an internal state, and operate on that state using a function that is actually invertible.
The Merkle–Damgård construction
In the case of the Merkle–Damgård construction, the function used is usually a block cipher. Normally, the go-to example of a block cipher is AES, but because of a related key attack, you would not want to use it to make a hash with this particular construction.
Basically, in the Merkle–Damgård construction, successive blocks of the hash input are used along with the internal state as the inputs to a block cipher; This is also how the construction compresses large inputs into a finite state. This is another requirement of hash functions: the ability to operate on (effectively) arbitrary sized inputs, and produce a finite sized output.
As for collision resistance, the MD construction has a proof: "... that if the one-way compression function f is collision resistant, then so is the hash function constructed using it.".
However, according to wikipedia, the MD construction itself, has generic vulnerabilities that are not the result of an unsatisfactory compression function:
Unfortunately, this construction also has several undesirable
- Second preimage attacks against long messages are always much more efficient than brute force.
- Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
- "Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more
work than finding a collision, but much less than would be expected to
do this for a random oracle.
- Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), where pad is the padding
function of the hash. That is, it is possible to find hashes of inputs
related to X even though X remains unknown. Length extension attack
was actually used to attack a number of commercial web message
authentication schemes such as one used by Flickr.
It is possible to use the MD construction with a sort of capacity, similar to a sponge, by not outputting the entire state. This is where the ideas of SHA-224 and SHA-384 fit in, for example. They are simply truncated outputs of SHA-256 and SHA-512 (with other small modifications). By not revealing the entire state, length extension attacks may be foiled, depending again on the "capacity", or number of bytes dropped this way. However, usage of a capacity/truncating the state does come at the price of a reduced output rate.
The sponge construction
The sponge construction operates in a different manner. The sponge too, has an internal state, and it uses an invertible permutation to mix the state. Basically, the sponge "absorbs" a message block into it's internal state, then applies the mixing permutation, and repeats this until all message blocks have been consumed into the state. This is how the sponge compresses data. The absorption of data either happens by XOR'ing the message block into the state, or simply replacing a section of the state with the message block.
The sponge construction being uninvertible, resistant to length extension attacks, and preimage resistant is related to the use of a "capacity" section of the state. Basically, there is an imaginary line dividing the internal state into two sections, a "rate" section, and the capacity section. The output stage of the function only "squeezes" bytes from the rate section of the internal state. Since the capacity is never output directly, length extension attacks are resisted. The security of the sponge against attacks is related to the capacity size of the state, along with how well the mixing function resists things like differential cryptanalysis.
There is a little bit more to hashing then a confusing/diffusing primitive that compresses data. Since we require that it be infeasible to generate any preimage for a given output, and prevent anyone from finding collisions, things like padding of the input become very important, in order to prevent trivial collisions from being created. This is a contributor as to why the construction of a hash is more complicated and often times requires more applications (rounds) then simply encrypting some data.
Other compression functions
There is actually an entire wikipedia article about one way compression functions, and there a few constructions one could use:
Some methods to turn any normal block cipher into a one-way
compression function are Davies–Meyer, Matyas–Meyer–Oseas,
Miyaguchi–Preneel (single-block-length compression functions) and
MDC-2, MDC-4, Hirose (double-block-length compressions functions)