1 // Copyright 2018 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // This file provides the generic implementation of Sum and MAC. Other files 6 // might provide optimized assembly implementations of some of this code. 7 8 package poly1305 9 10 import "encoding/binary" 11 12 // Poly1305 [RFC 7539] is a relatively simple algorithm: the authentication tag 13 // for a 64 bytes message is approximately 14 // 15 // s + m[0:16] * r⁴ + m[16:32] * r³ + m[32:48] * r² + m[48:64] * r mod 2¹³⁰ - 5 16 // 17 // for some secret r and s. It can be computed sequentially like 18 // 19 // for len(msg) > 0: 20 // h += read(msg, 16) 21 // h *= r 22 // h %= 2¹³⁰ - 5 23 // return h + s 24 // 25 // All the complexity is about doing performant constant-time math on numbers 26 // larger than any available numeric type. 27 28 func sumGeneric(out *[TagSize]byte, msg []byte, key *[32]byte) { 29 h := newMACGeneric(key) 30 h.Write(msg) 31 h.Sum(out) 32 } 33 34 func newMACGeneric(key *[32]byte) macGeneric { 35 m := macGeneric{} 36 initialize(key, &m.macState) 37 return m 38 } 39 40 // macState holds numbers in saturated 64-bit little-endian limbs. That is, 41 // the value of [x0, x1, x2] is x[0] + x[1] * 2⁶⁴ + x[2] * 2¹²⁸. 42 type macState struct { 43 // h is the main accumulator. It is to be interpreted modulo 2¹³⁰ - 5, but 44 // can grow larger during and after rounds. It must, however, remain below 45 // 2 * (2¹³⁰ - 5). 46 h [3]uint64 47 // r and s are the private key components. 48 r [2]uint64 49 s [2]uint64 50 } 51 52 type macGeneric struct { 53 macState 54 55 buffer [TagSize]byte 56 offset int 57 } 58 59 // Write splits the incoming message into TagSize chunks, and passes them to 60 // update. It buffers incomplete chunks. 61 func (h *macGeneric) Write(p []byte) (int, error) { 62 nn := len(p) 63 if h.offset > 0 { 64 n := copy(h.buffer[h.offset:], p) 65 if h.offset+n < TagSize { 66 h.offset += n 67 return nn, nil 68 } 69 p = p[n:] 70 h.offset = 0 71 updateGeneric(&h.macState, h.buffer[:]) 72 } 73 if n := len(p) - (len(p) % TagSize); n > 0 { 74 updateGeneric(&h.macState, p[:n]) 75 p = p[n:] 76 } 77 if len(p) > 0 { 78 h.offset += copy(h.buffer[h.offset:], p) 79 } 80 return nn, nil 81 } 82 83 // Sum flushes the last incomplete chunk from the buffer, if any, and generates 84 // the MAC output. It does not modify its state, in order to allow for multiple 85 // calls to Sum, even if no Write is allowed after Sum. 86 func (h *macGeneric) Sum(out *[TagSize]byte) { 87 state := h.macState 88 if h.offset > 0 { 89 updateGeneric(&state, h.buffer[:h.offset]) 90 } 91 finalize(out, &state.h, &state.s) 92 } 93 94 // [rMask0, rMask1] is the specified Poly1305 clamping mask in little-endian. It 95 // clears some bits of the secret coefficient to make it possible to implement 96 // multiplication more efficiently. 97 const ( 98 rMask0 = 0x0FFFFFFC0FFFFFFF 99 rMask1 = 0x0FFFFFFC0FFFFFFC 100 ) 101 102 // initialize loads the 256-bit key into the two 128-bit secret values r and s. 103 func initialize(key *[32]byte, m *macState) { 104 m.r[0] = binary.LittleEndian.Uint64(key[0:8]) & rMask0 105 m.r[1] = binary.LittleEndian.Uint64(key[8:16]) & rMask1 106 m.s[0] = binary.LittleEndian.Uint64(key[16:24]) 107 m.s[1] = binary.LittleEndian.Uint64(key[24:32]) 108 } 109 110 // uint128 holds a 128-bit number as two 64-bit limbs, for use with the 111 // bits.Mul64 and bits.Add64 intrinsics. 112 type uint128 struct { 113 lo, hi uint64 114 } 115 116 func mul64(a, b uint64) uint128 { 117 hi, lo := bitsMul64(a, b) 118 return uint128{lo, hi} 119 } 120 121 func add128(a, b uint128) uint128 { 122 lo, c := bitsAdd64(a.lo, b.lo, 0) 123 hi, c := bitsAdd64(a.hi, b.hi, c) 124 if c != 0 { 125 panic("poly1305: unexpected overflow") 126 } 127 return uint128{lo, hi} 128 } 129 130 func shiftRightBy2(a uint128) uint128 { 131 a.lo = a.lo>>2 | (a.hi&3)<<62 132 a.hi = a.hi >> 2 133 return a 134 } 135 136 // updateGeneric absorbs msg into the state.h accumulator. For each chunk m of 137 // 128 bits of message, it computes 138 // 139 // h₊ = (h + m) * r mod 2¹³⁰ - 5 140 // 141 // If the msg length is not a multiple of TagSize, it assumes the last 142 // incomplete chunk is the final one. 143 func updateGeneric(state *macState, msg []byte) { 144 h0, h1, h2 := state.h[0], state.h[1], state.h[2] 145 r0, r1 := state.r[0], state.r[1] 146 147 for len(msg) > 0 { 148 var c uint64 149 150 // For the first step, h + m, we use a chain of bits.Add64 intrinsics. 151 // The resulting value of h might exceed 2¹³⁰ - 5, but will be partially 152 // reduced at the end of the multiplication below. 153 // 154 // The spec requires us to set a bit just above the message size, not to 155 // hide leading zeroes. For full chunks, that's 1 << 128, so we can just 156 // add 1 to the most significant (2¹²⁸) limb, h2. 157 if len(msg) >= TagSize { 158 h0, c = bitsAdd64(h0, binary.LittleEndian.Uint64(msg[0:8]), 0) 159 h1, c = bitsAdd64(h1, binary.LittleEndian.Uint64(msg[8:16]), c) 160 h2 += c + 1 161 162 msg = msg[TagSize:] 163 } else { 164 var buf [TagSize]byte 165 copy(buf[:], msg) 166 buf[len(msg)] = 1 167 168 h0, c = bitsAdd64(h0, binary.LittleEndian.Uint64(buf[0:8]), 0) 169 h1, c = bitsAdd64(h1, binary.LittleEndian.Uint64(buf[8:16]), c) 170 h2 += c 171 172 msg = nil 173 } 174 175 // Multiplication of big number limbs is similar to elementary school 176 // columnar multiplication. Instead of digits, there are 64-bit limbs. 177 // 178 // We are multiplying a 3 limbs number, h, by a 2 limbs number, r. 179 // 180 // h2 h1 h0 x 181 // r1 r0 = 182 // ---------------- 183 // h2r0 h1r0 h0r0 <-- individual 128-bit products 184 // + h2r1 h1r1 h0r1 185 // ------------------------ 186 // m3 m2 m1 m0 <-- result in 128-bit overlapping limbs 187 // ------------------------ 188 // m3.hi m2.hi m1.hi m0.hi <-- carry propagation 189 // + m3.lo m2.lo m1.lo m0.lo 190 // ------------------------------- 191 // t4 t3 t2 t1 t0 <-- final result in 64-bit limbs 192 // 193 // The main difference from pen-and-paper multiplication is that we do 194 // carry propagation in a separate step, as if we wrote two digit sums 195 // at first (the 128-bit limbs), and then carried the tens all at once. 196 197 h0r0 := mul64(h0, r0) 198 h1r0 := mul64(h1, r0) 199 h2r0 := mul64(h2, r0) 200 h0r1 := mul64(h0, r1) 201 h1r1 := mul64(h1, r1) 202 h2r1 := mul64(h2, r1) 203 204 // Since h2 is known to be at most 7 (5 + 1 + 1), and r0 and r1 have their 205 // top 4 bits cleared by rMask{0,1}, we know that their product is not going 206 // to overflow 64 bits, so we can ignore the high part of the products. 207 // 208 // This also means that the product doesn't have a fifth limb (t4). 209 if h2r0.hi != 0 { 210 panic("poly1305: unexpected overflow") 211 } 212 if h2r1.hi != 0 { 213 panic("poly1305: unexpected overflow") 214 } 215 216 m0 := h0r0 217 m1 := add128(h1r0, h0r1) // These two additions don't overflow thanks again 218 m2 := add128(h2r0, h1r1) // to the 4 masked bits at the top of r0 and r1. 219 m3 := h2r1 220 221 t0 := m0.lo 222 t1, c := bitsAdd64(m1.lo, m0.hi, 0) 223 t2, c := bitsAdd64(m2.lo, m1.hi, c) 224 t3, _ := bitsAdd64(m3.lo, m2.hi, c) 225 226 // Now we have the result as 4 64-bit limbs, and we need to reduce it 227 // modulo 2¹³⁰ - 5. The special shape of this Crandall prime lets us do 228 // a cheap partial reduction according to the reduction identity 229 // 230 // c * 2¹³⁰ + n = c * 5 + n mod 2¹³⁰ - 5 231 // 232 // because 2¹³⁰ = 5 mod 2¹³⁰ - 5. Partial reduction since the result is 233 // likely to be larger than 2¹³⁰ - 5, but still small enough to fit the 234 // assumptions we make about h in the rest of the code. 235 // 236 // See also https://speakerdeck.com/gtank/engineering-prime-numbers?slide=23 237 238 // We split the final result at the 2¹³⁰ mark into h and cc, the carry. 239 // Note that the carry bits are effectively shifted left by 2, in other 240 // words, cc = c * 4 for the c in the reduction identity. 241 h0, h1, h2 = t0, t1, t2&maskLow2Bits 242 cc := uint128{t2 & maskNotLow2Bits, t3} 243 244 // To add c * 5 to h, we first add cc = c * 4, and then add (cc >> 2) = c. 245 246 h0, c = bitsAdd64(h0, cc.lo, 0) 247 h1, c = bitsAdd64(h1, cc.hi, c) 248 h2 += c 249 250 cc = shiftRightBy2(cc) 251 252 h0, c = bitsAdd64(h0, cc.lo, 0) 253 h1, c = bitsAdd64(h1, cc.hi, c) 254 h2 += c 255 256 // h2 is at most 3 + 1 + 1 = 5, making the whole of h at most 257 // 258 // 5 * 2¹²⁸ + (2¹²⁸ - 1) = 6 * 2¹²⁸ - 1 259 } 260 261 state.h[0], state.h[1], state.h[2] = h0, h1, h2 262 } 263 264 const ( 265 maskLow2Bits uint64 = 0x0000000000000003 266 maskNotLow2Bits uint64 = ^maskLow2Bits 267 ) 268 269 // select64 returns x if v == 1 and y if v == 0, in constant time. 270 func select64(v, x, y uint64) uint64 { return ^(v-1)&x | (v-1)&y } 271 272 // [p0, p1, p2] is 2¹³⁰ - 5 in little endian order. 273 const ( 274 p0 = 0xFFFFFFFFFFFFFFFB 275 p1 = 0xFFFFFFFFFFFFFFFF 276 p2 = 0x0000000000000003 277 ) 278 279 // finalize completes the modular reduction of h and computes 280 // 281 // out = h + s mod 2¹²⁸ 282 func finalize(out *[TagSize]byte, h *[3]uint64, s *[2]uint64) { 283 h0, h1, h2 := h[0], h[1], h[2] 284 285 // After the partial reduction in updateGeneric, h might be more than 286 // 2¹³⁰ - 5, but will be less than 2 * (2¹³⁰ - 5). To complete the reduction 287 // in constant time, we compute t = h - (2¹³⁰ - 5), and select h as the 288 // result if the subtraction underflows, and t otherwise. 289 290 hMinusP0, b := bitsSub64(h0, p0, 0) 291 hMinusP1, b := bitsSub64(h1, p1, b) 292 _, b = bitsSub64(h2, p2, b) 293 294 // h = h if h < p else h - p 295 h0 = select64(b, h0, hMinusP0) 296 h1 = select64(b, h1, hMinusP1) 297 298 // Finally, we compute the last Poly1305 step 299 // 300 // tag = h + s mod 2¹²⁸ 301 // 302 // by just doing a wide addition with the 128 low bits of h and discarding 303 // the overflow. 304 h0, c := bitsAdd64(h0, s[0], 0) 305 h1, _ = bitsAdd64(h1, s[1], c) 306 307 binary.LittleEndian.PutUint64(out[0:8], h0) 308 binary.LittleEndian.PutUint64(out[8:16], h1) 309 } 310