0
$\begingroup$

I was trying to implement a SHA1 algorithm last night, and I got stuck at preprocessing the chunks in SHA1.

As I have understood it, the message that has to be hashed, has to be broken into chunks of 512 bits, and if the last chunk is not equal to 512 bits, a 1 is appended to the bits, followed by '0', and at the end the number of bits of the last chunk of message is appended. So an example:

abc = 97 98 99
abc = 01100001 01100010 01100011
chunk = 0110000101100010011000111... ( 482 x 0) ...11000

But what would happen if the last chunk is 504 bits? Then 9 bits (2^9 = 512), should be used to describe the length of the message, but that does not fit, because there are only 512 - 504 - 1 = 7 bits left to describe the length.

I've looked into Wikipedia and the SHA documentation, but could not find my answer in there.

$\endgroup$
  • 1
    $\begingroup$ Appending a 1 bit (and the length) is not conditioned by anything, contrary to the questions's statement. Read section 5.1.1 in the the SHA documentation (I fixed the link in the question), it is unambiguous. $\endgroup$ – fgrieu Oct 13 '17 at 14:06
1
$\begingroup$

The answer is in both sources you linked.

Pseudocode from the Wikipedia article:

  • append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
  • append 0 ≤ k < 512 bits '0', such that the resulting message length in bits is congruent to −64 ≡ 448 (mod 512)
  • append ml, the original message length, as a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.

From the SHA documenation:

Suppose that the length of the message, $M$, is $l$ bits. Append the bit "$1$" to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $l+1+k\equiv 448 \mod 512$.

In both instances, the number is the smallest non-negative solution to the same congruency, just noted slightly differently. If you have an example where $-1$ would be a solution to the congruency, then the actual value of $k$ is $511$.

$\endgroup$
  • $\begingroup$ Does 448 mod 512 mean that the message needs to be broken into chunks of 448 bits, with 64 bits after the 448 containing 1 ...... k, where k is 448 in case of the end of the message has not been reached? Always the last 64 bits are added? $\endgroup$ – user274595 Oct 13 '17 at 14:59
  • $\begingroup$ @user274595 How do you take from those quotes, that anything changes how the message is split into chunks? It does not adress that at all, it is only about the padding at the end. You have the length, you know that you add at least $1+64$ bits, and then you can calculate the number that is required to 'fill up' to a multiple of $512$. And yes, the length encoded with 64 bit is always the last part, as specified clearly in both documents. $\endgroup$ – tylo Oct 13 '17 at 15:20

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.