What am I doing wrong when implementing sha256 in Rust?

Question

I'm trying to implement sha256 in Rust.

I usually used u8 to express bits, it made it easier to understand some things. Right now the code is not giving the output I want.

I'm sure I'm using Big Endian I have checked the xor, rotate and shift functions many times.

If I hash "ASD", the hash should start with 1100001110000111011101111.

main.rs

use shash::ShaGo;
fn main() {
    let obj = ShaGo::new();

    let dataw = ShaGo::string_to_bits("ASD");
    let data = ShaGo::create_blocks(dataw);

    println!("Data: {:?}", data);

    let hasho = obj.sha256_hash(data.clone());

    println!("{:?}", hasho);
}

mod shash {
    pub struct ShaGo {
        pub current_hash: Vec<[u8; 32]>,
        constants: Vec<[u8; 32]>,
    }

    impl ShaGo {
        fn init_values() -> Vec<[u8; 32]> {
            let vals: Vec<u32> = vec![
                0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab,
                0x5be0cd19,
            ];
            let mut result: Vec<[u8; 32]> = Vec::new();
            for val in vals {
                result.push(Self::u32_to_bits(val).try_into().unwrap());
            }

            result
        }

        fn round_constants() -> Vec<[u8; 32]> {
            let mut result: Vec<[u8; 32]> = Vec::with_capacity(64);
            let vals: Vec<u32> = vec![
                0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
                0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
                0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
                0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
                0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
                0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
                0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
                0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
                0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
                0xc67178f2,
            ];
            for val in vals {
                result.push(Self::u32_to_bits(val).try_into().unwrap());
            }
            result
        }

        pub fn new() -> Self {
            ShaGo {
                current_hash: Self::init_values(),
                constants: Self::round_constants(),
            }
        }

        pub fn string_to_bits(text: &str) -> Vec<u8> {
            let mut result: Vec<u8> = Vec::with_capacity(text.len() * 8);

            for kar in text.chars() {
                let mut bits = [0; 8];
                let mut num = kar as u8;
                for i in 0..8 {
                    bits[7 - i] = (num & 1 == 1) as u8;
                    num >>= 1;
                }

                for b in bits {
                    result.push(b);
                }
            }

            result
        }

        fn u64_to_bits(n: u64) -> Vec<u8> {
            let mut bits = Vec::with_capacity(64);

            for i in 0..64 {
                bits.push(((n >> i) & 1) as u8);
            }

            bits.reverse();
            bits
        }

        pub fn u32_to_bits(n: u32) -> Vec<u8> {
            let mut bits = Vec::with_capacity(32);

            for i in 0..32 {
                bits.push(((n >> i) & 1) as u8);
            }

            bits.reverse();
            bits
        }

        pub fn create_blocks(mut bits: Vec<u8>) -> Vec<[u8; 512]> {
            let mut result: Vec<[u8; 512]> = Vec::new();
            let msg_len = bits.len();

            println!("Bits len: {:?}", bits.len());

            let padding_size = 512 - ((bits.len() + 64) % 512);
            println!("Padding size: {:?}", padding_size);
            bits.push(1);

            for _ in 0..(padding_size - 1) {
                bits.push(0);
            }

            bits.append(&mut Self::u64_to_bits(msg_len as u64));

            /* pushes 512 bit array */
            // println!("Bits len: {:?}", bits.len());
            for i in 0..(bits.len() / 512) {
                result.push(bits[(i * 512)..((i + 1) * 512)].try_into().unwrap());
            }

            println!("Result SIZE: {:?}", result[0].len());
            result
        }

        fn rotate_right(bits: [u8; 32], rounds: usize) -> [u8; 32] {
            let mut part1 = bits[(bits.len() - rounds)..bits.len()].to_vec();
            let part2 = bits[0..(bits.len() - rounds)].to_vec();
            part1.extend(part2);

            part1.try_into().unwrap()
        }

        fn shift_right(bits: [u8; 32], rounds: usize) -> [u8; 32] {
            let mut result = vec![];
            let part2 = bits[0..(bits.len() - rounds)].to_vec();

            for _ in 0..rounds {
                result.push(0);
            }
            result.extend(part2);

            result.try_into().unwrap()
        }

        fn extended_xor(b1: [u8; 32], b2: [u8; 32]) -> [u8; 32] {
            let mut result = Vec::with_capacity(32);
            for i in 0..32 {
                result.push((b1[i] != b2[i]) as u8)
            }

            result.try_into().unwrap()
        }

