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