src/plugins/crypto_native/ghash.h

   1 /*
   2  *------------------------------------------------------------------
   3  * Copyright (c) 2019 Cisco and/or its affiliates.
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *------------------------------------------------------------------
  16  */
  17
  18 /*
  19  *------------------------------------------------------------------
  20  *  Copyright(c) 2018, Intel Corporation All rights reserved.
  21  *
  22  *  Redistribution and use in source and binary forms, with or without
  23  *  modification, are permitted provided that the following conditions
  24  *  are met:
  25  *    * Redistributions of source code must retain the above copyright
  26  *      notice, this list of conditions and the following disclaimer.
  27  *    * Redistributions in binary form must reproduce the above copyright
  28  *      notice, this list of conditions and the following disclaimer in
  29  *      the documentation and/or other materials provided with the
  30  *      distribution.
  31  *    * Neither the name of Intel Corporation nor the names of its
  32  *      contributors may be used to endorse or promote products derived
  33  *      from this software without specific prior written permission.
  34  *
  35  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  36  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  37  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  38  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  39  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES * LOSS OF USE,
  42  *  DATA, OR PROFITS * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  43  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  44  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  45  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  46  *------------------------------------------------------------------
  47  */
  48
  49 /*
  50  * Based on work by: Shay Gueron, Michael E. Kounavis, Erdinc Ozturk,
  51  *                   Vinodh Gopal, James Guilford, Tomasz Kantecki
  52  *
  53  * References:
  54  * [1] Vinodh Gopal et. al. Optimized Galois-Counter-Mode Implementation on
  55  *     Intel Architecture Processors. August, 2010
  56  * [2] Erdinc Ozturk et. al. Enabling High-Performance Galois-Counter-Mode on
  57  *     Intel Architecture Processors. October, 2012.
  58  * [3] intel-ipsec-mb library, https://github.com/01org/intel-ipsec-mb.git
  59  *
  60  * Definitions:
  61  *  GF    Galois Extension Field GF(2^128) - finite field where elements are
  62  *        represented as polynomials with coefficients in GF(2) with the
  63  *        highest degree of 127. Polynomials are represented as 128-bit binary
  64  *        numbers where each bit represents one coefficient.
  65  *        e.g. polynomial x^5 + x^3 + x + 1 is represented in binary 101011.
  66  *  H     hash key (128 bit)
  67  *  POLY  irreducible polynomial x^127 + x^7 + x^2 + x + 1
  68  *  RPOLY irreducible polynomial x^128 + x^127 + x^126 + x^121 + 1
  69  *  +     addition in GF, which equals to XOR operation
  70  *  *     multiplication in GF
  71  *
  72  * GF multiplication consists of 2 steps:
  73  *  - carry-less multiplication of two 128-bit operands into 256-bit result
  74  *  - reduction of 256-bit result into 128-bit with modulo POLY
  75  *
  76  * GHash is calculated on 128-bit blocks of data according to the following
  77  * formula:
  78  *    GH = (GH + data) * hash_key
  79  *
  80  * To avoid bit-reflection of data, this code uses GF multipication
  81  * with reversed polynomial:
  82  *   a * b * x^-127 mod RPOLY
  83  *
  84  * To improve computation speed table Hi is precomputed with powers of H',
  85  * where H' is calculated as H<<1 mod RPOLY.
  86  * This allows us to improve performance by deferring reduction. For example
  87  * to caclulate ghash of 4 128-bit blocks of data (b0, b1, b2, b3), we can do:
  88  *
  89  * __i128 Hi[4];
  90  * ghash_precompute (H, Hi, 4);
  91  *
  92  * ghash_data_t _gd, *gd = &_gd;
  93  * ghash_mul_first (gd, GH ^ b0, Hi[3]);
  94  * ghash_mul_next (gd, b1, Hi[2]);
  95  * ghash_mul_next (gd, b2, Hi[1]);
  96  * ghash_mul_next (gd, b3, Hi[0]);
  97  * ghash_reduce (gd);
  98  * ghash_reduce2 (gd);
  99  * GH = ghash_final (gd);
 100  *
 101  * Reduction step is split into 3 functions so it can be better interleaved
 102  * with other code, (i.e. with AES computation).
 103  */
 104
 105 #ifndef __ghash_h__
 106 #define __ghash_h__
 107
 108 /* on AVX-512 systems we can save a clock cycle by using ternary logic
 109    instruction to calculate a XOR b XOR c */
 110 static_always_inline u8x16
 111 ghash_xor3 (u8x16 a, u8x16 b, u8x16 c)
 112 {
 113 #if defined (__AVX512F__)
 114   return (u8x16) _mm_ternarylogic_epi32 ((__m128i) a, (__m128i) b,
 115                                          (__m128i) c, 0x96);
 116 #endif
 117   return a ^ b ^ c;
 118 }
 119
 120 static_always_inline u8x16
 121 gmul_lo_lo (u8x16 a, u8x16 b)
 122 {
 123 #if defined (__PCLMUL__)
 124   return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x00);
 125 #elif defined (__ARM_FEATURE_CRYPTO)
 126   return (u8x16) vmull_p64 ((poly64_t) vget_low_p64 ((poly64x2_t) a),
 127                             (poly64_t) vget_low_p64 ((poly64x2_t) b));
 128 #endif
 129 }
 130
 131 static_always_inline u8x16
 132 gmul_hi_lo (u8x16 a, u8x16 b)
 133 {
 134 #if defined (__PCLMUL__)
 135   return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x01);
 136 #elif defined (__ARM_FEATURE_CRYPTO)
 137   return (u8x16) vmull_p64 ((poly64_t) vget_high_p64 ((poly64x2_t) a),
 138                             (poly64_t) vget_low_p64 ((poly64x2_t) b));
 139 #endif
 140 }
 141
 142 static_always_inline u8x16
 143 gmul_lo_hi (u8x16 a, u8x16 b)
 144 {
 145 #if defined (__PCLMUL__)
 146   return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x10);
 147 #elif defined (__ARM_FEATURE_CRYPTO)
 148   return (u8x16) vmull_p64 ((poly64_t) vget_low_p64 ((poly64x2_t) a),
 149                             (poly64_t) vget_high_p64 ((poly64x2_t) b));
 150 #endif
 151 }
 152
 153 static_always_inline u8x16
 154 gmul_hi_hi (u8x16 a, u8x16 b)
 155 {
 156 #if defined (__PCLMUL__)
 157   return (u8x16) _mm_clmulepi64_si128 ((__m128i) a, (__m128i) b, 0x11);
 158 #elif defined (__ARM_FEATURE_CRYPTO)
 159   return (u8x16) vmull_high_p64 ((poly64x2_t) a, (poly64x2_t) b);
 160 #endif
 161 }
 162
 163 typedef struct
 164 {
 165   u8x16 mid, hi, lo, tmp_lo, tmp_hi;
 166   int pending;
 167 } ghash_data_t;
 168
 169 static const u8x16 ghash_poly = {
 170   0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 171   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc2
 172 };
 173
 174 static const u8x16 ghash_poly2 = {
 175   0x00, 0x00, 0x00, 0xc2, 0x01, 0x00, 0x00, 0x00,
 176   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc2
 177 };
 178
 179 static_always_inline void
 180 ghash_mul_first (ghash_data_t * gd, u8x16 a, u8x16 b)
 181 {
 182   /* a1 * b1 */
 183   gd->hi = gmul_hi_hi (a, b);
 184   /* a0 * b0 */
 185   gd->lo = gmul_lo_lo (a, b);
 186   /* a0 * b1 ^ a1 * b0 */
 187   gd->mid = (gmul_hi_lo (a, b) ^ gmul_lo_hi (a, b));
 188
 189   /* set gd->pending to 0 so next invocation of ghash_mul_next(...) knows that
 190      there is no pending data in tmp_lo and tmp_hi */
 191   gd->pending = 0;
 192 }
 193
 194 static_always_inline void
 195 ghash_mul_next (ghash_data_t * gd, u8x16 a, u8x16 b)
 196 {
 197   /* a1 * b1 */
 198   u8x16 hi = gmul_hi_hi (a, b);
 199   /* a0 * b0 */
 200   u8x16 lo = gmul_lo_lo (a, b);
 201
 202   /* this branch will be optimized out by the compiler, and it allows us to
 203      reduce number of XOR operations by using ternary logic */
 204   if (gd->pending)
 205     {
 206       /* there is peding data from previous invocation so we can XOR */
 207       gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, hi);
 208       gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, lo);
 209       gd->pending = 0;
 210     }
 211   else
 212     {
 213       /* there is no peding data from previous invocation so we postpone XOR */
 214       gd->tmp_hi = hi;
 215       gd->tmp_lo = lo;
 216       gd->pending = 1;
 217     }
 218
 219   /* gd->mid ^= a0 * b1 ^ a1 * b0  */
 220   gd->mid = ghash_xor3 (gd->mid, gmul_hi_lo (a, b), gmul_lo_hi (a, b));
 221 }
 222
 223 static_always_inline void
 224 ghash_reduce (ghash_data_t * gd)
 225 {
 226   u8x16 r;
 227
 228   /* Final combination:
 229      gd->lo ^= gd->mid << 64
 230      gd->hi ^= gd->mid >> 64 */
 231   u8x16 midl = u8x16_word_shift_left (gd->mid, 8);
 232   u8x16 midr = u8x16_word_shift_right (gd->mid, 8);
 233
 234   if (gd->pending)
 235     {
 236       gd->lo = ghash_xor3 (gd->lo, gd->tmp_lo, midl);
 237       gd->hi = ghash_xor3 (gd->hi, gd->tmp_hi, midr);
 238     }
 239   else
 240     {
 241       gd->lo ^= midl;
 242       gd->hi ^= midr;
 243     }
 244   r = gmul_hi_lo (ghash_poly2, gd->lo);
 245   gd->lo ^= u8x16_word_shift_left (r, 8);
 246 }
 247
 248 static_always_inline void
 249 ghash_reduce2 (ghash_data_t * gd)
 250 {
 251   gd->tmp_lo = gmul_lo_lo (ghash_poly2, gd->lo);
 252   gd->tmp_hi = gmul_lo_hi (ghash_poly2, gd->lo);
 253 }
 254
 255 static_always_inline u8x16
 256 ghash_final (ghash_data_t * gd)
 257 {
 258   return ghash_xor3 (gd->hi, u8x16_word_shift_right (gd->tmp_lo, 4),
 259                      u8x16_word_shift_left (gd->tmp_hi, 4));
 260 }
 261
 262 static_always_inline u8x16
 263 ghash_mul (u8x16 a, u8x16 b)
 264 {
 265   ghash_data_t _gd, *gd = &_gd;
 266   ghash_mul_first (gd, a, b);
 267   ghash_reduce (gd);
 268   ghash_reduce2 (gd);
 269   return ghash_final (gd);
 270 }
 271
 272 static_always_inline void
 273 ghash_precompute (u8x16 H, u8x16 * Hi, int count)
 274 {
 275   u8x16 r8;
 276   u32x4 r32;
 277   /* calcullate H<<1 mod poly from the hash key */
 278   r8 = (u8x16) ((u64x2) H >> 63);
 279   H = (u8x16) ((u64x2) H << 1);
 280   H |= u8x16_word_shift_left (r8, 8);
 281   r32 = (u32x4) u8x16_word_shift_right (r8, 8);
 282 #ifdef __SSE2__
 283   r32 = u32x4_shuffle (r32, 0, 1, 2, 0);
 284 #else
 285   r32[3] = r32[0];
 286 #endif
 287   /* *INDENT-OFF* */
 288   r32 = r32 == (u32x4) {1, 0, 0, 1};
 289   /* *INDENT-ON* */
 290   Hi[0] = H ^ ((u8x16) r32 & ghash_poly);
 291
 292   /* calculate H^(i + 1) */
 293   for (int i = 1; i < count; i++)
 294     Hi[i] = ghash_mul (Hi[0], Hi[i - 1]);
 295 }
 296
 297 #endif /* __ghash_h__ */
 298
 299 /*
 300  * fd.io coding-style-patch-verification: ON
 301  *
 302  * Local Variables:
 303  * eval: (c-set-style "gnu")
 304  * End:
 305  */