keccak.c

00001 /**
00002  * @file keccak.c
00003  * @brief Keccak sponge function
00004  *
00005  * @section License
00006  *
00007  * Copyright (C) 2010-2017 Oryx Embedded SARL. All rights reserved.
00008  *
00009  * This file is part of CycloneCrypto Open.
00010  *
00011  * This program is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU General Public License
00013  * as published by the Free Software Foundation; either version 2
00014  * of the License, or (at your option) any later version.
00015  *
00016  * This program is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  * GNU General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU General Public License
00022  * along with this program; if not, write to the Free Software Foundation,
00023  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00024  *
00025  * @author Oryx Embedded SARL (www.oryx-embedded.com)
00026  * @version 1.7.6
00027  **/
00028 
00029 //Switch to the appropriate trace level
00030 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
00031 
00032 //Dependencies
00033 #include <string.h>
00034 #include "crypto.h"
00035 #include "keccak.h"
00036 
00037 //Check crypto library configuration
00038 #if (KECCAK_SUPPORT == ENABLED)
00039 
00040 //Keccak round constants
00041 static const keccak_lane_t rc[KECCAK_NR] =
00042 {
00043    (keccak_lane_t) 0x0000000000000001,
00044    (keccak_lane_t) 0x0000000000008082,
00045    (keccak_lane_t) 0x800000000000808A,
00046    (keccak_lane_t) 0x8000000080008000,
00047    (keccak_lane_t) 0x000000000000808B,
00048    (keccak_lane_t) 0x0000000080000001,
00049    (keccak_lane_t) 0x8000000080008081,
00050    (keccak_lane_t) 0x8000000000008009,
00051    (keccak_lane_t) 0x000000000000008A,
00052    (keccak_lane_t) 0x0000000000000088,
00053    (keccak_lane_t) 0x0000000080008009,
00054    (keccak_lane_t) 0x000000008000000A,
00055    (keccak_lane_t) 0x000000008000808B,
00056    (keccak_lane_t) 0x800000000000008B,
00057    (keccak_lane_t) 0x8000000000008089,
00058    (keccak_lane_t) 0x8000000000008003,
00059    (keccak_lane_t) 0x8000000000008002,
00060    (keccak_lane_t) 0x8000000000000080,
00061 #if (KECCAK_L >= 4)
00062    (keccak_lane_t) 0x000000000000800A,
00063    (keccak_lane_t) 0x800000008000000A,
00064 #endif
00065 #if (KECCAK_L >= 5)
00066    (keccak_lane_t) 0x8000000080008081,
00067    (keccak_lane_t) 0x8000000000008080,
00068 #endif
00069 #if (KECCAK_L >= 6)
00070    (keccak_lane_t) 0x0000000080000001,
00071    (keccak_lane_t) 0x8000000080008008
00072 #endif
00073 };
00074 
00075 
00076 /**
00077  * @brief Apply theta transformation
00078  * @param[in,out] a State array
00079  **/
00080 
00081 static void theta(keccak_lane_t a[5][5])
00082 {
00083    keccak_lane_t c[5];
00084    keccak_lane_t d[5];
00085 
00086    //The effect of the theta transformation is to XOR each bit in the
00087    //state with the parities of two columns in the array
00088    c[0] = a[0][0] ^ a[1][0] ^ a[2][0] ^ a[3][0] ^ a[4][0];
00089    c[1] = a[0][1] ^ a[1][1] ^ a[2][1] ^ a[3][1] ^ a[4][1];
00090    c[2] = a[0][2] ^ a[1][2] ^ a[2][2] ^ a[3][2] ^ a[4][2];
00091    c[3] = a[0][3] ^ a[1][3] ^ a[2][3] ^ a[3][3] ^ a[4][3];
00092    c[4] = a[0][4] ^ a[1][4] ^ a[2][4] ^ a[3][4] ^ a[4][4];
00093 
00094    d[0] = c[4] ^ KECCAK_ROL(c[1], 1);
00095    d[1] = c[0] ^ KECCAK_ROL(c[2], 1);
00096    d[2] = c[1] ^ KECCAK_ROL(c[3], 1);
00097    d[3] = c[2] ^ KECCAK_ROL(c[4], 1);
00098    d[4] = c[3] ^ KECCAK_ROL(c[0], 1);
00099 
00100    a[0][0] ^= d[0];
00101    a[1][0] ^= d[0];
00102    a[2][0] ^= d[0];
00103    a[3][0] ^= d[0];
00104    a[4][0] ^= d[0];
00105 
00106    a[0][1] ^= d[1];
00107    a[1][1] ^= d[1];
00108    a[2][1] ^= d[1];
00109    a[3][1] ^= d[1];
00110    a[4][1] ^= d[1];
00111 
00112    a[0][2] ^= d[2];
00113    a[1][2] ^= d[2];
00114    a[2][2] ^= d[2];
00115    a[3][2] ^= d[2];
00116    a[4][2] ^= d[2];
00117 
00118    a[0][3] ^= d[3];
00119    a[1][3] ^= d[3];
00120    a[2][3] ^= d[3];
00121    a[3][3] ^= d[3];
00122    a[4][3] ^= d[3];
00123 
00124    a[0][4] ^= d[4];
00125    a[1][4] ^= d[4];
00126    a[2][4] ^= d[4];
00127    a[3][4] ^= d[4];
00128    a[4][4] ^= d[4];
00129 }
00130 
00131 
00132 /**
00133  * @brief Apply rho transformation
00134  * @param[in,out] a State array
00135  **/
00136 
00137 static void rho(keccak_lane_t a[5][5])
00138 {
00139    //The effect of the rho transformation is to rotate the bits of each lane by
00140    //an offset, which depends on the fixed x and y coordinates of the lane
00141    a[0][1] = KECCAK_ROL(a[0][1], 1   % KECCAK_W);
00142    a[0][2] = KECCAK_ROL(a[0][2], 190 % KECCAK_W);
00143    a[0][3] = KECCAK_ROL(a[0][3], 28  % KECCAK_W);
00144    a[0][4] = KECCAK_ROL(a[0][4], 91  % KECCAK_W);
00145 
00146    a[1][0] = KECCAK_ROL(a[1][0], 36  % KECCAK_W);
00147    a[1][1] = KECCAK_ROL(a[1][1], 300 % KECCAK_W);
00148    a[1][2] = KECCAK_ROL(a[1][2], 6   % KECCAK_W);
00149    a[1][3] = KECCAK_ROL(a[1][3], 55  % KECCAK_W);
00150    a[1][4] = KECCAK_ROL(a[1][4], 276 % KECCAK_W);
00151 
00152    a[2][0] = KECCAK_ROL(a[2][0], 3   % KECCAK_W);
00153    a[2][1] = KECCAK_ROL(a[2][1], 10  % KECCAK_W);
00154    a[2][2] = KECCAK_ROL(a[2][2], 171 % KECCAK_W);
00155    a[2][3] = KECCAK_ROL(a[2][3], 153 % KECCAK_W);
00156    a[2][4] = KECCAK_ROL(a[2][4], 231 % KECCAK_W);
00157 
00158    a[3][0] = KECCAK_ROL(a[3][0], 105 % KECCAK_W);
00159    a[3][1] = KECCAK_ROL(a[3][1], 45  % KECCAK_W);
00160    a[3][2] = KECCAK_ROL(a[3][2], 15  % KECCAK_W);
00161    a[3][3] = KECCAK_ROL(a[3][3], 21  % KECCAK_W);
00162    a[3][4] = KECCAK_ROL(a[3][4], 136 % KECCAK_W);
00163 
00164    a[4][0] = KECCAK_ROL(a[4][0], 210 % KECCAK_W);
00165    a[4][1] = KECCAK_ROL(a[4][1], 66  % KECCAK_W);
00166    a[4][2] = KECCAK_ROL(a[4][2], 253 % KECCAK_W);
00167    a[4][3] = KECCAK_ROL(a[4][3], 120 % KECCAK_W);
00168    a[4][4] = KECCAK_ROL(a[4][4], 78  % KECCAK_W);
00169 }
00170 
00171 
00172 /**
00173  * @brief Apply pi transformation
00174  * @param[in,out] a State array
00175  **/
00176 
00177 static void pi(keccak_lane_t a[5][5])
00178 {
00179    keccak_lane_t temp;
00180 
00181    //The effect of the pi transformation is to rearrange the
00182    //positions of the lanes
00183    temp = a[0][1];
00184    a[0][1] = a[1][1];
00185    a[1][1] = a[1][4];
00186    a[1][4] = a[4][2];
00187    a[4][2] = a[2][4];
00188    a[2][4] = a[4][0];
00189    a[4][0] = a[0][2];
00190    a[0][2] = a[2][2];
00191    a[2][2] = a[2][3];
00192    a[2][3] = a[3][4];
00193    a[3][4] = a[4][3];
00194    a[4][3] = a[3][0];
00195    a[3][0] = a[0][4];
00196    a[0][4] = a[4][4];
00197    a[4][4] = a[4][1];
00198    a[4][1] = a[1][3];
00199    a[1][3] = a[3][1];
00200    a[3][1] = a[1][0];
00201    a[1][0] = a[0][3];
00202    a[0][3] = a[3][3];
00203    a[3][3] = a[3][2];
00204    a[3][2] = a[2][1];
00205    a[2][1] = a[1][2];
00206    a[1][2] = a[2][0];
00207    a[2][0] = temp;
00208 }
00209 
00210 
00211 /**
00212  * @brief Apply chi transformation
00213  * @param[in,out] a State array
00214  **/
00215 
00216 static void chi(keccak_lane_t a[5][5])
00217 {
00218    keccak_lane_t temp1;
00219    keccak_lane_t temp2;
00220 
00221    //The effect of the chi transformation is to XOR each bit with
00222    //a non linear function of two other bits in its row
00223    temp1 = a[0][0];
00224    temp2 = a[0][1];
00225    a[0][0] ^= ~a[0][1] & a[0][2];
00226    a[0][1] ^= ~a[0][2] & a[0][3];
00227    a[0][2] ^= ~a[0][3] & a[0][4];
00228    a[0][3] ^= ~a[0][4] & temp1;
00229    a[0][4] ^= ~temp1 & temp2;
00230 
00231    temp1 = a[1][0];
00232    temp2 = a[1][1];
00233    a[1][0] ^= ~a[1][1] & a[1][2];
00234    a[1][1] ^= ~a[1][2] & a[1][3];
00235    a[1][2] ^= ~a[1][3] & a[1][4];
00236    a[1][3] ^= ~a[1][4] & temp1;
00237    a[1][4] ^= ~temp1 & temp2;
00238 
00239    temp1 = a[2][0];
00240    temp2 = a[2][1];
00241    a[2][0] ^= ~a[2][1] & a[2][2];
00242    a[2][1] ^= ~a[2][2] & a[2][3];
00243    a[2][2] ^= ~a[2][3] & a[2][4];
00244    a[2][3] ^= ~a[2][4] & temp1;
00245    a[2][4] ^= ~temp1 & temp2;
00246 
00247    temp1 = a[3][0];
00248    temp2 = a[3][1];
00249    a[3][0] ^= ~a[3][1] & a[3][2];
00250    a[3][1] ^= ~a[3][2] & a[3][3];
00251    a[3][2] ^= ~a[3][3] & a[3][4];
00252    a[3][3] ^= ~a[3][4] & temp1;
00253    a[3][4] ^= ~temp1 & temp2;
00254 
00255    temp1 = a[4][0];
00256    temp2 = a[4][1];
00257    a[4][0] ^= ~a[4][1] & a[4][2];
00258    a[4][1] ^= ~a[4][2] & a[4][3];
00259    a[4][2] ^= ~a[4][3] & a[4][4];
00260    a[4][3] ^= ~a[4][4] & temp1;
00261    a[4][4] ^= ~temp1 & temp2;
00262 }
00263 
00264 
00265 /**
00266  * @brief Apply iota transformation
00267  * @param[in,out] a State array
00268  * @param[index] round Round index
00269  **/
00270 
00271 static iota(keccak_lane_t a[5][5], uint_t index)
00272 {
00273    //The iota transformation is parameterized by the round index
00274    a[0][0] ^= rc[index];
00275 }
00276 
00277 
00278 /**
00279  * @brief Initialize Keccak context
00280  * @param[in] context Pointer to the Keccak context to initialize
00281  * @param[in] capacity Capacity of the sponge function
00282  **/
00283 
00284 error_t keccakInit(KeccakContext *context, uint_t capacity)
00285 {
00286    uint_t rate;
00287 
00288    //Clear Keccak context
00289    memset(context, 0, sizeof(KeccakContext));
00290 
00291    //The capacity cannot exceed the width of a Keccak-p permutation
00292    if(capacity > KECCAK_B)
00293       return ERROR_INVALID_PARAMETER;
00294 
00295    //The rate depends on the capacity of the sponge function
00296    rate = KECCAK_B - capacity;
00297 
00298    //The rate must be multiple of the lane size
00299    if(rate % KECCAK_W)
00300       return ERROR_INVALID_PARAMETER;
00301 
00302    //Save the block size, in bytes
00303    context->blockSize = rate / 8;
00304 
00305    //Successful initialization
00306    return NO_ERROR;
00307 }
00308 
00309 
00310 /**
00311  * @brief Absorb data
00312  * @param[in] context Pointer to the Keccak context
00313  * @param[in] input Pointer to the buffer being hashed
00314  * @param[in] length Length of the buffer
00315  **/
00316 
00317 void keccakAbsorb(KeccakContext *context, const void *input, size_t length)
00318 {
00319    uint_t i;
00320    size_t n;
00321    keccak_lane_t *a;
00322 
00323    //Point to the state array
00324    a = (keccak_lane_t *) context->a;
00325 
00326    //Absorbing phase
00327    while(length > 0)
00328    {
00329       //Limit the number of bytes to process at a time
00330       n = MIN(length, context->blockSize - context->length);
00331 
00332       //Copy the data to the buffer
00333       memcpy(context->buffer + context->length, input, n);
00334 
00335       //Number of data bytes that have been buffered
00336       context->length += n;
00337 
00338       //Advance the data pointer
00339       input = (uint8_t *) input + n;
00340       //Remaining bytes to process
00341       length -= n;
00342 
00343       //Absorb the message block by block
00344       if(context->length == context->blockSize)
00345       {
00346          //Absorb the current block
00347          for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
00348             a[i] ^= KECCAK_LETOH(context->block[i]);
00349 
00350          //Apply block permutation function
00351          keccakPermutBlock(context);
00352 
00353          //The input buffer is empty
00354          context->length = 0;
00355       }
00356    }
00357 }
00358 
00359 
00360 /**
00361  * @brief Finish absorbing phase
00362  * @param[in] context Pointer to the Keccak context
00363  * @param[in] pad Value of the padding byte (0x01 for Keccak, 0x06 for SHA-3 and 0x1F for XOF)
00364  **/
00365 
00366 void keccakFinal(KeccakContext *context, uint8_t pad)
00367 {
00368    uint_t i;
00369    size_t q;
00370    keccak_lane_t *a;
00371 
00372    //Point to the state array
00373    a = (keccak_lane_t *) context->a;
00374 
00375    //Compute the number of padding bytes
00376    q = context->blockSize - context->length;
00377 
00378    //Append padding
00379    memset(context->buffer + context->length, 0, q);
00380    context->buffer[context->length] |= pad;
00381    context->buffer[context->blockSize - 1] |= 0x80;
00382 
00383    //Absorb the final block
00384    for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
00385       a[i] ^= KECCAK_LETOH(context->block[i]);
00386 
00387    //Apply block permutation function
00388    keccakPermutBlock(context);
00389 
00390    //Convert lanes to little-endian byte order
00391    for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
00392       a[i] = KECCAK_HTOLE(a[i]);
00393 
00394    //Number of bytes available in the output buffer
00395    context->length = context->blockSize;
00396 }
00397 
00398 
00399 /**
00400  * @brief Extract data from the squeezing phase
00401  * @param[in] context Pointer to the Keccak context
00402  * @param[out] output Output string
00403  * @param[in] length Desired output length, in bytes
00404  **/
00405 
00406 void keccakSqueeze(KeccakContext *context, uint8_t *output, size_t length)
00407 {
00408    uint_t i;
00409    size_t n;
00410    keccak_lane_t *a;
00411 
00412    //Point to the state array
00413    a = (keccak_lane_t *) context->a;
00414 
00415    //An arbitrary number of output bits can be squeezed out of the state
00416    while(length > 0)
00417    {
00418       //Check whether more data is required
00419       if(context->length == 0)
00420       {
00421          //Convert lanes to host byte order
00422          for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
00423             a[i] = KECCAK_LETOH(a[i]);
00424 
00425          //Apply block permutation function
00426          keccakPermutBlock(context);
00427 
00428          //Convert lanes to little-endian byte order
00429          for(i = 0; i < context->blockSize / sizeof(keccak_lane_t); i++)
00430             a[i] = KECCAK_HTOLE(a[i]);
00431 
00432          //Number of bytes available in the output buffer
00433          context->length = context->blockSize;
00434       }
00435 
00436       //Compute the number of bytes to process at a time
00437       n = MIN(length, context->length);
00438 
00439       //Copy the output string
00440       if(output != NULL)
00441          memcpy(output, context->digest + context->blockSize - context->length, n);
00442 
00443       //Number of bytes available in the output buffer
00444       context->length -= n;
00445 
00446       //Advance the data pointer
00447       output = (uint8_t *) output + n;
00448       //Number of bytes that remains to be written
00449       length -= n;
00450    }
00451 }
00452 
00453 
00454 /**
00455  * @brief Block permutation
00456  * @param[in] context Pointer to the Keccak context
00457  **/
00458 
00459 void keccakPermutBlock(KeccakContext *context)
00460 {
00461    uint_t i;
00462 
00463    //Each round consists of a sequence of five transformations,
00464    //which are called the step mappings
00465    for(i = 0; i < KECCAK_NR; i++)
00466    {
00467       //Apply theta step mapping
00468       theta(context->a);
00469       //Apply rho step mapping
00470       rho(context->a);
00471       //Apply pi step mapping
00472       pi(context->a);
00473       //Apply chi step mapping
00474       chi(context->a);
00475       //Apply iota step mapping
00476       iota(context->a, i);
00477    }
00478 }
00479 
00480 #endif
00481