Coverage Report

Created: 2024-11-21 07:03

/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
}