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 : : }
|
