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>
siphash(const unsigned char * in,uint64_t inlen,const unsigned char (& k)[16],unsigned char (& out)[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
getSipHash_2_4_64(ArrayRef<uint8_t> In,const uint8_t (& K)[16],uint8_t (& Out)[8])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
getSipHash_2_4_128(ArrayRef<uint8_t> In,const uint8_t (& K)[16],uint8_t (& Out)[16])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.
getPointerAuthStableSipHash(StringRef Str)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