src/librustc_data_structures/blake2b.rs

   1 // Copyright 2016 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
  12 // An implementation of the Blake2b cryptographic hash function.
  13 // The implementation closely follows: https://tools.ietf.org/html/rfc7693
  14 //
  15 // "BLAKE2 is a cryptographic hash function faster than MD5, SHA-1, SHA-2, and
  16 //  SHA-3, yet is at least as secure as the latest standard SHA-3."
  17 // according to their own website :)
  18 //
  19 // Indeed this implementation is two to three times as fast as our SHA-256
  20 // implementation. If you have the luxury of being able to use crates from
  21 // crates.io, you can go there and find still faster implementations.
  22
  23 use std::mem;
  24 use std::slice;
  25
  26 pub struct Blake2bCtx {
  27     b: [u8; 128],
  28     h: [u64; 8],
  29     t: [u64; 2],
  30     c: usize,
  31     outlen: u16,
  32     finalized: bool
  33 }
  34
  35 impl ::std::fmt::Debug for Blake2bCtx {
  36     fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
  37         try!(write!(fmt, "hash: "));
  38         for v in &self.h[..] {
  39             try!(write!(fmt, "{:x}", v));
  40         }
  41         Ok(())
  42     }
  43 }
  44
  45 #[inline(always)]
  46 fn b2b_g(v: &mut [u64; 16],
  47          a: usize,
  48          b: usize,
  49          c: usize,
  50          d: usize,
  51          x: u64,
  52          y: u64)
  53 {
  54     v[a] = v[a].wrapping_add(v[b]).wrapping_add(x);
  55     v[d] = (v[d] ^ v[a]).rotate_right(32);
  56     v[c] = v[c].wrapping_add(v[d]);
  57     v[b] = (v[b] ^ v[c]).rotate_right(24);
  58     v[a] = v[a].wrapping_add(v[b]).wrapping_add(y);
  59     v[d] = (v[d] ^ v[a]).rotate_right(16);
  60     v[c] = v[c].wrapping_add(v[d]);
  61     v[b] = (v[b] ^ v[c]).rotate_right(63);
  62 }
  63
  64 // Initialization vector
  65 const BLAKE2B_IV: [u64; 8] = [
  66    0x6A09E667F3BCC908, 0xBB67AE8584CAA73B,
  67    0x3C6EF372FE94F82B, 0xA54FF53A5F1D36F1,
  68    0x510E527FADE682D1, 0x9B05688C2B3E6C1F,
  69    0x1F83D9ABFB41BD6B, 0x5BE0CD19137E2179
  70 ];
  71
  72 fn blake2b_compress(ctx: &mut Blake2bCtx, last: bool) {
  73
  74     const SIGMA: [[usize; 16]; 12] = [
  75         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
  76         [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 ],
  77         [11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 ],
  78         [7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 ],
  79         [9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 ],
  80         [2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 ],
  81         [12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 ],
  82         [13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 ],
  83         [6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 ],
  84         [10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0 ],
  85         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
  86         [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 ]
  87     ];
  88
  89     let mut v: [u64; 16] = [
  90         ctx.h[0],
  91         ctx.h[1],
  92         ctx.h[2],
  93         ctx.h[3],
  94         ctx.h[4],
  95         ctx.h[5],
  96         ctx.h[6],
  97         ctx.h[7],
  98
  99         BLAKE2B_IV[0],
 100         BLAKE2B_IV[1],
 101         BLAKE2B_IV[2],
 102         BLAKE2B_IV[3],
 103         BLAKE2B_IV[4],
 104         BLAKE2B_IV[5],
 105         BLAKE2B_IV[6],
 106         BLAKE2B_IV[7],
 107     ];
 108
 109     v[12] ^= ctx.t[0]; // low 64 bits of offset
 110     v[13] ^= ctx.t[1]; // high 64 bits
 111     if last {
 112         v[14] = !v[14];
 113     }
 114
 115     {
 116         // Re-interpret the input buffer in the state as u64s
 117         let m: &mut [u64; 16] = unsafe {
 118             let b: &mut [u8; 128] = &mut ctx.b;
 119             ::std::mem::transmute(b)
 120         };
 121
 122         // It's OK to modify the buffer in place since this is the last time
 123         // this data will be accessed before it's overwritten
 124         if cfg!(target_endian = "big") {
 125             for word in &mut m[..] {
 126                 *word = word.to_be();
 127             }
 128         }
 129
 130         for i in 0 .. 12 {
 131             b2b_g(&mut v, 0, 4,  8, 12, m[SIGMA[i][ 0]], m[SIGMA[i][ 1]]);
 132             b2b_g(&mut v, 1, 5,  9, 13, m[SIGMA[i][ 2]], m[SIGMA[i][ 3]]);
 133             b2b_g(&mut v, 2, 6, 10, 14, m[SIGMA[i][ 4]], m[SIGMA[i][ 5]]);
 134             b2b_g(&mut v, 3, 7, 11, 15, m[SIGMA[i][ 6]], m[SIGMA[i][ 7]]);
 135             b2b_g(&mut v, 0, 5, 10, 15, m[SIGMA[i][ 8]], m[SIGMA[i][ 9]]);
 136             b2b_g(&mut v, 1, 6, 11, 12, m[SIGMA[i][10]], m[SIGMA[i][11]]);
 137             b2b_g(&mut v, 2, 7,  8, 13, m[SIGMA[i][12]], m[SIGMA[i][13]]);
 138             b2b_g(&mut v, 3, 4,  9, 14, m[SIGMA[i][14]], m[SIGMA[i][15]]);
 139         }
 140     }
 141
 142     for i in 0 .. 8 {
 143         ctx.h[i] ^= v[i] ^ v[i + 8];
 144     }
 145 }
 146
 147 fn blake2b_new(outlen: usize, key: &[u8]) -> Blake2bCtx {
 148     assert!(outlen > 0 && outlen <= 64 && key.len() <= 64);
 149
 150     let mut ctx = Blake2bCtx {
 151         b: [0; 128],
 152         h: BLAKE2B_IV,
 153         t: [0; 2],
 154         c: 0,
 155         outlen: outlen as u16,
 156         finalized: false,
 157     };
 158
 159     ctx.h[0] ^= 0x01010000 ^ ((key.len() << 8) as u64) ^ (outlen as u64);
 160
 161     if key.len() > 0 {
 162        blake2b_update(&mut ctx, key);
 163        ctx.c = ctx.b.len();
 164     }
 165
 166     ctx
 167 }
 168
 169 fn blake2b_update(ctx: &mut Blake2bCtx, mut data: &[u8]) {
 170     assert!(!ctx.finalized, "Blake2bCtx already finalized");
 171
 172     let mut bytes_to_copy = data.len();
 173     let mut space_in_buffer = ctx.b.len() - ctx.c;
 174
 175     while bytes_to_copy > space_in_buffer {
 176         checked_mem_copy(data, &mut ctx.b[ctx.c .. ], space_in_buffer);
 177
 178         ctx.t[0] = ctx.t[0].wrapping_add(ctx.b.len() as u64);
 179         if ctx.t[0] < (ctx.b.len() as u64) {
 180             ctx.t[1] += 1;
 181         }
 182         blake2b_compress(ctx, false);
 183         ctx.c = 0;
 184
 185         data = &data[space_in_buffer .. ];
 186         bytes_to_copy -= space_in_buffer;
 187         space_in_buffer = ctx.b.len();
 188     }
 189
 190     if bytes_to_copy > 0 {
 191         checked_mem_copy(data, &mut ctx.b[ctx.c .. ], bytes_to_copy);
 192         ctx.c += bytes_to_copy;
 193     }
 194 }
 195
 196 fn blake2b_final(ctx: &mut Blake2bCtx)
 197 {
 198     assert!(!ctx.finalized, "Blake2bCtx already finalized");
 199
 200     ctx.t[0] = ctx.t[0].wrapping_add(ctx.c as u64);
 201     if ctx.t[0] < ctx.c as u64 {
 202         ctx.t[1] += 1;
 203     }
 204
 205     while ctx.c < 128 {
 206         ctx.b[ctx.c] = 0;
 207         ctx.c += 1;
 208     }
 209
 210     blake2b_compress(ctx, true);
 211
 212     if cfg!(target_endian = "big") {
 213         // Make sure that the data is in memory in little endian format, as is
 214         // demanded by BLAKE2
 215         for word in &mut ctx.h {
 216             *word = word.to_le();
 217         }
 218     }
 219
 220     ctx.finalized = true;
 221 }
 222
 223 #[inline(always)]
 224 fn checked_mem_copy<T1, T2>(from: &[T1], to: &mut [T2], byte_count: usize) {
 225     let from_size = from.len() * mem::size_of::<T1>();
 226     let to_size = to.len() * mem::size_of::<T2>();
 227     assert!(from_size >= byte_count);
 228     assert!(to_size >= byte_count);
 229     let from_byte_ptr = from.as_ptr() as * const u8;
 230     let to_byte_ptr = to.as_mut_ptr() as * mut u8;
 231     unsafe {
 232         ::std::ptr::copy_nonoverlapping(from_byte_ptr, to_byte_ptr, byte_count);
 233     }
 234 }
 235
 236 pub fn blake2b(out: &mut [u8], key: &[u8],  data: &[u8])
 237 {
 238     let mut ctx = blake2b_new(out.len(), key);
 239     blake2b_update(&mut ctx, data);
 240     blake2b_final(&mut ctx);
 241     checked_mem_copy(&ctx.h, out, ctx.outlen as usize);
 242 }
 243
 244 pub struct Blake2bHasher(Blake2bCtx);
 245
 246 impl ::std::hash::Hasher for Blake2bHasher {
 247     fn write(&mut self, bytes: &[u8]) {
 248         blake2b_update(&mut self.0, bytes);
 249     }
 250
 251     fn finish(&self) -> u64 {
 252         assert!(self.0.outlen == 8,
 253                 "Hasher initialized with incompatible output length");
 254         u64::from_le(self.0.h[0])
 255     }
 256 }
 257
 258 impl Blake2bHasher {
 259     pub fn new(outlen: usize, key: &[u8]) -> Blake2bHasher {
 260         Blake2bHasher(blake2b_new(outlen, key))
 261     }
 262
 263     pub fn finalize(&mut self) -> &[u8] {
 264         if !self.0.finalized {
 265             blake2b_final(&mut self.0);
 266         }
 267         debug_assert!(mem::size_of_val(&self.0.h) >= self.0.outlen as usize);
 268         let raw_ptr = (&self.0.h[..]).as_ptr() as * const u8;
 269         unsafe {
 270             slice::from_raw_parts(raw_ptr, self.0.outlen as usize)
 271         }
 272     }
 273 }
 274
 275 impl ::std::fmt::Debug for Blake2bHasher {
 276     fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
 277         write!(fmt, "{:?}", self.0)
 278     }
 279 }
 280
 281 #[cfg(test)]
 282 fn selftest_seq(out: &mut [u8], seed: u32)
 283 {
 284    let mut a: u32 = 0xDEAD4BADu32.wrapping_mul(seed);
 285    let mut b: u32 = 1;
 286
 287    for i in 0 .. out.len() {
 288        let t: u32 = a.wrapping_add(b);
 289        a = b;
 290        b = t;
 291        out[i] = ((t >> 24) & 0xFF) as u8;
 292    }
 293 }
 294
 295 #[test]
 296 fn blake2b_selftest()
 297 {
 298     use std::hash::Hasher;
 299
 300     // grand hash of hash results
 301     const BLAKE2B_RES: [u8; 32] = [
 302         0xC2, 0x3A, 0x78, 0x00, 0xD9, 0x81, 0x23, 0xBD,
 303         0x10, 0xF5, 0x06, 0xC6, 0x1E, 0x29, 0xDA, 0x56,
 304         0x03, 0xD7, 0x63, 0xB8, 0xBB, 0xAD, 0x2E, 0x73,
 305         0x7F, 0x5E, 0x76, 0x5A, 0x7B, 0xCC, 0xD4, 0x75
 306     ];
 307
 308     // parameter sets
 309     const B2B_MD_LEN: [usize; 4] = [20, 32, 48, 64];
 310     const B2B_IN_LEN: [usize; 6] = [0, 3, 128, 129, 255, 1024];
 311
 312     let mut data = [0u8; 1024];
 313     let mut md = [0u8; 64];
 314     let mut key = [0u8; 64];
 315
 316     let mut hasher = Blake2bHasher::new(32, &[]);
 317
 318     for i in 0 .. 4 {
 319        let outlen = B2B_MD_LEN[i];
 320        for j in 0 .. 6 {
 321             let inlen = B2B_IN_LEN[j];
 322
 323             selftest_seq(&mut data[.. inlen], inlen as u32); // unkeyed hash
 324             blake2b(&mut md[.. outlen], &[], &data[.. inlen]);
 325             hasher.write(&md[.. outlen]); // hash the hash
 326
 327             selftest_seq(&mut key[0 .. outlen], outlen as u32); // keyed hash
 328             blake2b(&mut md[.. outlen], &key[.. outlen], &data[.. inlen]);
 329             hasher.write(&md[.. outlen]); // hash the hash
 330        }
 331     }
 332
 333     // compute and compare the hash of hashes
 334     let md = hasher.finalize();
 335     for i in 0 .. 32 {
 336         assert_eq!(md[i], BLAKE2B_RES[i]);
 337     }
 338 }