SHA3.c (11814B)
1 /* 2 * SHA-3 (Keccak) Implementation 3 * FIPS 202 Standard 4 * 5 * Supports SHA3-224, SHA3-256, SHA3-384, SHA3-512 6 * Also supports SHAKE128 and SHAKE256 (extendable output functions) 7 */ 8 9 #include <stdint.h> 10 #include <string.h> 11 #include <stdlib.h> 12 13 /* Keccak round constants */ 14 static const uint64_t KeccakF_RoundConstants[24] = { 15 0x0000000000000001ULL, 0x0000000000008082ULL, 0x800000000000808aULL, 16 0x8000000080008000ULL, 0x000000000000808bULL, 0x0000000080000001ULL, 17 0x8000000080008081ULL, 0x8000000000008009ULL, 0x000000000000008aULL, 18 0x0000000000000088ULL, 0x0000000080008009ULL, 0x000000008000000aULL, 19 0x000000008000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL, 20 0x8000000000008003ULL, 0x8000000000008002ULL, 0x8000000000000080ULL, 21 0x000000000000800aULL, 0x800000008000000aULL, 0x8000000080008081ULL, 22 0x8000000000008080ULL, 0x0000000080000001ULL, 0x8000000080008008ULL 23 }; 24 25 #define ROL64(a, n) (((a) << (n)) | ((a) >> (64 - (n)))) 26 27 /* Keccak-f[1600] permutation - unrolled reference implementation */ 28 static void KeccakF1600(uint64_t *state) { 29 uint64_t Aba, Abe, Abi, Abo, Abu; 30 uint64_t Aga, Age, Agi, Ago, Agu; 31 uint64_t Aka, Ake, Aki, Ako, Aku; 32 uint64_t Ama, Ame, Ami, Amo, Amu; 33 uint64_t Asa, Ase, Asi, Aso, Asu; 34 uint64_t BCa, BCe, BCi, BCo, BCu; 35 uint64_t Da, De, Di, Do, Du; 36 uint64_t Eba, Ebe, Ebi, Ebo, Ebu; 37 uint64_t Ega, Ege, Egi, Ego, Egu; 38 uint64_t Eka, Eke, Eki, Eko, Eku; 39 uint64_t Ema, Eme, Emi, Emo, Emu; 40 uint64_t Esa, Ese, Esi, Eso, Esu; 41 42 Aba = state[ 0]; Abe = state[ 1]; Abi = state[ 2]; Abo = state[ 3]; Abu = state[ 4]; 43 Aga = state[ 5]; Age = state[ 6]; Agi = state[ 7]; Ago = state[ 8]; Agu = state[ 9]; 44 Aka = state[10]; Ake = state[11]; Aki = state[12]; Ako = state[13]; Aku = state[14]; 45 Ama = state[15]; Ame = state[16]; Ami = state[17]; Amo = state[18]; Amu = state[19]; 46 Asa = state[20]; Ase = state[21]; Asi = state[22]; Aso = state[23]; Asu = state[24]; 47 48 for (int round = 0; round < 24; round += 2) { 49 /* Round 1 */ 50 BCa = Aba^Aga^Aka^Ama^Asa; 51 BCe = Abe^Age^Ake^Ame^Ase; 52 BCi = Abi^Agi^Aki^Ami^Asi; 53 BCo = Abo^Ago^Ako^Amo^Aso; 54 BCu = Abu^Agu^Aku^Amu^Asu; 55 56 Da = BCu^ROL64(BCe, 1); 57 De = BCa^ROL64(BCi, 1); 58 Di = BCe^ROL64(BCo, 1); 59 Do = BCi^ROL64(BCu, 1); 60 Du = BCo^ROL64(BCa, 1); 61 62 Aba ^= Da; BCa = Aba; 63 Age ^= De; BCe = ROL64(Age, 44); 64 Aki ^= Di; BCi = ROL64(Aki, 43); 65 Amo ^= Do; BCo = ROL64(Amo, 21); 66 Asu ^= Du; BCu = ROL64(Asu, 14); 67 Eba = BCa^((~BCe)&BCi); Eba ^= KeccakF_RoundConstants[round]; 68 Ebe = BCe^((~BCi)&BCo); 69 Ebi = BCi^((~BCo)&BCu); 70 Ebo = BCo^((~BCu)&BCa); 71 Ebu = BCu^((~BCa)&BCe); 72 73 Abo ^= Do; BCa = ROL64(Abo, 28); 74 Agu ^= Du; BCe = ROL64(Agu, 20); 75 Aka ^= Da; BCi = ROL64(Aka, 3); 76 Ame ^= De; BCo = ROL64(Ame, 45); 77 Asi ^= Di; BCu = ROL64(Asi, 61); 78 Ega = BCa^((~BCe)&BCi); 79 Ege = BCe^((~BCi)&BCo); 80 Egi = BCi^((~BCo)&BCu); 81 Ego = BCo^((~BCu)&BCa); 82 Egu = BCu^((~BCa)&BCe); 83 84 Abe ^= De; BCa = ROL64(Abe, 1); 85 Agi ^= Di; BCe = ROL64(Agi, 6); 86 Ako ^= Do; BCi = ROL64(Ako, 25); 87 Amu ^= Du; BCo = ROL64(Amu, 8); 88 Asa ^= Da; BCu = ROL64(Asa, 18); 89 Eka = BCa^((~BCe)&BCi); 90 Eke = BCe^((~BCi)&BCo); 91 Eki = BCi^((~BCo)&BCu); 92 Eko = BCo^((~BCu)&BCa); 93 Eku = BCu^((~BCa)&BCe); 94 95 Abu ^= Du; BCa = ROL64(Abu, 27); 96 Aga ^= Da; BCe = ROL64(Aga, 36); 97 Ake ^= De; BCi = ROL64(Ake, 10); 98 Ami ^= Di; BCo = ROL64(Ami, 15); 99 Aso ^= Do; BCu = ROL64(Aso, 56); 100 Ema = BCa^((~BCe)&BCi); 101 Eme = BCe^((~BCi)&BCo); 102 Emi = BCi^((~BCo)&BCu); 103 Emo = BCo^((~BCu)&BCa); 104 Emu = BCu^((~BCa)&BCe); 105 106 Abi ^= Di; BCa = ROL64(Abi, 62); 107 Ago ^= Do; BCe = ROL64(Ago, 55); 108 Aku ^= Du; BCi = ROL64(Aku, 39); 109 Ama ^= Da; BCo = ROL64(Ama, 41); 110 Ase ^= De; BCu = ROL64(Ase, 2); 111 Esa = BCa^((~BCe)&BCi); 112 Ese = BCe^((~BCi)&BCo); 113 Esi = BCi^((~BCo)&BCu); 114 Eso = BCo^((~BCu)&BCa); 115 Esu = BCu^((~BCa)&BCe); 116 117 /* Round 2 */ 118 BCa = Eba^Ega^Eka^Ema^Esa; 119 BCe = Ebe^Ege^Eke^Eme^Ese; 120 BCi = Ebi^Egi^Eki^Emi^Esi; 121 BCo = Ebo^Ego^Eko^Emo^Eso; 122 BCu = Ebu^Egu^Eku^Emu^Esu; 123 124 Da = BCu^ROL64(BCe, 1); 125 De = BCa^ROL64(BCi, 1); 126 Di = BCe^ROL64(BCo, 1); 127 Do = BCi^ROL64(BCu, 1); 128 Du = BCo^ROL64(BCa, 1); 129 130 Eba ^= Da; BCa = Eba; 131 Ege ^= De; BCe = ROL64(Ege, 44); 132 Eki ^= Di; BCi = ROL64(Eki, 43); 133 Emo ^= Do; BCo = ROL64(Emo, 21); 134 Esu ^= Du; BCu = ROL64(Esu, 14); 135 Aba = BCa^((~BCe)&BCi); Aba ^= KeccakF_RoundConstants[round+1]; 136 Abe = BCe^((~BCi)&BCo); 137 Abi = BCi^((~BCo)&BCu); 138 Abo = BCo^((~BCu)&BCa); 139 Abu = BCu^((~BCa)&BCe); 140 141 Ebo ^= Do; BCa = ROL64(Ebo, 28); 142 Egu ^= Du; BCe = ROL64(Egu, 20); 143 Eka ^= Da; BCi = ROL64(Eka, 3); 144 Eme ^= De; BCo = ROL64(Eme, 45); 145 Esi ^= Di; BCu = ROL64(Esi, 61); 146 Aga = BCa^((~BCe)&BCi); 147 Age = BCe^((~BCi)&BCo); 148 Agi = BCi^((~BCo)&BCu); 149 Ago = BCo^((~BCu)&BCa); 150 Agu = BCu^((~BCa)&BCe); 151 152 Ebe ^= De; BCa = ROL64(Ebe, 1); 153 Egi ^= Di; BCe = ROL64(Egi, 6); 154 Eko ^= Do; BCi = ROL64(Eko, 25); 155 Emu ^= Du; BCo = ROL64(Emu, 8); 156 Esa ^= Da; BCu = ROL64(Esa, 18); 157 Aka = BCa^((~BCe)&BCi); 158 Ake = BCe^((~BCi)&BCo); 159 Aki = BCi^((~BCo)&BCu); 160 Ako = BCo^((~BCu)&BCa); 161 Aku = BCu^((~BCa)&BCe); 162 163 Ebu ^= Du; BCa = ROL64(Ebu, 27); 164 Ega ^= Da; BCe = ROL64(Ega, 36); 165 Eke ^= De; BCi = ROL64(Eke, 10); 166 Emi ^= Di; BCo = ROL64(Emi, 15); 167 Eso ^= Do; BCu = ROL64(Eso, 56); 168 Ama = BCa^((~BCe)&BCi); 169 Ame = BCe^((~BCi)&BCo); 170 Ami = BCi^((~BCo)&BCu); 171 Amo = BCo^((~BCu)&BCa); 172 Amu = BCu^((~BCa)&BCe); 173 174 Ebi ^= Di; BCa = ROL64(Ebi, 62); 175 Ego ^= Do; BCe = ROL64(Ego, 55); 176 Eku ^= Du; BCi = ROL64(Eku, 39); 177 Ema ^= Da; BCo = ROL64(Ema, 41); 178 Ese ^= De; BCu = ROL64(Ese, 2); 179 Asa = BCa^((~BCe)&BCi); 180 Ase = BCe^((~BCi)&BCo); 181 Asi = BCi^((~BCo)&BCu); 182 Aso = BCo^((~BCu)&BCa); 183 Asu = BCu^((~BCa)&BCe); 184 } 185 186 state[ 0] = Aba; state[ 1] = Abe; state[ 2] = Abi; state[ 3] = Abo; state[ 4] = Abu; 187 state[ 5] = Aga; state[ 6] = Age; state[ 7] = Agi; state[ 8] = Ago; state[ 9] = Agu; 188 state[10] = Aka; state[11] = Ake; state[12] = Aki; state[13] = Ako; state[14] = Aku; 189 state[15] = Ama; state[16] = Ame; state[17] = Ami; state[18] = Amo; state[19] = Amu; 190 state[20] = Asa; state[21] = Ase; state[22] = Asi; state[23] = Aso; state[24] = Asu; 191 } 192 193 /* Load 64-bit little-endian */ 194 static inline uint64_t load64_le(const uint8_t *x) { 195 return (uint64_t)x[0] | 196 ((uint64_t)x[1] << 8) | 197 ((uint64_t)x[2] << 16) | 198 ((uint64_t)x[3] << 24) | 199 ((uint64_t)x[4] << 32) | 200 ((uint64_t)x[5] << 40) | 201 ((uint64_t)x[6] << 48) | 202 ((uint64_t)x[7] << 56); 203 } 204 205 /* Store 64-bit little-endian */ 206 static inline void store64_le(uint8_t *x, uint64_t u) { 207 x[0] = (uint8_t)u; 208 x[1] = (uint8_t)(u >> 8); 209 x[2] = (uint8_t)(u >> 16); 210 x[3] = (uint8_t)(u >> 24); 211 x[4] = (uint8_t)(u >> 32); 212 x[5] = (uint8_t)(u >> 40); 213 x[6] = (uint8_t)(u >> 48); 214 x[7] = (uint8_t)(u >> 56); 215 } 216 217 /* Keccak context */ 218 typedef struct { 219 uint64_t state[25]; 220 uint8_t buffer[200]; 221 size_t buffer_len; 222 size_t rate; /* Rate in bytes */ 223 size_t capacity; /* Capacity in bytes */ 224 uint8_t delim; /* Domain separation byte */ 225 } keccak_context; 226 227 /* Initialize Keccak */ 228 static void keccak_init(keccak_context *ctx, size_t rate, uint8_t delim) { 229 memset(ctx->state, 0, sizeof(ctx->state)); 230 ctx->buffer_len = 0; 231 ctx->rate = rate; 232 ctx->capacity = 200 - rate; 233 ctx->delim = delim; 234 } 235 236 /* Update Keccak with data */ 237 static void keccak_update(keccak_context *ctx, const uint8_t *data, size_t len) { 238 while (len > 0) { 239 size_t take = ctx->rate - ctx->buffer_len; 240 if (take > len) take = len; 241 242 memcpy(ctx->buffer + ctx->buffer_len, data, take); 243 ctx->buffer_len += take; 244 data += take; 245 len -= take; 246 247 if (ctx->buffer_len == ctx->rate) { 248 /* Absorb block */ 249 for (size_t i = 0; i < ctx->rate / 8; i++) { 250 ctx->state[i] ^= load64_le(ctx->buffer + i * 8); 251 } 252 KeccakF1600(ctx->state); 253 ctx->buffer_len = 0; 254 } 255 } 256 } 257 258 /* Finalize Keccak and produce digest */ 259 static void keccak_final(keccak_context *ctx, uint8_t *digest, size_t digest_len) { 260 /* Pad with delim */ 261 ctx->buffer[ctx->buffer_len] = ctx->delim; 262 memset(ctx->buffer + ctx->buffer_len + 1, 0, ctx->rate - ctx->buffer_len - 1); 263 ctx->buffer[ctx->rate - 1] |= 0x80; 264 265 /* Absorb final block */ 266 for (size_t i = 0; i < ctx->rate / 8; i++) { 267 ctx->state[i] ^= load64_le(ctx->buffer + i * 8); 268 } 269 KeccakF1600(ctx->state); 270 271 /* Squeeze */ 272 size_t extracted = 0; 273 while (extracted < digest_len) { 274 size_t take = ctx->rate; 275 if (take > digest_len - extracted) { 276 take = digest_len - extracted; 277 } 278 279 for (size_t i = 0; i < take / 8; i++) { 280 store64_le(digest + extracted + i * 8, ctx->state[i]); 281 } 282 /* Handle partial word */ 283 if (take % 8) { 284 uint8_t temp[8]; 285 store64_le(temp, ctx->state[take / 8]); 286 memcpy(digest + extracted + (take / 8) * 8, temp, take % 8); 287 } 288 289 extracted += take; 290 291 if (extracted < digest_len) { 292 KeccakF1600(ctx->state); 293 } 294 } 295 } 296 297 /* SHA3-224 */ 298 void sha3_224(const uint8_t *data, size_t len, uint8_t digest[28]) { 299 keccak_context ctx; 300 keccak_init(&ctx, 144, 0x06); /* rate=1152 bits=144 bytes */ 301 keccak_update(&ctx, data, len); 302 keccak_final(&ctx, digest, 28); 303 memset(&ctx, 0, sizeof(ctx)); 304 } 305 306 /* SHA3-256 */ 307 void sha3_256(const uint8_t *data, size_t len, uint8_t digest[32]) { 308 keccak_context ctx; 309 keccak_init(&ctx, 136, 0x06); /* rate=1088 bits=136 bytes, SHA3 delim */ 310 keccak_update(&ctx, data, len); 311 keccak_final(&ctx, digest, 32); 312 memset(&ctx, 0, sizeof(ctx)); 313 } 314 315 /* SHA3-384 */ 316 void sha3_384(const uint8_t *data, size_t len, uint8_t digest[48]) { 317 keccak_context ctx; 318 keccak_init(&ctx, 104, 0x06); /* rate=832 bits=104 bytes */ 319 keccak_update(&ctx, data, len); 320 keccak_final(&ctx, digest, 48); 321 memset(&ctx, 0, sizeof(ctx)); 322 } 323 324 /* SHA3-512 */ 325 void sha3_512(const uint8_t *data, size_t len, uint8_t digest[64]) { 326 keccak_context ctx; 327 keccak_init(&ctx, 72, 0x06); /* rate=576 bits=72 bytes */ 328 keccak_update(&ctx, data, len); 329 keccak_final(&ctx, digest, 64); 330 memset(&ctx, 0, sizeof(ctx)); 331 } 332 333 /* SHAKE128 - Extendable output function */ 334 void shake128(const uint8_t *data, size_t len, uint8_t *output, size_t output_len) { 335 keccak_context ctx; 336 keccak_init(&ctx, 168, 0x1F); /* rate=1344 bits=168 bytes, SHAKE delim */ 337 keccak_update(&ctx, data, len); 338 keccak_final(&ctx, output, output_len); 339 memset(&ctx, 0, sizeof(ctx)); 340 } 341 342 /* SHAKE256 - Extendable output function */ 343 void shake256(const uint8_t *data, size_t len, uint8_t *output, size_t output_len) { 344 keccak_context ctx; 345 keccak_init(&ctx, 136, 0x1F); /* rate=1088 bits=136 bytes, SHAKE delim */ 346 keccak_update(&ctx, data, len); 347 keccak_final(&ctx, output, output_len); 348 memset(&ctx, 0, sizeof(ctx)); 349 }