const SHIFTS: [u32; 64] = [
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21,
];
const T: [u32; 64] = [
0xd76a_a478,
0xe8c7_b756,
0x2420_70db,
0xc1bd_ceee,
0xf57c_0faf,
0x4787_c62a,
0xa830_4613,
0xfd46_9501,
0x6980_98d8,
0x8b44_f7af,
0xffff_5bb1,
0x895c_d7be,
0x6b90_1122,
0xfd98_7193,
0xa679_438e,
0x49b4_0821,
0xf61e_2562,
0xc040_b340,
0x265e_5a51,
0xe9b6_c7aa,
0xd62f_105d,
0x0244_1453,
0xd8a1_e681,
0xe7d3_fbc8,
0x21e1_cde6,
0xc337_07d6,
0xf4d5_0d87,
0x455a_14ed,
0xa9e3_e905,
0xfcef_a3f8,
0x676f_02d9,
0x8d2a_4c8a,
0xfffa_3942,
0x8771_f681,
0x6d9d_6122,
0xfde5_380c,
0xa4be_ea44,
0x4bde_cfa9,
0xf6bb_4b60,
0xbebf_bc70,
0x289b_7ec6,
0xeaa1_27fa,
0xd4ef_3085,
0x0488_1d05,
0xd9d4_d039,
0xe6db_99e5,
0x1fa2_7cf8,
0xc4ac_5665,
0xf429_2244,
0x432a_ff97,
0xab94_23a7,
0xfc93_a039,
0x655b_59c3,
0x8f0c_cc92,
0xffef_f47d,
0x8584_5dd1,
0x6fa8_7e4f,
0xfe2c_e6e0,
0xa301_4314,
0x4e08_11a1,
0xf753_7e82,
0xbd3a_f235,
0x2ad7_d2bb,
0xeb86_d391,
];
const BLOCK_BYTES: usize = 64;
#[derive(Debug, Clone)]
pub(crate) struct Md5 {
state: [u32; 4],
block: [u8; BLOCK_BYTES],
filled: usize,
length: u64,
}
impl Md5 {
pub(crate) const fn new() -> Self {
Self {
state: [0x6745_2301, 0xefcd_ab89, 0x98ba_dcfe, 0x1032_5476],
block: [0; BLOCK_BYTES],
filled: 0,
length: 0,
}
}
pub(crate) fn update(&mut self, data: &[u8]) {
self.length = self.length.wrapping_add(data.len() as u64);
let mut rest = data;
if self.filled > 0 {
let want = (BLOCK_BYTES - self.filled).min(rest.len());
self.block[self.filled..self.filled + want].copy_from_slice(&rest[..want]);
self.filled += want;
rest = &rest[want..];
if self.filled < BLOCK_BYTES {
return;
}
let block = self.block;
self.compress(&block);
self.filled = 0;
}
let mut blocks = rest.chunks_exact(BLOCK_BYTES);
for block in &mut blocks {
let block: [u8; BLOCK_BYTES] =
block.try_into().expect("chunks_exact(64) yields 64 bytes");
self.compress(&block);
}
let tail = blocks.remainder();
self.block[..tail.len()].copy_from_slice(tail);
self.filled = tail.len();
}
pub(crate) fn finish(mut self) -> [u8; 16] {
let bits = self.length.wrapping_mul(8);
let pad = if self.filled < 56 {
56 - self.filled
} else {
120 - self.filled
};
let mut trailer = [0u8; 72];
trailer[0] = 0x80;
trailer[pad..pad + 8].copy_from_slice(&bits.to_le_bytes());
self.update(&trailer[..pad + 8]);
let mut digest = [0u8; 16];
for (out, word) in digest.chunks_exact_mut(4).zip(self.state) {
out.copy_from_slice(&word.to_le_bytes());
}
digest
}
fn compress(&mut self, block: &[u8; BLOCK_BYTES]) {
let mut words = [0u32; 16];
for (word, bytes) in words.iter_mut().zip(block.chunks_exact(4)) {
*word = u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
}
let [mut a, mut b, mut c, mut d] = self.state;
for i in 0..64 {
let (mixed, word) = match i / 16 {
0 => ((b & c) | (!b & d), i),
1 => ((b & d) | (c & !d), (5 * i + 1) % 16),
2 => (b ^ c ^ d, (3 * i + 5) % 16),
_ => (c ^ (b | !d), (7 * i) % 16),
};
let rotated = a
.wrapping_add(mixed)
.wrapping_add(T[i])
.wrapping_add(words[word])
.rotate_left(SHIFTS[i]);
a = d;
d = c;
c = b;
b = b.wrapping_add(rotated);
}
self.state[0] = self.state[0].wrapping_add(a);
self.state[1] = self.state[1].wrapping_add(b);
self.state[2] = self.state[2].wrapping_add(c);
self.state[3] = self.state[3].wrapping_add(d);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn hex(message: &[u8]) -> String {
let mut hasher = Md5::new();
hasher.update(message);
hasher
.finish()
.iter()
.map(|byte| format!("{byte:02x}"))
.collect()
}
#[test]
fn rfc_1321_test_suite() {
assert_eq!(hex(b""), "d41d8cd98f00b204e9800998ecf8427e");
assert_eq!(hex(b"a"), "0cc175b9c0f1b6a831c399e269772661");
assert_eq!(hex(b"abc"), "900150983cd24fb0d6963f7d28e17f72");
assert_eq!(hex(b"message digest"), "f96b697d7cb7938d525a2f31aaf161d0");
assert_eq!(
hex(b"abcdefghijklmnopqrstuvwxyz"),
"c3fcd3d76192e4007dfb496cca67e13b"
);
assert_eq!(
hex(b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"),
"d174ab98d277d9f5a5611c2c9f419d9f"
);
assert_eq!(
hex(
b"12345678901234567890123456789012345678901234567890123456789012345678901234567890"
),
"57edf4a22be3c955ac49da2e2107b67a"
);
}
#[test]
fn the_split_between_updates_is_invisible() {
let message: Vec<u8> = (0u32..1000).map(|i| (i % 251) as u8).collect();
let whole = {
let mut hasher = Md5::new();
hasher.update(&message);
hasher.finish()
};
for step in [1, 7, 55, 56, 63, 64, 65, 127, 128, 129, 512] {
let mut hasher = Md5::new();
for piece in message.chunks(step) {
hasher.update(piece);
}
assert_eq!(
hasher.finish(),
whole,
"the digest changed with a {step}-byte feed size"
);
}
}
#[test]
fn the_padding_boundary_lengths_agree_with_themselves() {
for length in [0usize, 1, 55, 56, 57, 63, 64, 65, 119, 120, 121] {
let message = vec![0x41u8; length];
let mut whole = Md5::new();
whole.update(&message);
let mut split = Md5::new();
for byte in &message {
split.update(&[*byte]);
}
assert_eq!(
whole.finish(),
split.finish(),
"padding disagreed at a length of {length} bytes"
);
}
}
#[test]
fn an_empty_message_still_has_a_digest() {
assert_eq!(Md5::new().finish().len(), 16);
assert_ne!(Md5::new().finish(), [0u8; 16]);
}
}