        fn sigma_zero(bits: [u8; 32]) -> [u8; 32] {
            let a = Self::rotate_right(bits, 7);
            let b = Self::rotate_right(bits, 18);
            let c = Self::shift_right(bits, 3);

            let first = Self::extended_xor(a, b);
            Self::extended_xor(first, c)
        }

        fn sigma_one(bits: [u8; 32]) -> [u8; 32] {
            let a = Self::rotate_right(bits, 17);
            let b = Self::rotate_right(bits, 19);
            let c = Self::shift_right(bits, 10);

            let first = Self::extended_xor(a, b);
            Self::extended_xor(first, c)
        }

        fn bits_to_u32(bits: &[u8; 32]) -> u32 {
            bits.iter()
                .enumerate()
                .fold(0, |acc, (i, &bit)| acc | ((bit as u32) << (31 - i)))
        }

        pub fn add_bits(a: [u8; 32], b: [u8; 32], c: [u8; 32], d: [u8; 32]) -> [u8; 32] {
            let _a = Self::bits_to_u32(&a);
            let _b = Self::bits_to_u32(&b);
            let _c = Self::bits_to_u32(&c);
            let _d = Self::bits_to_u32(&d);

            let mut sum = _a.wrapping_add(_b);
            sum = sum.wrapping_add(_c);
            sum = sum.wrapping_add(_d);

            Self::u32_to_bits(sum).try_into().unwrap()
        }

        pub fn expander(bits: [u8; 512]) -> Vec<[u8; 32]> {
            let mut result: Vec<[u8; 32]> = Vec::with_capacity(64);

            for i in 0..16 {
                result.push(bits[(i * 32)..((i + 1) * 32)].try_into().unwrap());
            }

            for i in 16..64 {
                let a = Self::sigma_one(result[i - 2]);
                let b = result[i - 7];
                let c = Self::sigma_zero(result[i - 5]);
                let d = result[i - 16];

                let data = Self::add_bits(a, b, c, d);
                result.push(data);
            }

            result
        }

        fn extended_and(a: [u8; 32], b: [u8; 32]) -> [u8; 32] {
            let mut result: Vec<u8> = Vec::with_capacity(32);

            for i in 0..32 {
                if (a[i] == 1) && (b[i] == 1) {
                    result.push(1);
                } else {
                    result.push(0);
                }
            }

            result.try_into().unwrap()
        }

        fn extended_not(a: [u8; 32]) -> [u8; 32] {
            let mut result: Vec<u8> = Vec::with_capacity(32);
            for i in 0..32 {
                result.push(1 - a[i]);
            }

            result.try_into().unwrap()
        }

        fn Ch(e: [u8; 32], f: [u8; 32], g: [u8; 32]) -> [u8; 32] {
            Self::extended_xor(
                Self::extended_and(e, f),
                Self::extended_and(Self::extended_not(e), g),
            )
        }

        fn Ma(a: [u8; 32], b: [u8; 32], c: [u8; 32]) -> [u8; 32] {
            Self::extended_xor(
                Self::extended_xor(Self::extended_and(a, b), Self::extended_and(a, c)),
                Self::extended_and(b, c),
            )
        }

        fn sig_one(e: [u8; 32]) -> [u8; 32] {
            Self::extended_xor(
                Self::extended_xor(Self::rotate_right(e, 6), Self::rotate_right(e, 11)),
                Self::rotate_right(e, 25),
            )
        }

        fn sig_zero(a: [u8; 32]) -> [u8; 32] {
            Self::extended_xor(
                Self::extended_xor(Self::rotate_right(a, 2), Self::rotate_right(a, 13)),
                Self::rotate_right(a, 22),
            )
        }

        pub fn compress_round(&self, block: [u8; 512], input: Vec<[u8; 32]>) -> Vec<[u8; 32]> {
            let start_vals = input.clone();
            let mut sinput = input.clone();

            let zero_arr = [0 as u8; 32];
            let mut result: Vec<[u8; 32]> = vec![
                zero_arr, zero_arr, zero_arr, zero_arr, zero_arr, zero_arr, zero_arr, zero_arr,
            ];
            let w = Self::expander(block);

            for t in 0..64 {
                // println!("SINPUT: {:?}", sinput);
                result[1] = sinput[0];
                result[2] = sinput[1];
                result[3] = sinput[2];
                result[5] = sinput[4];
                result[6] = sinput[5];
                result[7] = sinput[6];

                let wt_xor_kt = Self::extended_xor(w[t], self.constants[t]);
                let ch_result = Self::Ch(sinput[4], sinput[5], sinput[6]);

                let mut path =
                    Self::extended_xor(Self::extended_xor(wt_xor_kt, ch_result), sinput[7]);
                let sig_one_res = Self::sig_one(sinput[4]);

                path = Self::extended_xor(path, sig_one_res);

                result[4] = Self::extended_xor(sinput[3], path);
                path = Self::extended_xor(path, Self::Ma(sinput[0], sinput[1], sinput[2]));
                path = Self::extended_xor(Self::sig_zero(sinput[0]), path);

                result[0] = path;
                sinput = result.clone();
            }

            for i in 0..8 {
                result[i] = Self::extended_xor(result[i], start_vals[i]);
            }
            result
        }

