7
$\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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ a) SHA3 lacks the concept of "blocks" b) padding is much simpler here and does not include message length. $\endgroup$
    – SEJPM
    Commented Mar 14, 2017 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
    Commented Mar 14, 2017 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
    Commented Mar 14, 2017 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
    Commented Mar 14, 2017 at 19:36
  • $\begingroup$ In case you want to read it yourself: The relevant standard is FIPS-202 (PDF). $\endgroup$
    – SEJPM
    Commented Mar 14, 2017 at 19:46

2 Answers 2

Reset to default
4
$\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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ That answer is incorrect when it states that something special happens when the message length $\ell$ is a multiple of the rate $r$. Padding occurs just as it does normally. The last block never is empty. It's always padded to the full rate $r$, then (with zeroes) to $b=1600$ bits. True, it's possible to recognize from the last block that $\ell$ is an exact multiple of the rate $r$, but it's equally easy to recognize that $\ell\bmod r$ is any of the $r$ possible value in $[0,r)$. $\endgroup$
    – fgrieu ♦
    Commented Jan 2 at 20:45
2
$\begingroup$

No, there is no way to tell the message length from "the last block".

Argument: however we define it, said last block is unchanged when we prepend a message with an additional $r$ bits of arbitrary data, where $r$ is the "rate" (in bit) of the variant of SHA3. Or, whatever the variant, we can prepend 31824 bytes (that is 254592 bits, which is divisible by $r$ for SHA3-224, SHA3-256, SHA3-384, SHA3-512).

In the above, "the last block" might be either the 1600-bit (200-byte) last input of the KECCACK function during message processing, or the last block of the message with some degree of padding, with the previous blocks (if any) having $r$-bit.

This follows from FIPS 202 section 4 algorithm 8, which computes $\operatorname{SPONGE}[f,\operatorname{pad},r](N,d)$ starting in (with $b=1600$ the bit size of the input and output of the KECCACK function $f$)

  1. Let $P=N\mathbin\|\operatorname{pad}(r,\operatorname{len}(N))$.
  2. Let $n=\operatorname{len}(P)/r$.
  3. Let $c=b-r$.
  4. Let $P_0,\ldots,P_{n-1}$ be the unique sequence of strings of length $r$ such that $P=P_0\mathbin\|\ldots\mathbin\|P_{n-1}$.
  5. Let $S=\mathtt0^b$.
  6. For $i$ from $0$ to $n-1$, let $S=f(S\oplus(P_i\mathbin\|\mathtt0^c))$.

In the SHA3 context, this is with

  • $N$ the message right-padded with the two bits $\mathtt{01}$
  • $\operatorname{pad}$ some deterministic padding function $\operatorname{pad10*1}$ such that $\operatorname{len}(\operatorname{pad}(r,m))=((-2-m)\bmod r)+2$.

If $\ell$ is the message length (in bits), the properties of $\operatorname{pad10*1}$ make it possible to tell $\ell\bmod r$ (but not $\ell$) from $P_{n-1}$ or $P_{n-1}\mathbin\|\mathtt0^c$.

Improve this answer
$\endgroup$

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.