extendhash/
sha256.rs

1use alloc::vec::Vec;
2
3#[derive(Copy, Clone)]
4struct Sha256 {
5    h: [u32; 8],
6}
7
8impl Sha256 {
9    const K: [u32; 64] = [
10        0x428a_2f98,
11        0x7137_4491,
12        0xb5c0_fbcf,
13        0xe9b5_dba5,
14        0x3956_c25b,
15        0x59f1_11f1,
16        0x923f_82a4,
17        0xab1c_5ed5,
18        0xd807_aa98,
19        0x1283_5b01,
20        0x2431_85be,
21        0x550c_7dc3,
22        0x72be_5d74,
23        0x80de_b1fe,
24        0x9bdc_06a7,
25        0xc19b_f174,
26        0xe49b_69c1,
27        0xefbe_4786,
28        0x0fc1_9dc6,
29        0x240c_a1cc,
30        0x2de9_2c6f,
31        0x4a74_84aa,
32        0x5cb0_a9dc,
33        0x76f9_88da,
34        0x983e_5152,
35        0xa831_c66d,
36        0xb003_27c8,
37        0xbf59_7fc7,
38        0xc6e0_0bf3,
39        0xd5a7_9147,
40        0x06ca_6351,
41        0x1429_2967,
42        0x27b7_0a85,
43        0x2e1b_2138,
44        0x4d2c_6dfc,
45        0x5338_0d13,
46        0x650a_7354,
47        0x766a_0abb,
48        0x81c2_c92e,
49        0x9272_2c85,
50        0xa2bf_e8a1,
51        0xa81a_664b,
52        0xc24b_8b70,
53        0xc76c_51a3,
54        0xd192_e819,
55        0xd699_0624,
56        0xf40e_3585,
57        0x106a_a070,
58        0x19a4_c116,
59        0x1e37_6c08,
60        0x2748_774c,
61        0x34b0_bcb5,
62        0x391c_0cb3,
63        0x4ed8_aa4a,
64        0x5b9c_ca4f,
65        0x682e_6ff3,
66        0x748f_82ee,
67        0x78a5_636f,
68        0x84c8_7814,
69        0x8cc7_0208,
70        0x90be_fffa,
71        0xa450_6ceb,
72        0xbef9_a3f7,
73        0xc671_78f2,
74    ];
75
76    const fn padding_value_at_idx(input_length: usize, idx: usize) -> u8 {
77        let padding_length = Self::padding_length_for_input_length(input_length);
78        if idx == 0 {
79            0b1000_0000
80        } else if idx <= padding_length - 9 {
81            0
82        } else {
83            let offset = idx + 8 - padding_length;
84            let bytes = (input_length as u64).wrapping_mul(8).to_be_bytes();
85            bytes[offset]
86        }
87    }
88
89    const fn apply_chunk(self, chunk: [u8; 64]) -> Self {
90        let mut w = [0_u32; 64];
91        {
92            let mut i = 0;
93            while i < 64 {
94                if i < 16 {
95                    w[i] = u32::from_be_bytes([
96                        chunk[4 * i],
97                        chunk[4 * i + 1],
98                        chunk[4 * i + 2],
99                        chunk[4 * i + 3],
100                    ]);
101                } else {
102                    let s0 =
103                        w[i - 15].rotate_right(7) ^ w[i - 15].rotate_right(18) ^ (w[i - 15] >> 3);
104                    let s1 =
105                        w[i - 2].rotate_right(17) ^ w[i - 2].rotate_right(19) ^ (w[i - 2] >> 10);
106                    w[i] = w[i - 16]
107                        .wrapping_add(s0)
108                        .wrapping_add(w[i - 7])
109                        .wrapping_add(s1);
110                }
111                i += 1;
112            }
113        }
114
115        let mut h = self.h;
116
117        let mut i = 0;
118        while i < 64 {
119            let current_w = w[i];
120            let s1 = h[4].rotate_right(6) ^ h[4].rotate_right(11) ^ h[4].rotate_right(25);
121            let ch = (h[4] & h[5]) ^ ((!h[4]) & h[6]);
122            let temp1 = h[7]
123                .wrapping_add(s1)
124                .wrapping_add(ch)
125                .wrapping_add(Self::K[i])
126                .wrapping_add(current_w);
127            let s0 = h[0].rotate_right(2) ^ h[0].rotate_right(13) ^ h[0].rotate_right(22);
128            let maj = (h[0] & h[1]) ^ (h[0] & h[2]) ^ (h[1] & h[2]);
129            let temp2 = s0.wrapping_add(maj);
130
131            h[7] = h[6];
132            h[6] = h[5];
133            h[5] = h[4];
134            h[4] = h[3].wrapping_add(temp1);
135            h[3] = h[2];
136            h[2] = h[1];
137            h[1] = h[0];
138            h[0] = temp1.wrapping_add(temp2);
139
140            i += 1;
141        }
142
143        Self {
144            h: [
145                self.h[0].wrapping_add(h[0]),
146                self.h[1].wrapping_add(h[1]),
147                self.h[2].wrapping_add(h[2]),
148                self.h[3].wrapping_add(h[3]),
149                self.h[4].wrapping_add(h[4]),
150                self.h[5].wrapping_add(h[5]),
151                self.h[6].wrapping_add(h[6]),
152                self.h[7].wrapping_add(h[7]),
153            ],
154        }
155    }
156
157    const fn get_num_chunks(data_length: usize) -> usize {
158        (data_length + Self::padding_length_for_input_length(data_length)) / 64
159    }
160
161    const fn get_chunk(data: &[u8], data_len: usize, chunk_idx: usize) -> [u8; 64] {
162        let mut chunk = [0; 64];
163        let mut i = 0;
164        while i < 64 {
165            if chunk_idx * 64 + i < data.len() {
166                chunk[i] = data[chunk_idx * 64 + i];
167            } else {
168                let padding_len = Self::padding_length_for_input_length(data_len);
169                let index_into_padding = chunk_idx * 64 + i - data.len();
170                if index_into_padding < padding_len {
171                    chunk[i] = Self::padding_value_at_idx(data_len, index_into_padding);
172                } else {
173                    panic!("unreachable: internal error");
174                }
175            }
176            i += 1;
177        }
178        chunk
179    }
180
181    const fn hash_from_data(self) -> [u8; 32] {
182        let h = [
183            self.h[0].to_be_bytes(),
184            self.h[1].to_be_bytes(),
185            self.h[2].to_be_bytes(),
186            self.h[3].to_be_bytes(),
187            self.h[4].to_be_bytes(),
188            self.h[5].to_be_bytes(),
189            self.h[6].to_be_bytes(),
190            self.h[7].to_be_bytes(),
191        ];
192        [
193            h[0][0], h[0][1], h[0][2], h[0][3], h[1][0], h[1][1], h[1][2], h[1][3], h[2][0],
194            h[2][1], h[2][2], h[2][3], h[3][0], h[3][1], h[3][2], h[3][3], h[4][0], h[4][1],
195            h[4][2], h[4][3], h[5][0], h[5][1], h[5][2], h[5][3], h[6][0], h[6][1], h[6][2],
196            h[6][3], h[7][0], h[7][1], h[7][2], h[7][3],
197        ]
198    }
199
200    const fn padding_length_for_input_length(input_length: usize) -> usize {
201        if input_length % 64 <= 55 {
202            64 - input_length % 64
203        } else {
204            128 - input_length % 64
205        }
206    }
207
208    const fn new() -> Self {
209        Self {
210            h: [
211                0x6a09_e667,
212                0xbb67_ae85,
213                0x3c6e_f372,
214                0xa54f_f53a,
215                0x510e_527f,
216                0x9b05_688c,
217                0x1f83_d9ab,
218                0x5be0_cd19,
219            ],
220        }
221    }
222
223    const fn from(hash: [u8; 32]) -> Self {
224        Self {
225            h: [
226                u32::from_be_bytes([hash[0], hash[1], hash[2], hash[3]]),
227                u32::from_be_bytes([hash[4], hash[5], hash[6], hash[7]]),
228                u32::from_be_bytes([hash[8], hash[9], hash[10], hash[11]]),
229                u32::from_be_bytes([hash[12], hash[13], hash[14], hash[15]]),
230                u32::from_be_bytes([hash[16], hash[17], hash[18], hash[19]]),
231                u32::from_be_bytes([hash[20], hash[21], hash[22], hash[23]]),
232                u32::from_be_bytes([hash[24], hash[25], hash[26], hash[27]]),
233                u32::from_be_bytes([hash[28], hash[29], hash[30], hash[31]]),
234            ],
235        }
236    }
237}
238
239/// Compute the SHA-256 padding for the given input length.
240///
241/// # Arguments
242///
243/// * `input_length` - The length of the input length. This value
244///     is needed to determine the padding length, and to embed
245///     the length in the last 8 bytes of padding.
246///
247/// # Returns
248///
249/// This function returns SHA-256 padding for the given input size.
250/// This padding has a length you can determine by calling
251/// `sha256::padding_length_for_input_length`.
252///
253/// # Example
254///
255/// ```
256/// # use extendhash::sha256;
257/// let data = "This string will be hashed.";
258/// let padding = sha256::padding_for_length(data.len());
259/// assert_eq!(data.len() + padding.len(), 64);
260/// for (i, p) in padding.iter().enumerate() {
261///     match i {
262///         0       => 0b1000_0000,
263///         1..=28  => 0b0000_0000,
264///         29      => data.len() as u8 * 8,
265///         30..=36 => 0b0000_0000,
266///         _       => unreachable!("Invalid padding length")
267///     };
268/// }
269/// ```
270#[must_use]
271pub fn padding_for_length(input_length: usize) -> Vec<u8> {
272    let padding_length = padding_length_for_input_length(input_length);
273    let mut result = Vec::with_capacity(padding_length);
274    for i in 0..padding_length {
275        result.push(Sha256::padding_value_at_idx(input_length, i));
276    }
277    result
278}
279
280/// Compute the SHA-256 padding length (in bytes) for the
281/// given input length.
282///
283/// The result is always between 9 and 72 (inclusive).
284///
285/// # Arguments
286///
287/// * `input_length` - The length of the input length. This value
288///     is used because the amount of padding is always such that the
289///     total padded string is a multiple of 64 bytes.
290///
291/// # Returns
292///
293/// This function returns the amount of padding required for the given
294/// input length.
295///
296/// # Example
297///
298/// ```
299/// # use extendhash::sha256;
300/// let data = "This string will be hashed.";
301/// let padding_length =
302///     sha256::padding_length_for_input_length(data.len());
303/// assert_eq!(data.len() + padding_length, 64);
304/// ```
305#[must_use]
306pub const fn padding_length_for_input_length(input_length: usize) -> usize {
307    Sha256::padding_length_for_input_length(input_length)
308}
309
310/// Compute the SHA-256 hash of the input data
311///
312/// # Arguments
313///
314/// * `input` - The input data to be hashed - this could be a
315///     UTF-8 string or any other binary data.
316///
317/// # Returns
318///
319/// This function returns the computed SHA-256 hash.
320///
321/// # Example
322///
323/// ```
324/// # use extendhash::sha256;
325/// let secret_data = "input string".as_bytes();
326/// let hash = sha256::compute_hash(secret_data);
327/// assert_eq!(hash, [
328///     0xf2, 0x3f, 0x47, 0x81, 0xd6, 0x81, 0x4e, 0xbe,
329///     0x34, 0x9c, 0x6b, 0x23, 0x0c, 0x1f, 0x70, 0x07,
330///     0x14, 0xf4, 0xf7, 0x0f, 0x73, 0x50, 0x22, 0xbd,
331///     0x4b, 0x1f, 0xb6, 0x94, 0x21, 0x85, 0x99, 0x93]);
332/// ```
333#[must_use]
334pub const fn compute_hash(input: &[u8]) -> [u8; 32] {
335    let num_chunks = Sha256::get_num_chunks(input.len());
336    let mut sha256 = Sha256::new();
337    let mut i = 0;
338    while i < num_chunks {
339        let chunk = Sha256::get_chunk(input, input.len(), i);
340        sha256 = sha256.apply_chunk(chunk);
341        i += 1;
342    }
343    sha256.hash_from_data()
344}
345
346/// Calculate a SHA-256 hash extension.
347///
348/// # Arguments
349///
350/// * `hash` - The SHA-256 hash of some previous (unknown) data
351/// * `length` - The length of the unknown data (without any
352///       added padding)
353/// * `additional_input` - Additional input to be
354///       included in the new hash.
355///
356/// # Returns
357///
358/// This function returns the SHA-256 hash of the concatenation of
359/// the original unknown data, its padding, and the `additional_input`.
360/// You can see the included (intermediate) padding by
361/// calling `sha256::padding_for_length`.
362///
363/// # Example
364///
365/// ```
366/// # use extendhash::sha256;
367/// let secret_data = "This is a secret!".as_bytes();
368/// let hash = sha256::compute_hash(secret_data);
369/// let secret_data_length = secret_data.len();
370///
371/// // Now we try computing a hash extension, assuming that
372/// // `secret_data` is not available. We only need `hash`
373/// // and `secret_data_length`.
374/// let appended_message = "Appended message.".as_bytes();
375/// let combined_hash = sha256::extend_hash(
376///     hash, secret_data_length, appended_message);
377///
378/// // Now we verify that `combined_hash` matches the
379/// // concatenation (note the intermediate padding):
380/// let mut combined_data = Vec::<u8>::new();
381/// combined_data.extend_from_slice(secret_data);
382/// let padding = sha256::padding_for_length(secret_data_length);
383/// combined_data.extend_from_slice(padding.as_slice());
384/// combined_data.extend_from_slice(appended_message);
385/// assert_eq!(
386///     combined_hash,
387///     sha256::compute_hash(combined_data.as_slice()));
388/// ```
389#[must_use]
390pub const fn extend_hash(hash: [u8; 32], length: usize, additional_input: &[u8]) -> [u8; 32] {
391    let len = length + padding_length_for_input_length(length) + additional_input.len();
392    let num_chunks = (additional_input.len() + padding_length_for_input_length(len)) / 64;
393    let mut sha256 = Sha256::from(hash);
394    let mut i = 0;
395    while i < num_chunks {
396        let chunk = Sha256::get_chunk(additional_input, len, i);
397        sha256 = sha256.apply_chunk(chunk);
398        i += 1;
399    }
400    sha256.hash_from_data()
401}
402
403#[cfg(test)]
404mod tests {
405    use crate::sha256;
406    use alloc::vec::Vec;
407
408    #[test]
409    fn empty_hash() {
410        assert_eq!(
411            sha256::compute_hash(&[]),
412            [
413                0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f,
414                0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b,
415                0x78, 0x52, 0xb8, 0x55
416            ]
417        );
418    }
419
420    #[test]
421    fn a_test() {
422        assert_eq!(
423            sha256::compute_hash(b"a"),
424            [
425                0xca, 0x97, 0x81, 0x12, 0xca, 0x1b, 0xbd, 0xca, 0xfa, 0xc2, 0x31, 0xb3, 0x9a, 0x23,
426                0xdc, 0x4d, 0xa7, 0x86, 0xef, 0xf8, 0x14, 0x7c, 0x4e, 0x72, 0xb9, 0x80, 0x77, 0x85,
427                0xaf, 0xee, 0x48, 0xbb
428            ]
429        );
430    }
431
432    #[test]
433    fn quick_brown_fox_test() {
434        let s = b"The quick brown fox jumps over the lazy dog";
435        assert_eq!(
436            sha256::compute_hash(s),
437            [
438                0xd7, 0xa8, 0xfb, 0xb3, 0x07, 0xd7, 0x80, 0x94, 0x69, 0xca, 0x9a, 0xbc, 0xb0, 0x08,
439                0x2e, 0x4f, 0x8d, 0x56, 0x51, 0xe4, 0x6d, 0x3c, 0xdb, 0x76, 0x2d, 0x02, 0xd0, 0xbf,
440                0x37, 0xc9, 0xe5, 0x92
441            ]
442        );
443    }
444
445    #[test]
446    fn quick_brown_fox_test_2() {
447        let s = b"The quick brown fox jumps over the lazy cog";
448        assert_eq!(
449            sha256::compute_hash(s),
450            [
451                0xe4, 0xc4, 0xd8, 0xf3, 0xbf, 0x76, 0xb6, 0x92, 0xde, 0x79, 0x1a, 0x17, 0x3e, 0x05,
452                0x32, 0x11, 0x50, 0xf7, 0xa3, 0x45, 0xb4, 0x64, 0x84, 0xfe, 0x42, 0x7f, 0x6a, 0xcc,
453                0x7e, 0xcc, 0x81, 0xbe
454            ]
455        );
456    }
457
458    #[test]
459    fn abc_test() {
460        let s = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
461                  abcdefghijklmnopqrstuvwxyz0123456789";
462        assert_eq!(
463            sha256::compute_hash(s),
464            [
465                0xdb, 0x4b, 0xfc, 0xbd, 0x4d, 0xa0, 0xcd, 0x85, 0xa6, 0x0c, 0x3c, 0x37, 0xd3, 0xfb,
466                0xd8, 0x80, 0x5c, 0x77, 0xf1, 0x5f, 0xc6, 0xb1, 0xfd, 0xfe, 0x61, 0x4e, 0xe0, 0xa7,
467                0xc8, 0xfd, 0xb4, 0xc0
468            ]
469        );
470    }
471
472    #[test]
473    fn long_test() {
474        assert_eq!(
475            sha256::compute_hash(&alloc::vec![b'a'; 1_000_000].into_boxed_slice()),
476            [
477                0xcd, 0xc7, 0x6e, 0x5c, 0x99, 0x14, 0xfb, 0x92, 0x81, 0xa1, 0xc7, 0xe2, 0x84, 0xd7,
478                0x3e, 0x67, 0xf1, 0x80, 0x9a, 0x48, 0xa4, 0x97, 0x20, 0x0e, 0x04, 0x6d, 0x39, 0xcc,
479                0xc7, 0x11, 0x2c, 0xd0
480            ]
481        );
482    }
483
484    #[test]
485    fn padding_length_tests() {
486        assert_eq!(sha256::padding_length_for_input_length(0), 64);
487        assert_eq!(sha256::padding_length_for_input_length(1), 63);
488        assert_eq!(sha256::padding_length_for_input_length(2), 62);
489        assert_eq!(sha256::padding_length_for_input_length(3), 61);
490        assert_eq!(sha256::padding_length_for_input_length(4), 60);
491
492        assert_eq!(sha256::padding_length_for_input_length(50), 14);
493        assert_eq!(sha256::padding_length_for_input_length(54), 10);
494        assert_eq!(sha256::padding_length_for_input_length(55), 9);
495        assert_eq!(sha256::padding_length_for_input_length(56), 64 + 8);
496        assert_eq!(sha256::padding_length_for_input_length(57), 64 + 7);
497        assert_eq!(sha256::padding_length_for_input_length(62), 64 + 2);
498        assert_eq!(sha256::padding_length_for_input_length(63), 64 + 1);
499        assert_eq!(sha256::padding_length_for_input_length(64), 64);
500        assert_eq!(sha256::padding_length_for_input_length(128), 64);
501        assert_eq!(sha256::padding_length_for_input_length(64 * 100_000), 64);
502    }
503
504    #[test]
505    fn test_hash_ext() {
506        let secret = b"count=10&lat=37.351&user_id=1&\
507                       long=-119.827&waffle=eggo";
508        let hash = sha256::compute_hash(secret);
509
510        let appended_str = b"&waffle=liege";
511        let combined_hash = sha256::extend_hash(hash, secret.len(), appended_str);
512
513        let mut concatenation = Vec::<u8>::new();
514        concatenation.extend_from_slice(secret);
515        let padding = sha256::padding_for_length(secret.len());
516        concatenation.extend_from_slice(padding.as_slice());
517        concatenation.extend_from_slice(appended_str);
518        assert_eq!(
519            combined_hash,
520            sha256::compute_hash(concatenation.as_slice())
521        );
522    }
523}
extendhash/sha256.rs

extendhash/
sha256.rs
