0
$\begingroup$

This question revolves around the Hashing Algorithm attribute that the resulting digest is always the same size (also known as Fixed Width). For example, whether you hash the word "hello", or 10gb file, MD5 will always return a 128 bit digest.

My question is, how do hashing algorithms always result in a constant length digest ?

The only operation I can think of is the MOD / remainder operation that regardless of the starting value, after doing a MOD operation using modulus X, the result is always a value between 0 and (X-1). But I am specifically curious if there are other operations that also serve in reducing (or increasing, I guess) the digest size to get to the desire digest length.

note: I am not interested specifically in how MD5 does it, but in what operations exist that any hashing algorithm might use to always ensure the same size digest

$\endgroup$
  • 2
    $\begingroup$ For MD4,MD5,SHA1,SHA2 see en.wikipedia.org/wiki/Merkle%2dDamgård_construction, for SHA3 and others see en.wikipedia.org/wiki/Sponge_function $\endgroup$ – Henno Brandsma Nov 16 '15 at 19:29
  • 2
    $\begingroup$ To give a quick idea to OP, one way to achieve this is to (for instance), break an arbitrary-length message into fixed-size blocks, operate on the first block, combine it with the second block (XOR, ADD, whatever), operate on this result, combine it with the third block, and so on. $\endgroup$ – Stephen Touset Nov 16 '15 at 20:20
  • $\begingroup$ @StephenTouset That makes sense. Could you give an example of how that process would work if the string being hashed is smaller than the digest size? AKA, how does "hello" (5 bytes) turn into a 16 or 20 byte digest in the case of MD5 and SHA1, respectively. $\endgroup$ – Eddie Nov 16 '15 at 22:16
  • $\begingroup$ Padding. This converts any message into a unique message with length divisible by a given block size. $\endgroup$ – Stephen Touset Nov 16 '15 at 22:43
4
$\begingroup$

Basic Building Blocks of a Hash Function

The part of a hash function that leads to the digest always being the same size regardless of input length is called the compression function. The compression function is then linked whmacith a domain extender which extends the compression function to allow it to map across any length of input.

Construction From Block Ciphers

I am going to use the construction of the WHIRLPOOL hash function as an example of how a compression function and domain extender works.

Setup

It is very simple to construct a hash function from a block cipher. The first step in a block cipher algorithm would be to split the data to be hashed into blocks the same number of bits as the input to the block cipher being used. If needed padding is added to the input to make it a multiple of the key size. No difference here from normal block cipher operation.

Compression Function with Domain Extension

There is a lot of variation between different designs here but basically what they all perform though is some means of feeding each block into the chosen cipher and some combination of XOR or some other operation on the previous rounds output, the current rounds output, the input, or all of the above. For example the following is the compression function of WHIRLPOOL.

For the following let: $$ \begin{align} m_i\:&=\:\mbox{Message or Input}\\ H_i\:&=\:\mbox{Output}\\ W\:&=\:\mbox{Block Cipher}\\ g\:&=\:\mbox{Bit Mapping Function} \end{align} $$
The compression function of WHIRLPOOL

To construct a new hash function it would be possible to simply plug a new block cipher into $W$ and the size of input and output would change with the input and output new cipher. There are many other forms of compression function structures with different properties also, and they mainly consist of changing when, what, and in what order things are combined. I would put a link here but reputation limit, so wikipidia's compression functions article has more on this.

The domain extension which allows it to operate over any amount of data is simply how the output feeds back into the cipher as the key as each subsequent block is encrypted replacing the key schedule. It will only output the result after all blocks have been fed through the block cipher effectively limiting output to the size of the ciphers output no matter the input size.

Other Constructions

There are also hash functions that are based on mathematical problems that are hard to solve and also stream ciphers. This is really a topic that an entire book could be dedicated to but they all use the basic structure of a compression function and domain extender. More info on the general construction of hash functions, compression functions, and domain extenders can be found here: https://eprint.iacr.org/2012/322.pdf

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting and good answer $\endgroup$ – user20030 Nov 19 '15 at 5:57
  • $\begingroup$ I have a question regarding this, is it possible somehow to reduce the size of an arbitrary message to a fixed input of 128 bits somehow? $\endgroup$ – Scarl Feb 5 '17 at 13:16
0
$\begingroup$

This is just an analogy, but I think it is helpful. Think of the hash function as a Rubik's cube. As each part of the input comes in, it commands a different manipulation of the cube. There is no manipulation that can enlarge or shrink the cube, it is just rotated in the various ways possible... leading to a scrambled output of a known, fixed sized.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.