LCOV - code coverage report
Current view: top level - lib - sha3.c (source / functions) Hit Total Coverage
Test: lcov_coverage_final.info Lines: 79 81 97.5 %
Date: 2016-06-07 Functions: 8 8 100.0 %
Branches: 40 46 87.0 %

           Branch data     Line data    Source code
       1                 :            : /**
       2                 :            :  * \file lib/sha3.c
       3                 :            :  *
       4                 :            :  * \brief Implementation of SHA3
       5                 :            :  */
       6                 :            : 
       7                 :            : /*
       8                 :            : Implementation by the Keccak, Keyak and Ketje Teams, namely, Guido Bertoni,
       9                 :            : Joan Daemen, Michael Peeters, Gilles Van Assche and Ronny Van Keer, hereby
      10                 :            : denoted as "the implementer".
      11                 :            : 
      12                 :            : For more information, feedback or questions, please refer to our websites:
      13                 :            : http://keccak.noekeon.org/
      14                 :            : http://keyak.noekeon.org/
      15                 :            : http://ketje.noekeon.org/
      16                 :            : 
      17                 :            : To the extent possible under law, the implementer has waived all copyright
      18                 :            : and related or neighboring rights to the source code in this file.
      19                 :            : http://creativecommons.org/publicdomain/zero/1.0/
      20                 :            : */
      21                 :            : 
      22                 :            : /*
      23                 :            : ================================================================
      24                 :            : The purpose of this source file is to demonstrate a readable and compact
      25                 :            : implementation of all the Keccak instances approved in the FIPS 202 standard,
      26                 :            : including the hash functions and the extendable-output functions (XOFs).
      27                 :            : 
      28                 :            : We focused on clarity and on source-code compactness,
      29                 :            : rather than on the performance.
      30                 :            : 
      31                 :            : The advantages of this implementation are:
      32                 :            :     + The source code is compact, after removing the comments, that is. :-)
      33                 :            :     + There are no tables with arbitrary constants.
      34                 :            :     + For clarity, the comments link the operations to the specifications using
      35                 :            :         the same notation as much as possible.
      36                 :            :     + There is no restriction in cryptographic features. In particular,
      37                 :            :         the SHAKE128 and SHAKE256 XOFs can produce any output length.
      38                 :            :     + The code does not use much RAM, as all operations are done in place.
      39                 :            : 
      40                 :            : The drawbacks of this implementation are:
      41                 :            :     - There is no message queue. The whole message must be ready in a buffer.
      42                 :            :     - It is not optimized for peformance.
      43                 :            : 
      44                 :            : The implementation is even simpler on a little endian platform. Just define the
      45                 :            : LITTLE_ENDIAN symbol in that case.
      46                 :            : 
      47                 :            : For a more complete set of implementations, please refer to
      48                 :            : the Keccak Code Package at https://github.com/gvanas/KeccakCodePackage
      49                 :            : 
      50                 :            : For more information, please refer to:
      51                 :            :     * [Keccak Reference] http://keccak.noekeon.org/Keccak-reference-3.0.pdf
      52                 :            :     * [Keccak Specifications Summary] http://keccak.noekeon.org/specs_summary.html
      53                 :            : 
      54                 :            : This file uses UTF-8 encoding, as some comments use Greek letters.
      55                 :            : ================================================================
      56                 :            : */
      57                 :            : 
      58                 :            : /**
      59                 :            :   * Function to compute the Keccak[r, c] sponge function over a given input.
      60                 :            :   * @param  rate            The value of the rate r.
      61                 :            :   * @param  capacity        The value of the capacity c.
      62                 :            :   * @param  input           Pointer to the input message.
      63                 :            :   * @param  inputByteLen    The number of input bytes provided in the input message.
      64                 :            :   * @param  delimitedSuffix Bits that will be automatically appended to the end
      65                 :            :   *                         of the input message, as in domain separation.
      66                 :            :   *                         This is a byte containing from 0 to 7 bits
      67                 :            :   *                         These <i>n</i> bits must be in the least significant bit positions
      68                 :            :   *                         and must be delimited with a bit 1 at position <i>n</i>
      69                 :            :   *                         (counting from 0=LSB to 7=MSB) and followed by bits 0
      70                 :            :   *                         from position <i>n</i>+1 to position 7.
      71                 :            :   *                         Some examples:
      72                 :            :   *                             - If no bits are to be appended, then @a delimitedSuffix must be 0x01.
      73                 :            :   *                             - If the 2-bit sequence 0,1 is to be appended (as for SHA3-*), @a delimitedSuffix must be 0x06.
      74                 :            :   *                             - If the 4-bit sequence 1,1,1,1 is to be appended (as for SHAKE*), @a delimitedSuffix must be 0x1F.
      75                 :            :   *                             - If the 7-bit sequence 1,1,0,1,0,0,0 is to be absorbed, @a delimitedSuffix must be 0x8B.
      76                 :            :   * @param  output          Pointer to the buffer where to store the output.
      77                 :            :   * @param  outputByteLen   The number of output bytes desired.
      78                 :            :   * @pre    One must have r+c=1600 and the rate a multiple of 8 bits in this implementation.
      79                 :            :   */
      80                 :            : //void Keccak(unsigned int rate, unsigned int capacity, const unsigned char *input, unsigned long long int inputByteLen, unsigned char delimitedSuffix, unsigned char *output, unsigned long long int outputByteLen);
      81                 :            : 
      82                 :            : /**
      83                 :            :   *  Function to compute SHAKE128 on the input message with any output length.
      84                 :            :   */
      85                 :            : #include "sha3.h"
      86                 :            : 
      87                 :            : /*
      88                 :            : void FIPS202_SHAKE128(const unsigned char *input, unsigned int inputByteLen, unsigned char *output, int outputByteLen)
      89                 :            : {
      90                 :            :     Keccak(1344, 256, input, inputByteLen, 0x1F, output, outputByteLen);
      91                 :            : }
      92                 :            : */
      93                 :            : 
      94                 :            : /**
      95                 :            :   *  Function to compute SHAKE256 on the input message with any output length.
      96                 :            : void FIPS202_SHAKE256(const unsigned char *input, unsigned int inputByteLen, unsigned char *output, int outputByteLen)
      97                 :            : {
      98                 :            :     Keccak(1088, 512, input, inputByteLen, 0x1F, output, outputByteLen);
      99                 :            : }
     100                 :            : */
     101                 :            : 
     102                 :            : /**
     103                 :            :   *  Function to compute SHA3-224 on the input message. The output length is fixed to 28 bytes.
     104                 :            : void FIPS202_SHA3_224(const unsigned char *input, unsigned int inputByteLen, unsigned char *output)
     105                 :            : {
     106                 :            :     Keccak(1152, 448, input, inputByteLen, 0x06, output, 28);
     107                 :            : }
     108                 :            : */
     109                 :            : 
     110                 :            : /**
     111                 :            :   *  Function to compute SHA3-256 on the input message. The output length is fixed to 32 bytes.
     112                 :            :   */
     113                 :       7203 : void FIPS202_SHA3_256(const unsigned char *input, unsigned int inputByteLen, unsigned char *output)
     114                 :            : {
     115                 :       7203 :     Keccak(1088, 512, input, inputByteLen, 0x06, output, 32);
     116                 :       7203 : }
     117                 :            : 
     118                 :            : /**
     119                 :            :   *  Function to compute SHA3-384 on the input message. The output length is fixed to 48 bytes.
     120                 :            : void FIPS202_SHA3_384(const unsigned char *input, unsigned int inputByteLen, unsigned char *output)
     121                 :            : {
     122                 :            :     Keccak(832, 768, input, inputByteLen, 0x06, output, 48);
     123                 :            : }
     124                 :            : */
     125                 :            : 
     126                 :            : /**
     127                 :            :   *  Function to compute SHA3-512 on the input message. The output length is fixed to 64 bytes.
     128                 :            :   */
     129                 :        126 : void FIPS202_SHA3_512(const unsigned char *input, unsigned int inputByteLen, unsigned char *output)
     130                 :            : {
     131                 :        126 :     Keccak(576, 1024, input, inputByteLen, 0x06, output, 64);
     132                 :        126 : }
     133                 :            : 
     134                 :            : /*
     135                 :            : ================================================================
     136                 :            : Technicalities
     137                 :            : ================================================================
     138                 :            : */
     139                 :            : 
     140                 :            : typedef unsigned char UINT8;
     141                 :            : typedef unsigned long long int UINT64;
     142                 :            : typedef UINT64 tKeccakLane;
     143                 :            : 
     144                 :            : #ifndef LITTLE_ENDIAN
     145                 :            : /** Function to load a 64-bit value using the little-endian (LE) convention.
     146                 :            :   * On a LE platform, this could be greatly simplified using a cast.
     147                 :            :   */
     148                 :   13948200 : static UINT64 load64(const UINT8 *x)
     149                 :            : {
     150                 :            :     int i;
     151                 :   13948200 :     UINT64 u=0;
     152                 :            : 
     153         [ +  + ]:  125533800 :     for(i=7; i>=0; --i) {
     154                 :  111585600 :         u <<= 8;
     155                 :  111585600 :         u |= x[i];
     156                 :            :     }
     157                 :   13948200 :     return u;
     158                 :            : }
     159                 :            : 
     160                 :            : /** Function to store a 64-bit value using the little-endian (LE) convention.
     161                 :            :   * On a LE platform, this could be greatly simplified using a cast.
     162                 :            :   */
     163                 :    9112824 : static void store64(UINT8 *x, UINT64 u)
     164                 :            : {
     165                 :            :     unsigned int i;
     166                 :            : 
     167         [ +  + ]:   82015416 :     for(i=0; i<8; ++i) {
     168                 :   72902592 :         x[i] = u;
     169                 :   72902592 :         u >>= 8;
     170                 :            :     }
     171                 :    9112824 : }
     172                 :            : 
     173                 :            : /** Function to XOR into a 64-bit value using the little-endian (LE) convention.
     174                 :            :   * On a LE platform, this could be greatly simplified using a cast.
     175                 :            :   */
     176                 :    5315814 : static void xor64(UINT8 *x, UINT64 u)
     177                 :            : {
     178                 :            :     unsigned int i;
     179                 :            : 
     180         [ +  + ]:   47842326 :     for(i=0; i<8; ++i) {
     181                 :   42526512 :         x[i] ^= u;
     182                 :   42526512 :         u >>= 8;
     183                 :            :     }
     184                 :    5315814 : }
     185                 :            : #endif
     186                 :            : 
     187                 :            : /*
     188                 :            : ================================================================
     189                 :            : A readable and compact implementation of the Keccak-f[1600] permutation.
     190                 :            : ================================================================
     191                 :            : */
     192                 :            : 
     193                 :            : #define ROL64(a, offset) ((((UINT64)a) << offset) ^ (((UINT64)a) >> (64-offset)))
     194                 :            : #define i(x, y) ((x)+5*(y))
     195                 :            : 
     196                 :            : #ifdef LITTLE_ENDIAN
     197                 :            :     #define readLane(x, y)          (((tKeccakLane*)state)[i(x, y)])
     198                 :            :     #define writeLane(x, y, lane)   (((tKeccakLane*)state)[i(x, y)]) = (lane)
     199                 :            :     #define XORLane(x, y, lane)     (((tKeccakLane*)state)[i(x, y)]) ^= (lane)
     200                 :            : #else
     201                 :            :     #define readLane(x, y)          load64((UINT8*)state+sizeof(tKeccakLane)*i(x, y))
     202                 :            :     #define writeLane(x, y, lane)   store64((UINT8*)state+sizeof(tKeccakLane)*i(x, y), lane)
     203                 :            :     #define XORLane(x, y, lane)     xor64((UINT8*)state+sizeof(tKeccakLane)*i(x, y), lane)
     204                 :            : #endif
     205                 :            : 
     206                 :            : /**
     207                 :            :   * Function that computes the linear feedback shift register (LFSR) used to
     208                 :            :   * define the round constants (see [Keccak Reference, Section 1.2]).
     209                 :            :   */
     210                 :    1301832 : int LFSR86540(UINT8 *LFSR)
     211                 :            : {
     212                 :    1301832 :     int result = ((*LFSR) & 0x01) != 0;
     213         [ +  + ]:    1301832 :     if (((*LFSR) & 0x80) != 0)
     214                 :            :         // Primitive polynomial over GF(2): x^8+x^6+x^5+x^4+1
     215                 :     658665 :         (*LFSR) = ((*LFSR) << 1) ^ 0x71;
     216                 :            :     else
     217                 :     643167 :         (*LFSR) <<= 1;
     218                 :    1301832 :     return result;
     219                 :            : }
     220                 :            : 
     221                 :            : /**
     222                 :            :  * Function that computes the Keccak-f[1600] permutation on the given state.
     223                 :            :  */
     224                 :       7749 : void KeccakF1600_StatePermute(void *state)
     225                 :            : {
     226                 :            :     unsigned int round, x, y, j, t;
     227                 :       7749 :     UINT8 LFSRstate = 0x01;
     228                 :            : 
     229         [ +  + ]:     193725 :     for(round=0; round<24; round++) {
     230                 :            :         {   // === Theta step (see [Keccak Reference, Section 2.3.2]) ===
     231                 :            :             tKeccakLane C[5], D;
     232                 :            : 
     233                 :            :             // Compute the parity of the columns
     234         [ +  + ]:    1115856 :             for(x=0; x<5; x++)
     235                 :     929880 :                 C[x] = readLane(x, 0) ^ readLane(x, 1) ^ readLane(x, 2) ^ readLane(x, 3) ^ readLane(x, 4);
     236         [ +  + ]:    1115856 :             for(x=0; x<5; x++) {
     237                 :            :                 // Compute the theta effect for a given column
     238                 :     929880 :                 D = C[(x+4)%5] ^ ROL64(C[(x+1)%5], 1);
     239                 :            :                 // Add the theta effect to the whole column
     240         [ +  + ]:    5579280 :                 for (y=0; y<5; y++)
     241                 :    4649400 :                     XORLane(x, y, D);
     242                 :            :             }
     243                 :            :         }
     244                 :            : 
     245                 :            :         {   // === rho and pi steps (see [Keccak Reference, Sections 2.3.3 and 2.3.4]) ===
     246                 :            :             tKeccakLane current, temp;
     247                 :            :             // Start at coordinates (1 0)
     248                 :     185976 :             x = 1; y = 0;
     249                 :     185976 :             current = readLane(x, y);
     250                 :            :             // Iterate over ((0 1)(2 3))^t * (1 0) for 0 <= t <= 23
     251         [ +  + ]:    4649400 :             for(t=0; t<24; t++) {
     252                 :            :                 // Compute the rotation constant r = (t+1)(t+2)/2
     253                 :    4463424 :                 unsigned int r = ((t+1)*(t+2)/2)%64;
     254                 :            :                 // Compute ((0 1)(2 3)) * (x y)
     255                 :    4463424 :                 unsigned int Y = (2*x+3*y)%5; x = y; y = Y;
     256                 :            :                 // Swap current and state(x,y), and rotate
     257                 :    4463424 :                 temp = readLane(x, y);
     258                 :    4463424 :                 writeLane(x, y, ROL64(current, r));
     259                 :    4463424 :                 current = temp;
     260                 :            :             }
     261                 :            :         }
     262                 :            : 
     263                 :            :         {   // === chi step (see [Keccak Reference, Section 2.3.1]) ===
     264                 :            :             tKeccakLane temp[5];
     265         [ +  + ]:    1115856 :             for(y=0; y<5; y++) {
     266                 :            :                 // Take a copy of the plane
     267         [ +  + ]:    5579280 :                 for(x=0; x<5; x++)
     268                 :    4649400 :                     temp[x] = readLane(x, y);
     269                 :            :                 // Compute chi on the plane
     270         [ +  + ]:    5579280 :                 for(x=0; x<5; x++)
     271                 :    4649400 :                     writeLane(x, y, temp[x] ^((~temp[(x+1)%5]) & temp[(x+2)%5]));
     272                 :            :             }
     273                 :            :         }
     274                 :            : 
     275                 :            :         {   // === iota step (see [Keccak Reference, Section 2.3.5]) ===
     276         [ +  + ]:    1487808 :             for(j=0; j<7; j++) {
     277                 :    1301832 :                 unsigned int bitPosition = (1<<j)-1; //2^j-1
     278         [ +  + ]:    1301832 :                 if (LFSR86540(&LFSRstate))
     279                 :     666414 :                     XORLane(0, 0, (tKeccakLane)1<<bitPosition);
     280                 :            :             }
     281                 :            :         }
     282                 :            :     }
     283                 :       7749 : }
     284                 :            : 
     285                 :            : /*
     286                 :            : ================================================================
     287                 :            : A readable and compact implementation of the Keccak sponge functions
     288                 :            : that use the Keccak-f[1600] permutation.
     289                 :            : ================================================================
     290                 :            : */
     291                 :            : 
     292                 :            : #include <string.h>
     293                 :            : #define MIN(a, b) ((a) < (b) ? (a) : (b))
     294                 :            : 
     295                 :       7329 : void Keccak(unsigned int rate, unsigned int capacity, const unsigned char *input, unsigned long long int inputByteLen, unsigned char delimitedSuffix, unsigned char *output, unsigned long long int outputByteLen)
     296                 :            : {
     297                 :            :     UINT8 state[200];
     298                 :       7329 :     unsigned int rateInBytes = rate/8;
     299                 :       7329 :     unsigned int blockSize = 0;
     300                 :            :     unsigned int i;
     301                 :            : 
     302 [ +  - ][ +  - ]:       7329 :     if (((rate + capacity) != 1600) || ((rate % 8) != 0))
     303                 :          0 :         return;
     304                 :            : 
     305                 :            :     // === Initialize the state ===
     306                 :            :     memset(state, 0, sizeof(state));
     307                 :            : 
     308                 :            :     // === Absorb all the input blocks ===
     309         [ +  + ]:      15046 :     while(inputByteLen > 0) {
     310                 :       7717 :         blockSize = MIN(inputByteLen, rateInBytes);
     311         [ +  + ]:     722217 :         for(i=0; i<blockSize; i++)
     312                 :     714500 :             state[i] ^= input[i];
     313                 :       7717 :         input += blockSize;
     314                 :       7717 :         inputByteLen -= blockSize;
     315                 :            : 
     316         [ +  + ]:       7717 :         if (blockSize == rateInBytes) {
     317                 :        420 :             KeccakF1600_StatePermute(state);
     318                 :       7717 :             blockSize = 0;
     319                 :            :         }
     320                 :            :     }
     321                 :            : 
     322                 :            :     // === Do the padding and switch to the squeezing phase ===
     323                 :            :     // Absorb the last few bits and add the first bit of padding (which coincides with the delimiter in delimitedSuffix)
     324                 :       7329 :     state[blockSize] ^= delimitedSuffix;
     325                 :            :     // If the first bit of padding is at position rate-1, we need a whole new block for the second bit of padding
     326 [ -  + ][ #  # ]:       7329 :     if (((delimitedSuffix & 0x80) != 0) && (blockSize == (rateInBytes-1)))
     327                 :          0 :         KeccakF1600_StatePermute(state);
     328                 :            :     // Add the second bit of padding
     329                 :       7329 :     state[rateInBytes-1] ^= 0x80;
     330                 :            :     // Switch to the squeezing phase
     331                 :       7329 :     KeccakF1600_StatePermute(state);
     332                 :            : 
     333                 :            :     // === Squeeze out all the output blocks ===
     334         [ +  + ]:      14658 :     while(outputByteLen > 0) {
     335                 :       7329 :         blockSize = MIN(outputByteLen, rateInBytes);
     336                 :       7329 :         memcpy(output, state, blockSize);
     337                 :       7329 :         output += blockSize;
     338                 :       7329 :         outputByteLen -= blockSize;
     339                 :            : 
     340         [ -  + ]:       7329 :         if (outputByteLen > 0)
     341                 :       7329 :             KeccakF1600_StatePermute(state);
     342                 :            :     }
     343                 :            : }

Generated by: LCOV version 1.10