# Hashing large messages, how does it work?

Is the message divided into chunks, each chunk hashed separately, or something else?

• are you using a library or thinking about the internals? – kelalaka Sep 23 '19 at 9:04
• just overall how it usually works – H45hish Sep 23 '19 at 9:05

Hashing small messages works identical to hashing large messages.

Merkle–Damgård construction:

Currently the most common hash functions are based on the Merkle–Damgård construction (i.e. MD5, SHA1 and SHA2).

A message is divided into equal sized blocks and then each block goes through a one way compression function (to be exact, the next to be compressed block is appended to the compressed result so far to get a size-reduction). If you have a large message then it just has more blocks and therefore takes a little bit longer.

• Thanks. I have an idea for a one-way function that uses a public ledger as a "labyrinth", and the message as a "map", and thought that most of the technical issues such as... how to hash large messages, have been solved long ago. What you describe is my exact own ideas for how to combine my one way function with large messages. – H45hish Sep 23 '19 at 9:50

While hashing, the messages are divided into chunks and padded so that a message is fit into the chunks, properly. For example in SHA-256 the message appended 1, then many zeroes and finally the message size in 64-bit added. The total size must be $$x$$ multiple of 512 where $$x$$ is minimum.

No, they are not separately hashed, they are chained. If not it how would you combine the output? If you don't combine what is a hash there? There is actually, hash trees famously know as Merkle Trees used to verify data blocks, or many files where you only keep the root hash.

SHA-256, for example, uses Merkle–Damgård (MD) construction in which a compression function $$F$$ which is

$$F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$$

The 512-bit input space is the message space. 256-bit input space is the previous hash, if it is the first block then an IV is used.

let $$M\mathbin\|pad=m_1\mathbin\|m_2\mathbin\|\ldots\mathbin\|m_\ell$$ $$H_i = F(m_i,H_{i-1})$$ with $$H_0 = IV$$ then

$$\operatorname{SHA-256}(M||pad) = F(m_\ell, F\ldots F(IV,m_1)\ldots))$$

This tells you about the MD construction, MD5, SHA-1, SHA-2 uses MD. There is also sponge construction that SHA-3 is based on, which left the OP as an exercise.