What to do with a last chunk of 503 bits in SHA1? 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.
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 &lt; 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$.