polyval.h (4963B)
1 /* Copyright (c) 2025, The Tor Project, Inc. */ 2 /* See LICENSE for licensing information */ 3 4 /** 5 * \file polyval.h 6 * \brief APIs for polyval universal hash function. 7 **/ 8 9 #ifndef TOR_POLYVAL_H 10 #define TOR_POLYVAL_H 11 12 #include "orconfig.h" 13 #include "lib/cc/torint.h" 14 15 /* Decide which implementation to use. */ 16 #if defined(__amd64__) || defined(__amd64) || defined(__x86_64__) \ 17 || defined(_M_X64) || defined(_M_IX86) || defined(__i486) \ 18 || defined(__i386__) 19 #define PV_INTEL_ARCH 20 #endif 21 22 #if defined(PV_INTEL_ARCH) && defined(__PCLMUL__) 23 /* We're building for an architecture that always has the intel 24 * intrinsics for carryless multiply. 25 * No need for runtime detection. 26 */ 27 #define PV_USE_PCLMUL_UNCONDITIONAL 28 #define PCLMUL_ANY 29 30 #elif defined(PV_INTEL_ARCH) && SIZEOF_VOID_P >= 8 31 /* We _might_ have PCLMUL, or we might not. 32 * We need to detect it at runtime. 33 */ 34 #define PV_USE_PCLMUL_DETECT 35 #define PCLMUL_ANY 36 37 #elif SIZEOF_VOID_P >= 8 38 /* It's a 64-bit architecture; use the generic 64-bit constant-time 39 * implementation. 40 */ 41 #define PV_USE_CTMUL64 42 #elif SIZEOF_VOID_P == 4 43 /* It's a 64-bit architecture; use the generic 32-bit constant-time 44 * implementation. 45 */ 46 #define PV_USE_CTMUL 47 #else 48 #error "sizeof(void*) is implausibly weird." 49 #endif 50 51 #ifdef PCLMUL_ANY 52 #include <emmintrin.h> 53 54 #define POLYVAL_USE_EXPANDED_KEYS 55 #endif 56 57 /** 58 * Declare a 128 bit integer type. 59 # The exact representation will depend on which implementation we've chosen. 60 */ 61 #if defined(PV_USE_PCLMUL_UNCONDITIONAL) 62 typedef __m128i pv_u128_; 63 #elif defined(PV_USE_PCLMUL_DETECT) 64 typedef union pv_u128_ { 65 __m128i u128x1; 66 struct { 67 uint64_t lo; 68 uint64_t hi; 69 } u64x2; 70 } pv_u128_; 71 #elif defined(PV_USE_CTMUL64) 72 typedef struct pv_u128_ { 73 uint64_t lo; 74 uint64_t hi; 75 } pv_u128_; 76 #elif defined(PV_USE_CTMUL) 77 typedef struct pv_u128_ { 78 uint32_t v[4]; 79 } pv_u128_; 80 #endif 81 82 /** A key for a polyval hash, plus any precomputed key material. */ 83 typedef struct polyval_key_t { 84 pv_u128_ h; 85 } polyval_key_t; 86 87 /** 88 * State for an instance of the polyval hash. 89 **/ 90 typedef struct polyval_t { 91 /** The key used for this instance of polyval. */ 92 polyval_key_t key; 93 /** The accumulator */ 94 pv_u128_ y; 95 } polyval_t; 96 97 /** 98 * Length of a polyval key, in bytes. 99 */ 100 #define POLYVAL_KEY_LEN 16 101 /** 102 * Length of a polyval block, in bytes. 103 */ 104 #define POLYVAL_BLOCK_LEN 16 105 /** 106 * Length of a polyval tag (output), in bytes. 107 */ 108 #define POLYVAL_TAG_LEN 16 109 110 /** Do any necessary precomputation from a polyval key, 111 * and store it. 112 */ 113 void polyval_key_init(polyval_key_t *, const uint8_t *key); 114 /** 115 * Initialize a polyval instance with a given key. 116 */ 117 void polyval_init(polyval_t *, const uint8_t *key); 118 /** 119 * Initialize a polyval instance with a preconstructed key. 120 */ 121 void polyval_init_from_key(polyval_t *, const polyval_key_t *key); 122 /** 123 * Update a polyval instance with a new 16-byte block. 124 */ 125 void polyval_add_block(polyval_t *, const uint8_t *block); 126 /** 127 * Update a polyval instance with 'n' bytes from 'data'. 128 * If 'n' is not evenly divisible by 16, pad it at the end with zeros. 129 * 130 * NOTE: This is not a general-purpose padding construction; 131 * it can be insecure if your are using it in context where the input length 132 * is variable. 133 */ 134 void polyval_add_zpad(polyval_t *, const uint8_t *data, size_t n); 135 /** 136 * Copy the 16-byte tag from a polyval instance into 'tag_out' 137 */ 138 void polyval_get_tag(const polyval_t *, uint8_t *tag_out); 139 /** 140 * Reset a polyval instance to its original state, 141 * retaining its key. 142 */ 143 void polyval_reset(polyval_t *); 144 145 /** If a faster-than-default polyval implementation is available, use it. */ 146 void polyval_detect_implementation(void); 147 148 #ifdef POLYVAL_USE_EXPANDED_KEYS 149 /* These variations are as for polyval_\*, but they use pre-expanded keys. 150 * They're appropriate when you know a key is likely to get used more than once 151 * on a large input. 152 */ 153 154 /** How many blocks to handle at once with an expanded key */ 155 #define PV_BLOCK_STRIDE 8 156 typedef struct pv_expanded_key_t { 157 // powers of h in reverse order, down to 2. 158 // (in other words, contains 159 // h^PCLMUL_BLOCK_STRIDE .. H^2) 160 __m128i k[PV_BLOCK_STRIDE-1]; 161 } pv_expanded_key_t; 162 typedef struct polyvalx_t { 163 polyval_t pv; 164 pv_expanded_key_t expanded; 165 } polyvalx_t; 166 167 void polyvalx_init(polyvalx_t *, const uint8_t *key); 168 void polyvalx_init_from_key(polyvalx_t *, const polyval_key_t *key); 169 void polyvalx_add_block(polyvalx_t *, const uint8_t *block); 170 void polyvalx_add_zpad(polyvalx_t *, const uint8_t *data, size_t n); 171 void polyvalx_get_tag(const polyvalx_t *, uint8_t *tag_out); 172 void polyvalx_reset(polyvalx_t *); 173 174 #else 175 #define polyvalx_t polyval_t 176 #define polyvalx_key_init polyval_key_init 177 #define polyvalx_init polyval_init 178 #define polyvalx_init_from_key polyval_init_from_key 179 #define polyvalx_add_block polyval_add_block 180 #define polyvalx_add_zpad polyval_add_zpad 181 #define polyvalx_get_tag polyval_get_tag 182 #define polyvalx_reset polyval_reset 183 #endif 184 185 #endif