0
$\begingroup$

I'm not sure whether this questions is about SHA-256 algorithm itself or the particular implementation I'm using.

Usually, a hash algorithm implementation has functions, let us call them update and finalize. update feeds another chunk of data, finalize possibly feeds the last chunk and calculates the digest.

Should passing the whole array at once produce the same hash as passing it's chunks one by one? In other words, update(whole_array) vs update(1st_half); update(2nd_half)

$\endgroup$
  • 1
    $\begingroup$ This is a software implementation question (and thus technically off-topic here). If the chunks are of the correct block size, then generally you can update it bit by bit, otherwise the update functions wouldn't be very useful! The only reason there's an extra function to finalize it is because hashes like SHA-256 are Merkle–Damgård hashes which require specially encoded padding at the end of the message. The finalize functions just calculate that padding and update the hash with it. $\endgroup$ – forest Jun 12 '18 at 13:16
  • 2
    $\begingroup$ @forest: I don't know why you qualified your comment with "If the chunks are the correct block size"; update will take inputs of any size, and (unless the API is totally broken), the result will be the same as if you hashed the entire image all at once. $\endgroup$ – poncho Jun 12 '18 at 14:37
  • $\begingroup$ @poncho I don't know what implementation he is using, so I specified that to be safe. $\endgroup$ – forest Jun 12 '18 at 21:26
  • $\begingroup$ @forest: it would be horrid API design to embed the internals of the hash function (such as the "block length") into the API; I have never seen a hash API that does it. $\endgroup$ – poncho Jun 12 '18 at 21:35
1
$\begingroup$

Yes. SHA-2 uses a Merkle–Damgård construction and therefore can be computed "online". This means it has an internal state size, $n$, measured in bits. It uses an $n$ bit long initialization vector and a compression function with an $n$ bit output. It accepts inputs in $m$-bit long chunks. In the case of SHA-256 $n = 256$ and $m = 512$.

An API that exposes an online implementation of SHA-256 probably allows users to pass in arbitrary length byte arrays instead of fixed length "chunks". In that case the API maintains a state which encompasses the "internal state", a message buffer that is $m$ bits long, and a counter of the number of message bits processed so far. (The counter requires at most 64 bits.) That gives a minimum $256 + 512 + 64 = 832 \ \text{bits} = 104 \ \text{bytes}$ that the API needs to maintain to hash one data-stream. (Not including space used temporarily by the compression function.)

You describe an interface where someone provides the message chunks themselves, which is unusual but not impossible. So the API would only maintain $n$ bits of state space and it would instead be the user's responsibility to maintain a message length counter and allocate there own $m$ bit message buffer. I don't personally recall ever seeing APIs that force users to provide data in fixed width chunks instead of either requiring the full message or allowing arbitrary byte arrays.

SHA-3 use a Sponge construct, which is different from Merkle–Damgård but also allows an online implementation.

$\endgroup$
1
$\begingroup$

TL;DR: As long as the concatenation of all the binary input to the update / final operations, in order is identical then the secure hash function should return the same output hash.


The hash function implementations generally have a buffer the size of the block size. This internal block size is generally hidden to the user. For SHA-256 the block size is 512 bits, 64 bytes or - as SHA-256 is build using 32-bit operations - sixteen 32-bit words.

So what happens is that during update the buffer is filled until it is full, which is then processed by the internal compression function, altering the internal state. Then the buffer is filled again and again until all the blocks have been processed. The last part of the update will leave the buffer empty or partially filled. When a new update is processed the whole situation is repeated, starting with the values in the buffer from the last update (if any).

When the final is called then the input data for the final operation is processed as if it was an update. Then the internal bit padding (a one bit followed by X zero bits) takes place and the encoding of the total length is added. This forms the last one or two blocks which are then processed in order.


So with the description above, it is clear that passing the whole array at once produce the same hash as passing it's chunks one by one. This is because the the same buffers will be processed and the internal state will therefore be updated in exactly the same way. The required padding and total length is the same as well. That's all the input to the block operations within SHA-2 so the final output must be identical too.


If you get a different result then you may have run into encoding issues. SHA-2 processes binary data: bits or - for most implementations - bytes. If you perform a different encoding on a string (e.g. UTF-8 vs UTF-8 with Byte Order Mark) then the input will differ and the hash result will differ as well. In principle, the implementation could be faulty as well, but usually this is not the case; there aren't all that many input variants / edge cases to test and test vectors exist.


Notes:

  • It depends on the implementation if the final operation can contain input data or not. If it does it is identical to having an additional update with the given data and then performing the final operation with the padding and length encoding.
  • SHA-224 uses the same block size / 32-bit operations as SHA-256; SHA-512 uses 1024 bit blocks and 64-bit operations internally, and so does SHA-384 and the less common SHA-512/224 and SHA-512/256 hash functions.
  • SHA-3 uses a different internal scheme (a construction using a sponge instead of a Merkle-Damgard construction) but the description of the buffering and block size is still valid.
$\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.