1 /* -------------------------------------------------------------------------
2 * Works when compiled for either 32-bit or 64-bit targets, optimized for
3 * 64 bit.
4 *
5 * Canonical implementation of Init/Update/Finalize for SHA-3 byte input.
6 *
7 * SHA3-256, SHA3-384, SHA-512 are implemented. SHA-224 can easily be added.
8 *
9 * Based on code from http://keccak.noekeon.org/ .
10 *
11 * I place the code that I wrote into public domain, free to use.
12 *
13 * I would appreciate if you give credits to this work if you used it to
14 * write or test * your code.
15 *
16 * Aug 2015. Andrey Jivsov. crypto@brainhub.org
17 *
18 * ---------------------------------------------------------------------- */
19
20 /* I modified and removed some lines (e.g. test cases) of the file "sha3.c"
21 to make the C++ compiler happy. The result still remains in public domain.
22 June 1st, 2018. Heiko Stamer */
23
24 #include <stdio.h>
25 #include <stdint.h>
26 #include <string.h>
27
28 #define SHA3_ASSERT( x )
29 #if defined(_MSC_VER)
30 #define SHA3_TRACE( format, ...)
31 #define SHA3_TRACE_BUF( format, buf, l, ...)
32 #else
33 #define SHA3_TRACE(format, args...)
34 #define SHA3_TRACE_BUF(format, buf, l, args...)
35 #endif
36
37 //#define SHA3_USE_KECCAK
38 /*
39 * Define SHA3_USE_KECCAK to run "pure" Keccak, as opposed to SHA3.
40 * The tests that this macro enables use the input and output from [Keccak]
41 * (see the reference below). The used test vectors aren't correct for SHA3,
42 * however, they are helpful to verify the implementation.
43 * SHA3_USE_KECCAK only changes one line of code in Finalize.
44 */
45
46 #if defined(_MSC_VER)
47 #define SHA3_CONST(x) x
48 #else
49 #define SHA3_CONST(x) x##L
50 #endif
51
52 /* The following state definition should normally be in a separate
53 * header file
54 */
55
56 /* 'Words' here refers to uint64_t */
57 #define SHA3_KECCAK_SPONGE_WORDS \
58 (((1600)/8/*bits to byte*/)/sizeof(uint64_t))
59 typedef struct sha3_context_ {
60 uint64_t saved; /* the portion of the input message that we
61 * didn't consume yet */
62 union { /* Keccak's state */
63 uint64_t s[SHA3_KECCAK_SPONGE_WORDS];
64 uint8_t sb[SHA3_KECCAK_SPONGE_WORDS * 8];
65 };
66 unsigned byteIndex; /* 0..7--the next byte after the set one
67 * (starts from 0; 0--none are buffered) */
68 unsigned wordIndex; /* 0..24--the next word to integrate input
69 * (starts from 0) */
70 unsigned capacityWords; /* the double size of the hash output in
71 * words (e.g. 16 for Keccak 512) */
72 } sha3_context;
73
74 #ifndef SHA3_ROTL64
75 #define SHA3_ROTL64(x, y) \
76 (((x) << (y)) | ((x) >> ((sizeof(uint64_t)*8) - (y))))
77 #endif
78
79 static const uint64_t keccakf_rndc[24] = {
80 SHA3_CONST(0x0000000000000001UL), SHA3_CONST(0x0000000000008082UL),
81 SHA3_CONST(0x800000000000808aUL), SHA3_CONST(0x8000000080008000UL),
82 SHA3_CONST(0x000000000000808bUL), SHA3_CONST(0x0000000080000001UL),
83 SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008009UL),
84 SHA3_CONST(0x000000000000008aUL), SHA3_CONST(0x0000000000000088UL),
85 SHA3_CONST(0x0000000080008009UL), SHA3_CONST(0x000000008000000aUL),
86 SHA3_CONST(0x000000008000808bUL), SHA3_CONST(0x800000000000008bUL),
87 SHA3_CONST(0x8000000000008089UL), SHA3_CONST(0x8000000000008003UL),
88 SHA3_CONST(0x8000000000008002UL), SHA3_CONST(0x8000000000000080UL),
89 SHA3_CONST(0x000000000000800aUL), SHA3_CONST(0x800000008000000aUL),
90 SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008080UL),
91 SHA3_CONST(0x0000000080000001UL), SHA3_CONST(0x8000000080008008UL)
92 };
93
94 static const unsigned keccakf_rotc[24] = {
95 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14, 27, 41, 56, 8, 25, 43, 62,
96 18, 39, 61, 20, 44
97 };
98
99 static const unsigned keccakf_piln[24] = {
100 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4, 15, 23, 19, 13, 12, 2, 20,
101 14, 22, 9, 6, 1
102 };
103
104 /* generally called after SHA3_KECCAK_SPONGE_WORDS-ctx->capacityWords words
105 * are XORed into the state s
106 */
107 static void
keccakf(uint64_t s[25])108 keccakf(uint64_t s[25])
109 {
110 int i, j, round;
111 uint64_t t, bc[5];
112
113 for(round = 0; round < 24; round++) {
114
115 /* Theta */
116 for(i = 0; i < 5; i++)
117 bc[i] = s[i] ^ s[i + 5] ^ s[i + 10] ^ s[i + 15] ^ s[i + 20];
118
119 for(i = 0; i < 5; i++) {
120 t = bc[(i + 4) % 5] ^ SHA3_ROTL64(bc[(i + 1) % 5], 1);
121 for(j = 0; j < 25; j += 5)
122 s[j + i] ^= t;
123 }
124
125 /* Rho Pi */
126 t = s[1];
127 for(i = 0; i < 24; i++) {
128 j = keccakf_piln[i];
129 bc[0] = s[j];
130 s[j] = SHA3_ROTL64(t, keccakf_rotc[i]);
131 t = bc[0];
132 }
133
134 /* Chi */
135 for(j = 0; j < 25; j += 5) {
136 for(i = 0; i < 5; i++)
137 bc[i] = s[j + i];
138 for(i = 0; i < 5; i++)
139 s[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
140 }
141
142 /* Iota */
143 s[0] ^= keccakf_rndc[round];
144 }
145 }
146
147 /* *************************** Public Inteface ************************ */
148
149 /* For Init or Reset call these: */
150 static void
sha3_Init256(sha3_context * priv)151 sha3_Init256(sha3_context *priv)
152 {
153 sha3_context *ctx = priv;
154 memset(ctx, 0, sizeof(*ctx));
155 ctx->capacityWords = 2 * 256 / (8 * sizeof(uint64_t));
156 }
157
158 static void
sha3_Init384(sha3_context * priv)159 sha3_Init384(sha3_context *priv)
160 {
161 sha3_context *ctx = priv;
162 memset(ctx, 0, sizeof(*ctx));
163 ctx->capacityWords = 2 * 384 / (8 * sizeof(uint64_t));
164 }
165
166 static void
sha3_Init512(sha3_context * priv)167 sha3_Init512(sha3_context *priv)
168 {
169 sha3_context *ctx = priv;
170 memset(ctx, 0, sizeof(*ctx));
171 ctx->capacityWords = 2 * 512 / (8 * sizeof(uint64_t));
172 }
173
174 static void
sha3_Update(sha3_context * priv,const uint8_t * bufIn,size_t len)175 sha3_Update(sha3_context *priv, const uint8_t *bufIn, size_t len)
176 {
177 sha3_context *ctx = priv;
178
179 /* 0...7 -- how much is needed to have a word */
180 unsigned old_tail = (8 - ctx->byteIndex) & 7;
181
182 size_t words;
183 unsigned tail;
184
185 const uint8_t *buf = bufIn;
186
187 SHA3_TRACE_BUF("called to update with:", buf, len);
188
189 SHA3_ASSERT(ctx->byteIndex < 8);
190 SHA3_ASSERT(ctx->wordIndex < sizeof(ctx->s) / sizeof(ctx->s[0]));
191
192 if(len < old_tail) { /* have no complete word or haven't started
193 * the word yet */
194 SHA3_TRACE("because %d<%d, store it and return", (unsigned)len,
195 (unsigned)old_tail);
196 /* endian-independent code follows: */
197 while (len--)
198 ctx->saved |= (uint64_t) (*(buf++)) << ((ctx->byteIndex++) * 8);
199 SHA3_ASSERT(ctx->byteIndex < 8);
200 return;
201 }
202
203 if(old_tail) { /* will have one word to process */
204 SHA3_TRACE("completing one word with %d bytes", (unsigned)old_tail);
205 /* endian-independent code follows: */
206 len -= old_tail;
207 while (old_tail--)
208 ctx->saved |= (uint64_t) (*(buf++)) << ((ctx->byteIndex++) * 8);
209
210 /* now ready to add saved to the sponge */
211 ctx->s[ctx->wordIndex] ^= ctx->saved;
212 SHA3_ASSERT(ctx->byteIndex == 8);
213 ctx->byteIndex = 0;
214 ctx->saved = 0;
215 if(++ctx->wordIndex ==
216 (SHA3_KECCAK_SPONGE_WORDS - ctx->capacityWords)) {
217 keccakf(ctx->s);
218 ctx->wordIndex = 0;
219 }
220 }
221
222 /* now work in full words directly from input */
223
224 SHA3_ASSERT(ctx->byteIndex == 0);
225
226 words = len / sizeof(uint64_t);
227 tail = len - words * sizeof(uint64_t);
228
229 SHA3_TRACE("have %d full words to process", (unsigned)words);
230
231 for(size_t i = 0; i < words; i++, buf += sizeof(uint64_t)) {
232 const uint64_t t = (uint64_t) (buf[0]) |
233 ((uint64_t) (buf[1]) << 8 * 1) |
234 ((uint64_t) (buf[2]) << 8 * 2) |
235 ((uint64_t) (buf[3]) << 8 * 3) |
236 ((uint64_t) (buf[4]) << 8 * 4) |
237 ((uint64_t) (buf[5]) << 8 * 5) |
238 ((uint64_t) (buf[6]) << 8 * 6) |
239 ((uint64_t) (buf[7]) << 8 * 7);
240 #if defined(__x86_64__ ) || defined(__i386__)
241 SHA3_ASSERT(memcmp(&t, buf, 8) == 0);
242 #endif
243 ctx->s[ctx->wordIndex] ^= t;
244 if(++ctx->wordIndex ==
245 (SHA3_KECCAK_SPONGE_WORDS - ctx->capacityWords)) {
246 keccakf(ctx->s);
247 ctx->wordIndex = 0;
248 }
249 }
250
251 SHA3_TRACE("have %d bytes left to process, save them", (unsigned)tail);
252
253 /* finally, save the partial word */
254 SHA3_ASSERT(ctx->byteIndex == 0 && tail < 8);
255 while (tail--) {
256 SHA3_TRACE("Store byte %02x '%c'", *buf, *buf);
257 ctx->saved |= (uint64_t) (*(buf++)) << ((ctx->byteIndex++) * 8);
258 }
259 SHA3_ASSERT(ctx->byteIndex < 8);
260 SHA3_TRACE("Have saved=0x%016" PRIx64 " at the end", ctx->saved);
261 }
262
263 /* This is simply the 'update' with the padding block.
264 * The padding block is 0x01 || 0x00* || 0x80. First 0x01 and last 0x80
265 * bytes are always present, but they can be the same byte.
266 */
267 static uint8_t const *
sha3_Finalize(sha3_context * priv)268 sha3_Finalize(sha3_context *priv)
269 {
270 sha3_context *ctx = priv;
271
272 SHA3_TRACE("called with %d bytes in the buffer", ctx->byteIndex);
273
274 /* Append 2-bit suffix 01, per SHA-3 spec. Instead of 1 for padding we
275 * use 1<<2 below. The 0x02 below corresponds to the suffix 01.
276 * Overall, we feed 0, then 1, and finally 1 to start padding. Without
277 * M || 01, we would simply use 1 to start padding. */
278
279 #ifndef SHA3_USE_KECCAK
280 /* SHA3 version */
281 ctx->s[ctx->wordIndex] ^=
282 (ctx->saved ^ ((uint64_t) ((uint64_t) (0x02 | (1 << 2)) <<
283 ((ctx->byteIndex) * 8))));
284 #else
285 /* For testing the "pure" Keccak version */
286 ctx->s[ctx->wordIndex] ^=
287 (ctx->saved ^ ((uint64_t) ((uint64_t) 1 << (ctx->byteIndex *
288 8))));
289 #endif
290
291 ctx->s[SHA3_KECCAK_SPONGE_WORDS - ctx->capacityWords - 1] ^=
292 SHA3_CONST(0x8000000000000000UL);
293 keccakf(ctx->s);
294
295 /* Return first bytes of the ctx->s. This conversion is not needed for
296 * little-endian platforms e.g. wrap with #if !defined(__BYTE_ORDER__)
297 * || !defined(__ORDER_LITTLE_ENDIAN__) || \
298 * __BYTE_ORDER__!=__ORDER_LITTLE_ENDIAN__ ... the conversion below ...
299 * #endif */
300 {
301 unsigned i;
302 for(i = 0; i < SHA3_KECCAK_SPONGE_WORDS; i++) {
303 const unsigned t1 = (uint32_t) ctx->s[i];
304 const unsigned t2 = (uint32_t) ((ctx->s[i] >> 16) >> 16);
305 ctx->sb[i * 8 + 0] = (uint8_t) (t1);
306 ctx->sb[i * 8 + 1] = (uint8_t) (t1 >> 8);
307 ctx->sb[i * 8 + 2] = (uint8_t) (t1 >> 16);
308 ctx->sb[i * 8 + 3] = (uint8_t) (t1 >> 24);
309 ctx->sb[i * 8 + 4] = (uint8_t) (t2);
310 ctx->sb[i * 8 + 5] = (uint8_t) (t2 >> 8);
311 ctx->sb[i * 8 + 6] = (uint8_t) (t2 >> 16);
312 ctx->sb[i * 8 + 7] = (uint8_t) (t2 >> 24);
313 }
314 }
315
316 SHA3_TRACE_BUF("Hash: (first 32 bytes)", ctx->sb, 256 / 8);
317
318 return (ctx->sb);
319 }
320
321