| 1 |
|
| /* sha3.c - an implementation of Secure Hash Algorithm 3 (Keccak). |
| 2 |
|
| * based on the |
| 3 |
|
| * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011 |
| 4 |
|
| * by Guido Bertoni, Joan Daemen, Michaƫl Peeters and Gilles Van Assche |
| 5 |
|
| * |
| 6 |
|
| * Copyright (c) 2013, Aleksey Kravchenko <rhash.admin@gmail.com> |
| 7 |
|
| * |
| 8 |
|
| * Permission to use, copy, modify, and/or distribute this software for any |
| 9 |
|
| * purpose with or without fee is hereby granted. |
| 10 |
|
| * |
| 11 |
|
| * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH |
| 12 |
|
| * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY |
| 13 |
|
| * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, |
| 14 |
|
| * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM |
| 15 |
|
| * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE |
| 16 |
|
| * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR |
| 17 |
|
| * PERFORMANCE OF THIS SOFTWARE. |
| 18 |
|
| */ |
| 19 |
|
| |
| 20 |
|
| #include <assert.h> |
| 21 |
|
| #include <string.h> |
| 22 |
|
| #include "byte_order.h" |
| 23 |
|
| #include "sha3.h" |
| 24 |
|
| |
| 25 |
|
| /* constants */ |
| 26 |
|
| #define NumberOfRounds 24 |
| 27 |
|
| |
| 28 |
|
| /* SHA3 (Keccak) constants for 24 rounds */ |
| 29 |
|
| static uint64_t keccak_round_constants[NumberOfRounds] = { |
| 30 |
|
| I64(0x0000000000000001), I64(0x0000000000008082), I64(0x800000000000808A), I64(0x8000000080008000), |
| 31 |
|
| I64(0x000000000000808B), I64(0x0000000080000001), I64(0x8000000080008081), I64(0x8000000000008009), |
| 32 |
|
| I64(0x000000000000008A), I64(0x0000000000000088), I64(0x0000000080008009), I64(0x000000008000000A), |
| 33 |
|
| I64(0x000000008000808B), I64(0x800000000000008B), I64(0x8000000000008089), I64(0x8000000000008003), |
| 34 |
|
| I64(0x8000000000008002), I64(0x8000000000000080), I64(0x000000000000800A), I64(0x800000008000000A), |
| 35 |
|
| I64(0x8000000080008081), I64(0x8000000000008080), I64(0x0000000080000001), I64(0x8000000080008008) |
| 36 |
|
| }; |
| 37 |
|
| |
| 38 |
|
| /* Initializing a sha3 context for given number of output bits */ |
| 39 |
8 |
| static void rhash_keccak_init(sha3_ctx* ctx, unsigned bits) |
| 40 |
|
| { |
| 41 |
|
| /* NB: The Keccak capacity parameter = bits * 2 */ |
| 42 |
8 |
| unsigned rate = 1600 - bits * 2; |
| 43 |
|
| |
| 44 |
8 |
| memset(ctx, 0, sizeof(sha3_ctx)); |
| 45 |
8 |
| ctx->block_size = rate / 8; |
| 46 |
8 |
▶ | assert(rate <= 1600 && (rate % 64) == 0); |
Branch: 2 branches
| Branch | True | False | Total |
| assert(rate <= 1600 && (rate % 64) == 0); |
8 |
0 |
8 |
| assert(rate <= 1600 && (rate % 64) == 0); |
8 |
0 |
8 |
|
| 47 |
8 |
| } |
| 48 |
|
| |
| 49 |
|
| /** |
| 50 |
|
| * Initialize context before calculating hash. |
| 51 |
|
| * |
| 52 |
|
| * @param ctx context to initialize |
| 53 |
|
| */ |
| 54 |
2 |
| void rhash_sha3_224_init(sha3_ctx* ctx) |
| 55 |
|
| { |
| 56 |
2 |
| rhash_keccak_init(ctx, 224); |
| 57 |
2 |
| } |
| 58 |
|
| |
| 59 |
|
| /** |
| 60 |
|
| * Initialize context before calculating hash. |
| 61 |
|
| * |
| 62 |
|
| * @param ctx context to initialize |
| 63 |
|
| */ |
| 64 |
2 |
| void rhash_sha3_256_init(sha3_ctx* ctx) |
| 65 |
|
| { |
| 66 |
2 |
| rhash_keccak_init(ctx, 256); |
| 67 |
2 |
| } |
| 68 |
|
| |
| 69 |
|
| /** |
| 70 |
|
| * Initialize context before calculating hash. |
| 71 |
|
| * |
| 72 |
|
| * @param ctx context to initialize |
| 73 |
|
| */ |
| 74 |
2 |
| void rhash_sha3_384_init(sha3_ctx* ctx) |
| 75 |
|
| { |
| 76 |
2 |
| rhash_keccak_init(ctx, 384); |
| 77 |
2 |
| } |
| 78 |
|
| |
| 79 |
|
| /** |
| 80 |
|
| * Initialize context before calculating hash. |
| 81 |
|
| * |
| 82 |
|
| * @param ctx context to initialize |
| 83 |
|
| */ |
| 84 |
2 |
| void rhash_sha3_512_init(sha3_ctx* ctx) |
| 85 |
|
| { |
| 86 |
2 |
| rhash_keccak_init(ctx, 512); |
| 87 |
2 |
| } |
| 88 |
|
| |
| 89 |
|
| #define XORED_A(i) A[(i)] ^ A[(i) + 5] ^ A[(i) + 10] ^ A[(i) + 15] ^ A[(i) + 20] |
| 90 |
|
| #define THETA_STEP(i) \ |
| 91 |
|
| A[(i)] ^= D[(i)]; \ |
| 92 |
|
| A[(i) + 5] ^= D[(i)]; \ |
| 93 |
|
| A[(i) + 10] ^= D[(i)]; \ |
| 94 |
|
| A[(i) + 15] ^= D[(i)]; \ |
| 95 |
|
| A[(i) + 20] ^= D[(i)] \ |
| 96 |
|
| |
| 97 |
|
| /* Keccak theta() transformation */ |
| 98 |
192 |
| static void keccak_theta(uint64_t* A) |
| 99 |
|
| { |
| 100 |
|
| uint64_t D[5]; |
| 101 |
192 |
| D[0] = ROTL64(XORED_A(1), 1) ^ XORED_A(4); |
| 102 |
192 |
| D[1] = ROTL64(XORED_A(2), 1) ^ XORED_A(0); |
| 103 |
192 |
| D[2] = ROTL64(XORED_A(3), 1) ^ XORED_A(1); |
| 104 |
192 |
| D[3] = ROTL64(XORED_A(4), 1) ^ XORED_A(2); |
| 105 |
192 |
| D[4] = ROTL64(XORED_A(0), 1) ^ XORED_A(3); |
| 106 |
192 |
| THETA_STEP(0); |
| 107 |
192 |
| THETA_STEP(1); |
| 108 |
192 |
| THETA_STEP(2); |
| 109 |
192 |
| THETA_STEP(3); |
| 110 |
192 |
| THETA_STEP(4); |
| 111 |
192 |
| } |
| 112 |
|
| |
| 113 |
|
| /* Keccak pi() transformation */ |
| 114 |
192 |
| static void keccak_pi(uint64_t* A) |
| 115 |
|
| { |
| 116 |
|
| uint64_t A1; |
| 117 |
192 |
| A1 = A[1]; |
| 118 |
192 |
| A[ 1] = A[ 6]; |
| 119 |
192 |
| A[ 6] = A[ 9]; |
| 120 |
192 |
| A[ 9] = A[22]; |
| 121 |
192 |
| A[22] = A[14]; |
| 122 |
192 |
| A[14] = A[20]; |
| 123 |
192 |
| A[20] = A[ 2]; |
| 124 |
192 |
| A[ 2] = A[12]; |
| 125 |
192 |
| A[12] = A[13]; |
| 126 |
192 |
| A[13] = A[19]; |
| 127 |
192 |
| A[19] = A[23]; |
| 128 |
192 |
| A[23] = A[15]; |
| 129 |
192 |
| A[15] = A[ 4]; |
| 130 |
192 |
| A[ 4] = A[24]; |
| 131 |
192 |
| A[24] = A[21]; |
| 132 |
192 |
| A[21] = A[ 8]; |
| 133 |
192 |
| A[ 8] = A[16]; |
| 134 |
192 |
| A[16] = A[ 5]; |
| 135 |
192 |
| A[ 5] = A[ 3]; |
| 136 |
192 |
| A[ 3] = A[18]; |
| 137 |
192 |
| A[18] = A[17]; |
| 138 |
192 |
| A[17] = A[11]; |
| 139 |
192 |
| A[11] = A[ 7]; |
| 140 |
192 |
| A[ 7] = A[10]; |
| 141 |
192 |
| A[10] = A1; |
| 142 |
|
| /* note: A[ 0] is left as is */ |
| 143 |
192 |
| } |
| 144 |
|
| |
| 145 |
|
| #define CHI_STEP(i) \ |
| 146 |
|
| A0 = A[0 + (i)]; \ |
| 147 |
|
| A1 = A[1 + (i)]; \ |
| 148 |
|
| A[0 + (i)] ^= ~A1 & A[2 + (i)]; \ |
| 149 |
|
| A[1 + (i)] ^= ~A[2 + (i)] & A[3 + (i)]; \ |
| 150 |
|
| A[2 + (i)] ^= ~A[3 + (i)] & A[4 + (i)]; \ |
| 151 |
|
| A[3 + (i)] ^= ~A[4 + (i)] & A0; \ |
| 152 |
|
| A[4 + (i)] ^= ~A0 & A1 \ |
| 153 |
|
| |
| 154 |
|
| /* Keccak chi() transformation */ |
| 155 |
192 |
| static void keccak_chi(uint64_t* A) |
| 156 |
|
| { |
| 157 |
|
| uint64_t A0, A1; |
| 158 |
192 |
| CHI_STEP(0); |
| 159 |
192 |
| CHI_STEP(5); |
| 160 |
192 |
| CHI_STEP(10); |
| 161 |
192 |
| CHI_STEP(15); |
| 162 |
192 |
| CHI_STEP(20); |
| 163 |
192 |
| } |
| 164 |
|
| |
| 165 |
8 |
| static void rhash_sha3_permutation(uint64_t* state) |
| 166 |
|
| { |
| 167 |
|
| int round; |
| 168 |
200 |
▶ | for (round = 0; round < NumberOfRounds; round++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (round = 0; round < NumberOfRounds; round++) |
192 |
8 |
200 |
|
| 169 |
|
| { |
| 170 |
192 |
| keccak_theta(state); |
| 171 |
|
| |
| 172 |
|
| /* apply Keccak rho() transformation */ |
| 173 |
192 |
| state[ 1] = ROTL64(state[ 1], 1); |
| 174 |
192 |
| state[ 2] = ROTL64(state[ 2], 62); |
| 175 |
192 |
| state[ 3] = ROTL64(state[ 3], 28); |
| 176 |
192 |
| state[ 4] = ROTL64(state[ 4], 27); |
| 177 |
192 |
| state[ 5] = ROTL64(state[ 5], 36); |
| 178 |
192 |
| state[ 6] = ROTL64(state[ 6], 44); |
| 179 |
192 |
| state[ 7] = ROTL64(state[ 7], 6); |
| 180 |
192 |
| state[ 8] = ROTL64(state[ 8], 55); |
| 181 |
192 |
| state[ 9] = ROTL64(state[ 9], 20); |
| 182 |
192 |
| state[10] = ROTL64(state[10], 3); |
| 183 |
192 |
| state[11] = ROTL64(state[11], 10); |
| 184 |
192 |
| state[12] = ROTL64(state[12], 43); |
| 185 |
192 |
| state[13] = ROTL64(state[13], 25); |
| 186 |
192 |
| state[14] = ROTL64(state[14], 39); |
| 187 |
192 |
| state[15] = ROTL64(state[15], 41); |
| 188 |
192 |
| state[16] = ROTL64(state[16], 45); |
| 189 |
192 |
| state[17] = ROTL64(state[17], 15); |
| 190 |
192 |
| state[18] = ROTL64(state[18], 21); |
| 191 |
192 |
| state[19] = ROTL64(state[19], 8); |
| 192 |
192 |
| state[20] = ROTL64(state[20], 18); |
| 193 |
192 |
| state[21] = ROTL64(state[21], 2); |
| 194 |
192 |
| state[22] = ROTL64(state[22], 61); |
| 195 |
192 |
| state[23] = ROTL64(state[23], 56); |
| 196 |
192 |
| state[24] = ROTL64(state[24], 14); |
| 197 |
|
| |
| 198 |
192 |
| keccak_pi(state); |
| 199 |
192 |
| keccak_chi(state); |
| 200 |
|
| |
| 201 |
|
| /* apply iota(state, round) */ |
| 202 |
192 |
| *state ^= keccak_round_constants[round]; |
| 203 |
|
| } |
| 204 |
8 |
| } |
| 205 |
|
| |
| 206 |
|
| /** |
| 207 |
|
| * The core transformation. Process the specified block of data. |
| 208 |
|
| * |
| 209 |
|
| * @param hash the algorithm state |
| 210 |
|
| * @param block the message block to process |
| 211 |
|
| * @param block_size the size of the processed block in bytes |
| 212 |
|
| */ |
| 213 |
8 |
| static void rhash_sha3_process_block(uint64_t hash[25], const uint64_t* block, size_t block_size) |
| 214 |
|
| { |
| 215 |
|
| /* expanded loop */ |
| 216 |
8 |
| hash[ 0] ^= le2me_64(block[ 0]); |
| 217 |
8 |
| hash[ 1] ^= le2me_64(block[ 1]); |
| 218 |
8 |
| hash[ 2] ^= le2me_64(block[ 2]); |
| 219 |
8 |
| hash[ 3] ^= le2me_64(block[ 3]); |
| 220 |
8 |
| hash[ 4] ^= le2me_64(block[ 4]); |
| 221 |
8 |
| hash[ 5] ^= le2me_64(block[ 5]); |
| 222 |
8 |
| hash[ 6] ^= le2me_64(block[ 6]); |
| 223 |
8 |
| hash[ 7] ^= le2me_64(block[ 7]); |
| 224 |
8 |
| hash[ 8] ^= le2me_64(block[ 8]); |
| 225 |
|
| /* if not sha3-512 */ |
| 226 |
8 |
▶ | if (block_size > 72) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (block_size > 72) { |
6 |
2 |
8 |
|
| 227 |
6 |
| hash[ 9] ^= le2me_64(block[ 9]); |
| 228 |
6 |
| hash[10] ^= le2me_64(block[10]); |
| 229 |
6 |
| hash[11] ^= le2me_64(block[11]); |
| 230 |
6 |
| hash[12] ^= le2me_64(block[12]); |
| 231 |
|
| /* if not sha3-384 */ |
| 232 |
6 |
▶ | if (block_size > 104) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (block_size > 104) { |
4 |
2 |
6 |
|
| 233 |
4 |
| hash[13] ^= le2me_64(block[13]); |
| 234 |
4 |
| hash[14] ^= le2me_64(block[14]); |
| 235 |
4 |
| hash[15] ^= le2me_64(block[15]); |
| 236 |
4 |
| hash[16] ^= le2me_64(block[16]); |
| 237 |
|
| /* if not sha3-256 */ |
| 238 |
4 |
▶ | if (block_size > 136) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (block_size > 136) { |
2 |
2 |
4 |
|
| 239 |
2 |
| hash[17] ^= le2me_64(block[17]); |
| 240 |
|
| #ifdef FULL_SHA3_FAMILY_SUPPORT |
| 241 |
|
| /* if not sha3-224 */ |
| 242 |
|
| if (block_size > 144) { |
| 243 |
|
| hash[18] ^= le2me_64(block[18]); |
| 244 |
|
| hash[19] ^= le2me_64(block[19]); |
| 245 |
|
| hash[20] ^= le2me_64(block[20]); |
| 246 |
|
| hash[21] ^= le2me_64(block[21]); |
| 247 |
|
| hash[22] ^= le2me_64(block[22]); |
| 248 |
|
| hash[23] ^= le2me_64(block[23]); |
| 249 |
|
| hash[24] ^= le2me_64(block[24]); |
| 250 |
|
| } |
| 251 |
|
| #endif |
| 252 |
|
| } |
| 253 |
|
| } |
| 254 |
|
| } |
| 255 |
|
| /* make a permutation of the hash */ |
| 256 |
8 |
| rhash_sha3_permutation(hash); |
| 257 |
8 |
| } |
| 258 |
|
| |
| 259 |
|
| #define SHA3_FINALIZED 0x80000000 |
| 260 |
|
| |
| 261 |
|
| /** |
| 262 |
|
| * Calculate message hash. |
| 263 |
|
| * Can be called repeatedly with chunks of the message to be hashed. |
| 264 |
|
| * |
| 265 |
|
| * @param ctx the algorithm context containing current hashing state |
| 266 |
|
| * @param msg message chunk |
| 267 |
|
| * @param size length of the message chunk |
| 268 |
|
| */ |
| 269 |
8 |
| void rhash_sha3_update(sha3_ctx* ctx, const unsigned char* msg, size_t size) |
| 270 |
|
| { |
| 271 |
8 |
| size_t index = (size_t)ctx->rest; |
| 272 |
8 |
| size_t block_size = (size_t)ctx->block_size; |
| 273 |
|
| |
| 274 |
8 |
▶ | if (ctx->rest & SHA3_FINALIZED) return; /* too late for additional input */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (ctx->rest & SHA3_FINALIZED) return; /* too late for additional input */ |
0 |
8 |
8 |
|
| 275 |
8 |
| ctx->rest = (unsigned)((ctx->rest + size) % block_size); |
| 276 |
|
| |
| 277 |
|
| /* fill partial block */ |
| 278 |
8 |
▶ | if (index) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (index) { |
0 |
8 |
8 |
|
| 279 |
0 |
| size_t left = block_size - index; |
| 280 |
0 |
| memcpy((char*)ctx->message + index, msg, (size < left ? size : left)); |
| 281 |
0 |
▶ | if (size < left) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < left) return; |
0 |
0 |
0 |
|
| 282 |
|
| |
| 283 |
|
| /* process partial block */ |
| 284 |
0 |
| rhash_sha3_process_block(ctx->hash, ctx->message, block_size); |
| 285 |
0 |
| msg += left; |
| 286 |
0 |
| size -= left; |
| 287 |
|
| } |
| 288 |
8 |
▶ | while (size >= block_size) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (size >= block_size) { |
0 |
8 |
8 |
|
| 289 |
|
| uint64_t* aligned_message_block; |
| 290 |
0 |
▶ | if (IS_ALIGNED_64(msg)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (IS_ALIGNED_64(msg)) { |
0 |
0 |
0 |
|
| 291 |
|
| /* the most common case is processing of an already aligned message |
| 292 |
|
| without copying it */ |
| 293 |
0 |
| aligned_message_block = (uint64_t*)msg; |
| 294 |
|
| } else { |
| 295 |
0 |
| memcpy(ctx->message, msg, block_size); |
| 296 |
0 |
| aligned_message_block = ctx->message; |
| 297 |
|
| } |
| 298 |
|
| |
| 299 |
0 |
| rhash_sha3_process_block(ctx->hash, aligned_message_block, block_size); |
| 300 |
0 |
| msg += block_size; |
| 301 |
0 |
| size -= block_size; |
| 302 |
|
| } |
| 303 |
8 |
▶ | if (size) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (size) { |
8 |
0 |
8 |
|
| 304 |
8 |
| memcpy(ctx->message, msg, size); /* save leftovers */ |
| 305 |
|
| } |
| 306 |
|
| } |
| 307 |
|
| |
| 308 |
|
| /** |
| 309 |
|
| * Store calculated hash into the given array. |
| 310 |
|
| * |
| 311 |
|
| * @param ctx the algorithm context containing current hashing state |
| 312 |
|
| * @param result calculated hash in binary form |
| 313 |
|
| */ |
| 314 |
8 |
| void rhash_sha3_final(sha3_ctx* ctx, unsigned char* result) |
| 315 |
|
| { |
| 316 |
8 |
| size_t digest_length = 100 - ctx->block_size / 2; |
| 317 |
8 |
| const size_t block_size = ctx->block_size; |
| 318 |
|
| |
| 319 |
8 |
▶ | if (!(ctx->rest & SHA3_FINALIZED)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(ctx->rest & SHA3_FINALIZED)) |
8 |
0 |
8 |
|
| 320 |
|
| { |
| 321 |
|
| /* clear the rest of the data queue */ |
| 322 |
8 |
| memset((char*)ctx->message + ctx->rest, 0, block_size - ctx->rest); |
| 323 |
8 |
| ((char*)ctx->message)[ctx->rest] |= 0x06; |
| 324 |
8 |
| ((char*)ctx->message)[block_size - 1] |= 0x80; |
| 325 |
|
| |
| 326 |
|
| /* process final block */ |
| 327 |
8 |
| rhash_sha3_process_block(ctx->hash, ctx->message, block_size); |
| 328 |
8 |
| ctx->rest = SHA3_FINALIZED; /* mark context as finalized */ |
| 329 |
|
| } |
| 330 |
|
| |
| 331 |
8 |
▶ | assert(block_size > digest_length); |
Branch: 1 branch
| Branch | True | False | Total |
| assert(block_size > digest_length); |
0 |
8 |
8 |
|
| 332 |
8 |
▶ | if (result) me64_to_le_str(result, ctx->hash, digest_length); |
Branch: 1 branch
| Branch | True | False | Total |
| if (result) me64_to_le_str(result, ctx->hash, digest_length); |
8 |
0 |
8 |
|
| 333 |
8 |
| } |
| 334 |
|
| |
| 335 |
|
| #ifdef USE_KECCAK |
| 336 |
|
| /** |
| 337 |
|
| * Store calculated hash into the given array. |
| 338 |
|
| * |
| 339 |
|
| * @param ctx the algorithm context containing current hashing state |
| 340 |
|
| * @param result calculated hash in binary form |
| 341 |
|
| */ |
| 342 |
|
| void rhash_keccak_final(sha3_ctx* ctx, unsigned char* result) |
| 343 |
|
| { |
| 344 |
|
| size_t digest_length = 100 - ctx->block_size / 2; |
| 345 |
|
| const size_t block_size = ctx->block_size; |
| 346 |
|
| |
| 347 |
|
| if (!(ctx->rest & SHA3_FINALIZED)) |
| 348 |
|
| { |
| 349 |
|
| /* clear the rest of the data queue */ |
| 350 |
|
| memset((char*)ctx->message + ctx->rest, 0, block_size - ctx->rest); |
| 351 |
|
| ((char*)ctx->message)[ctx->rest] |= 0x01; |
| 352 |
|
| ((char*)ctx->message)[block_size - 1] |= 0x80; |
| 353 |
|
| |
| 354 |
|
| /* process final block */ |
| 355 |
|
| rhash_sha3_process_block(ctx->hash, ctx->message, block_size); |
| 356 |
|
| ctx->rest = SHA3_FINALIZED; /* mark context as finalized */ |
| 357 |
|
| } |
| 358 |
|
| |
| 359 |
|
| assert(block_size > digest_length); |
| 360 |
|
| if (result) me64_to_le_str(result, ctx->hash, digest_length); |
| 361 |
|
| } |
| 362 |
|
| #endif /* USE_KECCAK */ |