1 //===--- SipHash.cpp - An ABI-stable string hash --------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements an ABI-stable string hash based on SipHash, used to 10 // compute ptrauth discriminators. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/SipHash.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/StringExtras.h" 17 #include "llvm/ADT/StringRef.h" 18 #include "llvm/Support/Compiler.h" 19 #include "llvm/Support/Debug.h" 20 #include "llvm/Support/Endian.h" 21 #include <cstdint> 22 23 using namespace llvm; 24 using namespace support; 25 26 #define DEBUG_TYPE "llvm-siphash" 27 28 // Lightly adapted from the SipHash reference C implementation: 29 // https://github.com/veorq/SipHash 30 // by Jean-Philippe Aumasson and Daniel J. Bernstein 31 32 #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) 33 34 #define SIPROUND \ 35 do { \ 36 v0 += v1; \ 37 v1 = ROTL(v1, 13); \ 38 v1 ^= v0; \ 39 v0 = ROTL(v0, 32); \ 40 v2 += v3; \ 41 v3 = ROTL(v3, 16); \ 42 v3 ^= v2; \ 43 v0 += v3; \ 44 v3 = ROTL(v3, 21); \ 45 v3 ^= v0; \ 46 v2 += v1; \ 47 v1 = ROTL(v1, 17); \ 48 v1 ^= v2; \ 49 v2 = ROTL(v2, 32); \ 50 } while (0) 51 52 namespace { 53 54 /// Computes a SipHash value 55 /// 56 /// \param in: pointer to input data (read-only) 57 /// \param inlen: input data length in bytes (any size_t value) 58 /// \param k: reference to the key data 16-byte array (read-only) 59 /// \returns output data, must be 8 or 16 bytes 60 /// 61 template <int cROUNDS, int dROUNDS, size_t outlen> 62 void siphash(const unsigned char *in, uint64_t inlen, 63 const unsigned char (&k)[16], unsigned char (&out)[outlen]) { 64 65 const unsigned char *ni = (const unsigned char *)in; 66 const unsigned char *kk = (const unsigned char *)k; 67 68 static_assert(outlen == 8 || outlen == 16, "result should be 8 or 16 bytes"); 69 70 uint64_t v0 = UINT64_C(0x736f6d6570736575); 71 uint64_t v1 = UINT64_C(0x646f72616e646f6d); 72 uint64_t v2 = UINT64_C(0x6c7967656e657261); 73 uint64_t v3 = UINT64_C(0x7465646279746573); 74 uint64_t k0 = endian::read64le(kk); 75 uint64_t k1 = endian::read64le(kk + 8); 76 uint64_t m; 77 int i; 78 const unsigned char *end = ni + inlen - (inlen % sizeof(uint64_t)); 79 const int left = inlen & 7; 80 uint64_t b = ((uint64_t)inlen) << 56; 81 v3 ^= k1; 82 v2 ^= k0; 83 v1 ^= k1; 84 v0 ^= k0; 85 86 if (outlen == 16) 87 v1 ^= 0xee; 88 89 for (; ni != end; ni += 8) { 90 m = endian::read64le(ni); 91 v3 ^= m; 92 93 for (i = 0; i < cROUNDS; ++i) 94 SIPROUND; 95 96 v0 ^= m; 97 } 98 99 switch (left) { 100 case 7: 101 b |= ((uint64_t)ni[6]) << 48; 102 LLVM_FALLTHROUGH; 103 case 6: 104 b |= ((uint64_t)ni[5]) << 40; 105 LLVM_FALLTHROUGH; 106 case 5: 107 b |= ((uint64_t)ni[4]) << 32; 108 LLVM_FALLTHROUGH; 109 case 4: 110 b |= ((uint64_t)ni[3]) << 24; 111 LLVM_FALLTHROUGH; 112 case 3: 113 b |= ((uint64_t)ni[2]) << 16; 114 LLVM_FALLTHROUGH; 115 case 2: 116 b |= ((uint64_t)ni[1]) << 8; 117 LLVM_FALLTHROUGH; 118 case 1: 119 b |= ((uint64_t)ni[0]); 120 break; 121 case 0: 122 break; 123 } 124 125 v3 ^= b; 126 127 for (i = 0; i < cROUNDS; ++i) 128 SIPROUND; 129 130 v0 ^= b; 131 132 if (outlen == 16) 133 v2 ^= 0xee; 134 else 135 v2 ^= 0xff; 136 137 for (i = 0; i < dROUNDS; ++i) 138 SIPROUND; 139 140 b = v0 ^ v1 ^ v2 ^ v3; 141 endian::write64le(out, b); 142 143 if (outlen == 8) 144 return; 145 146 v1 ^= 0xdd; 147 148 for (i = 0; i < dROUNDS; ++i) 149 SIPROUND; 150 151 b = v0 ^ v1 ^ v2 ^ v3; 152 endian::write64le(out + 8, b); 153 } 154 155 } // end anonymous namespace 156 157 void llvm::getSipHash_2_4_64(ArrayRef<uint8_t> In, const uint8_t (&K)[16], 158 uint8_t (&Out)[8]) { 159 siphash<2, 4>(In.data(), In.size(), K, Out); 160 } 161 162 void llvm::getSipHash_2_4_128(ArrayRef<uint8_t> In, const uint8_t (&K)[16], 163 uint8_t (&Out)[16]) { 164 siphash<2, 4>(In.data(), In.size(), K, Out); 165 } 166 167 /// Compute an ABI-stable 16-bit hash of the given string. 168 uint16_t llvm::getPointerAuthStableSipHash(StringRef Str) { 169 static const uint8_t K[16] = {0xb5, 0xd4, 0xc9, 0xeb, 0x79, 0x10, 0x4a, 0x79, 170 0x6f, 0xec, 0x8b, 0x1b, 0x42, 0x87, 0x81, 0xd4}; 171 172 uint8_t RawHashBytes[8]; 173 getSipHash_2_4_64(arrayRefFromStringRef(Str), K, RawHashBytes); 174 uint64_t RawHash = endian::read64le(RawHashBytes); 175 176 // Produce a non-zero 16-bit discriminator. 177 uint16_t Discriminator = (RawHash % 0xFFFF) + 1; 178 LLVM_DEBUG( 179 dbgs() << "ptrauth stable hash discriminator: " << utostr(Discriminator) 180 << " (0x" 181 << utohexstr(Discriminator, /*Lowercase=*/false, /*Width=*/4) 182 << ")" 183 << " of: " << Str << "\n"); 184 return Discriminator; 185 } 186