git.bitcoin.ninja Git - rust-lightning/blob - src/util/poly1305.rs

   1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   4 // option. This file may not be copied, modified, or distributed
   5 // except according to those terms.
   6
   7 // This is a port of Andrew Moons poly1305-donna
   8 // https://github.com/floodyberry/poly1305-donna
   9
  10 use std::cmp::min;
  11 use util::byte_utils::{slice_to_le32, le32_to_array};
  12
  13 use crypto::mac::{Mac, MacResult};
  14
  15 #[derive(Clone, Copy)]
  16 pub struct Poly1305 {
  17         r         : [u32; 5],
  18         h         : [u32; 5],
  19         pad       : [u32; 4],
  20         leftover  : usize,
  21         buffer    : [u8; 16],
  22         finalized : bool,
  23 }
  24
  25 impl Poly1305 {
  26         pub fn new(key: &[u8]) -> Poly1305 {
  27                 assert!(key.len() == 32);
  28                 let mut poly = Poly1305{ r: [0u32; 5], h: [0u32; 5], pad: [0u32; 4], leftover: 0, buffer: [0u8; 16], finalized: false };
  29
  30                 // r &= 0xffffffc0ffffffc0ffffffc0fffffff
  31                 poly.r[0] = (slice_to_le32(&key[0..4])       ) & 0x3ffffff;
  32                 poly.r[1] = (slice_to_le32(&key[3..7])   >> 2) & 0x3ffff03;
  33                 poly.r[2] = (slice_to_le32(&key[6..10])  >> 4) & 0x3ffc0ff;
  34                 poly.r[3] = (slice_to_le32(&key[9..13])  >> 6) & 0x3f03fff;
  35                 poly.r[4] = (slice_to_le32(&key[12..16]) >> 8) & 0x00fffff;
  36
  37                 poly.pad[0] = slice_to_le32(&key[16..20]);
  38                 poly.pad[1] = slice_to_le32(&key[20..24]);
  39                 poly.pad[2] = slice_to_le32(&key[24..28]);
  40                 poly.pad[3] = slice_to_le32(&key[28..32]);
  41
  42                 poly
  43         }
  44
  45         fn block(&mut self, m: &[u8]) {
  46                 let hibit : u32 = if self.finalized { 0 } else { 1 << 24 };
  47
  48                 let r0 = self.r[0];
  49                 let r1 = self.r[1];
  50                 let r2 = self.r[2];
  51                 let r3 = self.r[3];
  52                 let r4 = self.r[4];
  53
  54                 let s1 = r1 * 5;
  55                 let s2 = r2 * 5;
  56                 let s3 = r3 * 5;
  57                 let s4 = r4 * 5;
  58
  59                 let mut h0 = self.h[0];
  60                 let mut h1 = self.h[1];
  61                 let mut h2 = self.h[2];
  62                 let mut h3 = self.h[3];
  63                 let mut h4 = self.h[4];
  64
  65                 // h += m
  66                 h0 += (slice_to_le32(&m[0..4])       ) & 0x3ffffff;
  67                 h1 += (slice_to_le32(&m[3..7])   >> 2) & 0x3ffffff;
  68                 h2 += (slice_to_le32(&m[6..10])  >> 4) & 0x3ffffff;
  69                 h3 += (slice_to_le32(&m[9..13])  >> 6) & 0x3ffffff;
  70                 h4 += (slice_to_le32(&m[12..16]) >> 8) | hibit;
  71
  72                 // h *= r
  73                 let     d0 = (h0 as u64 * r0 as u64) + (h1 as u64 * s4 as u64) + (h2 as u64 * s3 as u64) + (h3 as u64 * s2 as u64) + (h4 as u64 * s1 as u64);
  74                 let mut d1 = (h0 as u64 * r1 as u64) + (h1 as u64 * r0 as u64) + (h2 as u64 * s4 as u64) + (h3 as u64 * s3 as u64) + (h4 as u64 * s2 as u64);
  75                 let mut d2 = (h0 as u64 * r2 as u64) + (h1 as u64 * r1 as u64) + (h2 as u64 * r0 as u64) + (h3 as u64 * s4 as u64) + (h4 as u64 * s3 as u64);
  76                 let mut d3 = (h0 as u64 * r3 as u64) + (h1 as u64 * r2 as u64) + (h2 as u64 * r1 as u64) + (h3 as u64 * r0 as u64) + (h4 as u64 * s4 as u64);
  77                 let mut d4 = (h0 as u64 * r4 as u64) + (h1 as u64 * r3 as u64) + (h2 as u64 * r2 as u64) + (h3 as u64 * r1 as u64) + (h4 as u64 * r0 as u64);
  78
  79                 // (partial) h %= p
  80                 let mut c : u32;
  81                                 c = (d0 >> 26) as u32; h0 = d0 as u32 & 0x3ffffff;
  82                 d1 += c as u64; c = (d1 >> 26) as u32; h1 = d1 as u32 & 0x3ffffff;
  83                 d2 += c as u64; c = (d2 >> 26) as u32; h2 = d2 as u32 & 0x3ffffff;
  84                 d3 += c as u64; c = (d3 >> 26) as u32; h3 = d3 as u32 & 0x3ffffff;
  85                 d4 += c as u64; c = (d4 >> 26) as u32; h4 = d4 as u32 & 0x3ffffff;
  86                 h0 += c * 5;    c = h0 >> 26; h0 = h0 & 0x3ffffff;
  87                 h1 += c;
  88
  89                 self.h[0] = h0;
  90                 self.h[1] = h1;
  91                 self.h[2] = h2;
  92                 self.h[3] = h3;
  93                 self.h[4] = h4;
  94         }
  95
  96         fn finish(&mut self) {
  97                 if self.leftover > 0 {
  98                         self.buffer[self.leftover] = 1;
  99                         for i in self.leftover+1..16 {
 100                                 self.buffer[i] = 0;
 101                         }
 102                         self.finalized = true;
 103                         let tmp = self.buffer;
 104                         self.block(&tmp);
 105                 }
 106
 107                 // fully carry h
 108                 let mut h0 = self.h[0];
 109                 let mut h1 = self.h[1];
 110                 let mut h2 = self.h[2];
 111                 let mut h3 = self.h[3];
 112                 let mut h4 = self.h[4];
 113
 114                 let mut c : u32;
 115                              c = h1 >> 26; h1 = h1 & 0x3ffffff;
 116                 h2 +=     c; c = h2 >> 26; h2 = h2 & 0x3ffffff;
 117                 h3 +=     c; c = h3 >> 26; h3 = h3 & 0x3ffffff;
 118                 h4 +=     c; c = h4 >> 26; h4 = h4 & 0x3ffffff;
 119                 h0 += c * 5; c = h0 >> 26; h0 = h0 & 0x3ffffff;
 120                 h1 +=     c;
 121
 122                 // compute h + -p
 123                 let mut g0 = h0.wrapping_add(5); c = g0 >> 26; g0 &= 0x3ffffff;
 124                 let mut g1 = h1.wrapping_add(c); c = g1 >> 26; g1 &= 0x3ffffff;
 125                 let mut g2 = h2.wrapping_add(c); c = g2 >> 26; g2 &= 0x3ffffff;
 126                 let mut g3 = h3.wrapping_add(c); c = g3 >> 26; g3 &= 0x3ffffff;
 127                 let mut g4 = h4.wrapping_add(c).wrapping_sub(1 << 26);
 128
 129                 // select h if h < p, or h + -p if h >= p
 130                 let mut mask = (g4 >> (32 - 1)).wrapping_sub(1);
 131                 g0 &= mask;
 132                 g1 &= mask;
 133                 g2 &= mask;
 134                 g3 &= mask;
 135                 g4 &= mask;
 136                 mask = !mask;
 137                 h0 = (h0 & mask) | g0;
 138                 h1 = (h1 & mask) | g1;
 139                 h2 = (h2 & mask) | g2;
 140                 h3 = (h3 & mask) | g3;
 141                 h4 = (h4 & mask) | g4;
 142
 143                 // h = h % (2^128)
 144                 h0 = ((h0      ) | (h1 << 26)) & 0xffffffff;
 145                 h1 = ((h1 >>  6) | (h2 << 20)) & 0xffffffff;
 146                 h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff;
 147                 h3 = ((h3 >> 18) | (h4 <<  8)) & 0xffffffff;
 148
 149                 // h = mac = (h + pad) % (2^128)
 150                 let mut f : u64;
 151                 f = h0 as u64 + self.pad[0] as u64            ; h0 = f as u32;
 152                 f = h1 as u64 + self.pad[1] as u64 + (f >> 32); h1 = f as u32;
 153                 f = h2 as u64 + self.pad[2] as u64 + (f >> 32); h2 = f as u32;
 154                 f = h3 as u64 + self.pad[3] as u64 + (f >> 32); h3 = f as u32;
 155
 156                 self.h[0] = h0;
 157                 self.h[1] = h1;
 158                 self.h[2] = h2;
 159                 self.h[3] = h3;
 160         }
 161 }
 162
 163 impl Mac for Poly1305 {
 164         fn input(&mut self, data: &[u8]) {
 165                 assert!(!self.finalized);
 166                 let mut m = data;
 167
 168                 if self.leftover > 0 {
 169                         let want = min(16 - self.leftover, m.len());
 170                         for i in 0..want {
 171                                 self.buffer[self.leftover+i] = m[i];
 172                         }
 173                         m = &m[want..];
 174                         self.leftover += want;
 175
 176                         if self.leftover < 16 {
 177                                 return;
 178                         }
 179
 180                         // self.block(self.buffer[..]);
 181                         let tmp = self.buffer;
 182                         self.block(&tmp);
 183
 184                         self.leftover = 0;
 185                 }
 186
 187                 while m.len() >= 16 {
 188                         self.block(&m[0..16]);
 189                         m = &m[16..];
 190                 }
 191
 192                 for i in 0..m.len() {
 193                         self.buffer[i] = m[i];
 194                 }
 195                 self.leftover = m.len();
 196         }
 197
 198         fn reset(&mut self) {
 199                 self.h = [0u32; 5];
 200                 self.leftover = 0;
 201                 self.finalized = false;
 202         }
 203
 204         fn result(&mut self) -> MacResult {
 205                 let mut mac = [0u8; 16];
 206                 self.raw_result(&mut mac);
 207                 MacResult::new(&mac[..])
 208         }
 209
 210         fn raw_result(&mut self, output: &mut [u8]) {
 211                 assert!(output.len() >= 16);
 212                 if !self.finalized{
 213                         self.finish();
 214                 }
 215                 output[0..4].copy_from_slice(&le32_to_array(self.h[0]));
 216                 output[4..8].copy_from_slice(&le32_to_array(self.h[1]));
 217                 output[8..12].copy_from_slice(&le32_to_array(self.h[2]));
 218                 output[12..16].copy_from_slice(&le32_to_array(self.h[3]));
 219         }
 220
 221         fn output_bytes(&self) -> usize { 16 }
 222 }
 223
 224 #[cfg(test)]
 225 mod test {
 226         use std::iter::repeat;
 227
 228         use util::poly1305::Poly1305;
 229         use crypto::mac::Mac;
 230
 231         fn poly1305(key: &[u8], msg: &[u8], mac: &mut [u8]) {
 232                 let mut poly = Poly1305::new(key);
 233                 poly.input(msg);
 234                 poly.raw_result(mac);
 235         }
 236
 237         #[test]
 238         fn test_nacl_vector() {
 239                 let key = [
 240                         0xee,0xa6,0xa7,0x25,0x1c,0x1e,0x72,0x91,
 241                         0x6d,0x11,0xc2,0xcb,0x21,0x4d,0x3c,0x25,
 242                         0x25,0x39,0x12,0x1d,0x8e,0x23,0x4e,0x65,
 243                         0x2d,0x65,0x1f,0xa4,0xc8,0xcf,0xf8,0x80,
 244                 ];
 245
 246                 let msg = [
 247                         0x8e,0x99,0x3b,0x9f,0x48,0x68,0x12,0x73,
 248                         0xc2,0x96,0x50,0xba,0x32,0xfc,0x76,0xce,
 249                         0x48,0x33,0x2e,0xa7,0x16,0x4d,0x96,0xa4,
 250                         0x47,0x6f,0xb8,0xc5,0x31,0xa1,0x18,0x6a,
 251                         0xc0,0xdf,0xc1,0x7c,0x98,0xdc,0xe8,0x7b,
 252                         0x4d,0xa7,0xf0,0x11,0xec,0x48,0xc9,0x72,
 253                         0x71,0xd2,0xc2,0x0f,0x9b,0x92,0x8f,0xe2,
 254                         0x27,0x0d,0x6f,0xb8,0x63,0xd5,0x17,0x38,
 255                         0xb4,0x8e,0xee,0xe3,0x14,0xa7,0xcc,0x8a,
 256                         0xb9,0x32,0x16,0x45,0x48,0xe5,0x26,0xae,
 257                         0x90,0x22,0x43,0x68,0x51,0x7a,0xcf,0xea,
 258                         0xbd,0x6b,0xb3,0x73,0x2b,0xc0,0xe9,0xda,
 259                         0x99,0x83,0x2b,0x61,0xca,0x01,0xb6,0xde,
 260                         0x56,0x24,0x4a,0x9e,0x88,0xd5,0xf9,0xb3,
 261                         0x79,0x73,0xf6,0x22,0xa4,0x3d,0x14,0xa6,
 262                         0x59,0x9b,0x1f,0x65,0x4c,0xb4,0x5a,0x74,
 263                         0xe3,0x55,0xa5,
 264                 ];
 265
 266                 let expected = [
 267                         0xf3,0xff,0xc7,0x70,0x3f,0x94,0x00,0xe5,
 268                         0x2a,0x7d,0xfb,0x4b,0x3d,0x33,0x05,0xd9,
 269                 ];
 270
 271                 let mut mac = [0u8; 16];
 272                 poly1305(&key, &msg, &mut mac);
 273                 assert_eq!(&mac[..], &expected[..]);
 274
 275                 let mut poly = Poly1305::new(&key);
 276                 poly.input(&msg[0..32]);
 277                 poly.input(&msg[32..96]);
 278                 poly.input(&msg[96..112]);
 279                 poly.input(&msg[112..120]);
 280                 poly.input(&msg[120..124]);
 281                 poly.input(&msg[124..126]);
 282                 poly.input(&msg[126..127]);
 283                 poly.input(&msg[127..128]);
 284                 poly.input(&msg[128..129]);
 285                 poly.input(&msg[129..130]);
 286                 poly.input(&msg[130..131]);
 287                 poly.raw_result(&mut mac);
 288                 assert_eq!(&mac[..], &expected[..]);
 289         }
 290
 291         #[test]
 292         fn donna_self_test() {
 293                 let wrap_key = [
 294                         0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 295                         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 296                         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 297                         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 298                 ];
 299
 300                 let wrap_msg = [
 301                         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 302                         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 303                 ];
 304
 305                 let wrap_mac = [
 306                         0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 307                         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 308                 ];
 309
 310                 let mut mac = [0u8; 16];
 311                 poly1305(&wrap_key, &wrap_msg, &mut mac);
 312                 assert_eq!(&mac[..], &wrap_mac[..]);
 313
 314                 let total_key = [
 315                         0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xff,
 316                         0xfe, 0xfd, 0xfc, 0xfb, 0xfa, 0xf9, 0xff, 0xff,
 317                         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 318                         0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
 319                 ];
 320
 321                 let total_mac = [
 322                         0x64, 0xaf, 0xe2, 0xe8, 0xd6, 0xad, 0x7b, 0xbd,
 323                         0xd2, 0x87, 0xf9, 0x7c, 0x44, 0x62, 0x3d, 0x39,
 324                 ];
 325
 326                 let mut tpoly = Poly1305::new(&total_key);
 327                 for i in 0..256 {
 328                         let key: Vec<u8> = repeat(i as u8).take(32).collect();
 329                         let msg: Vec<u8> = repeat(i as u8).take(256).collect();
 330                         let mut mac = [0u8; 16];
 331                         poly1305(&key[..], &msg[0..i], &mut mac);
 332                         tpoly.input(&mac);
 333                 }
 334                 tpoly.raw_result(&mut mac);
 335                 assert_eq!(&mac[..], &total_mac[..]);
 336         }
 337
 338         #[test]
 339         fn test_tls_vectors() {
 340                 // from http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04
 341                 let key = b"this is 32-byte key for Poly1305";
 342                 let msg = [0u8; 32];
 343                 let expected = [
 344                         0x49, 0xec, 0x78, 0x09, 0x0e, 0x48, 0x1e, 0xc6,
 345                         0xc2, 0x6b, 0x33, 0xb9, 0x1c, 0xcc, 0x03, 0x07,
 346                 ];
 347                 let mut mac = [0u8; 16];
 348                 poly1305(key, &msg, &mut mac);
 349                 assert_eq!(&mac[..], &expected[..]);
 350
 351                 let msg = b"Hello world!";
 352                 let expected= [
 353                         0xa6, 0xf7, 0x45, 0x00, 0x8f, 0x81, 0xc9, 0x16,
 354                         0xa2, 0x0d, 0xcc, 0x74, 0xee, 0xf2, 0xb2, 0xf0,
 355                 ];
 356                 poly1305(key, msg, &mut mac);
 357                 assert_eq!(&mac[..], &expected[..]);
 358         }
 359 }