Line data Source code
1 : /**
2 : * The MIT License (MIT)
3 : *
4 : * Copyright (c) 2021 RSK Labs Ltd
5 : *
6 : * Permission is hereby granted, free of charge, to any person obtaining a copy
7 : * of this software and associated documentation files (the "Software"), to
8 : * deal in the Software without restriction, including without limitation the
9 : * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 : * sell copies of the Software, and to permit persons to whom the Software is
11 : * furnished to do so, subject to the following conditions:
12 : *
13 : * The above copyright notice and this permission notice shall be included in
14 : * all copies or substantial portions of the Software.
15 : *
16 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 : * IN THE SOFTWARE.
23 : */
24 :
25 : /**
26 : * Third party library taken from:
27 : * https://github.com/firefly/wallet/blob/29adeaf7029142063b7a6878e049efd4c6534982/source/libs/ethers/src/keccak256.c
28 : */
29 :
30 : /* sha3 - an implementation of Secure Hash Algorithm 3 (Keccak).
31 : * based on the
32 : * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011
33 : * by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche
34 : *
35 : * Copyright: 2013 Aleksey Kravchenko <rhash.admin@gmail.com>
36 : *
37 : * Permission is hereby granted, free of charge, to any person obtaining a
38 : * copy of this software and associated documentation files (the "Software"),
39 : * to deal in the Software without restriction, including without limitation
40 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
41 : * and/or sell copies of the Software, and to permit persons to whom the
42 : * Software is furnished to do so.
43 : *
44 : * This program is distributed in the hope that it will be useful, but
45 : * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
46 : * or FITNESS FOR A PARTICULAR PURPOSE. Use this program at your own risk!
47 : */
48 :
49 : #include "keccak256.h"
50 :
51 : //#include <avr/pgmspace.h>
52 :
53 : #include <string.h>
54 : #include <stdint.h>
55 :
56 : #define BLOCK_SIZE ((1600 - 256 * 2) / 8)
57 :
58 : #define I64(x) x##LL
59 : #define ROTL64(qword, n) ((qword) << (n) ^ ((qword) >> (64 - (n))))
60 : #define le2me_64(x) (x)
61 : #define IS_ALIGNED_64(p) (0 == (7 & ((const char*)(p) - (const char*)0)))
62 : #define me64_to_le_str(to, from, length) memcpy((to), (from), (length))
63 :
64 : /* constants */
65 :
66 : //const uint8_t round_constant_info[] PROGMEM = {
67 : //const uint8_t constants[] PROGMEM = {
68 : const uint8_t constants[] = {
69 :
70 : 1, 26, 94, 112, 31, 33, 121, 85, 14, 12, 53, 38, 63, 79, 93, 83, 82, 72, 22, 102, 121, 88, 33, 116,
71 : //};
72 :
73 : //const uint8_t pi_transform[] PROGMEM = {
74 : 1, 6, 9, 22, 14, 20, 2, 12, 13, 19, 23, 15, 4, 24, 21, 8, 16, 5, 3, 18, 17, 11, 7, 10,
75 : //};
76 :
77 : //const uint8_t rhoTransforms[] PROGMEM = {
78 : 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14,
79 : };
80 :
81 : #define TYPE_ROUND_INFO 0
82 : #define TYPE_PI_TRANSFORM 24
83 : #define TYPE_RHO_TRANSFORM 48
84 :
85 15960 : uint8_t getConstant(uint8_t type, uint8_t index) {
86 15960 : return constants[type + index];
87 : }
88 :
89 168 : static uint64_t get_round_constant(uint8_t round) {
90 168 : uint64_t result = 0;
91 :
92 168 : uint8_t roundInfo = getConstant(TYPE_ROUND_INFO, round);
93 168 : if (roundInfo & (1 << 6)) { result |= ((uint64_t)1 << 63); }
94 168 : if (roundInfo & (1 << 5)) { result |= ((uint64_t)1 << 31); }
95 168 : if (roundInfo & (1 << 4)) { result |= ((uint64_t)1 << 15); }
96 168 : if (roundInfo & (1 << 3)) { result |= ((uint64_t)1 << 7); }
97 168 : if (roundInfo & (1 << 2)) { result |= ((uint64_t)1 << 3); }
98 168 : if (roundInfo & (1 << 1)) { result |= ((uint64_t)1 << 1); }
99 168 : if (roundInfo & (1 << 0)) { result |= ((uint64_t)1 << 0); }
100 :
101 168 : return result;
102 : }
103 :
104 :
105 : /* Initializing a sha3 context for given number of output bits */
106 3 : void keccak_init(SHA3_CTX *ctx) {
107 : /* NB: The Keccak capacity parameter = bits * 2 */
108 :
109 3 : memset(ctx, 0, sizeof(SHA3_CTX));
110 3 : }
111 :
112 : /* Keccak theta() transformation */
113 168 : static void keccak_theta(uint64_t *A) {
114 : uint64_t C[5], D[5];
115 :
116 1008 : for (uint8_t i = 0; i < 5; i++) {
117 840 : C[i] = A[i];
118 4200 : for (uint8_t j = 5; j < 25; j += 5) { C[i] ^= A[i + j]; }
119 : }
120 :
121 1008 : for (uint8_t i = 0; i < 5; i++) {
122 840 : D[i] = ROTL64(C[(i + 1) % 5], 1) ^ C[(i + 4) % 5];
123 : }
124 :
125 1008 : for (uint8_t i = 0; i < 5; i++) {
126 : //for (uint8_t j = 0; j < 25; j += 5) {
127 5040 : for (uint8_t j = 0; j < 25; j += 5) { A[i + j] ^= D[i]; }
128 : }
129 168 : }
130 :
131 :
132 : /* Keccak pi() transformation */
133 168 : static void keccak_pi(uint64_t *A) {
134 168 : uint64_t A1 = A[1];
135 4032 : for (uint8_t i = 1; i < 24; i++) {
136 3864 : A[getConstant(TYPE_PI_TRANSFORM, i - 1)] = A[getConstant(TYPE_PI_TRANSFORM, i)];
137 : }
138 168 : A[10] = A1;
139 : /* note: A[ 0] is left as is */
140 168 : }
141 :
142 : /*
143 : ketch uses 30084 bytes (93%) of program storage space. Maximum is 32256 bytes.
144 : Global variables use 743 bytes (36%) of dynamic memory, leaving 1305 bytes for local variables. Maximum is 2048 bytes.
145 :
146 : */
147 : /* Keccak chi() transformation */
148 168 : static void keccak_chi(uint64_t *A) {
149 1008 : for (uint8_t i = 0; i < 25; i += 5) {
150 840 : uint64_t A0 = A[0 + i], A1 = A[1 + i];
151 840 : A[0 + i] ^= ~A1 & A[2 + i];
152 840 : A[1 + i] ^= ~A[2 + i] & A[3 + i];
153 840 : A[2 + i] ^= ~A[3 + i] & A[4 + i];
154 840 : A[3 + i] ^= ~A[4 + i] & A0;
155 840 : A[4 + i] ^= ~A0 & A1;
156 : }
157 168 : }
158 :
159 :
160 7 : static void sha3_permutation(uint64_t *state) {
161 175 : for (uint8_t round = 0; round < 24; round++) {
162 168 : keccak_theta(state);
163 :
164 : /* apply Keccak rho() transformation */
165 4200 : for (uint8_t i = 1; i < 25; i++) {
166 4032 : state[i] = ROTL64(state[i], getConstant(TYPE_RHO_TRANSFORM, i - 1));
167 : }
168 :
169 168 : keccak_pi(state);
170 168 : keccak_chi(state);
171 :
172 : /* apply iota(state, round) */
173 168 : *state ^= get_round_constant(round);
174 : }
175 7 : }
176 :
177 : /**
178 : * The core transformation. Process the specified block of data.
179 : *
180 : * @param hash the algorithm state
181 : * @param block the message block to process
182 : * @param block_size the size of the processed block in bytes
183 : */
184 7 : static void sha3_process_block(uint64_t hash[25], const uint64_t *block) {
185 126 : for (uint8_t i = 0; i < 17; i++) {
186 119 : hash[i] ^= le2me_64(block[i]);
187 : }
188 :
189 : /* make a permutation of the hash */
190 7 : sha3_permutation(hash);
191 7 : }
192 :
193 : //#define SHA3_FINALIZED 0x80000000
194 : //#define SHA3_FINALIZED 0x8000
195 :
196 : /**
197 : * Calculate message hash.
198 : * Can be called repeatedly with chunks of the message to be hashed.
199 : *
200 : * @param ctx the algorithm context containing current hashing state
201 : * @param msg message chunk
202 : * @param size length of the message chunk
203 : */
204 3 : void keccak_update(SHA3_CTX *ctx, const unsigned char *msg, uint16_t size)
205 : {
206 3 : uint16_t idx = (uint16_t)ctx->rest;
207 :
208 : //if (ctx->rest & SHA3_FINALIZED) return; /* too late for additional input */
209 3 : ctx->rest = (unsigned)((ctx->rest + size) % BLOCK_SIZE);
210 :
211 : /* fill partial block */
212 3 : if (idx) {
213 0 : uint16_t left = BLOCK_SIZE - idx;
214 0 : memcpy((char*)ctx->message + idx, msg, (size < left ? size : left));
215 0 : if (size < left) return;
216 :
217 : /* process partial block */
218 0 : sha3_process_block(ctx->hash, ctx->message);
219 0 : msg += left;
220 0 : size -= left;
221 : }
222 :
223 7 : while (size >= BLOCK_SIZE) {
224 : uint64_t* aligned_message_block;
225 4 : if (IS_ALIGNED_64(msg)) {
226 : // the most common case is processing of an already aligned message without copying it
227 4 : aligned_message_block = (uint64_t*)(void*)msg;
228 : } else {
229 0 : memcpy(ctx->message, msg, BLOCK_SIZE);
230 0 : aligned_message_block = ctx->message;
231 : }
232 :
233 4 : sha3_process_block(ctx->hash, aligned_message_block);
234 4 : msg += BLOCK_SIZE;
235 4 : size -= BLOCK_SIZE;
236 : }
237 :
238 3 : if (size) {
239 3 : memcpy(ctx->message, msg, size); /* save leftovers */
240 : }
241 : }
242 :
243 : /**
244 : * Store calculated hash into the given array.
245 : *
246 : * @param ctx the algorithm context containing current hashing state
247 : * @param result calculated hash in binary form
248 : */
249 3 : void keccak_final(SHA3_CTX *ctx, unsigned char* result)
250 : {
251 3 : uint16_t digest_length = 100 - BLOCK_SIZE / 2;
252 :
253 : // if (!(ctx->rest & SHA3_FINALIZED)) {
254 : /* clear the rest of the data queue */
255 3 : memset((char*)ctx->message + ctx->rest, 0, BLOCK_SIZE - ctx->rest);
256 3 : ((char*)ctx->message)[ctx->rest] |= 0x01;
257 3 : ((char*)ctx->message)[BLOCK_SIZE - 1] |= 0x80;
258 :
259 : /* process final block */
260 3 : sha3_process_block(ctx->hash, ctx->message);
261 : // ctx->rest = SHA3_FINALIZED; /* mark context as finalized */
262 : // }
263 :
264 3 : if (result) {
265 3 : me64_to_le_str(result, ctx->hash, digest_length);
266 : }
267 3 : }
|