        pub fn sha256_hash(self, blocks: Vec<[u8; 512]>) -> Vec<[u8; 32]> {
            println!("SHA 256 hash");
            println!("BLocks: {:?}", blocks);
            let mut current_hash = self.current_hash.clone();

            for block in blocks {
                println!("First round");
                current_hash = self.compress_round(block, current_hash);
            }

            current_hash
        }
    }
}

This is purely a 'personal development' project, so I'm not crazy enough to make my own sha256 lib :)

Answer 1

Part of the problem in your code is that you've structured it in a way that makes it very verbose and also error prone. That's because SHA-256 is typically implemented on 32-bit integers (since that is by far more efficient) and you've implemented it as single bits. That means that you've reimplemented things like XOR (with the wrong value; it's 1 if the bits are different) and you've also implemented the update at the end of the block compression as an XOR instead of an addition. Both of these would be much more obvious if you were using the standard 32-bit code approach.

I've totally refactored your code to do that below, replaced the custom implementations of operations with the native ones, and added some tests (computed against GNU coreutils's sha256sum) and it's a bunch shorter, easier to read, and faster. Note that because you're doing addition mod 2^32, you need to use Wrapping<u32>, or Rust will panic in debug mode. You've implemented that as wrapping_add, which is also fine.

My version also uses the standard init-update-finish approach used in cryptographic libraries. I have not, however, highly optimized it and there may be some inefficient or questionable practices left.

Note that the things I've mentioned above are just the things that I noticed right away; since I removed all of the bit conversion code, there may be other issues in that code that hide other bugs which I didn't notice. Fixing those is left as an exercise to the reader if you want to continue to try that approach.

#![allow(dead_code)]

use std::num::Wrapping;

pub struct ShaGo {
    current_hash: [u32; 8],
    buffer: [u8; 64],
    offset: usize,
    total_size: u64,
}

impl ShaGo {
    const INITIAL_VALUE: [u32; 8] = [
        0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab,
        0x5be0cd19,
    ];

    const ROUND_CONSTANTS: [u32; 64] = [
        0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
        0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
        0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
        0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
        0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
        0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
        0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
        0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
        0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
        0xc67178f2,
    ];

    pub fn new() -> Self {
        ShaGo {
            current_hash: Self::INITIAL_VALUE,
            buffer: [0u8; 64],
            offset: 0,
            total_size: 0,
        }
    }

    pub fn update(&mut self, data: &[u8]) {
        self.total_size += data.len() as u64;
        let data = if self.offset != 0 {
            let bytes = std::cmp::min(data.len(), 64 - self.offset);
            self.buffer[self.offset..self.offset + bytes].copy_from_slice(&data[0..bytes]);
            self.offset += bytes;
            if self.offset < 64 {
                return;
            }
            Self::compress_round(&mut self.current_hash, &self.buffer);
            self.offset = 0;
            &data[bytes..]
        } else {
            data
        };
        let mut offset = 0;
        while data.len() - offset >= 64 {
            Self::compress_round(&mut self.current_hash, &data[offset..offset + 64]);
            offset += 64;
        }
        let data = &data[offset..];
        self.buffer[0..data.len()].copy_from_slice(data);
        self.offset = data.len();
    }

    pub fn finish(mut self) -> [u8; 32] {
        let offset = self.offset;
        // We know there must be at least one byte left.
        self.buffer[self.offset] = 0x80;
        if offset < 56 {
            self.buffer[self.offset + 1..56].fill(0);
        } else {
            self.buffer[self.offset + 1..].fill(0);
            Self::compress_round(&mut self.current_hash, &self.buffer);
            self.buffer[0..56].fill(0);
        }
        self.total_size <<= 3;
        self.buffer[56..].copy_from_slice(&self.total_size.to_be_bytes());
        Self::compress_round(&mut self.current_hash, &self.buffer);
        let mut result = [0u8; 32];
        for (i, val) in self.current_hash.as_slice().iter().enumerate() {
            result[i * 4..=i * 4 + 3].copy_from_slice(&val.to_be_bytes());
        }
        result
    }

