ghash.go

     1  // Copyright 2024 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  package gcm
     6  
     7  import (
     8  	"crypto/internal/fips140"
     9  	"crypto/internal/fips140deps/byteorder"
    10  )
    11  
    12  // GHASH is exposed to allow crypto/cipher to implement non-AES GCM modes.
    13  // It is not allowed as a stand-alone operation in FIPS mode because it
    14  // is not ACVP tested.
    15  func GHASH(key *[16]byte, inputs ...[]byte) []byte {
    16  	fips140.RecordNonApproved()
    17  	var out [gcmBlockSize]byte
    18  	ghash(&out, key, inputs...)
    19  	return out[:]
    20  }
    21  
    22  // ghashMul does constant-time carry-less multiplication of two 32-bit integers,
    23  // returning the 64-bit product.
    24  func ghashMul(x, y uint32) uint64 {
    25  	// This function implements carryless multiplication using a technique first
    26  	// described by Thomas Pornin in the BearSSL documentation [0]. This
    27  	// technique uses generic integer multiplication, but ignores the carrys by
    28  	// masking all but 8 bits of the inputs, creating three bit holes between
    29  	// each unmasked bit. If the multiplications of any of the unmasked bits
    30  	// then cause a carry, the resulting carry bit spills into one of the three
    31  	// bit holes.
    32  	//
    33  	// Each 32-bit input is split into four 32-bit masked values, each
    34  	// containing 8 unmasked bits. The mask is shifted by one bit for each of
    35  	// the four values, such that the four values cover the full 32 bits of the
    36  	// input.
    37  	//
    38  	// In order to compute the bits at position z_k, z_k+4, z_k+8, ..., z_k+60
    39  	// for k = 0, 1, 2, 3, we compute the sum of the products x_i*y_j for all i,
    40  	// j such that i+j = k mod 4.
    41  	//
    42  	// We then mask the sum of each of the four products with the same mask used
    43  	// for the input values, which zeros out any spilled carry bits, and OR the
    44  	// masked values to get the final product.
    45  	//
    46  	// [0] https://www.bearssl.org/constanttime.html#ghash-for-gcm
    47  
    48  	var xm, ym [4]uint32
    49  	var z [4]uint64
    50  
    51  	for i := range 4 {
    52  		// Mask off the three bit holes in each input, creating four masked
    53  		// values for each input.
    54  		xm[i] = x & (0x11111111 << i)
    55  		ym[i] = y & (0x11111111 << i)
    56  	}
    57  
    58  	for i := range 4 {
    59  		// Compute the multiplication of x by the circulant matrix of y, using
    60  		// XOR to get carryless addition of the products:
    61  		//
    62  		//  | z[0] |   | ym[0] ym[3] ym[2] ym[1] |   | xm[0] |
    63  		//  | z[1] | = | ym[1] ym[0] ym[3] ym[2] | x | xm[1] |
    64  		//  | z[2] |   | ym[2] ym[1] ym[0] ym[3] |   | xm[2] |
    65  		//  | z[3] |   | ym[3] ym[2] ym[1] ym[0] |   | xm[3] |
    66  		z[i] = (uint64(xm[0]) * uint64(ym[i])) ^ (uint64(xm[1]) * uint64(ym[(i+3)%4])) ^ (uint64(xm[2]) * uint64(ym[(i+2)%4])) ^ (uint64(xm[3]) * uint64(ym[(i+1)%4]))
    67  		z[i] &= 0x1111111111111111 << i
    68  	}
    69  
    70  	return z[0] | z[1] | z[2] | z[3]
    71  }
    72  
    73  func ghash(out, H *[gcmBlockSize]byte, inputs ...[]byte) {
    74  	// The GHASH algorithm computes the sum of the products of two 128 bit
    75  	// integers Y and H (the input block and the key, respectively) in the field
    76  	// GF(2^128), modulo the field polynomial.
    77  	//
    78  	// We use the Karatsuba algorithm to decompose the 128-bit multiplication
    79  	// into three 64-bit multiplications, which we further decompose into 9
    80  	// 32-bit multiplications with 64-bit products.
    81  
    82  	// Make sure out is zeroed before we use it.
    83  	clear(out[:])
    84  
    85  	var y, h [4]uint32
    86  	for i := range 4 {
    87  		h[3-i] = byteorder.BEUint32(H[i*4 : (i*4)+4])
    88  	}
    89  
    90  	blockIterator := func(yield func([]byte) bool) {
    91  		for _, input := range inputs {
    92  			for len(input) >= 16 {
    93  				if !yield(input[:16]) {
    94  					return
    95  				}
    96  				input = input[16:]
    97  			}
    98  			if len(input) > 0 {
    99  				var partialBlock [gcmBlockSize]byte
   100  				copy(partialBlock[:], input)
   101  				if !yield(partialBlock[:]) {
   102  					return
   103  				}
   104  			}
   105  		}
   106  	}
   107  
   108  	// Compute the GHASH of the inputs by iterating over 16-byte blocks of the
   109  	// inputs, XORing each block into the current state, and multiplying the
   110  	// result by the key.
   111  	for block := range blockIterator {
   112  		for i := range 4 {
   113  			y[3-i] ^= byteorder.BEUint32(block[i*4 : (i*4)+4])
   114  		}
   115  
   116  		// Split y*h into nine products:
   117  		//
   118  		//  zLo = y0*h0, y2*h2, (y0^y2) * (h0^h2)
   119  		//  zHi = y1*h1, y3*h3, (y1^y3) * (h1^h3)
   120  		//  zSum = (y0^y1) * (h0^h1), (y2^y3) * (h2^h3), ((y0^y2) ^ (y1^y3)) * ((h0^h2) ^ (h1^h3))
   121  		var zLo, zHi, zSum [3]uint64
   122  
   123  		zLo[0] = ghashMul(y[0], h[0])
   124  		zHi[0] = ghashMul(y[1], h[1])
   125  		zSum[0] = ghashMul(y[0]^y[1], h[0]^h[1])
   126  
   127  		zLo[1] = ghashMul(y[2], h[2])
   128  		zHi[1] = ghashMul(y[3], h[3])
   129  		zSum[1] = ghashMul(y[2]^y[3], h[2]^h[3])
   130  
   131  		zLo[2] = ghashMul(y[0]^y[2], h[0]^h[2])
   132  		zHi[2] = ghashMul(y[1]^y[3], h[1]^h[3])
   133  		zSum[2] = ghashMul((y[0]^y[2])^(y[1]^y[3]), (h[0]^h[2])^(h[1]^h[3]))
   134  
   135  		// Reconstruct the 128-bit terms zLo, zHi, and zSum from their constituent 64-bit products
   136  		var result [3][2]uint64
   137  		for i := range 3 {
   138  			mid := zSum[i] ^ zLo[i] ^ zHi[i]
   139  			// Add the lower 32 bits of the middle term to the low term
   140  			result[i][0] = zLo[i] ^ (mid << 32)
   141  			// Add the upper 32 bits of the middle term to the high term
   142  			result[i][1] = zHi[i] ^ (mid >> 32)
   143  		}
   144  
   145  		// Compute the middle term by adding the high and low terms to the sum term
   146  		result[2][0] ^= result[0][0] ^ result[1][0]
   147  		result[2][1] ^= result[0][1] ^ result[1][1]
   148  
   149  		// Add the lower bits of the middle term to the higher bits of the low term
   150  		result[0][1] ^= result[2][0]
   151  		// Add the higher bits of the middle term to the lower bits of the high term
   152  		result[1][0] ^= result[2][1]
   153  
   154  		// Reconstruct the 256-bit product from the low and high terms, shifted
   155  		// by one bit to satisfy the GHASH construction.
   156  		var z [4]uint64
   157  		z[0] = result[0][0] << 1
   158  		z[1] = (result[0][1] << 1) | (result[0][0] >> 63)
   159  		z[2] = (result[1][0] << 1) | (result[0][1] >> 63)
   160  		z[3] = (result[1][1] << 1) | (result[1][0] >> 63)
   161  
   162  		// Reduce the 256-bit product modulo the field polynomial. z0 and z1 contain
   163  		// the high-degree terms (255 to 128), and z2 and z3 contain the low-degree terms (127 to 0).
   164  		for i := range 2 {
   165  			lw := z[i]
   166  			// Add the remainders of the high-degree terms to the low-degree terms
   167  			z[i+2] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7)
   168  			// Add the carrys from the reduction
   169  			z[i+1] ^= (lw << 63) ^ (lw << 62) ^ (lw << 57)
   170  		}
   171  
   172  		// Write the reduced 128-bit product back into y
   173  		y[0], y[1], y[2], y[3] = uint32(z[2]), uint32(z[2]>>32), uint32(z[3]), uint32(z[3]>>32)
   174  	}
   175  
   176  	for i := range 4 {
   177  		byteorder.BEPutUint32(out[i*4:(i*4)+4], y[3-i])
   178  	}
   179  }
   180
View as plain text