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 #![allow(deprecated)] // to_be32
17 use std
::iter
::{range_step, repeat}
;
19 use std
::slice
::bytes
::{MutableByteVector, copy_memory}
;
20 use serialize
::hex
::ToHex
;
22 /// Write a u32 into a vector, which must be 4 bytes long. The value is written in big-endian
24 fn write_u32_be(dst
: &mut[u8], input
: u32) {
25 dst
[0] = (input
>> 24) as u8;
26 dst
[1] = (input
>> 16) as u8;
27 dst
[2] = (input
>> 8) as u8;
31 /// Read the value of a vector of bytes as a u32 value in big-endian format.
32 fn read_u32_be(input
: &[u8]) -> u32 {
34 (input
[0] as u32) << 24 |
35 (input
[1] as u32) << 16 |
36 (input
[2] as u32) << 8 |
40 /// Read a vector of bytes into a vector of u32s. The values are read in big-endian format.
41 fn read_u32v_be(dst
: &mut[u32], input
: &[u8]) {
42 assert
!(dst
.len() * 4 == input
.len());
44 for chunk
in input
.chunks(4) {
45 dst
[pos
] = read_u32_be(chunk
);
51 /// Convert the value in bytes to the number of bits, a tuple where the 1st item is the
52 /// high-order value and the 2nd item is the low order value.
53 fn to_bits(self) -> (Self, Self);
57 fn to_bits(self) -> (u64, u64) {
58 return (self >> 61, self << 3);
62 /// Adds the specified number of bytes to the bit count. panic!() if this would cause numeric
64 fn add_bytes_to_bits
<T
: Int
+ ToBits
>(bits
: T
, bytes
: T
) -> T
{
65 let (new_high_bits
, new_low_bits
) = bytes
.to_bits();
67 if new_high_bits
> Int
::zero() {
68 panic
!("numeric overflow occurred.")
71 match bits
.checked_add(new_low_bits
) {
73 None
=> panic
!("numeric overflow occurred.")
77 /// A FixedBuffer, likes its name implies, is a fixed size buffer. When the buffer becomes full, it
78 /// must be processed. The input() method takes care of processing and then clearing the buffer
79 /// automatically. However, other methods do not and require the caller to process the buffer. Any
80 /// method that modifies the buffer directory or provides the caller with bytes that can be modified
81 /// results in those bytes being marked as used by the buffer.
83 /// Input a vector of bytes. If the buffer becomes full, process it with the provided
84 /// function and then clear the buffer.
85 fn input
<F
>(&mut self, input
: &[u8], func
: F
) where
91 /// Zero the buffer up until the specified index. The buffer position currently must not be
92 /// greater than that index.
93 fn zero_until(&mut self, idx
: uint
);
95 /// Get a slice of the buffer of the specified size. There must be at least that many bytes
96 /// remaining in the buffer.
97 fn next
<'s
>(&'s
mut self, len
: uint
) -> &'s
mut [u8];
99 /// Get the current buffer. The buffer must already be full. This clears the buffer as well.
100 fn full_buffer
<'s
>(&'s
mut self) -> &'s
[u8];
102 /// Get the current position of the buffer.
103 fn position(&self) -> uint
;
105 /// Get the number of bytes remaining in the buffer until it is full.
106 fn remaining(&self) -> uint
;
108 /// Get the size of the buffer
109 fn size(&self) -> uint
;
112 /// A FixedBuffer of 64 bytes useful for implementing Sha256 which has a 64 byte blocksize.
113 struct FixedBuffer64
{
119 /// Create a new FixedBuffer64
120 fn new() -> FixedBuffer64
{
121 return FixedBuffer64
{
128 impl FixedBuffer
for FixedBuffer64
{
129 fn input
<F
>(&mut self, input
: &[u8], mut func
: F
) where
134 let size
= self.size();
136 // If there is already data in the buffer, copy as much as we can into it and process
137 // the data if the buffer becomes full.
138 if self.buffer_idx
!= 0 {
139 let buffer_remaining
= size
- self.buffer_idx
;
140 if input
.len() >= buffer_remaining
{
142 &mut self.buffer
[self.buffer_idx
..size
],
143 &input
[..buffer_remaining
]);
146 i
+= buffer_remaining
;
149 &mut self.buffer
[self.buffer_idx
..self.buffer_idx
+ input
.len()],
151 self.buffer_idx
+= input
.len();
156 // While we have at least a full buffer size chunk's worth of data, process that data
157 // without copying it into the buffer
158 while input
.len() - i
>= size
{
159 func(&input
[i
..i
+ size
]);
163 // Copy any input data into the buffer. At this point in the method, the amount of
164 // data left in the input vector will be less than the buffer size and the buffer will
166 let input_remaining
= input
.len() - i
;
168 &mut self.buffer
[..input_remaining
],
170 self.buffer_idx
+= input_remaining
;
173 fn reset(&mut self) {
177 fn zero_until(&mut self, idx
: uint
) {
178 assert
!(idx
>= self.buffer_idx
);
179 self.buffer
[self.buffer_idx
..idx
].set_memory(0);
180 self.buffer_idx
= idx
;
183 fn next
<'s
>(&'s
mut self, len
: uint
) -> &'s
mut [u8] {
184 self.buffer_idx
+= len
;
185 return &mut self.buffer
[self.buffer_idx
- len
..self.buffer_idx
];
188 fn full_buffer
<'s
>(&'s
mut self) -> &'s
[u8] {
189 assert
!(self.buffer_idx
== 64);
191 return &self.buffer
[..64];
194 fn position(&self) -> uint { self.buffer_idx }
196 fn remaining(&self) -> uint { 64 - self.buffer_idx }
198 fn size(&self) -> uint { 64 }
201 /// The StandardPadding trait adds a method useful for Sha256 to a FixedBuffer struct.
202 trait StandardPadding
{
203 /// Add padding to the buffer. The buffer must not be full when this method is called and is
204 /// guaranteed to have exactly rem remaining bytes when it returns. If there are not at least
205 /// rem bytes available, the buffer will be zero padded, processed, cleared, and then filled
206 /// with zeros again until only rem bytes are remaining.
207 fn standard_padding
<F
>(&mut self, rem
: uint
, func
: F
) where F
: FnMut(&[u8]);
210 impl <T
: FixedBuffer
> StandardPadding
for T
{
211 fn standard_padding
<F
>(&mut self, rem
: uint
, mut func
: F
) where F
: FnMut(&[u8]) {
212 let size
= self.size();
214 self.next(1)[0] = 128;
216 if self.remaining() < rem
{
217 self.zero_until(size
);
218 func(self.full_buffer());
221 self.zero_until(size
- rem
);
225 /// The Digest trait specifies an interface common to digest functions, such as SHA-1 and the SHA-2
226 /// family of digest functions.
228 /// Provide message data.
232 /// * input - A vector of message data
233 fn input(&mut self, input
: &[u8]);
235 /// Retrieve the digest result. This method may be called multiple times.
239 /// * out - the vector to hold the result. Must be large enough to contain output_bits().
240 fn result(&mut self, out
: &mut [u8]);
242 /// Reset the digest. This method must be called after result() and before supplying more
246 /// Get the output size in bits.
247 fn output_bits(&self) -> uint
;
249 /// Convenience function that feeds a string into a digest.
253 /// * `input` The string to feed into the digest
254 fn input_str(&mut self, input
: &str) {
255 self.input(input
.as_bytes());
258 /// Convenience function that retrieves the result of a digest as a
259 /// newly allocated vec of bytes.
260 fn result_bytes(&mut self) -> Vec
<u8> {
261 let mut buf
: Vec
<u8> = repeat(0u8).take((self.output_bits()+7)/8).collect();
262 self.result(&mut buf
);
266 /// Convenience function that retrieves the result of a digest as a
267 /// String in hexadecimal format.
268 fn result_str(&mut self) -> String
{
269 self.result_bytes().to_hex().to_string()
273 // A structure that represents that state of a digest computation for the SHA-2 512 family of digest
275 struct Engine256State
{
286 impl Engine256State
{
287 fn new(h
: &[u32; 8]) -> Engine256State
{
288 return Engine256State
{
300 fn reset(&mut self, h
: &[u32; 8]) {
311 fn process_block(&mut self, data
: &[u8]) {
312 fn ch(x
: u32, y
: u32, z
: u32) -> u32 {
313 ((x
& y
) ^
((!x
) & z
))
316 fn maj(x
: u32, y
: u32, z
: u32) -> u32 {
317 ((x
& y
) ^
(x
& z
) ^
(y
& z
))
320 fn sum0(x
: u32) -> u32 {
321 ((x
>> 2) | (x
<< 30)) ^
((x
>> 13) | (x
<< 19)) ^
((x
>> 22) | (x
<< 10))
324 fn sum1(x
: u32) -> u32 {
325 ((x
>> 6) | (x
<< 26)) ^
((x
>> 11) | (x
<< 21)) ^
((x
>> 25) | (x
<< 7))
328 fn sigma0(x
: u32) -> u32 {
329 ((x
>> 7) | (x
<< 25)) ^
((x
>> 18) | (x
<< 14)) ^
(x
>> 3)
332 fn sigma1(x
: u32) -> u32 {
333 ((x
>> 17) | (x
<< 15)) ^
((x
>> 19) | (x
<< 13)) ^
(x
>> 10)
345 let mut w
= [0u32; 64];
347 // Sha-512 and Sha-256 use basically the same calculations which are implemented
348 // by these macros. Inlining the calculations seems to result in better generated code.
349 macro_rules
! schedule_round
{ ($t
:expr
) => (
350 w
[$t
] = sigma1(w
[$t
- 2]) + w
[$t
- 7] + sigma0(w
[$t
- 15]) + w
[$t
- 16];
354 macro_rules
! sha2_round
{
355 ($A
:ident
, $B
:ident
, $C
:ident
, $D
:ident
,
356 $E
:ident
, $F
:ident
, $G
:ident
, $H
:ident
, $K
:ident
, $t
:expr
) => (
358 $H
+= sum1($E
) + ch($E
, $F
, $G
) + $K
[$t
] + w
[$t
];
360 $H
+= sum0($A
) + maj($A
, $B
, $C
);
365 read_u32v_be(&mut w
[0..16], data
);
367 // Putting the message schedule inside the same loop as the round calculations allows for
368 // the compiler to generate better code.
369 for t
in range_step(0, 48, 8) {
370 schedule_round
!(t
+ 16);
371 schedule_round
!(t
+ 17);
372 schedule_round
!(t
+ 18);
373 schedule_round
!(t
+ 19);
374 schedule_round
!(t
+ 20);
375 schedule_round
!(t
+ 21);
376 schedule_round
!(t
+ 22);
377 schedule_round
!(t
+ 23);
379 sha2_round
!(a
, b
, c
, d
, e
, f
, g
, h
, K32
, t
);
380 sha2_round
!(h
, a
, b
, c
, d
, e
, f
, g
, K32
, t
+ 1);
381 sha2_round
!(g
, h
, a
, b
, c
, d
, e
, f
, K32
, t
+ 2);
382 sha2_round
!(f
, g
, h
, a
, b
, c
, d
, e
, K32
, t
+ 3);
383 sha2_round
!(e
, f
, g
, h
, a
, b
, c
, d
, K32
, t
+ 4);
384 sha2_round
!(d
, e
, f
, g
, h
, a
, b
, c
, K32
, t
+ 5);
385 sha2_round
!(c
, d
, e
, f
, g
, h
, a
, b
, K32
, t
+ 6);
386 sha2_round
!(b
, c
, d
, e
, f
, g
, h
, a
, K32
, t
+ 7);
389 for t
in range_step(48, 64, 8) {
390 sha2_round
!(a
, b
, c
, d
, e
, f
, g
, h
, K32
, t
);
391 sha2_round
!(h
, a
, b
, c
, d
, e
, f
, g
, K32
, t
+ 1);
392 sha2_round
!(g
, h
, a
, b
, c
, d
, e
, f
, K32
, t
+ 2);
393 sha2_round
!(f
, g
, h
, a
, b
, c
, d
, e
, K32
, t
+ 3);
394 sha2_round
!(e
, f
, g
, h
, a
, b
, c
, d
, K32
, t
+ 4);
395 sha2_round
!(d
, e
, f
, g
, h
, a
, b
, c
, K32
, t
+ 5);
396 sha2_round
!(c
, d
, e
, f
, g
, h
, a
, b
, K32
, t
+ 6);
397 sha2_round
!(b
, c
, d
, e
, f
, g
, h
, a
, K32
, t
+ 7);
411 static K32
: [u32; 64] = [
412 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
413 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
414 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
415 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
416 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
417 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
418 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
419 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
420 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
421 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
422 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
423 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
424 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
425 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
426 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
427 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
430 // A structure that keeps track of the state of the Sha-256 operation and contains the logic
431 // necessary to perform the final calculations.
434 buffer
: FixedBuffer64
,
435 state
: Engine256State
,
440 fn new(h
: &[u32; 8]) -> Engine256
{
443 buffer
: FixedBuffer64
::new(),
444 state
: Engine256State
::new(h
),
449 fn reset(&mut self, h
: &[u32; 8]) {
450 self.length_bits
= 0;
453 self.finished
= false;
456 fn input(&mut self, input
: &[u8]) {
457 assert
!(!self.finished
);
458 // Assumes that input.len() can be converted to u64 without overflow
459 self.length_bits
= add_bytes_to_bits(self.length_bits
, input
.len() as u64);
460 let self_state
= &mut self.state
;
461 self.buffer
.input(input
, |input
: &[u8]| { self_state.process_block(input) }
);
464 fn finish(&mut self) {
469 let self_state
= &mut self.state
;
470 self.buffer
.standard_padding(8, |input
: &[u8]| { self_state.process_block(input) }
);
471 write_u32_be(self.buffer
.next(4), (self.length_bits
>> 32) as u32 );
472 write_u32_be(self.buffer
.next(4), self.length_bits
as u32);
473 self_state
.process_block(self.buffer
.full_buffer());
475 self.finished
= true;
479 /// The SHA-256 hash algorithm
485 /// Construct a new instance of a SHA-256 digest.
486 pub fn new() -> Sha256
{
488 engine
: Engine256
::new(&H256
)
493 impl Digest
for Sha256
{
494 fn input(&mut self, d
: &[u8]) {
495 self.engine
.input(d
);
498 fn result(&mut self, out
: &mut [u8]) {
499 self.engine
.finish();
501 write_u32_be(&mut out
[0..4], self.engine
.state
.h0
);
502 write_u32_be(&mut out
[4..8], self.engine
.state
.h1
);
503 write_u32_be(&mut out
[8..12], self.engine
.state
.h2
);
504 write_u32_be(&mut out
[12..16], self.engine
.state
.h3
);
505 write_u32_be(&mut out
[16..20], self.engine
.state
.h4
);
506 write_u32_be(&mut out
[20..24], self.engine
.state
.h5
);
507 write_u32_be(&mut out
[24..28], self.engine
.state
.h6
);
508 write_u32_be(&mut out
[28..32], self.engine
.state
.h7
);
511 fn reset(&mut self) {
512 self.engine
.reset(&H256
);
515 fn output_bits(&self) -> uint { 256 }
518 static H256
: [u32; 8] = [
531 #![allow(deprecated)]
535 use self::rand
::isaac
::IsaacRng
;
536 use serialize
::hex
::FromHex
;
537 use std
::iter
::repeat
;
539 use super::{Digest, Sha256, FixedBuffer}
;
541 // A normal addition - no overflow occurs
543 fn test_add_bytes_to_bits_ok() {
544 assert
!(super::add_bytes_to_bits
::<u64>(100, 10) == 180);
547 // A simple failure case - adding 1 to the max value
550 fn test_add_bytes_to_bits_overflow() {
551 super::add_bytes_to_bits
::<u64>(Int
::max_value(), 1);
559 fn test_hash
<D
: Digest
>(sh
: &mut D
, tests
: &[Test
]) {
560 // Test that it works when accepting the message all at once
563 sh
.input_str(&t
.input
);
564 let out_str
= sh
.result_str();
565 assert
!(out_str
== t
.output_str
);
568 // Test that it works when accepting the message in pieces
571 let len
= t
.input
.len();
574 let take
= (left
+ 1) / 2;
575 sh
.input_str(&t
.input
[len
- left
..take
+ len
- left
]);
578 let out_str
= sh
.result_str();
579 assert
!(out_str
== t
.output_str
);
585 // Examples from wikipedia
586 let wikipedia_tests
= vec
!(
588 input
: "".to_string(),
589 output_str
: "e3b0c44298fc1c149afb\
590 f4c8996fb92427ae41e4649b934ca495991b7852b855".to_string()
593 input
: "The quick brown fox jumps over the lazy \
595 output_str
: "d7a8fbb307d7809469ca\
596 9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592".to_string()
599 input
: "The quick brown fox jumps over the lazy \
601 output_str
: "ef537f25c895bfa78252\
602 6529a9b63d97aa631564d5d789c2b765448c8635fb6c".to_string()
605 let tests
= wikipedia_tests
;
607 let mut sh
= box Sha256
::new();
609 test_hash(&mut *sh
, &tests
);
612 /// Feed 1,000,000 'a's into the digest with varying input sizes and check that the result is
614 fn test_digest_1million_random
<D
: Digest
>(digest
: &mut D
, blocksize
: uint
, expected
: &str) {
615 let total_size
= 1000000;
616 let buffer
: Vec
<u8> = repeat('a'
as u8).take(blocksize
* 2).collect();
617 let mut rng
= IsaacRng
::new_unseeded();
622 while count
< total_size
{
623 let next
: uint
= rng
.gen_range(0, 2 * blocksize
+ 1);
624 let remaining
= total_size
- count
;
625 let size
= if next
> remaining { remaining }
else { next }
;
626 digest
.input(&buffer
[..size
]);
630 let result_str
= digest
.result_str();
631 let result_bytes
= digest
.result_bytes();
633 assert_eq
!(expected
, result_str
);
635 let expected_vec
: Vec
<u8> = expected
.from_hex()
639 assert_eq
!(expected_vec
, result_bytes
);
643 fn test_1million_random_sha256() {
644 let mut sh
= Sha256
::new();
645 test_digest_1million_random(
648 "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0");
655 use self::test
::Bencher
;
656 use super::{Sha256, FixedBuffer, Digest}
;
659 pub fn sha256_10(b
: &mut Bencher
) {
660 let mut sh
= Sha256
::new();
661 let bytes
= [1u8; 10];
665 b
.bytes
= bytes
.len() as u64;
669 pub fn sha256_1k(b
: &mut Bencher
) {
670 let mut sh
= Sha256
::new();
671 let bytes
= [1u8; 1024];
675 b
.bytes
= bytes
.len() as u64;
679 pub fn sha256_64k(b
: &mut Bencher
) {
680 let mut sh
= Sha256
::new();
681 let bytes
= [1u8; 65536];
685 b
.bytes
= bytes
.len() as u64;