1 // Copyright 2012-2014 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.
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.
11 //! This module implements only the Sha256 function since that is all that is needed for internal
12 //! use. This implementation is not intended for external use or for any use where security is
15 use serialize::hex::ToHex;
17 /// Write a u32 into a vector, which must be 4 bytes long. The value is written in big-endian
19 fn write_u32_be(dst: &mut[u8], input: u32) {
20 dst[0] = (input >> 24) as u8;
21 dst[1] = (input >> 16) as u8;
22 dst[2] = (input >> 8) as u8;
26 /// Read the value of a vector of bytes as a u32 value in big-endian format.
27 fn read_u32_be(input: &[u8]) -> u32 {
29 (input[0] as u32) << 24 |
30 (input[1] as u32) << 16 |
31 (input[2] as u32) << 8 |
35 /// Read a vector of bytes into a vector of u32s. The values are read in big-endian format.
36 fn read_u32v_be(dst: &mut[u32], input: &[u8]) {
37 assert!(dst.len() * 4 == input.len());
39 for chunk in input.chunks(4) {
40 dst[pos] = read_u32_be(chunk);
46 /// Convert the value in bytes to the number of bits, a tuple where the 1st item is the
47 /// high-order value and the 2nd item is the low order value.
48 fn to_bits(self) -> (Self, Self);
52 fn to_bits(self) -> (u64, u64) {
53 return (self >> 61, self << 3);
57 /// Adds the specified number of bytes to the bit count. panic!() if this would cause numeric
59 fn add_bytes_to_bits(bits: u64, bytes: u64) -> u64 {
60 let (new_high_bits, new_low_bits) = bytes.to_bits();
62 if new_high_bits > 0 {
63 panic!("numeric overflow occurred.")
66 match bits.checked_add(new_low_bits) {
68 None => panic!("numeric overflow occurred.")
72 /// A FixedBuffer, likes its name implies, is a fixed size buffer. When the buffer becomes full, it
73 /// must be processed. The input() method takes care of processing and then clearing the buffer
74 /// automatically. However, other methods do not and require the caller to process the buffer. Any
75 /// method that modifies the buffer directory or provides the caller with bytes that can be modified
76 /// results in those bytes being marked as used by the buffer.
78 /// Input a vector of bytes. If the buffer becomes full, process it with the provided
79 /// function and then clear the buffer.
80 fn input<F>(&mut self, input: &[u8], func: F) where
86 /// Zero the buffer up until the specified index. The buffer position currently must not be
87 /// greater than that index.
88 fn zero_until(&mut self, idx: usize);
90 /// Get a slice of the buffer of the specified size. There must be at least that many bytes
91 /// remaining in the buffer.
92 fn next<'s>(&'s mut self, len: usize) -> &'s mut [u8];
94 /// Get the current buffer. The buffer must already be full. This clears the buffer as well.
95 fn full_buffer<'s>(&'s mut self) -> &'s [u8];
97 /// Get the current position of the buffer.
98 fn position(&self) -> usize;
100 /// Get the number of bytes remaining in the buffer until it is full.
101 fn remaining(&self) -> usize;
103 /// Get the size of the buffer
104 fn size(&self) -> usize;
107 /// A FixedBuffer of 64 bytes useful for implementing Sha256 which has a 64 byte blocksize.
108 struct FixedBuffer64 {
114 /// Create a new FixedBuffer64
115 fn new() -> FixedBuffer64 {
116 return FixedBuffer64 {
123 impl FixedBuffer for FixedBuffer64 {
124 fn input<F>(&mut self, input: &[u8], mut func: F) where
129 let size = self.size();
131 // If there is already data in the buffer, copy as much as we can into it and process
132 // the data if the buffer becomes full.
133 if self.buffer_idx != 0 {
134 let buffer_remaining = size - self.buffer_idx;
135 if input.len() >= buffer_remaining {
136 self.buffer[self.buffer_idx..size]
137 .clone_from_slice(&input[..buffer_remaining]);
140 i += buffer_remaining;
142 self.buffer[self.buffer_idx..self.buffer_idx + input.len()]
143 .clone_from_slice(input);
144 self.buffer_idx += input.len();
149 // While we have at least a full buffer size chunk's worth of data, process that data
150 // without copying it into the buffer
151 while input.len() - i >= size {
152 func(&input[i..i + size]);
156 // Copy any input data into the buffer. At this point in the method, the amount of
157 // data left in the input vector will be less than the buffer size and the buffer will
159 let input_remaining = input.len() - i;
160 self.buffer[..input_remaining].clone_from_slice(&input[i..]);
161 self.buffer_idx += input_remaining;
164 fn reset(&mut self) {
168 fn zero_until(&mut self, idx: usize) {
169 assert!(idx >= self.buffer_idx);
170 for slot in self.buffer[self.buffer_idx..idx].iter_mut() {
173 self.buffer_idx = idx;
176 fn next<'s>(&'s mut self, len: usize) -> &'s mut [u8] {
177 self.buffer_idx += len;
178 return &mut self.buffer[self.buffer_idx - len..self.buffer_idx];
181 fn full_buffer<'s>(&'s mut self) -> &'s [u8] {
182 assert!(self.buffer_idx == 64);
184 return &self.buffer[..64];
187 fn position(&self) -> usize { self.buffer_idx }
189 fn remaining(&self) -> usize { 64 - self.buffer_idx }
191 fn size(&self) -> usize { 64 }
194 /// The StandardPadding trait adds a method useful for Sha256 to a FixedBuffer struct.
195 trait StandardPadding {
196 /// Add padding to the buffer. The buffer must not be full when this method is called and is
197 /// guaranteed to have exactly rem remaining bytes when it returns. If there are not at least
198 /// rem bytes available, the buffer will be zero padded, processed, cleared, and then filled
199 /// with zeros again until only rem bytes are remaining.
200 fn standard_padding<F>(&mut self, rem: usize, func: F) where F: FnMut(&[u8]);
203 impl <T: FixedBuffer> StandardPadding for T {
204 fn standard_padding<F>(&mut self, rem: usize, mut func: F) where F: FnMut(&[u8]) {
205 let size = self.size();
207 self.next(1)[0] = 128;
209 if self.remaining() < rem {
210 self.zero_until(size);
211 func(self.full_buffer());
214 self.zero_until(size - rem);
218 /// The Digest trait specifies an interface common to digest functions, such as SHA-1 and the SHA-2
219 /// family of digest functions.
221 /// Provide message data.
225 /// * input - A vector of message data
226 fn input(&mut self, input: &[u8]);
228 /// Retrieve the digest result. This method may be called multiple times.
232 /// * out - the vector to hold the result. Must be large enough to contain output_bits().
233 fn result(&mut self, out: &mut [u8]);
235 /// Reset the digest. This method must be called after result() and before supplying more
239 /// Get the output size in bits.
240 fn output_bits(&self) -> usize;
242 /// Convenience function that feeds a string into a digest.
246 /// * `input` The string to feed into the digest
247 fn input_str(&mut self, input: &str) {
248 self.input(input.as_bytes());
251 /// Convenience function that retrieves the result of a digest as a
252 /// newly allocated vec of bytes.
253 fn result_bytes(&mut self) -> Vec<u8> {
254 let mut buf = vec![0; (self.output_bits()+7)/8];
255 self.result(&mut buf);
259 /// Convenience function that retrieves the result of a digest as a
260 /// String in hexadecimal format.
261 fn result_str(&mut self) -> String {
262 self.result_bytes().to_hex().to_string()
266 // A structure that represents that state of a digest computation for the SHA-2 512 family of digest
268 struct Engine256State {
279 impl Engine256State {
280 fn new(h: &[u32; 8]) -> Engine256State {
281 return Engine256State {
293 fn reset(&mut self, h: &[u32; 8]) {
304 fn process_block(&mut self, data: &[u8]) {
305 fn ch(x: u32, y: u32, z: u32) -> u32 {
306 ((x & y) ^ ((!x) & z))
309 fn maj(x: u32, y: u32, z: u32) -> u32 {
310 ((x & y) ^ (x & z) ^ (y & z))
313 fn sum0(x: u32) -> u32 {
314 ((x >> 2) | (x << 30)) ^ ((x >> 13) | (x << 19)) ^ ((x >> 22) | (x << 10))
317 fn sum1(x: u32) -> u32 {
318 ((x >> 6) | (x << 26)) ^ ((x >> 11) | (x << 21)) ^ ((x >> 25) | (x << 7))
321 fn sigma0(x: u32) -> u32 {
322 ((x >> 7) | (x << 25)) ^ ((x >> 18) | (x << 14)) ^ (x >> 3)
325 fn sigma1(x: u32) -> u32 {
326 ((x >> 17) | (x << 15)) ^ ((x >> 19) | (x << 13)) ^ (x >> 10)
340 // Sha-512 and Sha-256 use basically the same calculations which are implemented
341 // by these macros. Inlining the calculations seems to result in better generated code.
342 macro_rules! schedule_round { ($t:expr) => (
343 w[$t] = sigma1(w[$t - 2]).wrapping_add(w[$t - 7])
344 .wrapping_add(sigma0(w[$t - 15])).wrapping_add(w[$t - 16]);
348 macro_rules! sha2_round {
349 ($A:ident, $B:ident, $C:ident, $D:ident,
350 $E:ident, $F:ident, $G:ident, $H:ident, $K:ident, $t:expr) => (
352 $H = $H.wrapping_add(sum1($E)).wrapping_add(ch($E, $F, $G))
353 .wrapping_add($K[$t]).wrapping_add(w[$t]);
354 $D = $D.wrapping_add($H);
355 $H = $H.wrapping_add(sum0($A)).wrapping_add(maj($A, $B, $C));
360 read_u32v_be(&mut w[0..16], data);
362 // Putting the message schedule inside the same loop as the round calculations allows for
363 // the compiler to generate better code.
364 for t in (0..48).step_by(8) {
365 schedule_round!(t + 16);
366 schedule_round!(t + 17);
367 schedule_round!(t + 18);
368 schedule_round!(t + 19);
369 schedule_round!(t + 20);
370 schedule_round!(t + 21);
371 schedule_round!(t + 22);
372 schedule_round!(t + 23);
374 sha2_round!(a, b, c, d, e, f, g, h, K32, t);
375 sha2_round!(h, a, b, c, d, e, f, g, K32, t + 1);
376 sha2_round!(g, h, a, b, c, d, e, f, K32, t + 2);
377 sha2_round!(f, g, h, a, b, c, d, e, K32, t + 3);
378 sha2_round!(e, f, g, h, a, b, c, d, K32, t + 4);
379 sha2_round!(d, e, f, g, h, a, b, c, K32, t + 5);
380 sha2_round!(c, d, e, f, g, h, a, b, K32, t + 6);
381 sha2_round!(b, c, d, e, f, g, h, a, K32, t + 7);
384 for t in (48..64).step_by(8) {
385 sha2_round!(a, b, c, d, e, f, g, h, K32, t);
386 sha2_round!(h, a, b, c, d, e, f, g, K32, t + 1);
387 sha2_round!(g, h, a, b, c, d, e, f, K32, t + 2);
388 sha2_round!(f, g, h, a, b, c, d, e, K32, t + 3);
389 sha2_round!(e, f, g, h, a, b, c, d, K32, t + 4);
390 sha2_round!(d, e, f, g, h, a, b, c, K32, t + 5);
391 sha2_round!(c, d, e, f, g, h, a, b, K32, t + 6);
392 sha2_round!(b, c, d, e, f, g, h, a, K32, t + 7);
395 self.h0 = self.h0.wrapping_add(a);
396 self.h1 = self.h1.wrapping_add(b);
397 self.h2 = self.h2.wrapping_add(c);
398 self.h3 = self.h3.wrapping_add(d);
399 self.h4 = self.h4.wrapping_add(e);
400 self.h5 = self.h5.wrapping_add(f);
401 self.h6 = self.h6.wrapping_add(g);
402 self.h7 = self.h7.wrapping_add(h);
406 static K32: [u32; 64] = [
407 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
408 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
409 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
410 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
411 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
412 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
413 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
414 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
415 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
416 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
417 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
418 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
419 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
420 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
421 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
422 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
425 // A structure that keeps track of the state of the Sha-256 operation and contains the logic
426 // necessary to perform the final calculations.
429 buffer: FixedBuffer64,
430 state: Engine256State,
435 fn new(h: &[u32; 8]) -> Engine256 {
438 buffer: FixedBuffer64::new(),
439 state: Engine256State::new(h),
444 fn reset(&mut self, h: &[u32; 8]) {
445 self.length_bits = 0;
448 self.finished = false;
451 fn input(&mut self, input: &[u8]) {
452 assert!(!self.finished);
453 // Assumes that input.len() can be converted to u64 without overflow
454 self.length_bits = add_bytes_to_bits(self.length_bits, input.len() as u64);
455 let self_state = &mut self.state;
456 self.buffer.input(input, |input: &[u8]| { self_state.process_block(input) });
459 fn finish(&mut self) {
464 let self_state = &mut self.state;
465 self.buffer.standard_padding(8, |input: &[u8]| { self_state.process_block(input) });
466 write_u32_be(self.buffer.next(4), (self.length_bits >> 32) as u32 );
467 write_u32_be(self.buffer.next(4), self.length_bits as u32);
468 self_state.process_block(self.buffer.full_buffer());
470 self.finished = true;
474 /// The SHA-256 hash algorithm
480 /// Construct a new instance of a SHA-256 digest.
481 /// Do not – under any circumstances – use this where timing attacks might be possible!
482 pub fn new() -> Sha256 {
484 engine: Engine256::new(&H256)
489 impl Digest for Sha256 {
490 fn input(&mut self, d: &[u8]) {
491 self.engine.input(d);
494 fn result(&mut self, out: &mut [u8]) {
495 self.engine.finish();
497 write_u32_be(&mut out[0..4], self.engine.state.h0);
498 write_u32_be(&mut out[4..8], self.engine.state.h1);
499 write_u32_be(&mut out[8..12], self.engine.state.h2);
500 write_u32_be(&mut out[12..16], self.engine.state.h3);
501 write_u32_be(&mut out[16..20], self.engine.state.h4);
502 write_u32_be(&mut out[20..24], self.engine.state.h5);
503 write_u32_be(&mut out[24..28], self.engine.state.h6);
504 write_u32_be(&mut out[28..32], self.engine.state.h7);
507 fn reset(&mut self) {
508 self.engine.reset(&H256);
511 fn output_bits(&self) -> usize { 256 }
514 static H256: [u32; 8] = [
527 #![allow(deprecated)]
531 use self::rand::isaac::IsaacRng;
532 use serialize::hex::FromHex;
534 use super::{Digest, Sha256, FixedBuffer};
536 // A normal addition - no overflow occurs
538 fn test_add_bytes_to_bits_ok() {
539 assert!(super::add_bytes_to_bits(100, 10) == 180);
542 // A simple failure case - adding 1 to the max value
545 fn test_add_bytes_to_bits_overflow() {
546 super::add_bytes_to_bits(u64::MAX, 1);
554 fn test_hash<D: Digest>(sh: &mut D, tests: &[Test]) {
555 // Test that it works when accepting the message all at once
558 sh.input_str(&t.input);
559 let out_str = sh.result_str();
560 assert!(out_str == t.output_str);
563 // Test that it works when accepting the message in pieces
566 let len = t.input.len();
569 let take = (left + 1) / 2;
570 sh.input_str(&t.input[len - left..take + len - left]);
573 let out_str = sh.result_str();
574 assert!(out_str == t.output_str);
580 // Examples from wikipedia
581 let wikipedia_tests = vec!(
583 input: "".to_string(),
584 output_str: "e3b0c44298fc1c149afb\
585 f4c8996fb92427ae41e4649b934ca495991b7852b855".to_string()
588 input: "The quick brown fox jumps over the lazy \
590 output_str: "d7a8fbb307d7809469ca\
591 9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592".to_string()
594 input: "The quick brown fox jumps over the lazy \
596 output_str: "ef537f25c895bfa78252\
597 6529a9b63d97aa631564d5d789c2b765448c8635fb6c".to_string()
600 let tests = wikipedia_tests;
602 let mut sh: Box<_> = box Sha256::new();
604 test_hash(&mut *sh, &tests);
607 /// Feed 1,000,000 'a's into the digest with varying input sizes and check that the result is
609 fn test_digest_1million_random<D: Digest>(digest: &mut D, blocksize: usize, expected: &str) {
610 let total_size = 1000000;
611 let buffer = vec![b'a'; blocksize * 2];
612 let mut rng = IsaacRng::new_unseeded();
617 while count < total_size {
618 let next: usize = rng.gen_range(0, 2 * blocksize + 1);
619 let remaining = total_size - count;
620 let size = if next > remaining { remaining } else { next };
621 digest.input(&buffer[..size]);
625 let result_str = digest.result_str();
626 let result_bytes = digest.result_bytes();
628 assert_eq!(expected, result_str);
630 let expected_vec: Vec<u8> = expected.from_hex()
634 assert_eq!(expected_vec, result_bytes);
638 fn test_1million_random_sha256() {
639 let mut sh = Sha256::new();
640 test_digest_1million_random(
643 "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0");
650 use self::test::Bencher;
651 use super::{Sha256, FixedBuffer, Digest};
654 pub fn sha256_10(b: &mut Bencher) {
655 let mut sh = Sha256::new();
660 b.bytes = bytes.len() as u64;
664 pub fn sha256_1k(b: &mut Bencher) {
665 let mut sh = Sha256::new();
666 let bytes = [1; 1024];
670 b.bytes = bytes.len() as u64;
674 pub fn sha256_64k(b: &mut Bencher) {
675 let mut sh = Sha256::new();
676 let bytes = [1; 65536];
680 b.bytes = bytes.len() as u64;