rucc_sysroot/
sha256.rs

1//! sha256, as published in FIPS 180-4.
2//!
3//! Here rather than behind `spec/18-package-layout.md` section 18.3's dependency wall. The whole
4//! of the algorithm is one table of constants and two loops, the test vectors are published with
5//! it, and a hash a manifest names itself by is not a reason to take on a crate and everything it
6//! depends on. The other direction of that wall matters too: this runs over a manifest, so a
7//! change in what it answers would change what every recorded digest means, and a constant in this
8//! file cannot change underneath us the way a version resolution can.
9//!
10//! It hashes a whole slice, and the caller that has a file reads the file. The largest thing it is
11//! asked about is a release artifact of a few tens of megabytes, on its way into the cache, which
12//! fits in memory on any machine that can run a compiler. A streaming interface would be more code
13//! for the same answer and no caller wants one.
14
15/// The initial state: the first thirty two bits of the fractional parts of the square roots of the
16/// first eight primes.
17const INITIAL: [u32; 8] = [
18    0x6a09_e667,
19    0xbb67_ae85,
20    0x3c6e_f372,
21    0xa54f_f53a,
22    0x510e_527f,
23    0x9b05_688c,
24    0x1f83_d9ab,
25    0x5be0_cd19,
26];
27
28/// One constant per round: the first thirty two bits of the fractional parts of the cube roots of
29/// the first sixty four primes.
30const ROUND: [u32; 64] = [
31    0x428a_2f98,
32    0x7137_4491,
33    0xb5c0_fbcf,
34    0xe9b5_dba5,
35    0x3956_c25b,
36    0x59f1_11f1,
37    0x923f_82a4,
38    0xab1c_5ed5,
39    0xd807_aa98,
40    0x1283_5b01,
41    0x2431_85be,
42    0x550c_7dc3,
43    0x72be_5d74,
44    0x80de_b1fe,
45    0x9bdc_06a7,
46    0xc19b_f174,
47    0xe49b_69c1,
48    0xefbe_4786,
49    0x0fc1_9dc6,
50    0x240c_a1cc,
51    0x2de9_2c6f,
52    0x4a74_84aa,
53    0x5cb0_a9dc,
54    0x76f9_88da,
55    0x983e_5152,
56    0xa831_c66d,
57    0xb003_27c8,
58    0xbf59_7fc7,
59    0xc6e0_0bf3,
60    0xd5a7_9147,
61    0x06ca_6351,
62    0x1429_2967,
63    0x27b7_0a85,
64    0x2e1b_2138,
65    0x4d2c_6dfc,
66    0x5338_0d13,
67    0x650a_7354,
68    0x766a_0abb,
69    0x81c2_c92e,
70    0x9272_2c85,
71    0xa2bf_e8a1,
72    0xa81a_664b,
73    0xc24b_8b70,
74    0xc76c_51a3,
75    0xd192_e819,
76    0xd699_0624,
77    0xf40e_3585,
78    0x106a_a070,
79    0x19a4_c116,
80    0x1e37_6c08,
81    0x2748_774c,
82    0x34b0_bcb5,
83    0x391c_0cb3,
84    0x4ed8_aa4a,
85    0x5b9c_ca4f,
86    0x682e_6ff3,
87    0x748f_82ee,
88    0x78a5_636f,
89    0x84c8_7814,
90    0x8cc7_0208,
91    0x90be_fffa,
92    0xa450_6ceb,
93    0xbef9_a3f7,
94    0xc671_78f2,
95];
96
97/// The sha256 of these bytes, as sixty four lowercase hex characters.
98///
99/// The same number `sha256sum` prints for a file holding them, which is the property that makes a
100/// digest worth printing at all: whoever is handed one can check it with a tool they already have
101/// rather than with ours.
102pub fn hex(message: &[u8]) -> String {
103    let mut state = INITIAL;
104    let mut blocks = message.chunks_exact(64);
105    for block in &mut blocks {
106        compress(&mut state, block);
107    }
108
109    // The padding is a one bit, then zeros, then the length in bits as a big endian sixty four bit
110    // number. That needs a second block when what is left of the message leaves no room for the
111    // length, so the tail is two blocks wide and one or both of them are hashed.
112    let rest = blocks.remainder();
113    let mut tail = [0u8; 128];
114    tail[..rest.len()].copy_from_slice(rest);
115    tail[rest.len()] = 0x80;
116    let width = if rest.len() + 9 > 64 { 128 } else { 64 };
117    // In bits, and a message long enough to overflow this does not fit in any machine's memory.
118    let bits = (message.len() as u64).wrapping_mul(8);
119    tail[width - 8..width].copy_from_slice(&bits.to_be_bytes());
120    for block in tail[..width].chunks_exact(64) {
121        compress(&mut state, block);
122    }
123
124    let mut out = String::with_capacity(64);
125    for word in state {
126        for byte in word.to_be_bytes() {
127            out.push(char::from_digit(u32::from(byte >> 4), 16).unwrap_or('0'));
128            out.push(char::from_digit(u32::from(byte & 0xf), 16).unwrap_or('0'));
129        }
130    }
131    out
132}
133
134/// One block of sixty four bytes into the state.
135///
136/// # Panics
137///
138/// A block that is not sixty four bytes, which is a caller that did not chunk its message. The
139/// slice is a slice rather than an array reference because `chunks_exact` yields slices and the
140/// conversion would be the same assertion one line up.
141fn compress(state: &mut [u32; 8], block: &[u8]) {
142    assert_eq!(block.len(), 64, "sha256 compresses sixty four bytes at a time");
143
144    // The message schedule: sixteen words read out of the block and forty eight more derived from
145    // them, which is what spreads one changed byte across the whole block.
146    let mut words = [0u32; 64];
147    for (word, bytes) in words.iter_mut().zip(block.chunks_exact(4)) {
148        let quad: [u8; 4] = bytes.try_into().expect("four bytes out of a chunk of four");
149        *word = u32::from_be_bytes(quad);
150    }
151    for index in 16..64 {
152        let first = words[index - 15];
153        let second = words[index - 2];
154        let low = first.rotate_right(7) ^ first.rotate_right(18) ^ (first >> 3);
155        let high = second.rotate_right(17) ^ second.rotate_right(19) ^ (second >> 10);
156        words[index] =
157            words[index - 16].wrapping_add(low).wrapping_add(words[index - 7]).wrapping_add(high);
158    }
159
160    let [mut a, mut b, mut c, mut d, mut e, mut f, mut g, mut h] = *state;
161    for (constant, word) in ROUND.iter().zip(words.iter()) {
162        let sigma = e.rotate_right(6) ^ e.rotate_right(11) ^ e.rotate_right(25);
163        let choose = (e & f) ^ (!e & g);
164        let one =
165            h.wrapping_add(sigma).wrapping_add(choose).wrapping_add(*constant).wrapping_add(*word);
166        let sum = a.rotate_right(2) ^ a.rotate_right(13) ^ a.rotate_right(22);
167        let majority = (a & b) ^ (a & c) ^ (b & c);
168        let two = sum.wrapping_add(majority);
169        h = g;
170        g = f;
171        f = e;
172        e = d.wrapping_add(one);
173        d = c;
174        c = b;
175        b = a;
176        a = one.wrapping_add(two);
177    }
178
179    for (slot, round) in state.iter_mut().zip([a, b, c, d, e, f, g, h]) {
180        *slot = slot.wrapping_add(round);
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use super::hex;
187
188    #[test]
189    fn the_published_vectors() {
190        // The three in FIPS 180-4's own examples and in every other implementation's tests. The
191        // empty message is the one that exercises the padding on its own, since there is nothing
192        // else in the block it pads.
193        assert_eq!(hex(b""), "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855");
194        assert_eq!(hex(b"abc"), "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad");
195        assert_eq!(
196            hex(b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"),
197            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1"
198        );
199    }
200
201    #[test]
202    fn a_message_that_fills_its_last_block_takes_a_second_one() {
203        // 55 bytes leaves exactly room for the one bit and the length, 56 does not, and the
204        // boundary between those two is where an implementation that got the padding wrong stops
205        // agreeing with everybody else.
206        assert_eq!(
207            hex(&b"a".repeat(55)),
208            "9f4390f8d30c2dd92ec9f095b65e2b9ae9b0a925a5258e241c9f1e910f734318"
209        );
210        assert_eq!(
211            hex(&b"a".repeat(56)),
212            "b35439a4ac6f0948b6d6f9e3c6af0f5f590ce20f1bde7090ef7970686ec6738a"
213        );
214        assert_eq!(
215            hex(&b"a".repeat(64)),
216            "ffe054fe7ae0cb6dc65c3af9b61d5209f439851db43d0ba5997337df154668eb"
217        );
218    }
219
220    #[test]
221    fn a_long_message_is_hashed_block_by_block() {
222        // A million a's, which is the fourth vector everyone publishes and the only one that goes
223        // through the loop enough times for a wrong count of blocks to show.
224        assert_eq!(
225            hex(&b"a".repeat(1_000_000)),
226            "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0"
227        );
228    }
229}
rucc_sysroot/sha256.rs

rucc_sysroot/
sha256.rs
