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 an array
 117         // of little-endian u64s, converting them to machine
 118         // endianness. It's OK to modify the buffer in place
 119         // since this is the last time  this data will be accessed
 120         // before it's overwritten.
 121
 122         let m: &mut [u64; 16] = unsafe {
 123             let b: &mut [u8; 128] = &mut ctx.b;
 124             ::std::mem::transmute(b)
 125         };
 126
 127         if cfg!(target_endian = "big") {
 128             for word in &mut m[..] {
 129                 *word = u64::from_le(*word);
 130             }
 131         }
 132
 133         for i in 0 .. 12 {
 134             b2b_g(&mut v, 0, 4,  8, 12, m[SIGMA[i][ 0]], m[SIGMA[i][ 1]]);
 135             b2b_g(&mut v, 1, 5,  9, 13, m[SIGMA[i][ 2]], m[SIGMA[i][ 3]]);
 136             b2b_g(&mut v, 2, 6, 10, 14, m[SIGMA[i][ 4]], m[SIGMA[i][ 5]]);
 137             b2b_g(&mut v, 3, 7, 11, 15, m[SIGMA[i][ 6]], m[SIGMA[i][ 7]]);
 138             b2b_g(&mut v, 0, 5, 10, 15, m[SIGMA[i][ 8]], m[SIGMA[i][ 9]]);
 139             b2b_g(&mut v, 1, 6, 11, 12, m[SIGMA[i][10]], m[SIGMA[i][11]]);
 140             b2b_g(&mut v, 2, 7,  8, 13, m[SIGMA[i][12]], m[SIGMA[i][13]]);
 141             b2b_g(&mut v, 3, 4,  9, 14, m[SIGMA[i][14]], m[SIGMA[i][15]]);
 142         }
 143     }
 144
 145     for i in 0 .. 8 {
 146         ctx.h[i] ^= v[i] ^ v[i + 8];
 147     }
 148 }
 149
 150 fn blake2b_new(outlen: usize, key: &[u8]) -> Blake2bCtx {
 151     assert!(outlen > 0 && outlen <= 64 && key.len() <= 64);
 152
 153     let mut ctx = Blake2bCtx {
 154         b: [0; 128],
 155         h: BLAKE2B_IV,
 156         t: [0; 2],
 157         c: 0,
 158         outlen: outlen as u16,
 159         finalized: false,
 160     };
 161
 162     ctx.h[0] ^= 0x01010000 ^ ((key.len() << 8) as u64) ^ (outlen as u64);
 163
 164     if key.len() > 0 {
 165        blake2b_update(&mut ctx, key);
 166        ctx.c = ctx.b.len();
 167     }
 168
 169     ctx
 170 }
 171
 172 fn blake2b_update(ctx: &mut Blake2bCtx, mut data: &[u8]) {
 173     assert!(!ctx.finalized, "Blake2bCtx already finalized");
 174
 175     let mut bytes_to_copy = data.len();
 176     let mut space_in_buffer = ctx.b.len() - ctx.c;
 177
 178     while bytes_to_copy > space_in_buffer {
 179         checked_mem_copy(data, &mut ctx.b[ctx.c .. ], space_in_buffer);
 180
 181         ctx.t[0] = ctx.t[0].wrapping_add(ctx.b.len() as u64);
 182         if ctx.t[0] < (ctx.b.len() as u64) {
 183             ctx.t[1] += 1;
 184         }
 185         blake2b_compress(ctx, false);
 186         ctx.c = 0;
 187
 188         data = &data[space_in_buffer .. ];
 189         bytes_to_copy -= space_in_buffer;
 190         space_in_buffer = ctx.b.len();
 191     }
 192
 193     if bytes_to_copy > 0 {
 194         checked_mem_copy(data, &mut ctx.b[ctx.c .. ], bytes_to_copy);
 195         ctx.c += bytes_to_copy;
 196     }
 197 }
 198
 199 fn blake2b_final(ctx: &mut Blake2bCtx)
 200 {
 201     assert!(!ctx.finalized, "Blake2bCtx already finalized");
 202
 203     ctx.t[0] = ctx.t[0].wrapping_add(ctx.c as u64);
 204     if ctx.t[0] < ctx.c as u64 {
 205         ctx.t[1] += 1;
 206     }
 207
 208     while ctx.c < 128 {
 209         ctx.b[ctx.c] = 0;
 210         ctx.c += 1;
 211     }
 212
 213     blake2b_compress(ctx, true);
 214
 215     // Modify our buffer to little-endian format as it will be read
 216     // as a byte array. It's OK to modify the buffer in place since
 217     // this is the last time this data will be accessed.
 218     if cfg!(target_endian = "big") {
 219         for word in &mut ctx.h {
 220             *word = word.to_le();
 221         }
 222     }
 223
 224     ctx.finalized = true;
 225 }
 226
 227 #[inline(always)]
 228 fn checked_mem_copy<T1, T2>(from: &[T1], to: &mut [T2], byte_count: usize) {
 229     let from_size = from.len() * mem::size_of::<T1>();
 230     let to_size = to.len() * mem::size_of::<T2>();
 231     assert!(from_size >= byte_count);
 232     assert!(to_size >= byte_count);
 233     let from_byte_ptr = from.as_ptr() as * const u8;
 234     let to_byte_ptr = to.as_mut_ptr() as * mut u8;
 235     unsafe {
 236         ::std::ptr::copy_nonoverlapping(from_byte_ptr, to_byte_ptr, byte_count);
 237     }
 238 }
 239
 240 pub fn blake2b(out: &mut [u8], key: &[u8],  data: &[u8])
 241 {
 242     let mut ctx = blake2b_new(out.len(), key);
 243     blake2b_update(&mut ctx, data);
 244     blake2b_final(&mut ctx);
 245     checked_mem_copy(&ctx.h, out, ctx.outlen as usize);
 246 }
 247
 248 pub struct Blake2bHasher(Blake2bCtx);
 249
 250 impl ::std::hash::Hasher for Blake2bHasher {
 251     fn write(&mut self, bytes: &[u8]) {
 252         blake2b_update(&mut self.0, bytes);
 253     }
 254
 255     fn finish(&self) -> u64 {
 256         assert!(self.0.outlen == 8,
 257                 "Hasher initialized with incompatible output length");
 258         u64::from_le(self.0.h[0])
 259     }
 260 }
 261
 262 impl Blake2bHasher {
 263     pub fn new(outlen: usize, key: &[u8]) -> Blake2bHasher {
 264         Blake2bHasher(blake2b_new(outlen, key))
 265     }
 266
 267     pub fn finalize(&mut self) -> &[u8] {
 268         if !self.0.finalized {
 269             blake2b_final(&mut self.0);
 270         }
 271         debug_assert!(mem::size_of_val(&self.0.h) >= self.0.outlen as usize);
 272         let raw_ptr = (&self.0.h[..]).as_ptr() as * const u8;
 273         unsafe {
 274             slice::from_raw_parts(raw_ptr, self.0.outlen as usize)
 275         }
 276     }
 277 }
 278
 279 impl ::std::fmt::Debug for Blake2bHasher {
 280     fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
 281         write!(fmt, "{:?}", self.0)
 282     }
 283 }
 284
 285 #[cfg(test)]
 286 fn selftest_seq(out: &mut [u8], seed: u32)
 287 {
 288    let mut a: u32 = 0xDEAD4BADu32.wrapping_mul(seed);
 289    let mut b: u32 = 1;
 290
 291    for i in 0 .. out.len() {
 292        let t: u32 = a.wrapping_add(b);
 293        a = b;
 294        b = t;
 295        out[i] = ((t >> 24) & 0xFF) as u8;
 296    }
 297 }
 298
 299 #[test]
 300 fn blake2b_selftest()
 301 {
 302     use std::hash::Hasher;
 303
 304     // grand hash of hash results
 305     const BLAKE2B_RES: [u8; 32] = [
 306         0xC2, 0x3A, 0x78, 0x00, 0xD9, 0x81, 0x23, 0xBD,
 307         0x10, 0xF5, 0x06, 0xC6, 0x1E, 0x29, 0xDA, 0x56,
 308         0x03, 0xD7, 0x63, 0xB8, 0xBB, 0xAD, 0x2E, 0x73,
 309         0x7F, 0x5E, 0x76, 0x5A, 0x7B, 0xCC, 0xD4, 0x75
 310     ];
 311
 312     // parameter sets
 313     const B2B_MD_LEN: [usize; 4] = [20, 32, 48, 64];
 314     const B2B_IN_LEN: [usize; 6] = [0, 3, 128, 129, 255, 1024];
 315
 316     let mut data = [0u8; 1024];
 317     let mut md = [0u8; 64];
 318     let mut key = [0u8; 64];
 319
 320     let mut hasher = Blake2bHasher::new(32, &[]);
 321
 322     for i in 0 .. 4 {
 323        let outlen = B2B_MD_LEN[i];
 324        for j in 0 .. 6 {
 325             let inlen = B2B_IN_LEN[j];
 326
 327             selftest_seq(&mut data[.. inlen], inlen as u32); // unkeyed hash
 328             blake2b(&mut md[.. outlen], &[], &data[.. inlen]);
 329             hasher.write(&md[.. outlen]); // hash the hash
 330
 331             selftest_seq(&mut key[0 .. outlen], outlen as u32); // keyed hash
 332             blake2b(&mut md[.. outlen], &key[.. outlen], &data[.. inlen]);
 333             hasher.write(&md[.. outlen]); // hash the hash
 334        }
 335     }
 336
 337     // compute and compare the hash of hashes
 338     let md = hasher.finalize();
 339     for i in 0 .. 32 {
 340         assert_eq!(md[i], BLAKE2B_RES[i]);
 341     }
 342 }