utils/md5/
bruteforce.rs

1use crate::{md5, multithreading, multiversion};
2use std::array;
3use std::num::NonZeroUsize;
4use std::sync::atomic::{AtomicBool, AtomicU32, Ordering};
5
6/// Brute force hashes of a prefix followed by an increasing integer.
7///
8/// This function calls the predicate repeatedly until it returns true from a pool of worker threads
9/// each using the [`FASTEST`](super::FASTEST) supported vectorized MD5 implementation to hash
10/// multiple inputs at once.
11///
12/// When `additional_hashes` is zero, the predicate will be called with:
13/// ```ignore
14/// predicate(i, hash(prefix + i.to_string()))
15/// ```
16///
17/// When `additional_hashes` is more than zero, key stretching is used. For example, passing 2 will
18/// cause the predicate to be called with:
19/// ```ignore
20/// predicate(i, hash(to_hex(hash(to_hex(hash(prefix + i.to_string()))))))
21/// ```
22pub fn find_hash_with_appended_count(
23    prefix: &str,
24    additional_hashes: u32,
25    predicate: impl Fn(u32, [u32; 4]) -> bool + Copy + Sync,
26) {
27    let counter = AtomicU32::new(0);
28    let done = AtomicBool::new(false);
29    multithreading::worker_pool(|| {
30        worker(
31            prefix.as_bytes(),
32            additional_hashes,
33            &predicate,
34            &counter,
35            &done,
36        );
37    });
38}
39
40fn u32_to_ascii(buf: &mut [u8], mut value: u32) -> usize {
41    assert!(buf.len() >= 10);
42
43    let length = 1 + value.checked_ilog10().unwrap_or(0) as usize;
44    assert!(length < 10);
45
46    for d in (0..length).rev() {
47        let new = (value % 10) as u8 + b'0';
48        buf[d] = new;
49        value /= 10;
50    }
51
52    length
53}
54
55multiversion! {
56    use {crate::simd::*, crate::md5::*};
57
58    #[dyn_dispatch = md5::FASTEST]
59    #[expect(clippy::cast_possible_truncation)]
60    fn worker(
61        prefix: &[u8],
62        additional_hashes: u32,
63        predicate: impl Fn(u32, [u32; 4]) -> bool + Copy + Send,
64        counter: &AtomicU32,
65        done: &AtomicBool,
66    ) {
67        let lane_size = prefix.len() + 10; // u32::MAX is 10 digits long
68
69        let mut buf = vec![0u8; lane_size * U32Vector::LANES];
70        for i in 0..prefix.len() {
71            buf[i * U32Vector::LANES..(i + 1) * U32Vector::LANES].fill(prefix[i]);
72        }
73
74        let mut single = vec![0u8; lane_size];
75        single[..prefix.len()].copy_from_slice(prefix);
76
77        let batch_size = if additional_hashes > 0 {
78            U32Vector::LANES as u32
79        }  else {
80            1000u32.next_multiple_of(U32Vector::LANES as u32)
81        };
82
83        while !done.load(Ordering::Acquire) {
84            let batch_start = counter.fetch_add(batch_size, Ordering::AcqRel);
85            for base in (batch_start..batch_start + batch_size).step_by(U32Vector::LANES) {
86                let mut hashes = match u32_to_ascii_multi(&mut buf[U32Vector::LANES * prefix.len()..], base) {
87                    Some(length) => hash(&buf[..U32Vector::LANES * (prefix.len() + length.get())]),
88                    None => {
89                        // Lengths are different
90                        array::from_fn(|i| {
91                            let digits = u32_to_ascii(&mut single[prefix.len()..], base + i as u32);
92                            md5::hash(&single[..prefix.len() + digits])
93                        })
94                    }
95                };
96
97                let mut hex_buf = [0u8; 32 * U32Vector::LANES];
98                for _ in 0..additional_hashes {
99                    for i in 0..U32Vector::LANES {
100                        let hex = md5::to_hex(hashes[i]);
101                        for h in 0..32 {
102                            hex_buf[h * U32Vector::LANES + i] = hex[h];
103                        }
104                    }
105                    hashes = hash(&hex_buf);
106                }
107
108                for (i, &hash) in hashes.iter().enumerate() {
109                    if predicate(base + i as u32, hash) {
110                        // Don't return early. For example, in 2016 day 5, this block of a thousand
111                        // could include more than one password letter. If we break early after
112                        // completing the password with the first letter, we won't process the
113                        // second letter which may have a lower count than the letter stored at that
114                        // position.
115                        done.store(true, Ordering::Release);
116                    }
117                }
118            }
119        }
120    }
121
122    #[inline]
123    #[expect(clippy::cast_possible_truncation)]
124    pub fn u32_to_ascii_multi(buf: &mut [u8], base: u32) -> Option<NonZeroUsize> {
125        assert!(buf.len() >= U32Vector::LANES * 10);
126
127        let length = 1 + base.checked_ilog10().unwrap_or(0) as usize;
128        assert!(length <= 10);
129
130        let mut values: [u32; U32Vector::LANES] = array::from_fn(|i| base + i as u32);
131        for d in (0..length).rev() {
132            let digits: &mut [u8; U32Vector::LANES] =
133                (&mut buf[d * U32Vector::LANES..(d + 1) * U32Vector::LANES]).try_into().unwrap();
134            for i in 0..U32Vector::LANES {
135                digits[i] = (values[i] % 10) as u8 + b'0';
136                values[i] /= 10;
137            }
138        }
139
140        if values.iter().any(|&x| x > 0) {
141            // At least one number has an extra digit, fallback to scalar code
142            return None;
143        }
144
145        Some(NonZeroUsize::new(length).unwrap())
146    }
147}
utils/md5/bruteforce.rs

utils/md5/
bruteforce.rs
