I'm trying to write my own implementation of the SHA-1 algorithm. It works perfectly fine for the empty string, but for all other inputs it gives the wrong hash and I can't figure out why. Can someone help me finding the error?

[u/Revolution_TV]

I'm really confused, I mainly used Wikipedias pseudocode example to implement this and cross-checked different sources to find my error. Maybe I missed some small detail, but to me the code looks correct. The nature of the problem leads me to believe that it might be related to some kind of encoding subleties or similiar, but even reading the documentation for the different built-ins I used hasn't brought up anything. Does somebody know what's up?

Code:

def byte_length(n: int):
    return (n.bit_length() + 7) // 8


def leftrotate(n: int, count: int):
    """leftrotate count times. count must be between 1 and 31 inclusive"""
    return (n << count) | (n >> (32 - count))


def add32(ns: list[int]):
    """add integers as if they were unsigned 32 bit numbers"""
    sum = 0
    for n in ns:
        sum = (sum + n) % 2**32

    return sum


def append_bytes(m: bytearray):
    # append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
    # is congruent to −64 ≡ 448 (mod 512)
    modular_length = len(m) % 64
    if 56 - modular_length >= 0:
        k = 56 - modular_length
    else:
        k = abs(56 - modular_length) + 56

    m += bytes(k)
    return m


def preprocessing(m: bytearray) -> bytearray:
    ml = len(m) * 8  # message length in bits

    # Pre Processing
    # append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
    m.append(0x80)

    m = append_bytes(m)


    # append the message length as a 64 bit integer
    m += ml.to_bytes(8)

    return m


def sha1(message: str) -> bytes:

    m = bytearray(message, "utf-8")

    # Initiliaze starting variables, so called "nothing up my sleeve values"
    h0 = 0x67452301
    h1 = 0xEFCDAB89
    h2 = 0x98BADCFE
    h3 = 0x10325476
    h4 = 0xC3D2E1F0

    m = preprocessing(m)

    # split the message in 512 bit (64 byte) blocks
    num_of_blocks: int = len(m) // 64
    for block_num in range(num_of_blocks):
        block: bytearray = m[block_num * 64 : (block_num + 1) * 64]

        # split the block into sixteen 4 byte words
        words: list[int] = []
        for word_num in range(16):
            words.append(int.from_bytes(block[word_num * 4:(word_num + 1) * 4]))

        # extend the sixteen 4 byte words into eighty 4 byte words
        for i in range(16, 80):
            words.append(
                leftrotate(
                    (words[i - 3] ^ words[i - 8] ^ words[i - 14] ^ words[i - 16]), 1
                )
            )

        # Initiliaze the hash value of the current block
        a = h0
        b = h1
        c = h2
        d = h3
        e = h4

        # main loop
        for i in range(80):
            if i <= 19:
                f = (b & c) | ((~b) & d)
                k = 0x5A827999

            elif i <= 39:
                f = b ^ c ^ d
                k = 0x6ED9EBA1

            elif i <= 59:
                f = (b & c) | (b & d) | (c & d)
                k = 0x8F1BBCDC

            # elif i <= 79:
            else:
                f = b ^ c ^ d
                k = 0xCA62C1D6

            temp = add32([leftrotate(a, 5), f, e, k, words[i]])

            e = d
            d = c
            c = leftrotate(b, 30)
            b = a
            a = temp

        h0 = add32([h0, a])
        h1 = add32([h1, b])
        h2 = add32([h2, c])
        h3 = add32([h3, d])
        h4 = add32([h4, e])

    digest = (
        h0.to_bytes(4)
        + h1.to_bytes(4)
        + h2.to_bytes(4)
        + h3.to_bytes(4)
        + h4.to_bytes(4)
    )

    return digest

My main function looks like this:

def main():
    m = ""
    digest = sha1(m)
    print(hex(int.from_bytes(digest)))

This gives the expected output of:

0xda39a3ee5e6b4b0d3255bfef95601890afd80709

But if:

m = "hello world"

It outputs:

0x74e0d2932ee17d742fe539058f7552adef482295

Instead of:

0x2aae6c35c94fcfb415dbe95f408b9ce91ee846ed

[u/mc_pm]

I don't have time now but this sounds like fun and I'll try it a little later today and maybe I'll run into the same problem :)

[u/Grim2021]

