randen_hwaes.cc (18438B)
1 // Copyright 2017 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // HERMETIC NOTE: The randen_hwaes target must not introduce duplicate 16 // symbols from arbitrary system and other headers, since it may be built 17 // with different flags from other targets, using different levels of 18 // optimization, potentially introducing ODR violations. 19 20 #include "absl/random/internal/randen_hwaes.h" 21 22 #include <cstdint> 23 #include <cstring> 24 25 #include "absl/base/attributes.h" 26 #include "absl/numeric/int128.h" 27 #include "absl/random/internal/platform.h" 28 #include "absl/random/internal/randen_traits.h" 29 30 // ABSL_RANDEN_HWAES_IMPL indicates whether this file will contain 31 // a hardware accelerated implementation of randen, or whether it 32 // will contain stubs that exit the process. 33 #if ABSL_HAVE_ACCELERATED_AES 34 // The following platforms have implemented RandenHwAes. 35 #if defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) || \ 36 defined(ABSL_ARCH_PPC) || defined(ABSL_ARCH_ARM) || \ 37 defined(ABSL_ARCH_AARCH64) 38 #define ABSL_RANDEN_HWAES_IMPL 1 39 #endif 40 #endif 41 42 #if !defined(ABSL_RANDEN_HWAES_IMPL) 43 // No accelerated implementation is supported. 44 // The RandenHwAes functions are stubs that print an error and exit. 45 46 #include <cstdio> 47 #include <cstdlib> 48 49 namespace absl { 50 ABSL_NAMESPACE_BEGIN 51 namespace random_internal { 52 53 // No accelerated implementation. 54 bool HasRandenHwAesImplementation() { return false; } 55 56 // NOLINTNEXTLINE 57 const void* RandenHwAes::GetKeys() { 58 // Attempted to dispatch to an unsupported dispatch target. 59 const int d = ABSL_RANDOM_INTERNAL_AES_DISPATCH; 60 fprintf(stderr, "AES Hardware detection failed (%d).\n", d); 61 exit(1); 62 return nullptr; 63 } 64 65 // NOLINTNEXTLINE 66 void RandenHwAes::Absorb(const void*, void*) { 67 // Attempted to dispatch to an unsupported dispatch target. 68 const int d = ABSL_RANDOM_INTERNAL_AES_DISPATCH; 69 fprintf(stderr, "AES Hardware detection failed (%d).\n", d); 70 exit(1); 71 } 72 73 // NOLINTNEXTLINE 74 void RandenHwAes::Generate(const void*, void*) { 75 // Attempted to dispatch to an unsupported dispatch target. 76 const int d = ABSL_RANDOM_INTERNAL_AES_DISPATCH; 77 fprintf(stderr, "AES Hardware detection failed (%d).\n", d); 78 exit(1); 79 } 80 81 } // namespace random_internal 82 ABSL_NAMESPACE_END 83 } // namespace absl 84 85 #else // defined(ABSL_RANDEN_HWAES_IMPL) 86 // 87 // Accelerated implementations are supported. 88 // We need the per-architecture includes and defines. 89 // 90 namespace { 91 92 using absl::random_internal::RandenTraits; 93 94 } // namespace 95 96 // TARGET_CRYPTO defines a crypto attribute for each architecture. 97 // 98 // NOTE: Evaluate whether we should eliminate ABSL_TARGET_CRYPTO. 99 #if (defined(__clang__) || defined(__GNUC__)) 100 #if defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) 101 #define ABSL_TARGET_CRYPTO __attribute__((target("aes"))) 102 #elif defined(ABSL_ARCH_PPC) 103 #define ABSL_TARGET_CRYPTO __attribute__((target("crypto"))) 104 #else 105 #define ABSL_TARGET_CRYPTO 106 #endif 107 #else 108 #define ABSL_TARGET_CRYPTO 109 #endif 110 111 #if defined(ABSL_ARCH_PPC) 112 // NOTE: Keep in mind that PPC can operate in little-endian or big-endian mode, 113 // however the PPC altivec vector registers (and thus the AES instructions) 114 // always operate in big-endian mode. 115 116 #include <altivec.h> 117 // <altivec.h> #defines vector __vector; in C++, this is bad form. 118 #undef vector 119 #undef bool 120 121 // Rely on the PowerPC AltiVec vector operations for accelerated AES 122 // instructions. GCC support of the PPC vector types is described in: 123 // https://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/PowerPC-AltiVec_002fVSX-Built-in-Functions.html 124 // 125 // Already provides operator^=. 126 using Vector128 = __vector unsigned long long; // NOLINT(runtime/int) 127 128 namespace { 129 inline ABSL_TARGET_CRYPTO Vector128 ReverseBytes(const Vector128& v) { 130 // Reverses the bytes of the vector. 131 const __vector unsigned char perm = {15, 14, 13, 12, 11, 10, 9, 8, 132 7, 6, 5, 4, 3, 2, 1, 0}; 133 return vec_perm(v, v, perm); 134 } 135 136 // WARNING: these load/store in native byte order. It is OK to load and then 137 // store an unchanged vector, but interpreting the bits as a number or input 138 // to AES will have undefined results. 139 inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { 140 return vec_vsx_ld(0, reinterpret_cast<const Vector128*>(from)); 141 } 142 143 inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { 144 vec_vsx_st(v, 0, reinterpret_cast<Vector128*>(to)); 145 } 146 147 // One round of AES. "round_key" is a public constant for breaking the 148 // symmetry of AES (ensures previously equal columns differ afterwards). 149 inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, 150 const Vector128& round_key) { 151 return Vector128(__builtin_crypto_vcipher(state, round_key)); 152 } 153 154 // Enables native loads in the round loop by pre-swapping. 155 inline ABSL_TARGET_CRYPTO void SwapEndian(absl::uint128* state) { 156 for (uint32_t block = 0; block < RandenTraits::kFeistelBlocks; ++block) { 157 Vector128Store(ReverseBytes(Vector128Load(state + block)), state + block); 158 } 159 } 160 161 } // namespace 162 163 #elif defined(ABSL_ARCH_ARM) || defined(ABSL_ARCH_AARCH64) 164 165 // Rely on the ARM NEON+Crypto advanced simd types, defined in <arm_neon.h>. 166 // uint8x16_t is the user alias for underlying __simd128_uint8_t type. 167 // http://infocenter.arm.com/help/topic/com.arm.doc.ihi0073a/IHI0073A_arm_neon_intrinsics_ref.pdf 168 // 169 // <arm_neon> defines the following 170 // 171 // typedef __attribute__((neon_vector_type(16))) uint8_t uint8x16_t; 172 // typedef __attribute__((neon_vector_type(16))) int8_t int8x16_t; 173 // typedef __attribute__((neon_polyvector_type(16))) int8_t poly8x16_t; 174 // 175 // vld1q_v 176 // vst1q_v 177 // vaeseq_v 178 // vaesmcq_v 179 #include <arm_neon.h> 180 181 // Already provides operator^=. 182 using Vector128 = uint8x16_t; 183 184 namespace { 185 186 inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { 187 return vld1q_u8(reinterpret_cast<const uint8_t*>(from)); 188 } 189 190 inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { 191 vst1q_u8(reinterpret_cast<uint8_t*>(to), v); 192 } 193 194 // One round of AES. "round_key" is a public constant for breaking the 195 // symmetry of AES (ensures previously equal columns differ afterwards). 196 inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, 197 const Vector128& round_key) { 198 // It is important to always use the full round function - omitting the 199 // final MixColumns reduces security [https://eprint.iacr.org/2010/041.pdf] 200 // and does not help because we never decrypt. 201 // 202 // Note that ARM divides AES instructions differently than x86 / PPC, 203 // And we need to skip the first AddRoundKey step and add an extra 204 // AddRoundKey step to the end. Lucky for us this is just XOR. 205 return vaesmcq_u8(vaeseq_u8(state, uint8x16_t{})) ^ round_key; 206 } 207 208 inline ABSL_TARGET_CRYPTO void SwapEndian(void*) {} 209 210 } // namespace 211 212 #elif defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) 213 // On x86 we rely on the aesni instructions 214 #include <immintrin.h> 215 216 namespace { 217 218 // Vector128 class is only wrapper for __m128i, benchmark indicates that it's 219 // faster than using __m128i directly. 220 class Vector128 { 221 public: 222 // Convert from/to intrinsics. 223 inline explicit Vector128(const __m128i& v) : data_(v) {} 224 225 inline __m128i data() const { return data_; } 226 227 inline Vector128& operator^=(const Vector128& other) { 228 data_ = _mm_xor_si128(data_, other.data()); 229 return *this; 230 } 231 232 private: 233 __m128i data_; 234 }; 235 236 inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { 237 return Vector128(_mm_load_si128(reinterpret_cast<const __m128i*>(from))); 238 } 239 240 inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { 241 _mm_store_si128(reinterpret_cast<__m128i*>(to), v.data()); 242 } 243 244 // One round of AES. "round_key" is a public constant for breaking the 245 // symmetry of AES (ensures previously equal columns differ afterwards). 246 inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, 247 const Vector128& round_key) { 248 // It is important to always use the full round function - omitting the 249 // final MixColumns reduces security [https://eprint.iacr.org/2010/041.pdf] 250 // and does not help because we never decrypt. 251 return Vector128(_mm_aesenc_si128(state.data(), round_key.data())); 252 } 253 254 inline ABSL_TARGET_CRYPTO void SwapEndian(void*) {} 255 256 } // namespace 257 258 #endif 259 260 #ifdef __clang__ 261 #pragma clang diagnostic push 262 #pragma clang diagnostic ignored "-Wunknown-pragmas" 263 #endif 264 265 // At this point, all of the platform-specific features have been defined / 266 // implemented. 267 // 268 // REQUIRES: using Vector128 = ... 269 // REQUIRES: Vector128 Vector128Load(void*) {...} 270 // REQUIRES: void Vector128Store(Vector128, void*) {...} 271 // REQUIRES: Vector128 AesRound(Vector128, Vector128) {...} 272 // REQUIRES: void SwapEndian(uint64_t*) {...} 273 // 274 // PROVIDES: absl::random_internal::RandenHwAes::Absorb 275 // PROVIDES: absl::random_internal::RandenHwAes::Generate 276 namespace { 277 278 // Block shuffles applies a shuffle to the entire state between AES rounds. 279 // Improved odd-even shuffle from "New criterion for diffusion property". 280 inline ABSL_TARGET_CRYPTO void BlockShuffle(absl::uint128* state) { 281 static_assert(RandenTraits::kFeistelBlocks == 16, 282 "Expecting 16 FeistelBlocks."); 283 284 constexpr size_t shuffle[RandenTraits::kFeistelBlocks] = { 285 7, 2, 13, 4, 11, 8, 3, 6, 15, 0, 9, 10, 1, 14, 5, 12}; 286 287 const Vector128 v0 = Vector128Load(state + shuffle[0]); 288 const Vector128 v1 = Vector128Load(state + shuffle[1]); 289 const Vector128 v2 = Vector128Load(state + shuffle[2]); 290 const Vector128 v3 = Vector128Load(state + shuffle[3]); 291 const Vector128 v4 = Vector128Load(state + shuffle[4]); 292 const Vector128 v5 = Vector128Load(state + shuffle[5]); 293 const Vector128 v6 = Vector128Load(state + shuffle[6]); 294 const Vector128 v7 = Vector128Load(state + shuffle[7]); 295 const Vector128 w0 = Vector128Load(state + shuffle[8]); 296 const Vector128 w1 = Vector128Load(state + shuffle[9]); 297 const Vector128 w2 = Vector128Load(state + shuffle[10]); 298 const Vector128 w3 = Vector128Load(state + shuffle[11]); 299 const Vector128 w4 = Vector128Load(state + shuffle[12]); 300 const Vector128 w5 = Vector128Load(state + shuffle[13]); 301 const Vector128 w6 = Vector128Load(state + shuffle[14]); 302 const Vector128 w7 = Vector128Load(state + shuffle[15]); 303 304 Vector128Store(v0, state + 0); 305 Vector128Store(v1, state + 1); 306 Vector128Store(v2, state + 2); 307 Vector128Store(v3, state + 3); 308 Vector128Store(v4, state + 4); 309 Vector128Store(v5, state + 5); 310 Vector128Store(v6, state + 6); 311 Vector128Store(v7, state + 7); 312 Vector128Store(w0, state + 8); 313 Vector128Store(w1, state + 9); 314 Vector128Store(w2, state + 10); 315 Vector128Store(w3, state + 11); 316 Vector128Store(w4, state + 12); 317 Vector128Store(w5, state + 13); 318 Vector128Store(w6, state + 14); 319 Vector128Store(w7, state + 15); 320 } 321 322 // Feistel round function using two AES subrounds. Very similar to F() 323 // from Simpira v2, but with independent subround keys. Uses 17 AES rounds 324 // per 16 bytes (vs. 10 for AES-CTR). Computing eight round functions in 325 // parallel hides the 7-cycle AESNI latency on HSW. Note that the Feistel 326 // XORs are 'free' (included in the second AES instruction). 327 inline ABSL_TARGET_CRYPTO const absl::uint128* FeistelRound( 328 absl::uint128* state, 329 const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { 330 static_assert(RandenTraits::kFeistelBlocks == 16, 331 "Expecting 16 FeistelBlocks."); 332 333 // MSVC does a horrible job at unrolling loops. 334 // So we unroll the loop by hand to improve the performance. 335 const Vector128 s0 = Vector128Load(state + 0); 336 const Vector128 s1 = Vector128Load(state + 1); 337 const Vector128 s2 = Vector128Load(state + 2); 338 const Vector128 s3 = Vector128Load(state + 3); 339 const Vector128 s4 = Vector128Load(state + 4); 340 const Vector128 s5 = Vector128Load(state + 5); 341 const Vector128 s6 = Vector128Load(state + 6); 342 const Vector128 s7 = Vector128Load(state + 7); 343 const Vector128 s8 = Vector128Load(state + 8); 344 const Vector128 s9 = Vector128Load(state + 9); 345 const Vector128 s10 = Vector128Load(state + 10); 346 const Vector128 s11 = Vector128Load(state + 11); 347 const Vector128 s12 = Vector128Load(state + 12); 348 const Vector128 s13 = Vector128Load(state + 13); 349 const Vector128 s14 = Vector128Load(state + 14); 350 const Vector128 s15 = Vector128Load(state + 15); 351 352 // Encode even blocks with keys. 353 const Vector128 e0 = AesRound(s0, Vector128Load(keys + 0)); 354 const Vector128 e2 = AesRound(s2, Vector128Load(keys + 1)); 355 const Vector128 e4 = AesRound(s4, Vector128Load(keys + 2)); 356 const Vector128 e6 = AesRound(s6, Vector128Load(keys + 3)); 357 const Vector128 e8 = AesRound(s8, Vector128Load(keys + 4)); 358 const Vector128 e10 = AesRound(s10, Vector128Load(keys + 5)); 359 const Vector128 e12 = AesRound(s12, Vector128Load(keys + 6)); 360 const Vector128 e14 = AesRound(s14, Vector128Load(keys + 7)); 361 362 // Encode odd blocks with even output from above. 363 const Vector128 o1 = AesRound(e0, s1); 364 const Vector128 o3 = AesRound(e2, s3); 365 const Vector128 o5 = AesRound(e4, s5); 366 const Vector128 o7 = AesRound(e6, s7); 367 const Vector128 o9 = AesRound(e8, s9); 368 const Vector128 o11 = AesRound(e10, s11); 369 const Vector128 o13 = AesRound(e12, s13); 370 const Vector128 o15 = AesRound(e14, s15); 371 372 // Store odd blocks. (These will be shuffled later). 373 Vector128Store(o1, state + 1); 374 Vector128Store(o3, state + 3); 375 Vector128Store(o5, state + 5); 376 Vector128Store(o7, state + 7); 377 Vector128Store(o9, state + 9); 378 Vector128Store(o11, state + 11); 379 Vector128Store(o13, state + 13); 380 Vector128Store(o15, state + 15); 381 382 return keys + 8; 383 } 384 385 // Cryptographic permutation based via type-2 Generalized Feistel Network. 386 // Indistinguishable from ideal by chosen-ciphertext adversaries using less than 387 // 2^64 queries if the round function is a PRF. This is similar to the b=8 case 388 // of Simpira v2, but more efficient than its generic construction for b=16. 389 inline ABSL_TARGET_CRYPTO void Permute( 390 absl::uint128* state, 391 const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { 392 // (Successfully unrolled; the first iteration jumps into the second half) 393 #ifdef __clang__ 394 #pragma clang loop unroll_count(2) 395 #endif 396 for (size_t round = 0; round < RandenTraits::kFeistelRounds; ++round) { 397 keys = FeistelRound(state, keys); 398 BlockShuffle(state); 399 } 400 } 401 402 } // namespace 403 404 namespace absl { 405 ABSL_NAMESPACE_BEGIN 406 namespace random_internal { 407 408 bool HasRandenHwAesImplementation() { return true; } 409 410 const void* ABSL_TARGET_CRYPTO RandenHwAes::GetKeys() { 411 // Round keys for one AES per Feistel round and branch. 412 // The canonical implementation uses first digits of Pi. 413 #if defined(ABSL_ARCH_PPC) 414 return kRandenRoundKeysBE; 415 #else 416 return kRandenRoundKeys; 417 #endif 418 } 419 420 // NOLINTNEXTLINE 421 void ABSL_TARGET_CRYPTO RandenHwAes::Absorb(const void* seed_void, 422 void* state_void) { 423 static_assert(RandenTraits::kCapacityBytes / sizeof(Vector128) == 1, 424 "Unexpected Randen kCapacityBlocks"); 425 static_assert(RandenTraits::kStateBytes / sizeof(Vector128) == 16, 426 "Unexpected Randen kStateBlocks"); 427 428 auto* state = reinterpret_cast<absl::uint128 * ABSL_RANDOM_INTERNAL_RESTRICT>( 429 state_void); 430 const auto* seed = 431 reinterpret_cast<const absl::uint128 * ABSL_RANDOM_INTERNAL_RESTRICT>( 432 seed_void); 433 434 Vector128 b1 = Vector128Load(state + 1); 435 b1 ^= Vector128Load(seed + 0); 436 Vector128Store(b1, state + 1); 437 438 Vector128 b2 = Vector128Load(state + 2); 439 b2 ^= Vector128Load(seed + 1); 440 Vector128Store(b2, state + 2); 441 442 Vector128 b3 = Vector128Load(state + 3); 443 b3 ^= Vector128Load(seed + 2); 444 Vector128Store(b3, state + 3); 445 446 Vector128 b4 = Vector128Load(state + 4); 447 b4 ^= Vector128Load(seed + 3); 448 Vector128Store(b4, state + 4); 449 450 Vector128 b5 = Vector128Load(state + 5); 451 b5 ^= Vector128Load(seed + 4); 452 Vector128Store(b5, state + 5); 453 454 Vector128 b6 = Vector128Load(state + 6); 455 b6 ^= Vector128Load(seed + 5); 456 Vector128Store(b6, state + 6); 457 458 Vector128 b7 = Vector128Load(state + 7); 459 b7 ^= Vector128Load(seed + 6); 460 Vector128Store(b7, state + 7); 461 462 Vector128 b8 = Vector128Load(state + 8); 463 b8 ^= Vector128Load(seed + 7); 464 Vector128Store(b8, state + 8); 465 466 Vector128 b9 = Vector128Load(state + 9); 467 b9 ^= Vector128Load(seed + 8); 468 Vector128Store(b9, state + 9); 469 470 Vector128 b10 = Vector128Load(state + 10); 471 b10 ^= Vector128Load(seed + 9); 472 Vector128Store(b10, state + 10); 473 474 Vector128 b11 = Vector128Load(state + 11); 475 b11 ^= Vector128Load(seed + 10); 476 Vector128Store(b11, state + 11); 477 478 Vector128 b12 = Vector128Load(state + 12); 479 b12 ^= Vector128Load(seed + 11); 480 Vector128Store(b12, state + 12); 481 482 Vector128 b13 = Vector128Load(state + 13); 483 b13 ^= Vector128Load(seed + 12); 484 Vector128Store(b13, state + 13); 485 486 Vector128 b14 = Vector128Load(state + 14); 487 b14 ^= Vector128Load(seed + 13); 488 Vector128Store(b14, state + 14); 489 490 Vector128 b15 = Vector128Load(state + 15); 491 b15 ^= Vector128Load(seed + 14); 492 Vector128Store(b15, state + 15); 493 } 494 495 // NOLINTNEXTLINE 496 void ABSL_TARGET_CRYPTO RandenHwAes::Generate(const void* keys_void, 497 void* state_void) { 498 static_assert(RandenTraits::kCapacityBytes == sizeof(Vector128), 499 "Capacity mismatch"); 500 501 auto* state = reinterpret_cast<absl::uint128*>(state_void); 502 const auto* keys = reinterpret_cast<const absl::uint128*>(keys_void); 503 504 const Vector128 prev_inner = Vector128Load(state); 505 506 SwapEndian(state); 507 508 Permute(state, keys); 509 510 SwapEndian(state); 511 512 // Ensure backtracking resistance. 513 Vector128 inner = Vector128Load(state); 514 inner ^= prev_inner; 515 Vector128Store(inner, state); 516 } 517 518 #ifdef __clang__ 519 #pragma clang diagnostic pop 520 #endif 521 522 } // namespace random_internal 523 ABSL_NAMESPACE_END 524 } // namespace absl 525 526 #endif // (ABSL_RANDEN_HWAES_IMPL)