    fn sigma_zero(x: Wrapping<u32>) -> Wrapping<u32> {
        Wrapping(x.0.rotate_right(7) ^ x.0.rotate_right(18) ^ (x.0 >> 3))
    }

    fn sigma_one(x: Wrapping<u32>) -> Wrapping<u32> {
        Wrapping(x.0.rotate_right(17) ^ x.0.rotate_right(19) ^ (x.0 >> 10))
    }

    pub fn expander(bits: &[u32]) -> [Wrapping<u32>; 64] {
        let bits: Vec<_> = bits.iter().map(|b| Wrapping(*b)).collect();
        let mut result = [Wrapping(0u32); 64];
        result[0..16].copy_from_slice(&bits);

        for i in 16..64 {
            let s0 = Self::sigma_zero(result[i - 15]);
            let s1 = Self::sigma_one(result[i - 2]);
            result[i] = result[i - 16] + s0 + result[i - 7] + s1;
        }

        result
    }

    fn choose(e: Wrapping<u32>, f: Wrapping<u32>, g: Wrapping<u32>) -> Wrapping<u32> {
        (e & f) ^ ((!e) & g)
    }

    fn majority(a: Wrapping<u32>, b: Wrapping<u32>, c: Wrapping<u32>) -> Wrapping<u32> {
        (a & b) ^ (a & c) ^ (b & c)
    }

    fn sig_one(e: Wrapping<u32>) -> Wrapping<u32> {
        Wrapping(e.0.rotate_right(6) ^ e.0.rotate_right(11) ^ e.0.rotate_right(25))
    }

    fn sig_zero(a: Wrapping<u32>) -> Wrapping<u32> {
        Wrapping(a.0.rotate_right(2) ^ a.0.rotate_right(13) ^ a.0.rotate_right(22))
    }

    fn compress_round(input: &mut [u32; 8], block: &[u8]) {
        let block = &block[0..64];

        let block: Vec<u32> = block
            .chunks(4)
            .map(|c| u32::from_be_bytes(c.try_into().unwrap()))
            .collect();

        let w = Self::expander(&block);

        let mut a = Wrapping(input[0]);
        let mut b = Wrapping(input[1]);
        let mut c = Wrapping(input[2]);
        let mut d = Wrapping(input[3]);
        let mut e = Wrapping(input[4]);
        let mut f = Wrapping(input[5]);
        let mut g = Wrapping(input[6]);
        let mut h = Wrapping(input[7]);

        for (i, val) in w.iter().enumerate() {
            let s1 = Self::sig_one(e);
            let ch = Self::choose(e, f, g);
            let t1 = h + s1 + ch + Wrapping(Self::ROUND_CONSTANTS[i]) + val;
            let s0 = Self::sig_zero(a);
            let maj = Self::majority(a, b, c);
            let t2 = s0 + maj;

            h = g;
            g = f;
            f = e;
            e = d + t1;
            d = c;
            c = b;
            b = a;
            a = t1 + t2;
        }

        *input = [
            (Wrapping(input[0]) + a).0,
            (Wrapping(input[1]) + b).0,
            (Wrapping(input[2]) + c).0,
            (Wrapping(input[3]) + d).0,
            (Wrapping(input[4]) + e).0,
            (Wrapping(input[5]) + f).0,
            (Wrapping(input[6]) + g).0,
            (Wrapping(input[7]) + h).0,
        ];
    }
}

#[cfg(test)]
mod tests {
    fn assert_value(input: &[u8], expected: &str) {
        let mut hash = super::ShaGo::new();
        hash.update(input);
        let result = hash.finish();
        assert_eq!(hex::encode(result), expected);
    }

    #[test]
    fn basic() {
        assert_value(
            b"",
            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
        );
        assert_value(
            b"abc",
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
        );
        assert_value(
            b"message digest",
            "f7846f55cf23e14eebeab5b4e1550cad5b509e3348fbc4efa3a1413d393cb650",
        );
        let v = vec![b'a'; 1000000];
        assert_value(
            &v,
            "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0",
        );
    }
}

Main code:

mod shash;

fn main() {
    let mut obj = shash::ShaGo::new();

    obj.update(b"ASD");

    let hasho = obj.finish();

    println!("{:?}", hasho);
}