keccak.c
Go to the documentation of this file.
1 /**
2  * @file keccak.c
3  * @brief Keccak sponge function
4  *
5  * @section License
6  *
7  * Copyright (C) 2010-2018 Oryx Embedded SARL. All rights reserved.
8  *
9  * This file is part of CycloneCrypto Open.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24  *
25  * @author Oryx Embedded SARL (www.oryx-embedded.com)
26  * @version 1.9.0
27  **/
28 
29 //Switch to the appropriate trace level
30 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
31 
32 //Dependencies
33 #include "core/crypto.h"
34 #include "xof/keccak.h"
35 
36 //Check crypto library configuration
37 #if (KECCAK_SUPPORT == ENABLED)
38 
39 //Keccak round constants
40 static const keccak_lane_t rc[KECCAK_NR] =
41 {
42  (keccak_lane_t) 0x0000000000000001,
43  (keccak_lane_t) 0x0000000000008082,
44  (keccak_lane_t) 0x800000000000808A,
45  (keccak_lane_t) 0x8000000080008000,
46  (keccak_lane_t) 0x000000000000808B,
47  (keccak_lane_t) 0x0000000080000001,
48  (keccak_lane_t) 0x8000000080008081,
49  (keccak_lane_t) 0x8000000000008009,
50  (keccak_lane_t) 0x000000000000008A,
51  (keccak_lane_t) 0x0000000000000088,
52  (keccak_lane_t) 0x0000000080008009,
53  (keccak_lane_t) 0x000000008000000A,
54  (keccak_lane_t) 0x000000008000808B,
55  (keccak_lane_t) 0x800000000000008B,
56  (keccak_lane_t) 0x8000000000008089,
57  (keccak_lane_t) 0x8000000000008003,
58  (keccak_lane_t) 0x8000000000008002,
59  (keccak_lane_t) 0x8000000000000080,
60 #if (KECCAK_L >= 4)
61  (keccak_lane_t) 0x000000000000800A,
62  (keccak_lane_t) 0x800000008000000A,
63 #endif
64 #if (KECCAK_L >= 5)
65  (keccak_lane_t) 0x8000000080008081,
66  (keccak_lane_t) 0x8000000000008080,
67 #endif
68 #if (KECCAK_L >= 6)
69  (keccak_lane_t) 0x0000000080000001,
70  (keccak_lane_t) 0x8000000080008008
71 #endif
72 };
73 
74 
75 /**
76  * @brief Apply theta transformation
77  * @param[in,out] a State array
78  **/
79 
80 static void theta(keccak_lane_t a[5][5])
81 {
82  keccak_lane_t c[5];
83  keccak_lane_t d[5];
84 
85  //The effect of the theta transformation is to XOR each bit in the
86  //state with the parities of two columns in the array
87  c[0] = a[0][0] ^ a[1][0] ^ a[2][0] ^ a[3][0] ^ a[4][0];
88  c[1] = a[0][1] ^ a[1][1] ^ a[2][1] ^ a[3][1] ^ a[4][1];
89  c[2] = a[0][2] ^ a[1][2] ^ a[2][2] ^ a[3][2] ^ a[4][2];
90  c[3] = a[0][3] ^ a[1][3] ^ a[2][3] ^ a[3][3] ^ a[4][3];
91  c[4] = a[0][4] ^ a[1][4] ^ a[2][4] ^ a[3][4] ^ a[4][4];
92 
93  d[0] = c[4] ^ KECCAK_ROL(c[1], 1);
94  d[1] = c[0] ^ KECCAK_ROL(c[2], 1);
95  d[2] = c[1] ^ KECCAK_ROL(c[3], 1);
96  d[3] = c[2] ^ KECCAK_ROL(c[4], 1);
97  d[4] = c[3] ^ KECCAK_ROL(c[0], 1);
98 
99  a[0][0] ^= d[0];
100  a[1][0] ^= d[0];
101  a[2][0] ^= d[0];
102  a[3][0] ^= d[0];
103  a[4][0] ^= d[0];
104 
105  a[0][1] ^= d[1];
106  a[1][1] ^= d[1];
107  a[2][1] ^= d[1];
108  a[3][1] ^= d[1];
109  a[4][1] ^= d[1];
110 
111  a[0][2] ^= d[2];
112  a[1][2] ^= d[2];
113  a[2][2] ^= d[2];
114  a[3][2] ^= d[2];
115  a[4][2] ^= d[2];
116 
117  a[0][3] ^= d[3];
118  a[1][3] ^= d[3];
119  a[2][3] ^= d[3];
120  a[3][3] ^= d[3];
121  a[4][3] ^= d[3];
122 
123  a[0][4] ^= d[4];
124  a[1][4] ^= d[4];
125  a[2][4] ^= d[4];
126  a[3][4] ^= d[4];
127  a[4][4] ^= d[4];
128 }
129 
130 
131 /**
132  * @brief Apply rho transformation
133  * @param[in,out] a State array
134  **/
135 
136 static void rho(keccak_lane_t a[5][5])
137 {
138  //The effect of the rho transformation is to rotate the bits of each lane by
139  //an offset, which depends on the fixed x and y coordinates of the lane
140  a[0][1] = KECCAK_ROL(a[0][1], 1 % KECCAK_W);
141  a[0][2] = KECCAK_ROL(a[0][2], 190 % KECCAK_W);
142  a[0][3] = KECCAK_ROL(a[0][3], 28 % KECCAK_W);
143  a[0][4] = KECCAK_ROL(a[0][4], 91 % KECCAK_W);
144 
145  a[1][0] = KECCAK_ROL(a[1][0], 36 % KECCAK_W);
146  a[1][1] = KECCAK_ROL(a[1][1], 300 % KECCAK_W);
147  a[1][2] = KECCAK_ROL(a[1][2], 6 % KECCAK_W);
148  a[1][3] = KECCAK_ROL(a[1][3], 55 % KECCAK_W);
149  a[1][4] = KECCAK_ROL(a[1][4], 276 % KECCAK_W);
150 
151  a[2][0] = KECCAK_ROL(a[2][0], 3 % KECCAK_W);
152  a[2][1] = KECCAK_ROL(a[2][1], 10 % KECCAK_W);
153  a[2][2] = KECCAK_ROL(a[2][2], 171 % KECCAK_W);
154  a[2][3] = KECCAK_ROL(a[2][3], 153 % KECCAK_W);
155  a[2][4] = KECCAK_ROL(a[2][4], 231 % KECCAK_W);
156 
157  a[3][0] = KECCAK_ROL(a[3][0], 105 % KECCAK_W);
158  a[3][1] = KECCAK_ROL(a[3][1], 45 % KECCAK_W);
159  a[3][2] = KECCAK_ROL(a[3][2], 15 % KECCAK_W);
160  a[3][3] = KECCAK_ROL(a[3][3], 21 % KECCAK_W);
161  a[3][4] = KECCAK_ROL(a[3][4], 136 % KECCAK_W);
162 
163  a[4][0] = KECCAK_ROL(a[4][0], 210 % KECCAK_W);
164  a[4][1] = KECCAK_ROL(a[4][1], 66 % KECCAK_W);
165  a[4][2] = KECCAK_ROL(a[4][2], 253 % KECCAK_W);
166  a[4][3] = KECCAK_ROL(a[4][3], 120 % KECCAK_W);
167  a[4][4] = KECCAK_ROL(a[4][4], 78 % KECCAK_W);
168 }
169 
170 
171 /**
172  * @brief Apply pi transformation
173  * @param[in,out] a State array
174  **/
175 
176 static void pi(keccak_lane_t a[5][5])
177 {
178  keccak_lane_t temp;
179 
180  //The effect of the pi transformation is to rearrange the
181  //positions of the lanes
182  temp = a[0][1];
183  a[0][1] = a[1][1];
184  a[1][1] = a[1][4];
185  a[1][4] = a[4][2];
186  a[4][2] = a[2][4];
187  a[2][4] = a[4][0];
188  a[4][0] = a[0][2];
189  a[0][2] = a[2][2];
190  a[2][2] = a[2][3];
191  a[2][3] = a[3][4];
192  a[3][4] = a[4][3];
193  a[4][3] = a[3][0];
194  a[3][0] = a[0][4];
195  a[0][4] = a[4][4];
196  a[4][4] = a[4][1];
197  a[4][1] = a[1][3];
198  a[1][3] = a[3][1];
199  a[3][1] = a[1][0];
200  a[1][0] = a[0][3];
201  a[0][3] = a[3][3];
202  a[3][3] = a[3][2];
203  a[3][2] = a[2][1];
204  a[2][1] = a[1][2];
205  a[1][2] = a[2][0];
206  a[2][0] = temp;
207 }
208 
209 
210 /**
211  * @brief Apply chi transformation
212  * @param[in,out] a State array
213  **/
214 
215 static void chi(keccak_lane_t a[5][5])
216 {
217  keccak_lane_t temp1;
218  keccak_lane_t temp2;
219 
220  //The effect of the chi transformation is to XOR each bit with
221  //a non linear function of two other bits in its row
222  temp1 = a[0][0];
223  temp2 = a[0][1];
224  a[0][0] ^= ~a[0][1] & a[0][2];
225  a[0][1] ^= ~a[0][2] & a[0][3];
226  a[0][2] ^= ~a[0][3] & a[0][4];
227  a[0][3] ^= ~a[0][4] & temp1;
228  a[0][4] ^= ~temp1 & temp2;
229 
230  temp1 = a[1][0];
231  temp2 = a[1][1];
232  a[1][0] ^= ~a[1][1] & a[1][2];
233  a[1][1] ^= ~a[1][2] & a[1][3];
234  a[1][2] ^= ~a[1][3] & a[1][4];
235  a[1][3] ^= ~a[1][4] & temp1;
236  a[1][4] ^= ~temp1 & temp2;
237 
238  temp1 = a[2][0];
239  temp2 = a[2][1];
240  a[2][0] ^= ~a[2][1] & a[2][2];
241  a[2][1] ^= ~a[2][2] & a[2][3];
242  a[2][2] ^= ~a[2][3] & a[2][4];
243  a[2][3] ^= ~a[2][4] & temp1;
244  a[2][4] ^= ~temp1 & temp2;
245 
246  temp1 = a[3][0];
247  temp2 = a[3][1];
248  a[3][0] ^= ~a[3][1] & a[3][2];
249  a[3][1] ^= ~a[3][2] & a[3][3];
250  a[3][2] ^= ~a[3][3] & a[3][4];
251  a[3][3] ^= ~a[3][4] & temp1;
252  a[3][4] ^= ~temp1 & temp2;
253 
254  temp1 = a[4][0];
255  temp2 = a[4][1];
256  a[4][0] ^= ~a[4][1] & a[4][2];
257  a[4][1] ^= ~a[4][2] & a[4][3];
258  a[4][2] ^= ~a[4][3] & a[4][4];
259  a[4][3] ^= ~a[4][4] & temp1;
260  a[4][4] ^= ~temp1 & temp2;
261 }
262 
263 
264 /**
265  * @brief Apply iota transformation
266  * @param[in,out] a State array
267  * @param[index] round Round index
268  **/
269 
270 static void iota(keccak_lane_t a[5][5], uint_t index)
271 {
272  //The iota transformation is parameterized by the round index
273  a[0][0] ^= rc[index];
274 }
275 
276 
277 /**
278  * @brief Initialize Keccak context
279  * @param[in] context Pointer to the Keccak context to initialize
280  * @param[in] capacity Capacity of the sponge function
281  **/
282 
284 {
285  uint_t rate;
286 
287  //Clear Keccak context
288  cryptoMemset(context, 0, sizeof(KeccakContext));
289 
290  //The capacity cannot exceed the width of a Keccak-p permutation
291  if(capacity >= KECCAK_B)
293 
294  //The rate depends on the capacity of the sponge function
295  rate = KECCAK_B - capacity;
296 
297  //The rate must be multiple of the lane size
298  if((rate % KECCAK_W) != 0)
300 
301  //Save the block size, in bytes
302  context->blockSize = rate / 8;
303 
304  //Successful initialization
305  return NO_ERROR;
306 }
307 
308 
309 /**
310  * @brief Absorb data
311  * @param[in] context Pointer to the Keccak context
312  * @param[in] input Pointer to the buffer being hashed
313  * @param[in] length Length of the buffer
314  **/
315 
316 void keccakAbsorb(KeccakContext *context, const void *input, size_t length)
317 {
318  uint_t i;
319  size_t n;
320  keccak_lane_t *a;
321 
322  //Point to the state array
323  a = (keccak_lane_t *) context->a;
324 
325  //Absorbing phase
326  while(length > 0)
327  {
328  //Limit the number of bytes to process at a time
329  n = MIN(length, context->blockSize - context->length);
330 
331  //Copy the data to the buffer
332  cryptoMemcpy(context->buffer + context->length, input, n);
333 
334  //Number of data bytes that have been buffered
335  context->length += n;
336 
337  //Advance the data pointer
338  input = (uint8_t *) input + n;
339  //Remaining bytes to process
340  length -= n;
341 
342  //Absorb the message block by block
343  if(context->length == context->blockSize)
344  {
345  //Absorb the current block
346  for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
347  {
348  a[i] ^= KECCAK_LETOH(context->block[i]);
349  }
350 
351  //Apply block permutation function
352  keccakPermutBlock(context);
353 
354  //The input buffer is empty
355  context->length = 0;
356  }
357  }
358 }
359 
360 
361 /**
362  * @brief Finish absorbing phase
363  * @param[in] context Pointer to the Keccak context
364  * @param[in] pad Value of the padding byte (0x01 for Keccak, 0x06 for SHA-3 and 0x1F for XOF)
365  **/
366 
367 void keccakFinal(KeccakContext *context, uint8_t pad)
368 {
369  uint_t i;
370  size_t q;
371  keccak_lane_t *a;
372 
373  //Point to the state array
374  a = (keccak_lane_t *) context->a;
375 
376  //Compute the number of padding bytes
377  q = context->blockSize - context->length;
378 
379  //Append padding
380  cryptoMemset(context->buffer + context->length, 0, q);
381  context->buffer[context->length] |= pad;
382  context->buffer[context->blockSize - 1] |= 0x80;
383 
384  //Absorb the final block
385  for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
386  {
387  a[i] ^= KECCAK_LETOH(context->block[i]);
388  }
389 
390  //Apply block permutation function
391  keccakPermutBlock(context);
392 
393  //Convert lanes to little-endian byte order
394  for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
395  {
396  a[i] = KECCAK_HTOLE(a[i]);
397  }
398 
399  //Number of bytes available in the output buffer
400  context->length = context->blockSize;
401 }
402 
403 
404 /**
405  * @brief Extract data from the squeezing phase
406  * @param[in] context Pointer to the Keccak context
407  * @param[out] output Output string
408  * @param[in] length Desired output length, in bytes
409  **/
410 
411 void keccakSqueeze(KeccakContext *context, uint8_t *output, size_t length)
412 {
413  uint_t i;
414  size_t n;
415  keccak_lane_t *a;
416 
417  //Point to the state array
418  a = (keccak_lane_t *) context->a;
419 
420  //An arbitrary number of output bits can be squeezed out of the state
421  while(length > 0)
422  {
423  //Check whether more data is required
424  if(context->length == 0)
425  {
426  //Convert lanes to host byte order
427  for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
428  {
429  a[i] = KECCAK_LETOH(a[i]);
430  }
431 
432  //Apply block permutation function
433  keccakPermutBlock(context);
434 
435  //Convert lanes to little-endian byte order
436  for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
437  {
438  a[i] = KECCAK_HTOLE(a[i]);
439  }
440 
441  //Number of bytes available in the output buffer
442  context->length = context->blockSize;
443  }
444 
445  //Compute the number of bytes to process at a time
446  n = MIN(length, context->length);
447 
448  //Copy the output string
449  if(output != NULL)
450  {
451  cryptoMemcpy(output, context->digest + context->blockSize -
452  context->length, n);
453  }
454 
455  //Number of bytes available in the output buffer
456  context->length -= n;
457 
458  //Advance the data pointer
459  output = (uint8_t *) output + n;
460  //Number of bytes that remains to be written
461  length -= n;
462  }
463 }
464 
465 
466 /**
467  * @brief Block permutation
468  * @param[in] context Pointer to the Keccak context
469  **/
470 
472 {
473  uint_t i;
474 
475  //Each round consists of a sequence of five transformations,
476  //which are called the step mappings
477  for(i = 0; i < KECCAK_NR; i++)
478  {
479  //Apply theta step mapping
480  theta(context->a);
481  //Apply rho step mapping
482  rho(context->a);
483  //Apply pi step mapping
484  pi(context->a);
485  //Apply chi step mapping
486  chi(context->a);
487  //Apply iota step mapping
488  iota(context->a, i);
489  }
490 }
491 
492 #endif
#define KECCAK_LETOH(a)
Definition: keccak.h:76
uint8_t buffer[1]
Definition: keccak.h:115
#define KECCAK_HTOLE(a)
Definition: keccak.h:74
uint8_t c
Definition: ndp.h:510
#define cryptoMemcpy(dest, src, length)
Definition: crypto.h:590
General definitions for cryptographic algorithms.
Invalid parameter.
Definition: error.h:45
Keccak sponge function.
uint8_t digest[1]
Definition: keccak.h:110
uint8_t a
Definition: ndp.h:407
void keccakAbsorb(KeccakContext *context, const void *input, size_t length)
Absorb data.
Definition: keccak.c:316
void keccakSqueeze(KeccakContext *context, uint8_t *output, size_t length)
Extract data from the squeezing phase.
Definition: keccak.c:411
Keccak context.
Definition: keccak.h:105
#define KECCAK_NR
Definition: keccak.h:86
keccak_lane_t block[24]
Definition: keccak.h:114
#define KECCAK_ROL(a, n)
Definition: keccak.h:72
void keccakPermutBlock(KeccakContext *context)
Block permutation.
Definition: keccak.c:471
error_t keccakInit(KeccakContext *context, uint_t capacity)
Initialize Keccak context.
Definition: keccak.c:283
#define KECCAK_B
Definition: keccak.h:84
#define MIN(a, b)
Definition: os_port.h:60
uint_t blockSize
Definition: keccak.h:117
Success.
Definition: error.h:42
error_t
Error codes.
Definition: error.h:40
unsigned int uint_t
Definition: compiler_port.h:43
#define KECCAK_W
Definition: keccak.h:82
#define cryptoMemset(p, value, length)
Definition: crypto.h:584
#define keccak_lane_t
Definition: keccak.h:70
uint8_t length
Definition: dtls_misc.h:140
uint8_t n
void keccakFinal(KeccakContext *context, uint8_t pad)
Finish absorbing phase.
Definition: keccak.c:367
keccak_lane_t a[5][5]
Definition: keccak.h:109
size_t length
Definition: keccak.h:118