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