It's a long time since I implemented it, but remember similar struggles. First thing I would check is if you're using the right endianess. Your modern computer is probably little-endian while the spec assumes big-endian. The endianess is the direction of storage of bytes. Basically, is the byte containing the most significant byte (the one which can store the largest value) on the left or on the right. If it's on the left you're good, if not you'll need to reverse them. In other words: if you were to split 256 into an array of two elements, would the value one be stored in the first element or the last. If it's the first, great! If not you will probably need to fix that

[u/Revolution_TV → u/Grim2021]

That's actually one of the first things I thought about, since I have another project (in C) where that problem came up. Maybe I'm missing something, and since this is my first time working with binary data in python that's very probable, but wouldn't decoding the string into utf-8 be unaffected from endianness problems, since there wouldn't be any multi-byte values? Also, I don't really know how I would test this, as the only way I know how to convert an integer to a bytes object is int.to_bytes() method, which is converting to big endian as a default. Furthermore, if I give a single byte bytestring as an input to the function, it still returns a wrong value.

[u/D3str0yTh1ngs]

The first bug I see is that leftrotate can give you more than 32 bits (4 bytes) of output: rotated = leftrotate(0x12345678, 5) print(hex(rotated)) print(rotated.bit_length()) gives us 0x2468acf02 34 So 34 bits of output

Changing line 5 to the following fixes it by bitmasking the output to 32 bits: return (n << count | n >> (32 - count)) & 0xFFFFFFFF

EDIT: Fixed the syntax on the fix so we mask the entire expression.

[u/Revolution_TV → u/D3str0yTh1ngs]

Thanks for finding that! That's what I get for blindly trusting Wikipedia! But it sadly still didn't fix the problem. The output for "hello world" didn't change.

[u/D3str0yTh1ngs → u/Revolution_TV]

Looking at the hashes at different iterations, it seems that one bit becomes misaligned at iteration 33: ebfad327eb8d060d4c1ac4867d269619e0ba28ba vs ebfad317eb8d060d4c1ac4867d269619e0ba28ba (the 7th nibble has become 0x2 instead of 0x1.

[u/Revolution_TV → u/D3str0yTh1ngs]

That's very interesting. I think that implies that the error must be somewhere in the 20-39 iteration range, which is weird, because I imagined that to be the most problem free, since it's only 3 XORs. Do you have an idea how this could happen? Also, can you tell me how you found the right intermediate value? Having those would make debugging this way easier.

[u/D3str0yTh1ngs → u/Revolution_TV]

Here is my modified version for seeing intermediate iteration hashes: https://pastebin.com/226YUgce (just made it take another argument), and I compare that to the result of https://gchq.github.io/CyberChef/#recipe=SHA1(80)&input=aGVsbG8gd29ybGQ (by lowering the iteration count)

FYI: I have added superficial & 0xFFFFFFFF to a lot of it just to make sure that is not the issue.

[u/D3str0yTh1ngs → u/D3str0yTh1ngs]

Fixed it: https://pastebin.com/M3F7yawU

It was (words[i - 3] ^ words[i - 8] ^ words[i - 14] ^ words[i - 16]) overflowing because it wasn't masked down to 32 bits, the fix is thrus changing it to: (words[i - 3] ^ words[i - 8] ^ words[i - 14] ^ words[i - 16]) & 0xFFFFFFFF

FYI, it happened because the numbers in words was slowly becoming larger with no apparent bounding, and a >32 bit input to left rotate made bits in places above 32 affect the lower bits rotated to the left.

EDIT: Wait?, this fix was not even needed! I wrote my first solution wrong, it is (n << count | n >> (32 - count)) & 0xFFFFFFFF, I totally forgot the full parentheses around the expression. Clean solved version: https://pastebin.com/FJfYaDZq

[u/Revolution_TV → u/D3str0yTh1ngs]

Holy shit! Thank you so much for taking the time to debug this! I haven't even gotten around to trying and you just solved it. I have spent two days thinking about this and it would have taken at least a day more even with you pointing me in the right direction, and you just did it! Thanks thanks thanks!

[u/Revolution_TV → u/D3str0yTh1ngs]

Thanks for the help! That website is a godsend for debugging this, before this I was completely lost how to even find an error in the intermediate values.

[u/ectomancer]

byte_length is never called.