advent_of_code/common/
md5.rs

1//! NOTE: Inlined (and slightly modified) from <https://github.com/stainless-steel/md5>
2//! The [MD5] hash function.
3//!
4//! ## Security Warning
5//!
6//! The package is provided for the purposes of interoperability with protocols
7//! and systems that mandate the use of MD5. However, MD5 should be considered
8//! [cryptographically broken and unsuitable for further use][VU836068].
9//! Collision attacks against MD5 are both practical and trivial, and
10//! [theoretical attacks against MD5 have been found][ACM1724151].
11//!
12//! [RFC6151] advises no new protocols to be designed with any MD5-based
13//! constructions, including HMAC-MD5.
14//!
15//! [MD5]: https://en.wikipedia.org/wiki/MD5
16//!
17//! [ACM1724151]: https://dl.acm.org/citation.cfm?id=1724151
18//! [RFC6151]: https://tools.ietf.org/html/rfc6151
19//! [VU836068]: https://www.kb.cert.org/vuls/id/836068
20
21// The implementation is based on:
22// https://people.csail.mit.edu/rivest/Md5.c
23// https://tools.ietf.org/html/rfc1321
24
25/// A context.
26#[derive(Clone)]
27pub struct Context {
28    buffer: [u8; 64],
29    count: [u32; 2],
30    state: [u32; 4],
31}
32
33const PADDING: [u8; 64] = [
34    0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
35    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
36    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
37    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
38];
39
40impl Context {
41    /// Create a context for computing a digest.
42    #[inline]
43    pub const fn new() -> Self {
44        #![allow(clippy::unreadable_literal)]
45        Self {
46            buffer: [0; 64],
47            count: [0, 0],
48            state: [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476],
49        }
50    }
51
52    pub fn consume(&mut self, data: &[u8]) {
53        let Self {
54            buffer,
55            count,
56            state,
57        } = self;
58        let mut input = [0_u32; 16];
59        let mut k = ((count[0] >> 3) & 0x3f) as usize;
60        let length = data.len() as u32;
61        count[0] = count[0].wrapping_add(length << 3);
62        if count[0] < length << 3 {
63            count[1] = count[1].wrapping_add(1);
64        }
65        count[1] = count[1].wrapping_add(length >> 29);
66        for &value in data {
67            buffer[k] = value;
68            k += 1;
69            if k == 0x40 {
70                let mut j = 0;
71                for i in &mut input {
72                    *i = (u32::from(buffer[j + 3]) << 24)
73                        | (u32::from(buffer[j + 2]) << 16)
74                        | (u32::from(buffer[j + 1]) << 8)
75                        | (u32::from(buffer[j]));
76                    j += 4;
77                }
78                transform(state, &input);
79                k = 0;
80            }
81        }
82    }
83
84    /// Finalize and return the digest.
85    pub fn compute(mut self) -> [u8; 16] {
86        let mut input = [0_u32; 16];
87        let k = ((self.count[0] >> 3) & 0x3f) as usize;
88        input[14] = self.count[0];
89        input[15] = self.count[1];
90        self.consume(&PADDING[..(if k < 56 { 56 - k } else { 120 - k })]);
91        let mut j = 0;
92        for i in input.iter_mut().take(14) {
93            *i = (u32::from(self.buffer[j + 3]) << 24)
94                | (u32::from(self.buffer[j + 2]) << 16)
95                | (u32::from(self.buffer[j + 1]) << 8)
96                | (u32::from(self.buffer[j]));
97            j += 4;
98        }
99        transform(&mut self.state, &input);
100        let mut digest = [0_u8; 16];
101        let mut j = 0;
102        for i in 0..4 {
103            digest[j] = ((self.state[i]) & 0xff) as u8;
104            digest[j + 1] = ((self.state[i] >> 8) & 0xff) as u8;
105            digest[j + 2] = ((self.state[i] >> 16) & 0xff) as u8;
106            digest[j + 3] = ((self.state[i] >> 24) & 0xff) as u8;
107            j += 4;
108        }
109        digest
110    }
111}
112
113/// Compute the digest of data.
114#[inline]
115#[cfg(test)]
116pub fn compute<T: AsRef<[u8]>>(data: T) -> [u8; 16] {
117    let mut context = Context::new();
118    context.consume(data.as_ref());
119    context.compute()
120}
121
122#[cfg(test)]
123fn lower_hex(data: &[u8]) -> String {
124    use std::fmt::Write;
125    let mut buf = String::new();
126    for value in data {
127        write!(buf, "{value:02x}").unwrap();
128        //buf.write_fmt("{:02x}", value);
129    }
130    buf
131}
132
133const fn transform(state: &mut [u32; 4], input: &[u32; 16]) {
134    #![allow(clippy::unreadable_literal)]
135    #![allow(clippy::tuple_array_conversions)]
136    let (mut a, mut b, mut c, mut d) = (state[0], state[1], state[2], state[3]);
137    macro_rules! add(
138        ($a:expr, $b:expr) => ($a.wrapping_add($b));
139    );
140    macro_rules! rotate(
141        //($x:expr, $n:expr) => (($x << $n) | ($x >> (32 - $n)));
142        ($x:expr, $n:expr) => ($x.rotate_left($n));
143    );
144    {
145        macro_rules! F(
146            ($x:expr, $y:expr, $z:expr) => (($x & $y) | (!$x & $z));
147        );
148        macro_rules! T(
149            ($a:expr, $b:expr, $c:expr, $d:expr, $x:expr, $s:expr, $ac:expr) => ({
150                $a = add!(add!(add!($a, F!($b, $c, $d)), $x), $ac);
151                $a = rotate!($a, $s);
152                $a = add!($a, $b);
153            });
154        );
155        const S1: u32 = 7;
156        const S2: u32 = 12;
157        const S3: u32 = 17;
158        const S4: u32 = 22;
159        T!(a, b, c, d, input[0], S1, 3614090360);
160        T!(d, a, b, c, input[1], S2, 3905402710);
161        T!(c, d, a, b, input[2], S3, 606105819);
162        T!(b, c, d, a, input[3], S4, 3250441966);
163        T!(a, b, c, d, input[4], S1, 4118548399);
164        T!(d, a, b, c, input[5], S2, 1200080426);
165        T!(c, d, a, b, input[6], S3, 2821735955);
166        T!(b, c, d, a, input[7], S4, 4249261313);
167        T!(a, b, c, d, input[8], S1, 1770035416);
168        T!(d, a, b, c, input[9], S2, 2336552879);
169        T!(c, d, a, b, input[10], S3, 4294925233);
170        T!(b, c, d, a, input[11], S4, 2304563134);
171        T!(a, b, c, d, input[12], S1, 1804603682);
172        T!(d, a, b, c, input[13], S2, 4254626195);
173        T!(c, d, a, b, input[14], S3, 2792965006);
174        T!(b, c, d, a, input[15], S4, 1236535329);
175    }
176    {
177        macro_rules! F(
178            ($x:expr, $y:expr, $z:expr) => (($x & $z) | ($y & !$z));
179        );
180        macro_rules! T(
181            ($a:expr, $b:expr, $c:expr, $d:expr, $x:expr, $s:expr, $ac:expr) => ({
182                $a = add!(add!(add!($a, F!($b, $c, $d)), $x), $ac);
183                $a = rotate!($a, $s);
184                $a = add!($a, $b);
185            });
186        );
187        const S1: u32 = 5;
188        const S2: u32 = 9;
189        const S3: u32 = 14;
190        const S4: u32 = 20;
191        T!(a, b, c, d, input[1], S1, 4129170786);
192        T!(d, a, b, c, input[6], S2, 3225465664);
193        T!(c, d, a, b, input[11], S3, 643717713);
194        T!(b, c, d, a, input[0], S4, 3921069994);
195        T!(a, b, c, d, input[5], S1, 3593408605);
196        T!(d, a, b, c, input[10], S2, 38016083);
197        T!(c, d, a, b, input[15], S3, 3634488961);
198        T!(b, c, d, a, input[4], S4, 3889429448);
199        T!(a, b, c, d, input[9], S1, 568446438);
200        T!(d, a, b, c, input[14], S2, 3275163606);
201        T!(c, d, a, b, input[3], S3, 4107603335);
202        T!(b, c, d, a, input[8], S4, 1163531501);
203        T!(a, b, c, d, input[13], S1, 2850285829);
204        T!(d, a, b, c, input[2], S2, 4243563512);
205        T!(c, d, a, b, input[7], S3, 1735328473);
206        T!(b, c, d, a, input[12], S4, 2368359562);
207    }
208    {
209        macro_rules! F(
210            ($x:expr, $y:expr, $z:expr) => ($x ^ $y ^ $z);
211        );
212        macro_rules! T(
213            ($a:expr, $b:expr, $c:expr, $d:expr, $x:expr, $s:expr, $ac:expr) => ({
214                $a = add!(add!(add!($a, F!($b, $c, $d)), $x), $ac);
215                $a = rotate!($a, $s);
216                $a = add!($a, $b);
217            });
218        );
219        const S1: u32 = 4;
220        const S2: u32 = 11;
221        const S3: u32 = 16;
222        const S4: u32 = 23;
223        T!(a, b, c, d, input[5], S1, 4294588738);
224        T!(d, a, b, c, input[8], S2, 2272392833);
225        T!(c, d, a, b, input[11], S3, 1839030562);
226        T!(b, c, d, a, input[14], S4, 4259657740);
227        T!(a, b, c, d, input[1], S1, 2763975236);
228        T!(d, a, b, c, input[4], S2, 1272893353);
229        T!(c, d, a, b, input[7], S3, 4139469664);
230        T!(b, c, d, a, input[10], S4, 3200236656);
231        T!(a, b, c, d, input[13], S1, 681279174);
232        T!(d, a, b, c, input[0], S2, 3936430074);
233        T!(c, d, a, b, input[3], S3, 3572445317);
234        T!(b, c, d, a, input[6], S4, 76029189);
235        T!(a, b, c, d, input[9], S1, 3654602809);
236        T!(d, a, b, c, input[12], S2, 3873151461);
237        T!(c, d, a, b, input[15], S3, 530742520);
238        T!(b, c, d, a, input[2], S4, 3299628645);
239    }
240    {
241        macro_rules! F(
242            ($x:expr, $y:expr, $z:expr) => ($y ^ ($x | !$z));
243        );
244        macro_rules! T(
245            ($a:expr, $b:expr, $c:expr, $d:expr, $x:expr, $s:expr, $ac:expr) => ({
246                $a = add!(add!(add!($a, F!($b, $c, $d)), $x), $ac);
247                $a = rotate!($a, $s);
248                $a = add!($a, $b);
249            });
250        );
251        const S1: u32 = 6;
252        const S2: u32 = 10;
253        const S3: u32 = 15;
254        const S4: u32 = 21;
255        T!(a, b, c, d, input[0], S1, 4096336452);
256        T!(d, a, b, c, input[7], S2, 1126891415);
257        T!(c, d, a, b, input[14], S3, 2878612391);
258        T!(b, c, d, a, input[5], S4, 4237533241);
259        T!(a, b, c, d, input[12], S1, 1700485571);
260        T!(d, a, b, c, input[3], S2, 2399980690);
261        T!(c, d, a, b, input[10], S3, 4293915773);
262        T!(b, c, d, a, input[1], S4, 2240044497);
263        T!(a, b, c, d, input[8], S1, 1873313359);
264        T!(d, a, b, c, input[15], S2, 4264355552);
265        T!(c, d, a, b, input[6], S3, 2734768916);
266        T!(b, c, d, a, input[13], S4, 1309151649);
267        T!(a, b, c, d, input[4], S1, 4149444226);
268        T!(d, a, b, c, input[11], S2, 3174756917);
269        T!(c, d, a, b, input[2], S3, 718787259);
270        T!(b, c, d, a, input[9], S4, 3951481745);
271    }
272    state[0] = add!(state[0], a);
273    state[1] = add!(state[1], b);
274    state[2] = add!(state[2], c);
275    state[3] = add!(state[3], d);
276}
277
278#[cfg(test)]
279mod tests {
280    #[test]
281    fn compute() {
282        let inputs = [
283            "",
284            "a",
285            "abc",
286            "message digest",
287            "abcdefghijklmnopqrstuvwxyz",
288            "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
289            "0123456789012345678901234567890123456789012345678901234567890123",
290            "12345678901234567890123456789012345678901234567890123456789012345678901234567890",
291        ];
292        let outputs = [
293            "d41d8cd98f00b204e9800998ecf8427e",
294            "0cc175b9c0f1b6a831c399e269772661",
295            "900150983cd24fb0d6963f7d28e17f72",
296            "f96b697d7cb7938d525a2f31aaf161d0",
297            "c3fcd3d76192e4007dfb496cca67e13b",
298            "d174ab98d277d9f5a5611c2c9f419d9f",
299            "7f7bfd348709deeaace19e3f535f8c54",
300            "57edf4a22be3c955ac49da2e2107b67a",
301        ];
302        for (input, &output) in inputs.iter().zip(outputs.iter()) {
303            assert_eq!(super::lower_hex(&super::compute(input)), output);
304        }
305    }
306
307    #[test]
308    fn index() {
309        let mut digest = super::compute(b"abc");
310        assert_eq!(digest[0], 0x90);
311        assert_eq!(&digest[0], &0x90);
312        assert_eq!(&mut digest[0], &mut 0x90);
313    }
314
315    #[test]
316    fn overflow_count() {
317        let data = vec![0; 8 * 1024 * 1024];
318        let mut context = super::Context::new();
319        for _ in 0..64 {
320            context.consume(&data);
321        }
322        assert_eq!(
323            super::lower_hex(&context.compute()),
324            "aa559b4e3523a6c931f08f4df52d58f2"
325        );
326    }
327}
advent_of_code/common/md5.rs

advent_of_code/common/
md5.rs
