1 /*
2 * An implementation of the SHA3 (Keccak) hash function family.
3 *
4 * Algorithm specifications: http://keccak.noekeon.org/
5 * NIST Announcement:
6 * http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html
7 *
8 * Written in 2013 by Fabrizio Tarizzo <fabrizio@fabriziotarizzo.org>
9 *
10 * ===================================================================
11 * The contents of this file are dedicated to the public domain. To
12 * the extent that dedication to the public domain is not available,
13 * everyone is granted a worldwide, perpetual, royalty-free,
14 * non-exclusive license to exercise all rights associated with the
15 * contents of this file for any purpose whatsoever.
16 * No rights are reserved.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
22 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
23 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 * SOFTWARE.
26 * ===================================================================
27 */
28
29 #include <string.h>
30 #include <assert.h>
31 #include "common.h"
32 #include "endianess.h"
33
34 FAKE_INIT(keccak)
35
36 typedef struct
37 {
38 uint64_t state[25];
39
40 /* The buffer is as long as the state,
41 * but only 'rate' bytes will be used.
42 */
43 uint8_t buf[200];
44
45 /* When absorbing, this is the number of bytes in buf that
46 * are coming from the message and outstanding.
47 * When squeezing, this is the remaining number of bytes
48 * that can be used as digest.
49 */
50 unsigned valid_bytes;
51
52 /* All values in bytes */
53 unsigned capacity;
54 unsigned rate;
55
56 uint8_t squeezing;
57 uint8_t padding;
58 } keccak_state;
59
60 #undef ROL64
61 #define ROL64(x,y) ((((x) << (y)) | (x) >> (64-(y))) & 0xFFFFFFFFFFFFFFFFULL)
62
63 static void keccak_function (uint64_t *state);
64
keccak_absorb_internal(keccak_state * self)65 static void keccak_absorb_internal (keccak_state *self)
66 {
67 unsigned i,j;
68 uint64_t d;
69
70 for (i=j=0; j < self->rate; ++i, j += 8) {
71 d = LOAD_U64_LITTLE(self->buf + j);
72 self->state[i] ^= d;
73 }
74 }
75
76 static void
keccak_squeeze_internal(keccak_state * self)77 keccak_squeeze_internal (keccak_state *self)
78 {
79 unsigned i, j;
80
81 for (i=j=0; j < self->rate; ++i, j += 8) {
82 STORE_U64_LITTLE(self->buf+j, self->state[i]);
83 }
84 }
85
keccak_init(keccak_state ** state,size_t capacity_bytes,uint8_t padding)86 EXPORT_SYM int keccak_init (keccak_state **state,
87 size_t capacity_bytes,
88 uint8_t padding)
89 {
90 keccak_state *ks;
91
92 if (NULL == state) {
93 return ERR_NULL;
94 }
95
96 *state = ks = (keccak_state*) calloc(1, sizeof(keccak_state));
97 if (NULL == ks)
98 return ERR_MEMORY;
99
100 if (capacity_bytes >= 200)
101 return ERR_DIGEST_SIZE;
102
103 ks->capacity = (unsigned)capacity_bytes;
104
105 ks->rate = 200 - ks->capacity;
106
107 ks->squeezing = 0;
108 ks->padding = padding;
109
110 return 0;
111 }
112
keccak_destroy(keccak_state * state)113 EXPORT_SYM int keccak_destroy(keccak_state *state)
114 {
115 free(state);
116 return 0;
117 }
118
keccak_absorb(keccak_state * self,const uint8_t * in,size_t length)119 EXPORT_SYM int keccak_absorb (keccak_state *self,
120 const uint8_t *in,
121 size_t length)
122 {
123 if (NULL==self || NULL==in)
124 return ERR_NULL;
125
126 if (self->squeezing != 0)
127 return ERR_UNKNOWN;
128
129 while (length > 0) {
130 unsigned tc;
131 unsigned left;
132
133 left = self->rate - self->valid_bytes;
134 tc = (unsigned) MIN(length, left);
135 memcpy(self->buf + self->valid_bytes, in, tc);
136
137 self->valid_bytes += tc;
138 in += tc;
139 length -= tc;
140
141 if (self->valid_bytes == self->rate) {
142 keccak_absorb_internal (self);
143 keccak_function (self->state);
144 self->valid_bytes = 0;
145 }
146 }
147
148 return 0;
149 }
150
keccak_finish(keccak_state * self)151 static void keccak_finish (keccak_state *self)
152 {
153 assert(self->squeezing == 0);
154 assert(self->valid_bytes < self->rate);
155
156 /* Padding */
157 memset(self->buf + self->valid_bytes, 0, self->rate - self->valid_bytes);
158 self->buf[self->valid_bytes] = self->padding;
159 self->buf[self->rate-1] |= 0x80;
160
161 /* Final absorb */
162 keccak_absorb_internal (self);
163 keccak_function (self->state);
164
165 /* First squeeze */
166 self->squeezing = 1;
167 keccak_squeeze_internal (self);
168 self->valid_bytes = self->rate;
169 }
170
keccak_squeeze(keccak_state * self,uint8_t * out,size_t length)171 EXPORT_SYM int keccak_squeeze (keccak_state *self, uint8_t *out, size_t length)
172 {
173 if ((NULL == self) || (NULL == out))
174 return ERR_NULL;
175
176 if (self->squeezing == 0) {
177 keccak_finish (self);
178 }
179
180 assert(self->squeezing == 1);
181 assert(self->valid_bytes > 0);
182 assert(self->valid_bytes <= self->rate);
183
184 while (length > 0) {
185 unsigned tc;
186
187 tc = (unsigned)MIN(self->valid_bytes, length);
188 memcpy(out, self->buf + (self->rate - self->valid_bytes), tc);
189
190 self->valid_bytes -= tc;
191 out += tc;
192 length -= tc;
193
194 if (self->valid_bytes == 0) {
195 keccak_function (self->state);
196 keccak_squeeze_internal (self);
197 self->valid_bytes = self->rate;
198 }
199 }
200
201 return 0;
202 }
203
keccak_digest(keccak_state * state,uint8_t * digest,size_t len)204 EXPORT_SYM int keccak_digest(keccak_state *state, uint8_t *digest, size_t len)
205 {
206 keccak_state tmp;
207
208 if ((NULL==state) || (NULL==digest))
209 return ERR_NULL;
210
211 if (2*len != state->capacity)
212 return ERR_UNKNOWN;
213
214 tmp = *state;
215 return keccak_squeeze(&tmp, digest, len);
216 }
217
218 /* Keccak core function */
219
220 #define KECCAK_ROUNDS 24
221
222 #define ROT_01 36
223 #define ROT_02 3
224 #define ROT_03 41
225 #define ROT_04 18
226 #define ROT_05 1
227 #define ROT_06 44
228 #define ROT_07 10
229 #define ROT_08 45
230 #define ROT_09 2
231 #define ROT_10 62
232 #define ROT_11 6
233 #define ROT_12 43
234 #define ROT_13 15
235 #define ROT_14 61
236 #define ROT_15 28
237 #define ROT_16 55
238 #define ROT_17 25
239 #define ROT_18 21
240 #define ROT_19 56
241 #define ROT_20 27
242 #define ROT_21 20
243 #define ROT_22 39
244 #define ROT_23 8
245 #define ROT_24 14
246
247 static const uint64_t roundconstants[KECCAK_ROUNDS] = {
248 0x0000000000000001ULL,
249 0x0000000000008082ULL,
250 0x800000000000808aULL,
251 0x8000000080008000ULL,
252 0x000000000000808bULL,
253 0x0000000080000001ULL,
254 0x8000000080008081ULL,
255 0x8000000000008009ULL,
256 0x000000000000008aULL,
257 0x0000000000000088ULL,
258 0x0000000080008009ULL,
259 0x000000008000000aULL,
260 0x000000008000808bULL,
261 0x800000000000008bULL,
262 0x8000000000008089ULL,
263 0x8000000000008003ULL,
264 0x8000000000008002ULL,
265 0x8000000000000080ULL,
266 0x000000000000800aULL,
267 0x800000008000000aULL,
268 0x8000000080008081ULL,
269 0x8000000000008080ULL,
270 0x0000000080000001ULL,
271 0x8000000080008008ULL
272 };
273
keccak_function(uint64_t * state)274 void keccak_function (uint64_t *state)
275 {
276 short i;
277
278 /* Temporary variables to avoid indexing overhead */
279 uint64_t a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12;
280 uint64_t a13, a14, a15, a16, a17, a18, a19, a20, a21, a22, a23, a24;
281
282 uint64_t b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12;
283 uint64_t b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24;
284
285 uint64_t c0, c1, c2, c3, c4, d;
286
287 a0 = state[0];
288 a1 = state[1];
289 a2 = state[2];
290 a3 = state[3];
291 a4 = state[4];
292 a5 = state[5];
293 a6 = state[6];
294 a7 = state[7];
295 a8 = state[8];
296 a9 = state[9];
297 a10 = state[10];
298 a11 = state[11];
299 a12 = state[12];
300 a13 = state[13];
301 a14 = state[14];
302 a15 = state[15];
303 a16 = state[16];
304 a17 = state[17];
305 a18 = state[18];
306 a19 = state[19];
307 a20 = state[20];
308 a21 = state[21];
309 a22 = state[22];
310 a23 = state[23];
311 a24 = state[24];
312
313 for (i = 0; i < KECCAK_ROUNDS; ++i) {
314 /*
315 Uses temporary variables and loop unrolling to
316 avoid array indexing and inner loops overhead
317 */
318
319 /* Prepare column parity for Theta step */
320 c0 = a0 ^ a5 ^ a10 ^ a15 ^ a20;
321 c1 = a1 ^ a6 ^ a11 ^ a16 ^ a21;
322 c2 = a2 ^ a7 ^ a12 ^ a17 ^ a22;
323 c3 = a3 ^ a8 ^ a13 ^ a18 ^ a23;
324 c4 = a4 ^ a9 ^ a14 ^ a19 ^ a24;
325
326 /* Theta + Rho + Pi steps */
327 d = c4 ^ ROL64(c1, 1);
328 b0 = d ^ a0;
329 b16 = ROL64(d ^ a5, ROT_01);
330 b7 = ROL64(d ^ a10, ROT_02);
331 b23 = ROL64(d ^ a15, ROT_03);
332 b14 = ROL64(d ^ a20, ROT_04);
333
334 d = c0 ^ ROL64(c2, 1);
335 b10 = ROL64(d ^ a1, ROT_05);
336 b1 = ROL64(d ^ a6, ROT_06);
337 b17 = ROL64(d ^ a11, ROT_07);
338 b8 = ROL64(d ^ a16, ROT_08);
339 b24 = ROL64(d ^ a21, ROT_09);
340
341 d = c1 ^ ROL64(c3, 1);
342 b20 = ROL64(d ^ a2, ROT_10);
343 b11 = ROL64(d ^ a7, ROT_11);
344 b2 = ROL64(d ^ a12, ROT_12);
345 b18 = ROL64(d ^ a17, ROT_13);
346 b9 = ROL64(d ^ a22, ROT_14);
347
348 d = c2 ^ ROL64(c4, 1);
349 b5 = ROL64(d ^ a3, ROT_15);
350 b21 = ROL64(d ^ a8, ROT_16);
351 b12 = ROL64(d ^ a13, ROT_17);
352 b3 = ROL64(d ^ a18, ROT_18);
353 b19 = ROL64(d ^ a23, ROT_19);
354
355 d = c3 ^ ROL64(c0, 1);
356 b15 = ROL64(d ^ a4, ROT_20);
357 b6 = ROL64(d ^ a9, ROT_21);
358 b22 = ROL64(d ^ a14, ROT_22);
359 b13 = ROL64(d ^ a19, ROT_23);
360 b4 = ROL64(d ^ a24, ROT_24);
361
362 /* Chi + Iota steps */
363 a0 = b0 ^ (~b1 & b2) ^ roundconstants[i];
364 a1 = b1 ^ (~b2 & b3);
365 a2 = b2 ^ (~b3 & b4);
366 a3 = b3 ^ (~b4 & b0);
367 a4 = b4 ^ (~b0 & b1);
368
369 a5 = b5 ^ (~b6 & b7);
370 a6 = b6 ^ (~b7 & b8);
371 a7 = b7 ^ (~b8 & b9);
372 a8 = b8 ^ (~b9 & b5);
373 a9 = b9 ^ (~b5 & b6);
374
375 a10 = b10 ^ (~b11 & b12);
376 a11 = b11 ^ (~b12 & b13);
377 a12 = b12 ^ (~b13 & b14);
378 a13 = b13 ^ (~b14 & b10);
379 a14 = b14 ^ (~b10 & b11);
380
381 a15 = b15 ^ (~b16 & b17);
382 a16 = b16 ^ (~b17 & b18);
383 a17 = b17 ^ (~b18 & b19);
384 a18 = b18 ^ (~b19 & b15);
385 a19 = b19 ^ (~b15 & b16);
386
387 a20 = b20 ^ (~b21 & b22);
388 a21 = b21 ^ (~b22 & b23);
389 a22 = b22 ^ (~b23 & b24);
390 a23 = b23 ^ (~b24 & b20);
391 a24 = b24 ^ (~b20 & b21);
392 }
393
394 state[0] = a0;
395 state[1] = a1;
396 state[2] = a2;
397 state[3] = a3;
398 state[4] = a4;
399 state[5] = a5;
400 state[6] = a6;
401 state[7] = a7;
402 state[8] = a8;
403 state[9] = a9;
404 state[10] = a10;
405 state[11] = a11;
406 state[12] = a12;
407 state[13] = a13;
408 state[14] = a14;
409 state[15] = a15;
410 state[16] = a16;
411 state[17] = a17;
412 state[18] = a18;
413 state[19] = a19;
414 state[20] = a20;
415 state[21] = a21;
416 state[22] = a22;
417 state[23] = a23;
418 state[24] = a24;
419 }
420
421
422