Kagome
Polkadot Runtime Engine in C++17
keccak.c
Go to the documentation of this file.
1 
6 #include <stdint.h>
7 #include <stdio.h>
8 #include <string.h>
9 
10 #include "crypto/keccak/keccak.h"
12 
13 #define SHA3_ASSERT(x)
14 #if defined(_MSC_VER)
15 #define SHA3_TRACE(format, ...)
16 #define SHA3_TRACE_BUF(format, buf, l, ...)
17 #else
18 #define SHA3_TRACE(format, args...)
19 #define SHA3_TRACE_BUF(format, buf, l, args...)
20 #endif
21 
22 /*
23  * This flag is used to configure "pure" Keccak, as opposed to NIST SHA3.
24  */
25 #define SHA3_USE_KECCAK_FLAG 0x80000000
26 #define SHA3_CW(x) ((x) & (~SHA3_USE_KECCAK_FLAG))
27 
28 #if defined(_MSC_VER)
29 #define SHA3_CONST(x) x
30 #else
31 #define SHA3_CONST(x) x##L
32 #endif
33 
34 #ifndef SHA3_ROTL64
35 #define SHA3_ROTL64(x, y) \
36  (((x) << (y)) | ((x) >> ((sizeof(uint64_t) * 8) - (y))))
37 #endif
38 
39 static const uint64_t keccakf_rndc[24] = {
40  SHA3_CONST(0x0000000000000001UL), SHA3_CONST(0x0000000000008082UL),
41  SHA3_CONST(0x800000000000808aUL), SHA3_CONST(0x8000000080008000UL),
42  SHA3_CONST(0x000000000000808bUL), SHA3_CONST(0x0000000080000001UL),
43  SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008009UL),
44  SHA3_CONST(0x000000000000008aUL), SHA3_CONST(0x0000000000000088UL),
45  SHA3_CONST(0x0000000080008009UL), SHA3_CONST(0x000000008000000aUL),
46  SHA3_CONST(0x000000008000808bUL), SHA3_CONST(0x800000000000008bUL),
47  SHA3_CONST(0x8000000000008089UL), SHA3_CONST(0x8000000000008003UL),
48  SHA3_CONST(0x8000000000008002UL), SHA3_CONST(0x8000000000000080UL),
49  SHA3_CONST(0x000000000000800aUL), SHA3_CONST(0x800000008000000aUL),
50  SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008080UL),
51  SHA3_CONST(0x0000000080000001UL), SHA3_CONST(0x8000000080008008UL)};
52 
53 static const unsigned keccakf_rotc[24] = {1, 3, 6, 10, 15, 21, 28, 36,
54  45, 55, 2, 14, 27, 41, 56, 8,
55  25, 43, 62, 18, 39, 61, 20, 44};
56 
57 static const unsigned keccakf_piln[24] = {10, 7, 11, 17, 18, 3, 5, 16,
58  8, 21, 24, 4, 15, 23, 19, 13,
59  12, 2, 20, 14, 22, 9, 6, 1};
60 
61 /* generally called after SHA3_KECCAK_SPONGE_WORDS-ctx->capacityWords words
62  * are XORed into the state s
63  */
64 void keccakf(uint64_t s[25]) {
65  int i, j, round; // NOLINT
66  uint64_t t, bc[5]; // NOLINT
67 #define KECCAK_ROUNDS 24
68 
69 #if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
70  for (i = 0; i < 25; i++) {
71  s[i] = LE_BE_SWAP64(s[i]);
72  }
73 #endif
74 
75  for (round = 0; round < KECCAK_ROUNDS; round++) {
76  /* Theta */
77  for (i = 0; i < 5; i++)
78  bc[i] = s[i] ^ s[i + 5] ^ s[i + 10] ^ s[i + 15] ^ s[i + 20];
79 
80  for (i = 0; i < 5; i++) {
81  t = bc[(i + 4) % 5] ^ SHA3_ROTL64(bc[(i + 1) % 5], 1);
82  for (j = 0; j < 25; j += 5) s[j + i] ^= t;
83  }
84 
85  /* Rho Pi */
86  t = s[1];
87  for (i = 0; i < 24; i++) {
88  j = keccakf_piln[i]; // NOLINT
89  bc[0] = s[j];
90  s[j] = SHA3_ROTL64(t, keccakf_rotc[i]);
91  t = bc[0];
92  }
93 
94  /* Chi */
95  for (j = 0; j < 25; j += 5) {
96  for (i = 0; i < 5; i++) bc[i] = s[j + i];
97  for (i = 0; i < 5; i++) s[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
98  }
99 
100  /* Iota */
101  s[0] ^= keccakf_rndc[round];
102  }
103 
104 #if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
105  for (i = 0; i < 25; i++) {
106  s[i] = LE_BE_SWAP64(s[i]);
107  }
108 #endif
109 }
110 
111 /* *************************** Public Inteface ************************ */
112 
113 /* For Init or Reset call these: */
114 sha3_return_t sha3_Init(void *priv, unsigned bitSize) {
115  sha3_context *ctx = (sha3_context *)priv;
116  if (bitSize != 256 && bitSize != 384 && bitSize != 512)
117  return SHA3_RETURN_BAD_PARAMS;
118  memset(ctx, 0, sizeof(*ctx));
119  ctx->capacityWords = 2 * bitSize / (8 * sizeof(uint64_t));
120  return SHA3_RETURN_OK;
121 }
122 
123 void sha3_Init256(void *priv) {
124  sha3_Init(priv, 256);
125 }
126 
127 void sha3_Init384(void *priv) {
128  sha3_Init(priv, 384);
129 }
130 
131 void sha3_Init512(void *priv) {
132  sha3_Init(priv, 512);
133 }
134 
135 enum SHA3_FLAGS sha3_SetFlags(void *priv, enum SHA3_FLAGS flags) {
136  sha3_context *ctx = (sha3_context *)priv;
137  flags &= SHA3_FLAGS_KECCAK;
138  ctx->capacityWords |= (flags == SHA3_FLAGS_KECCAK ? SHA3_USE_KECCAK_FLAG : 0);
139  return flags;
140 }
141 
142 void sha3_Update(void *priv, void const *bufIn, size_t len) {
143  sha3_context *ctx = (sha3_context *)priv;
144 
145  /* 0...7 -- how much is needed to have a word */
146  unsigned old_tail = (8 - ctx->byteIndex) & 7;
147 
148  size_t words;
149  unsigned tail;
150  size_t i;
151 
152  const uint8_t *buf = bufIn;
153 
154  SHA3_TRACE_BUF("called to update with:", buf, len);
155 
156  SHA3_ASSERT(ctx->byteIndex < 8);
157  SHA3_ASSERT(ctx->wordIndex < sizeof(ctx->s) / sizeof(ctx->s[0]));
158 
159  if (len < old_tail) { /* have no complete word or haven't started
160  * the word yet */
161  SHA3_TRACE("because %d<%d, store it and return",
162  (unsigned)len,
163  (unsigned)old_tail);
164  /* endian-independent code follows: */
165  while (len--)
166  ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
167  SHA3_ASSERT(ctx->byteIndex < 8);
168  return;
169  }
170 
171  if (old_tail) { /* will have one word to process */
172  SHA3_TRACE("completing one word with %d bytes", (unsigned)old_tail);
173  /* endian-independent code follows: */
174  len -= old_tail;
175  while (old_tail--)
176  ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
177 
178  /* now ready to add saved to the sponge */
179  ctx->s[ctx->wordIndex] ^= ctx->saved;
180  SHA3_ASSERT(ctx->byteIndex == 8);
181  ctx->byteIndex = 0;
182  ctx->saved = 0;
183  if (++ctx->wordIndex
185  keccakf(ctx->s);
186  ctx->wordIndex = 0;
187  }
188  }
189 
190  /* now work in full words directly from input */
191 
192  SHA3_ASSERT(ctx->byteIndex == 0);
193 
194  words = len / sizeof(uint64_t);
195  tail = len - words * sizeof(uint64_t);
196 
197  SHA3_TRACE("have %d full words to process", (unsigned)words);
198 
199  for (i = 0; i < words; i++, buf += sizeof(uint64_t)) {
200  const uint64_t t =
201  (uint64_t)(buf[0]) | ((uint64_t)(buf[1]) << 8 * 1)
202  | ((uint64_t)(buf[2]) << 8 * 2) | ((uint64_t)(buf[3]) << 8 * 3)
203  | ((uint64_t)(buf[4]) << 8 * 4) | ((uint64_t)(buf[5]) << 8 * 5)
204  | ((uint64_t)(buf[6]) << 8 * 6) | ((uint64_t)(buf[7]) << 8 * 7);
205 #if defined(__x86_64__) || defined(__i386__)
206  SHA3_ASSERT(memcmp(&t, buf, 8) == 0);
207 #endif
208  ctx->s[ctx->wordIndex] ^= t;
209  if (++ctx->wordIndex
211  keccakf(ctx->s);
212  ctx->wordIndex = 0;
213  }
214  }
215 
216  SHA3_TRACE("have %d bytes left to process, save them", (unsigned)tail);
217 
218  /* finally, save the partial word */
219  SHA3_ASSERT(ctx->byteIndex == 0 && tail < 8);
220  while (tail--) {
221  SHA3_TRACE("Store byte %02x '%c'", *buf, *buf);
222  ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
223  }
224  SHA3_ASSERT(ctx->byteIndex < 8);
225  SHA3_TRACE("Have saved=0x%016" PRIx64 " at the end", ctx->saved);
226 }
227 
228 /* This is simply the 'update' with the padding block.
229  * The padding block is 0x01 || 0x00* || 0x80. First 0x01 and last 0x80
230  * bytes are always present, but they can be the same byte.
231  */
232 void const *sha3_Finalize(void *priv) {
233  sha3_context *ctx = (sha3_context *)priv;
234 
235  SHA3_TRACE("called with %d bytes in the buffer", ctx->byteIndex);
236 
237  /* Append 2-bit suffix 01, per SHA-3 spec. Instead of 1 for padding we
238  * use 1<<2 below. The 0x02 below corresponds to the suffix 01.
239  * Overall, we feed 0, then 1, and finally 1 to start padding. Without
240  * M || 01, we would simply use 1 to start padding. */
241 
242  uint64_t t;
243 
244  if (ctx->capacityWords & SHA3_USE_KECCAK_FLAG) {
245  /* Keccak version */
246  t = (uint64_t)(((uint64_t)1) << (ctx->byteIndex * 8)); // NOLINT
247  } else {
248  /* SHA3 version */
249  t = (uint64_t)(((uint64_t)(0x02 | (1 << 2))) // NOLINT
250  << ((ctx->byteIndex) * 8)); // NOLINT
251  }
252 
253  ctx->s[ctx->wordIndex] ^= ctx->saved ^ t;
254 
255  ctx->s[SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords) - 1] ^=
256  SHA3_CONST(0x8000000000000000UL);
257  keccakf(ctx->s);
258 
259  /* Return first bytes of the ctx->s. This conversion is not needed for
260  * little-endian platforms e.g. wrap with #if !defined(__BYTE_ORDER__)
261  * || !defined(__ORDER_LITTLE_ENDIAN__) ||
262  * __BYTE_ORDER__!=__ORDER_LITTLE_ENDIAN__
263  * ... the conversion below ...
264  * #endif */
265  {
266  unsigned i;
267  for (i = 0; i < SHA3_KECCAK_SPONGE_WORDS; i++) { // NOLINT
268  const unsigned t1 = (uint32_t)ctx->s[i];
269  const unsigned t2 = (uint32_t)((ctx->s[i] >> 16) >> 16);
270  ctx->sb[i * 8 + 0] = (uint8_t)(t1);
271  ctx->sb[i * 8 + 1] = (uint8_t)(t1 >> 8);
272  ctx->sb[i * 8 + 2] = (uint8_t)(t1 >> 16);
273  ctx->sb[i * 8 + 3] = (uint8_t)(t1 >> 24);
274  ctx->sb[i * 8 + 4] = (uint8_t)(t2);
275  ctx->sb[i * 8 + 5] = (uint8_t)(t2 >> 8);
276  ctx->sb[i * 8 + 6] = (uint8_t)(t2 >> 16);
277  ctx->sb[i * 8 + 7] = (uint8_t)(t2 >> 24);
278  }
279  }
280 
281  SHA3_TRACE_BUF("Hash: (first 32 bytes)", ctx->sb, 256 / 8);
282 
283  return (ctx->sb);
284 }
285 
287  enum SHA3_FLAGS flags,
288  const void *in,
289  unsigned inBytes,
290  void *out,
291  unsigned outBytes) {
292  sha3_return_t err;
293  sha3_context c;
294 
295  err = sha3_Init(&c, bitSize);
296  if (err != SHA3_RETURN_OK) return err;
297  if (sha3_SetFlags(&c, flags) != flags) {
298  return SHA3_RETURN_BAD_PARAMS;
299  }
300  sha3_Update(&c, in, inBytes);
301  const void *h = sha3_Finalize(&c);
302 
303  if (outBytes > bitSize / 8) outBytes = bitSize / 8;
304  memcpy(out, h, outBytes);
305  return SHA3_RETURN_OK;
306 }
void sha3_Init512(void *priv)
Definition: keccak.c:131
#define SHA3_TRACE(format, args...)
Definition: keccak.c:18
#define SHA3_CW(x)
Definition: keccak.c:26
unsigned byteIndex
Definition: keccak.h:23
sha3_return_t sha3_HashBuffer(unsigned bitSize, enum SHA3_FLAGS flags, const void *in, unsigned inBytes, void *out, unsigned outBytes)
Definition: keccak.c:286
#define SHA3_KECCAK_SPONGE_WORDS
Definition: keccak.h:14
#define KECCAK_ROUNDS
unsigned capacityWords
Definition: keccak.h:27
#define SHA3_USE_KECCAK_FLAG
Definition: keccak.c:25
void keccakf(uint64_t s[25])
Definition: keccak.c:64
void sha3_Init256(void *priv)
Definition: keccak.c:123
#define SHA3_ROTL64(x, y)
Definition: keccak.c:35
enum SHA3_FLAGS sha3_SetFlags(void *priv, enum SHA3_FLAGS flags)
Definition: keccak.c:135
#define LE_BE_SWAP64
sha3_return_t sha3_Init(void *priv, unsigned bitSize)
Definition: keccak.c:114
enum SHA3_RETURN sha3_return_t
Definition: keccak.h:34
SHA3_FLAGS
Definition: keccak.h:31
void sha3_Update(void *priv, void const *bufIn, size_t len)
Definition: keccak.c:142
static const unsigned keccakf_piln[24]
Definition: keccak.c:57
void sha3_Init384(void *priv)
Definition: keccak.c:127
#define SHA3_CONST(x)
Definition: keccak.c:31
static const uint64_t keccakf_rndc[24]
Definition: keccak.c:39
unsigned wordIndex
Definition: keccak.h:25
static const unsigned keccakf_rotc[24]
Definition: keccak.c:53
#define SHA3_TRACE_BUF(format, buf, l, args...)
Definition: keccak.c:19
uint64_t saved
Definition: keccak.h:17
#define SHA3_ASSERT(x)
Definition: keccak.c:13
void const * sha3_Finalize(void *priv)
Definition: keccak.c:232