/src/trezor-firmware/crypto/ripemd160.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "ripemd160.h" |
2 | | #include <assert.h> |
3 | | #include "memzero.h" |
4 | | |
5 | | // Downlaoded from https://github.com/sipa/Coin25519/blob/master/src/crypto/ripemd160.c |
6 | | |
7 | | // adapted by Pieter Wuille in 2012; all changes are in the public domain |
8 | | |
9 | | /* |
10 | | * |
11 | | * RIPEMD160.c : RIPEMD-160 implementation |
12 | | * |
13 | | * Written in 2008 by Dwayne C. Litzenberger <dlitz@dlitz.net> |
14 | | * |
15 | | * =================================================================== |
16 | | * The contents of this file are dedicated to the public domain. To |
17 | | * the extent that dedication to the public domain is not available, |
18 | | * everyone is granted a worldwide, perpetual, royalty-free, |
19 | | * non-exclusive license to exercise all rights associated with the |
20 | | * contents of this file for any purpose whatsoever. |
21 | | * No rights are reserved. |
22 | | * |
23 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
24 | | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
25 | | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
26 | | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS |
27 | | * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN |
28 | | * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
29 | | * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
30 | | * SOFTWARE. |
31 | | * =================================================================== |
32 | | * |
33 | | * Country of origin: Canada |
34 | | * |
35 | | * This implementation (written in C) is based on an implementation the author |
36 | | * wrote in Python. |
37 | | * |
38 | | * This implementation was written with reference to the RIPEMD-160 |
39 | | * specification, which is available at: |
40 | | * http://homes.esat.kuleuven.be/~cosicart/pdf/AB-9601/ |
41 | | * |
42 | | * It is also documented in the _Handbook of Applied Cryptography_, as |
43 | | * Algorithm 9.55. It's on page 30 of the following PDF file: |
44 | | * http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf |
45 | | * |
46 | | * The RIPEMD-160 specification doesn't really tell us how to do padding, but |
47 | | * since RIPEMD-160 is inspired by MD4, you can use the padding algorithm from |
48 | | * RFC 1320. |
49 | | * |
50 | | * According to http://www.users.zetnet.co.uk/hopwood/crypto/scan/md.html: |
51 | | * "RIPEMD-160 is big-bit-endian, little-byte-endian, and left-justified." |
52 | | */ |
53 | | |
54 | | #include <stdint.h> |
55 | | |
56 | | #include <string.h> |
57 | | |
58 | 104 | #define RIPEMD160_DIGEST_SIZE RIPEMD160_DIGEST_LENGTH |
59 | | |
60 | | /* cyclic left-shift the 32-bit word n left by s bits */ |
61 | 12.0M | #define ROL(s, n) (((n) << (s)) | ((n) >> (32-(s)))) |
62 | | |
63 | | /* Initial values for the chaining variables. |
64 | | * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */ |
65 | | static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u }; |
66 | | |
67 | | /* Ordering of message words. Based on the permutations rho(i) and pi(i), defined as follows: |
68 | | * |
69 | | * rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i] 0 <= i <= 15 |
70 | | * |
71 | | * pi(i) := 9*i + 5 (mod 16) |
72 | | * |
73 | | * Line | Round 1 | Round 2 | Round 3 | Round 4 | Round 5 |
74 | | * -------+-----------+-----------+-----------+-----------+----------- |
75 | | * left | id | rho | rho^2 | rho^3 | rho^4 |
76 | | * right | pi | rho pi | rho^2 pi | rho^3 pi | rho^4 pi |
77 | | */ |
78 | | |
79 | | /* Left line */ |
80 | | static const uint8_t RL[5][16] = { |
81 | | { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, /* Round 1: id */ |
82 | | { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }, /* Round 2: rho */ |
83 | | { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 }, /* Round 3: rho^2 */ |
84 | | { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 }, /* Round 4: rho^3 */ |
85 | | { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 } /* Round 5: rho^4 */ |
86 | | }; |
87 | | |
88 | | /* Right line */ |
89 | | static const uint8_t RR[5][16] = { |
90 | | { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 }, /* Round 1: pi */ |
91 | | { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 }, /* Round 2: rho pi */ |
92 | | { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 }, /* Round 3: rho^2 pi */ |
93 | | { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 }, /* Round 4: rho^3 pi */ |
94 | | { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 } /* Round 5: rho^4 pi */ |
95 | | }; |
96 | | |
97 | | /* |
98 | | * Shifts - Since we don't actually re-order the message words according to |
99 | | * the permutations above (we could, but it would be slower), these tables |
100 | | * come with the permutations pre-applied. |
101 | | */ |
102 | | |
103 | | /* Shifts, left line */ |
104 | | static const uint8_t SL[5][16] = { |
105 | | { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */ |
106 | | { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */ |
107 | | { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */ |
108 | | { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */ |
109 | | { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 } /* Round 5 */ |
110 | | }; |
111 | | |
112 | | /* Shifts, right line */ |
113 | | static const uint8_t SR[5][16] = { |
114 | | { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */ |
115 | | { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */ |
116 | | { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */ |
117 | | { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */ |
118 | | { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 } /* Round 5 */ |
119 | | }; |
120 | | |
121 | | /* Boolean functions */ |
122 | | |
123 | | #define F1(x, y, z) ((x) ^ (y) ^ (z)) |
124 | | #define F2(x, y, z) (((x) & (y)) | (~(x) & (z))) |
125 | | #define F3(x, y, z) (((x) | ~(y)) ^ (z)) |
126 | | #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z))) |
127 | | #define F5(x, y, z) ((x) ^ ((y) | ~(z))) |
128 | | |
129 | | /* Round constants, left line */ |
130 | | static const uint32_t KL[5] = { |
131 | | 0x00000000u, /* Round 1: 0 */ |
132 | | 0x5A827999u, /* Round 2: floor(2**30 * sqrt(2)) */ |
133 | | 0x6ED9EBA1u, /* Round 3: floor(2**30 * sqrt(3)) */ |
134 | | 0x8F1BBCDCu, /* Round 4: floor(2**30 * sqrt(5)) */ |
135 | | 0xA953FD4Eu /* Round 5: floor(2**30 * sqrt(7)) */ |
136 | | }; |
137 | | |
138 | | /* Round constants, right line */ |
139 | | static const uint32_t KR[5] = { |
140 | | 0x50A28BE6u, /* Round 1: floor(2**30 * cubert(2)) */ |
141 | | 0x5C4DD124u, /* Round 2: floor(2**30 * cubert(3)) */ |
142 | | 0x6D703EF3u, /* Round 3: floor(2**30 * cubert(5)) */ |
143 | | 0x7A6D76E9u, /* Round 4: floor(2**30 * cubert(7)) */ |
144 | | 0x00000000u /* Round 5: 0 */ |
145 | | }; |
146 | | |
147 | | void ripemd160_init(ripemd160_state *self) |
148 | 52 | { |
149 | | |
150 | 52 | memcpy(self->h, initial_h, RIPEMD160_DIGEST_SIZE); |
151 | 52 | memset(&self->buf, 0, sizeof(self->buf)); |
152 | 52 | self->length = 0; |
153 | 52 | self->bufpos = 0; |
154 | 52 | } |
155 | | |
156 | | #ifdef PCT_BIG_ENDIAN |
157 | | static inline void byteswap32(uint32_t *v) |
158 | | { |
159 | | union { uint32_t w; uint8_t b[4]; } x = {0}, y = {0}; |
160 | | |
161 | | x.w = *v; |
162 | | y.b[0] = x.b[3]; |
163 | | y.b[1] = x.b[2]; |
164 | | y.b[2] = x.b[1]; |
165 | | y.b[3] = x.b[0]; |
166 | | *v = y.w; |
167 | | |
168 | | /* Wipe temporary variables */ |
169 | | x.w = y.w = 0; |
170 | | } |
171 | | |
172 | | static inline void byteswap_digest(uint32_t *p) |
173 | | { |
174 | | unsigned int i = 0; |
175 | | |
176 | | for (i = 0; i < 4; i++) { |
177 | | byteswap32(p++); |
178 | | byteswap32(p++); |
179 | | byteswap32(p++); |
180 | | byteswap32(p++); |
181 | | } |
182 | | } |
183 | | #endif |
184 | | |
185 | | /* The RIPEMD160 compression function. Operates on self->buf */ |
186 | | static void ripemd160_compress(ripemd160_state *self) |
187 | 37.6k | { |
188 | 37.6k | uint8_t w = 0, round = 0; |
189 | 37.6k | uint32_t T = 0; |
190 | 37.6k | uint32_t AL = 0, BL = 0, CL = 0, DL = 0, EL = 0; /* left line */ |
191 | 37.6k | uint32_t AR = 0, BR = 0, CR = 0, DR = 0, ER = 0; /* right line */ |
192 | | |
193 | | /* Sanity check */ |
194 | 37.6k | assert(self->bufpos == 64); |
195 | | |
196 | | /* Byte-swap the buffer if we're on a big-endian machine */ |
197 | | #ifdef PCT_BIG_ENDIAN |
198 | | byteswap_digest(self->buf.w); |
199 | | #endif |
200 | | |
201 | | /* Load the left and right lines with the initial state */ |
202 | 37.6k | AL = AR = self->h[0]; |
203 | 37.6k | BL = BR = self->h[1]; |
204 | 37.6k | CL = CR = self->h[2]; |
205 | 37.6k | DL = DR = self->h[3]; |
206 | 37.6k | EL = ER = self->h[4]; |
207 | | |
208 | | /* Round 1 */ |
209 | 37.6k | round = 0; |
210 | 639k | for (w = 0; w < 16; w++) { /* left line */ |
211 | 601k | T = ROL(SL[round][w], AL + F1(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL; |
212 | 601k | AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T; |
213 | 601k | } |
214 | 639k | for (w = 0; w < 16; w++) { /* right line */ |
215 | 601k | T = ROL(SR[round][w], AR + F5(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER; |
216 | 601k | AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T; |
217 | 601k | } |
218 | | |
219 | | /* Round 2 */ |
220 | 37.6k | round++; |
221 | 639k | for (w = 0; w < 16; w++) { /* left line */ |
222 | 601k | T = ROL(SL[round][w], AL + F2(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL; |
223 | 601k | AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T; |
224 | 601k | } |
225 | 639k | for (w = 0; w < 16; w++) { /* right line */ |
226 | 601k | T = ROL(SR[round][w], AR + F4(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER; |
227 | 601k | AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T; |
228 | 601k | } |
229 | | |
230 | | /* Round 3 */ |
231 | 37.6k | round++; |
232 | 639k | for (w = 0; w < 16; w++) { /* left line */ |
233 | 601k | T = ROL(SL[round][w], AL + F3(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL; |
234 | 601k | AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T; |
235 | 601k | } |
236 | 639k | for (w = 0; w < 16; w++) { /* right line */ |
237 | 601k | T = ROL(SR[round][w], AR + F3(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER; |
238 | 601k | AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T; |
239 | 601k | } |
240 | | |
241 | | /* Round 4 */ |
242 | 37.6k | round++; |
243 | 639k | for (w = 0; w < 16; w++) { /* left line */ |
244 | 601k | T = ROL(SL[round][w], AL + F4(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL; |
245 | 601k | AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T; |
246 | 601k | } |
247 | 639k | for (w = 0; w < 16; w++) { /* right line */ |
248 | 601k | T = ROL(SR[round][w], AR + F2(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER; |
249 | 601k | AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T; |
250 | 601k | } |
251 | | |
252 | | /* Round 5 */ |
253 | 37.6k | round++; |
254 | 639k | for (w = 0; w < 16; w++) { /* left line */ |
255 | 601k | T = ROL(SL[round][w], AL + F5(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL; |
256 | 601k | AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T; |
257 | 601k | } |
258 | 639k | for (w = 0; w < 16; w++) { /* right line */ |
259 | 601k | T = ROL(SR[round][w], AR + F1(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER; |
260 | 601k | AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T; |
261 | 601k | } |
262 | | |
263 | | /* Final mixing stage */ |
264 | 37.6k | T = self->h[1] + CL + DR; |
265 | 37.6k | self->h[1] = self->h[2] + DL + ER; |
266 | 37.6k | self->h[2] = self->h[3] + EL + AR; |
267 | 37.6k | self->h[3] = self->h[4] + AL + BR; |
268 | 37.6k | self->h[4] = self->h[0] + BL + CR; |
269 | 37.6k | self->h[0] = T; |
270 | | |
271 | | /* Clear the buffer and wipe the temporary variables */ |
272 | 37.6k | memzero(&self->buf, sizeof(self->buf)); |
273 | 37.6k | memzero(&T, sizeof(T)); |
274 | 37.6k | memzero(&AL, sizeof(AL)); |
275 | 37.6k | memzero(&BL, sizeof(BL)); |
276 | 37.6k | memzero(&CL, sizeof(CL)); |
277 | 37.6k | memzero(&DL, sizeof(DL)); |
278 | 37.6k | memzero(&EL, sizeof(EL)); |
279 | 37.6k | memzero(&AR, sizeof(AR)); |
280 | 37.6k | memzero(&BR, sizeof(BR)); |
281 | 37.6k | memzero(&CR, sizeof(CR)); |
282 | 37.6k | memzero(&DR, sizeof(DR)); |
283 | 37.6k | memzero(&ER, sizeof(ER)); |
284 | 37.6k | self->bufpos = 0; |
285 | 37.6k | } |
286 | | |
287 | | void ripemd160_process(ripemd160_state * self, const uint8_t *p, size_t length) |
288 | 15.9k | { |
289 | 15.9k | unsigned long bytes_needed = 0; |
290 | | |
291 | | /* Some assertions */ |
292 | 15.9k | assert(p != NULL); |
293 | | |
294 | | /* We never leave a full buffer */ |
295 | 15.9k | assert(self->bufpos < 64); |
296 | | |
297 | 53.5k | while (length > 0) { |
298 | | /* Figure out how many bytes we need to fill the internal buffer. */ |
299 | 38.0k | bytes_needed = 64 - self->bufpos; |
300 | | |
301 | 38.0k | if ((unsigned long) length >= bytes_needed) { |
302 | | /* We have enough bytes, so copy them into the internal buffer and run |
303 | | * the compression function. */ |
304 | 37.5k | memcpy(&self->buf.b[self->bufpos], p, bytes_needed); |
305 | 37.5k | self->bufpos += bytes_needed; |
306 | 37.5k | self->length += bytes_needed << 3; /* length is in bits */ |
307 | 37.5k | p += bytes_needed; |
308 | 37.5k | ripemd160_compress(self); |
309 | 37.5k | length -= bytes_needed; |
310 | 37.5k | continue; |
311 | 37.5k | } |
312 | | |
313 | | /* We do not have enough bytes to fill the internal buffer. |
314 | | * Copy what's there and return. */ |
315 | 520 | memcpy(&self->buf.b[self->bufpos], p, length); |
316 | 520 | self->bufpos += length; |
317 | 520 | self->length += length << 3; /* length is in bits */ |
318 | 520 | return; |
319 | 38.0k | } |
320 | 15.9k | } |
321 | | |
322 | | void ripemd160_done(ripemd160_state * self, uint8_t out[RIPEMD160_DIGEST_LENGTH]) |
323 | 52 | { |
324 | | /* Append the padding */ |
325 | 52 | self->buf.b[self->bufpos++] = 0x80; |
326 | | |
327 | 52 | if (self->bufpos > 56) { |
328 | 13 | self->bufpos = 64; |
329 | 13 | ripemd160_compress(self); |
330 | 13 | } |
331 | | |
332 | | /* Append the length */ |
333 | 52 | self->buf.w[14] = (uint32_t) (self->length & 0xFFFFffffu); |
334 | 52 | self->buf.w[15] = (uint32_t) ((self->length >> 32) & 0xFFFFffffu); |
335 | | #ifdef PCT_BIG_ENDIAN |
336 | | byteswap32(&self->buf.w[14]); |
337 | | byteswap32(&self->buf.w[15]); |
338 | | #endif |
339 | 52 | self->bufpos = 64; |
340 | 52 | ripemd160_compress(self); |
341 | | |
342 | | /* Copy the final state into the output buffer */ |
343 | | #ifdef PCT_BIG_ENDIAN |
344 | | byteswap_digest(self->h); |
345 | | #endif |
346 | 52 | memcpy(out, &self->h, RIPEMD160_DIGEST_SIZE); |
347 | 52 | memzero(self, sizeof(ripemd160_state)); |
348 | 52 | } |
349 | | |
350 | | void ripemd160(const uint8_t *in, size_t length, uint8_t out[RIPEMD160_DIGEST_LENGTH]) |
351 | 0 | { |
352 | 0 | ripemd160_state md = {0}; |
353 | 0 | ripemd160_init(&md); |
354 | 0 | ripemd160_process(&md, in, length); |
355 | 0 | ripemd160_done(&md, out); |
356 | 0 | } |