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