7
$\begingroup$

What I understand is: When we parse a message into 512 bit message blocks. Then we extend the first message block to 64 entry array and start with the compression function.

What happens if the message is longer than 512 bits? As a result, we would receive several message blocks, but where are these fed into the function.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

Your question essentially is how message length is dealt with in Merkle-Damgård constructions. However, your description is flawed so let's clarify some things:

The whole point of using this kind of construction is to build a hash function that maps arbitrary-length inputs to fixed-length outputs, given a compression function (that is hopefully collision-resistant, among other things).

First the input message is split into $n$ blocks of equal size - following your example, let's assume this block size is 512-bit (as in MD5, and the smaller SHA-2 algorithms). Then, the message is "padded" (extended) until the total message length

$l_{msg} \equiv 448$ mod $512$

Lastly, a 64-bit extension to the last block is added which is essentially a representation of the initial message length. Now all $n$ blocks are exactly 512-bits. Subsequently, the compression function is applied in a loop over all blocks, where in each round it takes as input the current block and the result from the previous round. After $n$ iterations, the final hash value is produced.

What happens if the message is longer than 512 bits?

As soon as your message length exceeds 448 bits, a second block is needed. So a longer message only increases the number of blocks, and thus loop iterations required.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Isn't $l_{msg}$ the length of the unpadded message? $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 19, 2018 at 23:47
  • $\begingroup$ @MaartenBodewes thanks for pointing it out, I changed the wording accordingly $\endgroup$
    – indiscreteLog
    Commented Jan 20, 2018 at 8:03
  • $\begingroup$ First of all, thank you for taking the time to answer my questions. I have 1 question about the compression function. Is the compression function you are talking about the same as explained in wikipedia. Where you take the 64 entery array and rotate and shift the bits. If that is true, does it do somthing like this: Take the first block,compress it and get the values for the constants h0...h7. And then take the next block and update h0...h7. $\endgroup$
    – Lizz4rd merge me
    Commented Jan 20, 2018 at 21:28
  • 1
    $\begingroup$ Yes, but to be clear: the compression function takes two inputs, and yields one output. You start with a set of pre-defined variables (initialisation vector) and the first block (sub-divided into "words") as inputs. For each additional block, inputs are the previous round's result variables and the current block words. The operations applied on the block are indeed bit shifts/rotations. In the end the variable set is concatenated to produce the final hash. Also note that SHA-256 works with 32-bit, and SHA-512 with 64-bit words (mentioning this because of your explicit reference to SHA-256) $\endgroup$
    – indiscreteLog
    Commented Jan 20, 2018 at 21:39
10
$\begingroup$

If the input message is longer than 512 bits, the input is chopped in “chunks” (read: pieces) with fitting length (512 bits) and those are successively fed to the hash compression function.

See, in layman’s terms, SHA-256 processes things like this:

  1. init SHA-256
  2. while there are input chunks,
    update hash compression function with the next input chunk (pad to 512 bits if needed)
  3. finalize SHA-256 and return the result (which is the hash output)

As mentioned in “2”, when SHA-256 reaches a chunk which is less than 512 bits, it is padded accordingly… so that all input chunks fed to the hash compression function are exactly 512 bits long. For details on the padding itself, see “How is input message for SHA-2 padded?” and “SHA256: Padding a 512 bits length message”.

A note aside: The maximum message size which can handled by SHA-256 is $2^{64}-1$ bits, which means SHA-256’s compression function can handle up to $\lceil(2^{64}+64)/512\rceil$ of 512-bit input chunks. In the (unlikely) case when you try to feed more input than the maximum, the hash function should refuse output (read: fail with error).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sorry that I am asking again but even with your answer i can´t find my probelm. If a message is shorter than 448 bits then every works correctly but if the message is longer then it doesn´t work anymore. For example, if i have a message that is 632 bits long i add a single '1' bit then fill it up with zeros and add a 000...1001111000 at the end. Then i split it up into two arrays (the first array is therefore not affected by the one bit or the length that is attached to the back) and start with the hash process. Is this how the padding works with longer messages. $\endgroup$
    – Lizz4rd merge me
    Commented Jan 30, 2018 at 20:41
  • $\begingroup$ @Lizz4rd Assuming that 101111000 is part of the bits describing the message length which you're adding to the end of the last message chunk, yes. Simply stated, the last chunk(s) end with "…1 | fill with needed 0 | msg length". Note that the msg length is part of the final chunk. Also, if the msg length wouldn't fit the final chunk, you add a nother chunk and pad the msg length to a new, final chunk. Hope that helps? $\endgroup$
    – e-sushi
    Commented Jan 31, 2018 at 9:28
  • $\begingroup$ @Lizz4rd Looking at your comment again — the fact that your implementation stops working for inputs larger than 448 bits clearly points to the fact you're doing something wrong when adding the msg length. (512 bit chunk - 448 msg bits = 64 bits) Remember that the last 64 bits of the last chunk always describe the input message length. (Pad accordingly; create new final chunk if needed so that the 64 bits describing the msg length fit at the end of the final chunk.) $\endgroup$
    – e-sushi
    Commented Jan 31, 2018 at 9:45
  • $\begingroup$ Thank you for your help! I found the problem. For example, when converting from integer to hexadecimal at the end, the value 219206355 was converted to D10D2D3, even though the correct value should actually be 0D10D2D3. $\endgroup$
    – Lizz4rd merge me
    Commented Feb 2, 2018 at 18:15
  • $\begingroup$ @Lizz4rd Glad I could help. Cheers! $\endgroup$
    – e-sushi
    Commented Feb 3, 2018 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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