6
$\begingroup$

Let M be the message that has been padded for use into the SHA3 (standardized Keccak) hash function. Is there a way, like it's the case for SHA1, to know the total length of the message M just by looking at the last block?

For example, in SHA1, I can give you the last block (that was padded) and you can extract the total length of the message (I'm not worried about security here).

Is there anything similar with SHA3 or do I need to count each block separately?

$\endgroup$
  • 3
    $\begingroup$ a) SHA3 lacks the concept of "blocks" b) padding is much simpler here and does not include message length. $\endgroup$ – SEJPM Mar 14 '17 at 17:04
  • $\begingroup$ Thank you for your answer. I heard in a video, called "Keccak [GPN13]", that SHA3 is based on a Merkle-Damgard Wide-pipe construction, like shown here: upload.wikimedia.org/wikipedia/commons/e/e4/… In the picture, the length is appended at the end. Also, in the document opencores.org/usercontent,doc,1359445372 it is stated that $P = M || pad[576](|M|)$ where $|M|$ is the length of the message I assume. So I'm rather confused. $\endgroup$ – Symeof Mar 14 '17 at 17:24
  • 5
    $\begingroup$ @SEJPM: actually, SHA3 does have the concept of blocks, in that it (like SHA-2) divides the message into an equal sized segments (for SHA3, each segment is 1600 bits minus the capacity), and then processes each segment in succession. Now, SHA3 might not refer to these segments as 'blocks'; however that appears to be a distinction in terminology... $\endgroup$ – poncho Mar 14 '17 at 19:15
  • $\begingroup$ @poncho Well, the concept of "a block" certainly is far less important with SHA3 (Sponge) than it is with SHA2 (Merkle-Damgard) $\endgroup$ – SEJPM Mar 14 '17 at 19:36
  • $\begingroup$ In case you want to read it yourself: The relevant standard is FIPS-202 (PDF). $\endgroup$ – SEJPM Mar 14 '17 at 19:46
3
$\begingroup$

In some specific cases the answer is yes, in other cases the answer is maybe. SHA-3 has four flavors 224, 256, 384, and 512. Now the “block length” given a particular version is 1152, 1088, 832, and 576 bits respectively. Block length is in quotes because this is only the first step in message pre-processing.

All this means is that given the particular variation of SHA-3 that is being processed, the input message will be broken down into 1152, 1088, 832 or 576 bit chunks. Keep in mind this step is completed before any padding actually occurs so the last chuck doesn’t necessarily have to be one of previously mentioned lengths.

Now you have a_set_of_bit_strings, and we’re interested in the last location, or a_set_of_bit_strings[-1] as per python’s notation. At this particular location if the length of the bit string is not one of the following values 1152, 1088, 832 or 576 it will be padded to one of those lengths as outline in FIPS 202.

Next based on the particular SHA-3 implementation all bit strings contained in a_set_of_bit_strings will be back appended with zeros until their length is 1600 bits as per the width specified in FIPS 202. For the purpose of my explanation I DON’T consider this step padding, because it’s not variable based on input message length. People like to use "sponge" to describe this, but I feel it just adds confusion (I don't mean the crypto definition, I mean it's just misinformation). It just means that over each iteration of SHA-3 security(ie collision resistance) is achieved through bits that aren't included in each "block", because in reality the XOR operation can be manipulated to shift all leading bits to either 1 or 0, but you have no control over tailing bits. Hence the strongest version SHA-3(512) splits the message input into the least number of bit chunks!

Things get interesting when the message you’re trying to hash has a bit length that is an integer multiple of one of the following values 1152, 1088, 832 or 576. In this particular situation no padding occurs, and instead an empty string is appended to the end of your message. Why this happens you can determine for yourself. It’s also important to note that this empty string is then passed to the padding protocol outline in FIPS 202. So to answer your question if the bit length of your message is an integer multiple of 1152, 1088, 832 or 576, and matches with its respective SHA-3 implementation, then yes, if you hand me a_set_of_bit_strings[-1] and it’s equal to ‘’ (An empty string) then I’ll know the input message’s length is an integer multiple of 1152, 1088, 832 or 576. But this is a very specific situation. Past this I have not investigated.

I’ve included my SHA-3 bit orientated code below, it’s gross and hacky but it might help you see what’s happening at the end points. The function you’d be interested in would be sb(), and should investigate value set_main[-1] in sb() . If you want to check it against other open source implementations use online_convert().

Link to SHA-3 Code

I will investigate values that aren’t multiples of 1152, 1088, 832 or 576.

$\endgroup$
  • $\begingroup$ Appreciate your answer! Looking forward to learning more. $\endgroup$ – Symeof Mar 15 '17 at 9:11

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.