Debian Codegraph @

ext/digest/sha3.c

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