(index<- ) ./libextra/crypto/md5.rs
1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use std::iter::range_step;
12
13 use cryptoutil::{write_u32_le, read_u32v_le, FixedBuffer, FixedBuffer64, StandardPadding};
14 use digest::Digest;
15
16
17 // A structure that represents that state of a digest computation for the MD5 digest function
18 struct Md5State {
19 s0: u32,
20 s1: u32,
21 s2: u32,
22 s3: u32
23 }
24
25 impl Md5State {
26 fn new() -> Md5State {
27 return Md5State {
28 s0: 0x67452301,
29 s1: 0xefcdab89,
30 s2: 0x98badcfe,
31 s3: 0x10325476
32 };
33 }
34
35 fn reset(&mut self) {
36 self.s0 = 0x67452301;
37 self.s1 = 0xefcdab89;
38 self.s2 = 0x98badcfe;
39 self.s3 = 0x10325476;
40 }
41
42 fn process_block(&mut self, input: &[u8]) {
43 fn f(u: u32, v: u32, w: u32) -> u32 {
44 return (u & v) | (!u & w);
45 }
46
47 fn g(u: u32, v: u32, w: u32) -> u32 {
48 return (u & w) | (v & !w);
49 }
50
51 fn h(u: u32, v: u32, w: u32) -> u32 {
52 return u ^ v ^ w;
53 }
54
55 fn i(u: u32, v: u32, w: u32) -> u32 {
56 return v ^ (u | !w);
57 }
58
59 fn rotate_left(x: u32, n: u32) -> u32 {
60 return (x << n) | (x >> (32 - n));
61 }
62
63 fn op_f(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
64 return rotate_left(w + f(x, y, z) + m, s) + x;
65 }
66
67 fn op_g(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
68 return rotate_left(w + g(x, y, z) + m, s) + x;
69 }
70
71 fn op_h(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
72 return rotate_left(w + h(x, y, z) + m, s) + x;
73 }
74
75 fn op_i(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
76 return rotate_left(w + i(x, y, z) + m, s) + x;
77 }
78
79 let mut a = self.s0;
80 let mut b = self.s1;
81 let mut c = self.s2;
82 let mut d = self.s3;
83
84 let mut data = [0u32, ..16];
85
86 read_u32v_le(data, input);
87
88 // round 1
89 for i in range_step(0u, 16, 4) {
90 a = op_f(a, b, c, d, data[i] + C1[i], 7);
91 d = op_f(d, a, b, c, data[i + 1] + C1[i + 1], 12);
92 c = op_f(c, d, a, b, data[i + 2] + C1[i + 2], 17);
93 b = op_f(b, c, d, a, data[i + 3] + C1[i + 3], 22);
94 }
95
96 // round 2
97 let mut t = 1;
98 for i in range_step(0u, 16, 4) {
99 a = op_g(a, b, c, d, data[t & 0x0f] + C2[i], 5);
100 d = op_g(d, a, b, c, data[(t + 5) & 0x0f] + C2[i + 1], 9);
101 c = op_g(c, d, a, b, data[(t + 10) & 0x0f] + C2[i + 2], 14);
102 b = op_g(b, c, d, a, data[(t + 15) & 0x0f] + C2[i + 3], 20);
103 t += 20;
104 }
105
106 // round 3
107 t = 5;
108 for i in range_step(0u, 16, 4) {
109 a = op_h(a, b, c, d, data[t & 0x0f] + C3[i], 4);
110 d = op_h(d, a, b, c, data[(t + 3) & 0x0f] + C3[i + 1], 11);
111 c = op_h(c, d, a, b, data[(t + 6) & 0x0f] + C3[i + 2], 16);
112 b = op_h(b, c, d, a, data[(t + 9) & 0x0f] + C3[i + 3], 23);
113 t += 12;
114 }
115
116 // round 4
117 t = 0;
118 for i in range_step(0u, 16, 4) {
119 a = op_i(a, b, c, d, data[t & 0x0f] + C4[i], 6);
120 d = op_i(d, a, b, c, data[(t + 7) & 0x0f] + C4[i + 1], 10);
121 c = op_i(c, d, a, b, data[(t + 14) & 0x0f] + C4[i + 2], 15);
122 b = op_i(b, c, d, a, data[(t + 21) & 0x0f] + C4[i + 3], 21);
123 t += 28;
124 }
125
126 self.s0 += a;
127 self.s1 += b;
128 self.s2 += c;
129 self.s3 += d;
130 }
131 }
132
133 // Round 1 constants
134 static C1: [u32, ..16] = [
135 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
136 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821
137 ];
138
139 // Round 2 constants
140 static C2: [u32, ..16] = [
141 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
142 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a
143 ];
144
145 // Round 3 constants
146 static C3: [u32, ..16] = [
147 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
148 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665
149 ];
150
151 // Round 4 constants
152 static C4: [u32, ..16] = [
153 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
154 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
155 ];
156
157
158 /// The MD5 Digest algorithm
159 struct Md5 {
160 priv length_bytes: u64,
161 priv buffer: FixedBuffer64,
162 priv state: Md5State,
163 priv finished: bool,
164 }
165
166 impl Md5 {
167 /// Construct a new instance of the MD5 Digest.
168 pub fn new() -> Md5 {
169 return Md5 {
170 length_bytes: 0,
171 buffer: FixedBuffer64::new(),
172 state: Md5State::new(),
173 finished: false
174 }
175 }
176 }
177
178 impl Digest for Md5 {
179 fn input(&mut self, input: &[u8]) {
180 assert!(!self.finished);
181 // Unlike Sha1 and Sha2, the length value in MD5 is defined as the length of the message mod
182 // 2^64 - ie: integer overflow is OK.
183 self.length_bytes += input.len() as u64;
184 self.buffer.input(input, |d: &[u8]| { self.state.process_block(d); });
185 }
186
187 fn reset(&mut self) {
188 self.length_bytes = 0;
189 self.buffer.reset();
190 self.state.reset();
191 self.finished = false;
192 }
193
194 fn result(&mut self, out: &mut [u8]) {
195 if !self.finished {
196 self.buffer.standard_padding(8, |d: &[u8]| { self.state.process_block(d); });
197 write_u32_le(self.buffer.next(4), (self.length_bytes << 3) as u32);
198 write_u32_le(self.buffer.next(4), (self.length_bytes >> 29) as u32);
199 self.state.process_block(self.buffer.full_buffer());
200 self.finished = true;
201 }
202
203 write_u32_le(out.mut_slice(0, 4), self.state.s0);
204 write_u32_le(out.mut_slice(4, 8), self.state.s1);
205 write_u32_le(out.mut_slice(8, 12), self.state.s2);
206 write_u32_le(out.mut_slice(12, 16), self.state.s3);
207 }
208
209 fn output_bits(&self) -> uint { 128 }
210 }
211
212
213 #[cfg(test)]
214 mod tests {
215 use cryptoutil::test::test_digest_1million_random;
216 use digest::Digest;
217 use md5::Md5;
218
219
220 struct Test {
221 input: ~str,
222 output_str: ~str,
223 }
224
225 fn test_hash<D: Digest>(sh: &mut D, tests: &[Test]) {
226 // Test that it works when accepting the message all at once
227 for t in tests.iter() {
228 sh.input_str(t.input);
229
230 let out_str = sh.result_str();
231 assert!(out_str == t.output_str);
232
233 sh.reset();
234 }
235
236 // Test that it works when accepting the message in pieces
237 for t in tests.iter() {
238 let len = t.input.len();
239 let mut left = len;
240 while left > 0u {
241 let take = (left + 1u) / 2u;
242 sh.input_str(t.input.slice(len - left, take + len - left));
243 left = left - take;
244 }
245
246 let out_str = sh.result_str();
247 assert!(out_str == t.output_str);
248
249 sh.reset();
250 }
251 }
252
253 #[test]
254 fn test_md5() {
255 // Examples from wikipedia
256 let wikipedia_tests = ~[
257 Test {
258 input: ~"",
259 output_str: ~"d41d8cd98f00b204e9800998ecf8427e"
260 },
261 Test {
262 input: ~"The quick brown fox jumps over the lazy dog",
263 output_str: ~"9e107d9d372bb6826bd81d3542a419d6"
264 },
265 Test {
266 input: ~"The quick brown fox jumps over the lazy dog.",
267 output_str: ~"e4d909c290d0fb1ca068ffaddf22cbd0"
268 },
269 ];
270
271 let tests = wikipedia_tests;
272
273 let mut sh = Md5::new();
274
275 test_hash(&mut sh, tests);
276 }
277
278 #[test]
279 fn test_1million_random_md5() {
280 let mut sh = Md5::new();
281 test_digest_1million_random(
282 &mut sh,
283 64,
284 "7707d6ae4e027c70eea2a935c2296f21");
285 }
286 }
287
288
289 #[cfg(test)]
290 mod bench {
291 use extra::test::BenchHarness;
292
293 use md5::Md5;
294
295
296 #[bench]
297 pub fn md5_10(bh: & mut BenchHarness) {
298 let mut sh = Md5::new();
299 let bytes = [1u8, ..10];
300 do bh.iter {
301 sh.input(bytes);
302 }
303 bh.bytes = bytes.len() as u64;
304 }
305
306 #[bench]
307 pub fn md5_1k(bh: & mut BenchHarness) {
308 let mut sh = Md5::new();
309 let bytes = [1u8, ..1024];
310 do bh.iter {
311 sh.input(bytes);
312 }
313 bh.bytes = bytes.len() as u64;
314 }
315
316 #[bench]
317 pub fn md5_64k(bh: & mut BenchHarness) {
318 let mut sh = Md5::new();
319 let bytes = [1u8, ..65536];
320 do bh.iter {
321 sh.input(bytes);
322 }
323 bh.bytes = bytes.len() as u64;
324 }
325 }
libextra/crypto/md5.rs:51:8-51:8 -fn- definition:
fn h(u: u32, v: u32, w: u32) -> u32 {
return u ^ v ^ w;
references:-72: return rotate_left(w + h(x, y, z) + m, s) + x;
libextra/crypto/md5.rs:47:8-47:8 -fn- definition:
fn g(u: u32, v: u32, w: u32) -> u32 {
return (u & w) | (v & !w);
references:-68: return rotate_left(w + g(x, y, z) + m, s) + x;
libextra/crypto/md5.rs:158:29-158:29 -struct- definition:
/// The MD5 Digest algorithm
struct Md5 {
references:-168: pub fn new() -> Md5 {
166: impl Md5 {
178: impl Digest for Md5 {
169: return Md5 {
libextra/crypto/md5.rs:75:8-75:8 -fn- definition:
fn op_i(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
return rotate_left(w + i(x, y, z) + m, s) + x;
references:-121: c = op_i(c, d, a, b, data[(t + 14) & 0x0f] + C4[i + 2], 15);
122: b = op_i(b, c, d, a, data[(t + 21) & 0x0f] + C4[i + 3], 21);
119: a = op_i(a, b, c, d, data[t & 0x0f] + C4[i], 6);
120: d = op_i(d, a, b, c, data[(t + 7) & 0x0f] + C4[i + 1], 10);
libextra/crypto/md5.rs:63:8-63:8 -fn- definition:
fn op_f(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
return rotate_left(w + f(x, y, z) + m, s) + x;
references:-93: b = op_f(b, c, d, a, data[i + 3] + C1[i + 3], 22);
92: c = op_f(c, d, a, b, data[i + 2] + C1[i + 2], 17);
91: d = op_f(d, a, b, c, data[i + 1] + C1[i + 1], 12);
90: a = op_f(a, b, c, d, data[i] + C1[i], 7);
libextra/crypto/md5.rs:43:8-43:8 -fn- definition:
fn f(u: u32, v: u32, w: u32) -> u32 {
return (u & v) | (!u & w);
references:-64: return rotate_left(w + f(x, y, z) + m, s) + x;
libextra/crypto/md5.rs:71:8-71:8 -fn- definition:
fn op_h(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
return rotate_left(w + h(x, y, z) + m, s) + x;
references:-112: b = op_h(b, c, d, a, data[(t + 9) & 0x0f] + C3[i + 3], 23);
110: d = op_h(d, a, b, c, data[(t + 3) & 0x0f] + C3[i + 1], 11);
109: a = op_h(a, b, c, d, data[t & 0x0f] + C3[i], 4);
111: c = op_h(c, d, a, b, data[(t + 6) & 0x0f] + C3[i + 2], 16);
libextra/crypto/md5.rs:55:8-55:8 -fn- definition:
fn i(u: u32, v: u32, w: u32) -> u32 {
return v ^ (u | !w);
references:-76: return rotate_left(w + i(x, y, z) + m, s) + x;
libextra/crypto/md5.rs:59:8-59:8 -fn- definition:
fn rotate_left(x: u32, n: u32) -> u32 {
return (x << n) | (x >> (32 - n));
references:-72: return rotate_left(w + h(x, y, z) + m, s) + x;
76: return rotate_left(w + i(x, y, z) + m, s) + x;
64: return rotate_left(w + f(x, y, z) + m, s) + x;
68: return rotate_left(w + g(x, y, z) + m, s) + x;
libextra/crypto/md5.rs:67:8-67:8 -fn- definition:
fn op_g(w: u32, x: u32, y: u32, z: u32, m: u32, s: u32) -> u32 {
return rotate_left(w + g(x, y, z) + m, s) + x;
references:-102: b = op_g(b, c, d, a, data[(t + 15) & 0x0f] + C2[i + 3], 20);
100: d = op_g(d, a, b, c, data[(t + 5) & 0x0f] + C2[i + 1], 9);
101: c = op_g(c, d, a, b, data[(t + 10) & 0x0f] + C2[i + 2], 14);
99: a = op_g(a, b, c, d, data[t & 0x0f] + C2[i], 5);
libextra/crypto/md5.rs:17:94-17:94 -struct- definition:
// A structure that represents that state of a digest computation for the MD5 digest function
struct Md5State {
references:-25: impl Md5State {
162: priv state: Md5State,
26: fn new() -> Md5State {
27: return Md5State {