FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
ripemd.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2007 Michael Niedermayer <michaelni@gmx.at>
3  * Copyright (C) 2013 James Almer
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 #include <string.h>
23 
24 #include "attributes.h"
25 #include "avutil.h"
26 #include "bswap.h"
27 #include "intreadwrite.h"
28 #include "ripemd.h"
29 #include "mem.h"
30 
31 /** hash context */
32 typedef struct AVRIPEMD {
33  uint8_t digest_len; ///< digest length in 32-bit words
34  uint64_t count; ///< number of bytes in buffer
35  uint8_t buffer[64]; ///< 512-bit buffer of input values used in hash updating
36  uint32_t state[10]; ///< current hash value
37  uint8_t ext; ///< extension (0 for 128 and 160, 1 for 256 and 320)
38  /** function used to update hash for 512-bit input block */
39  void (*transform)(uint32_t *state, const uint8_t buffer[64], int ext);
40 } AVRIPEMD;
41 
42 const int av_ripemd_size = sizeof(AVRIPEMD);
43 
45 {
46  return av_mallocz(sizeof(struct AVRIPEMD));
47 }
48 
49 static const uint32_t KA[4] = {
50  0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xa953fd4e
51 };
52 
53 static const uint32_t KB[4] = {
54  0x50a28be6, 0x5c4dd124, 0x6d703ef3, 0x7a6d76e9
55 };
56 
57 static const int ROTA[80] = {
58  11, 14, 15, 12, 5, 8, 7 , 9, 11, 13, 14, 15, 6, 7, 9, 8,
59  7 , 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12,
60  11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5,
61  11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12,
62  9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6
63 };
64 
65 static const int ROTB[80] = {
66  8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6,
67  9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11,
68  9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5,
69  15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8,
70  8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11
71 };
72 
73 static const int WA[80] = {
74  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
75  7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8,
76  3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12,
77  1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2,
78  4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13
79 };
80 
81 static const int WB[80] = {
82  5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12,
83  6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2,
84  15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13,
85  8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14,
86  12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11
87 };
88 
89 #define rol(value, bits) ((value << bits) | (value >> (32 - bits)))
90 
91 #define SWAP(a,b) if (ext) { t = a; a = b; b = t; }
92 
93 #define ROUND128_0_TO_15(a,b,c,d,e,f,g,h) \
94  a = rol(a + (( b ^ c ^ d) + block[WA[n]]), ROTA[n]); \
95  e = rol(e + ((((f ^ g) & h) ^ g) + block[WB[n]] + KB[0]), ROTB[n]); \
96  n++
97 
98 #define ROUND128_16_TO_31(a,b,c,d,e,f,g,h) \
99  a = rol(a + ((((c ^ d) & b) ^ d) + block[WA[n]] + KA[0]), ROTA[n]); \
100  e = rol(e + (((~g | f) ^ h) + block[WB[n]] + KB[1]), ROTB[n]); \
101  n++
102 
103 #define ROUND128_32_TO_47(a,b,c,d,e,f,g,h) \
104  a = rol(a + (((~c | b) ^ d) + block[WA[n]] + KA[1]), ROTA[n]); \
105  e = rol(e + ((((g ^ h) & f) ^ h) + block[WB[n]] + KB[2]), ROTB[n]); \
106  n++
107 
108 #define ROUND128_48_TO_63(a,b,c,d,e,f,g,h) \
109  a = rol(a + ((((b ^ c) & d) ^ c) + block[WA[n]] + KA[2]), ROTA[n]); \
110  e = rol(e + (( f ^ g ^ h) + block[WB[n]]), ROTB[n]); \
111  n++
112 
113 static void ripemd128_transform(uint32_t *state, const uint8_t buffer[64], int ext)
114 {
115  uint32_t a, b, c, d, e, f, g, h, t;
116  uint32_t block[16];
117  int n;
118 
119  if (ext) {
120  a = state[0]; b = state[1]; c = state[2]; d = state[3];
121  e = state[4]; f = state[5]; g = state[6]; h = state[7];
122  } else {
123  a = e = state[0];
124  b = f = state[1];
125  c = g = state[2];
126  d = h = state[3];
127  }
128 
129  for (n = 0; n < 16; n++)
130  block[n] = AV_RL32(buffer + 4 * n);
131  n = 0;
132 
133 #if CONFIG_SMALL
134  for (; n < 16;) {
135  ROUND128_0_TO_15(a,b,c,d,e,f,g,h);
136  t = d; d = c; c = b; b = a; a = t;
137  t = h; h = g; g = f; f = e; e = t;
138  }
139  SWAP(a,e)
140 
141  for (; n < 32;) {
142  ROUND128_16_TO_31(a,b,c,d,e,f,g,h);
143  t = d; d = c; c = b; b = a; a = t;
144  t = h; h = g; g = f; f = e; e = t;
145  }
146  SWAP(b,f)
147 
148  for (; n < 48;) {
149  ROUND128_32_TO_47(a,b,c,d,e,f,g,h);
150  t = d; d = c; c = b; b = a; a = t;
151  t = h; h = g; g = f; f = e; e = t;
152  }
153  SWAP(c,g)
154 
155  for (; n < 64;) {
156  ROUND128_48_TO_63(a,b,c,d,e,f,g,h);
157  t = d; d = c; c = b; b = a; a = t;
158  t = h; h = g; g = f; f = e; e = t;
159  }
160  SWAP(d,h)
161 #else
162 
163 #define R128_0 \
164  ROUND128_0_TO_15(a,b,c,d,e,f,g,h); \
165  ROUND128_0_TO_15(d,a,b,c,h,e,f,g); \
166  ROUND128_0_TO_15(c,d,a,b,g,h,e,f); \
167  ROUND128_0_TO_15(b,c,d,a,f,g,h,e)
168 
169  R128_0; R128_0; R128_0; R128_0;
170  SWAP(a,e)
171 
172 #define R128_16 \
173  ROUND128_16_TO_31(a,b,c,d,e,f,g,h); \
174  ROUND128_16_TO_31(d,a,b,c,h,e,f,g); \
175  ROUND128_16_TO_31(c,d,a,b,g,h,e,f); \
176  ROUND128_16_TO_31(b,c,d,a,f,g,h,e)
177 
178  R128_16; R128_16; R128_16; R128_16;
179  SWAP(b,f)
180 
181 #define R128_32 \
182  ROUND128_32_TO_47(a,b,c,d,e,f,g,h); \
183  ROUND128_32_TO_47(d,a,b,c,h,e,f,g); \
184  ROUND128_32_TO_47(c,d,a,b,g,h,e,f); \
185  ROUND128_32_TO_47(b,c,d,a,f,g,h,e)
186 
187  R128_32; R128_32; R128_32; R128_32;
188  SWAP(c,g)
189 
190 #define R128_48 \
191  ROUND128_48_TO_63(a,b,c,d,e,f,g,h); \
192  ROUND128_48_TO_63(d,a,b,c,h,e,f,g); \
193  ROUND128_48_TO_63(c,d,a,b,g,h,e,f); \
194  ROUND128_48_TO_63(b,c,d,a,f,g,h,e)
195 
196  R128_48; R128_48; R128_48; R128_48;
197  SWAP(d,h)
198 #endif
199 
200  if (ext) {
201  state[0] += a; state[1] += b; state[2] += c; state[3] += d;
202  state[4] += e; state[5] += f; state[6] += g; state[7] += h;
203  } else {
204  h += c + state[1];
205  state[1] = state[2] + d + e;
206  state[2] = state[3] + a + f;
207  state[3] = state[0] + b + g;
208  state[0] = h;
209  }
210 }
211 
212 #define ROTATE(x,y) \
213  x = rol(x, 10); \
214  y = rol(y, 10); \
215  n++
216 
217 #define ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j) \
218  a = rol(a + (( b ^ c ^ d) + block[WA[n]]), ROTA[n]) + e; \
219  f = rol(f + (((~i | h) ^ g) + block[WB[n]] + KB[0]), ROTB[n]) + j; \
220  ROTATE(c,h)
221 
222 #define ROUND160_16_TO_31(a,b,c,d,e,f,g,h,i,j) \
223  a = rol(a + ((((c ^ d) & b) ^ d) + block[WA[n]] + KA[0]), ROTA[n]) + e; \
224  f = rol(f + ((((g ^ h) & i) ^ h) + block[WB[n]] + KB[1]), ROTB[n]) + j; \
225  ROTATE(c,h)
226 
227 #define ROUND160_32_TO_47(a,b,c,d,e,f,g,h,i,j) \
228  a = rol(a + (((~c | b) ^ d) + block[WA[n]] + KA[1]), ROTA[n]) + e; \
229  f = rol(f + (((~h | g) ^ i) + block[WB[n]] + KB[2]), ROTB[n]) + j; \
230  ROTATE(c,h)
231 
232 #define ROUND160_48_TO_63(a,b,c,d,e,f,g,h,i,j) \
233  a = rol(a + ((((b ^ c) & d) ^ c) + block[WA[n]] + KA[2]), ROTA[n]) + e; \
234  f = rol(f + ((((h ^ i) & g) ^ i) + block[WB[n]] + KB[3]), ROTB[n]) + j; \
235  ROTATE(c,h)
236 
237 #define ROUND160_64_TO_79(a,b,c,d,e,f,g,h,i,j) \
238  a = rol(a + (((~d | c) ^ b) + block[WA[n]] + KA[3]), ROTA[n]) + e; \
239  f = rol(f + (( g ^ h ^ i) + block[WB[n]]), ROTB[n]) + j; \
240  ROTATE(c,h)
241 
242 static void ripemd160_transform(uint32_t *state, const uint8_t buffer[64], int ext)
243 {
244  uint32_t a, b, c, d, e, f, g, h, i, j, t;
245  uint32_t block[16];
246  int n;
247 
248  if (ext) {
249  a = state[0]; b = state[1]; c = state[2]; d = state[3]; e = state[4];
250  f = state[5]; g = state[6]; h = state[7]; i = state[8]; j = state[9];
251  } else {
252  a = f = state[0];
253  b = g = state[1];
254  c = h = state[2];
255  d = i = state[3];
256  e = j = state[4];
257  }
258 
259  for (n = 0; n < 16; n++)
260  block[n] = AV_RL32(buffer + 4 * n);
261  n = 0;
262 
263 #if CONFIG_SMALL
264  for (; n < 16;) {
265  ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j);
266  t = e; e = d; d = c; c = b; b = a; a = t;
267  t = j; j = i; i = h; h = g; g = f; f = t;
268  }
269  SWAP(b,g)
270 
271  for (; n < 32;) {
272  ROUND160_16_TO_31(a,b,c,d,e,f,g,h,i,j);
273  t = e; e = d; d = c; c = b; b = a; a = t;
274  t = j; j = i; i = h; h = g; g = f; f = t;
275  }
276  SWAP(d,i)
277 
278  for (; n < 48;) {
279  ROUND160_32_TO_47(a,b,c,d,e,f,g,h,i,j);
280  t = e; e = d; d = c; c = b; b = a; a = t;
281  t = j; j = i; i = h; h = g; g = f; f = t;
282  }
283  SWAP(a,f)
284 
285  for (; n < 64;) {
286  ROUND160_48_TO_63(a,b,c,d,e,f,g,h,i,j);
287  t = e; e = d; d = c; c = b; b = a; a = t;
288  t = j; j = i; i = h; h = g; g = f; f = t;
289  }
290  SWAP(c,h)
291 
292  for (; n < 80;) {
293  ROUND160_64_TO_79(a,b,c,d,e,f,g,h,i,j);
294  t = e; e = d; d = c; c = b; b = a; a = t;
295  t = j; j = i; i = h; h = g; g = f; f = t;
296  }
297  SWAP(e,j)
298 #else
299 
300 #define R160_0 \
301  ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j); \
302  ROUND160_0_TO_15(e,a,b,c,d,j,f,g,h,i); \
303  ROUND160_0_TO_15(d,e,a,b,c,i,j,f,g,h); \
304  ROUND160_0_TO_15(c,d,e,a,b,h,i,j,f,g); \
305  ROUND160_0_TO_15(b,c,d,e,a,g,h,i,j,f)
306 
307  R160_0; R160_0; R160_0;
308  ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j);
309  SWAP(a,f)
310 
311 #define R160_16 \
312  ROUND160_16_TO_31(e,a,b,c,d,j,f,g,h,i); \
313  ROUND160_16_TO_31(d,e,a,b,c,i,j,f,g,h); \
314  ROUND160_16_TO_31(c,d,e,a,b,h,i,j,f,g); \
315  ROUND160_16_TO_31(b,c,d,e,a,g,h,i,j,f); \
316  ROUND160_16_TO_31(a,b,c,d,e,f,g,h,i,j)
317 
318  R160_16; R160_16; R160_16;
319  ROUND160_16_TO_31(e,a,b,c,d,j,f,g,h,i);
320  SWAP(b,g)
321 
322 #define R160_32 \
323  ROUND160_32_TO_47(d,e,a,b,c,i,j,f,g,h); \
324  ROUND160_32_TO_47(c,d,e,a,b,h,i,j,f,g); \
325  ROUND160_32_TO_47(b,c,d,e,a,g,h,i,j,f); \
326  ROUND160_32_TO_47(a,b,c,d,e,f,g,h,i,j); \
327  ROUND160_32_TO_47(e,a,b,c,d,j,f,g,h,i)
328 
329  R160_32; R160_32; R160_32;
330  ROUND160_32_TO_47(d,e,a,b,c,i,j,f,g,h);
331  SWAP(c,h)
332 
333 #define R160_48 \
334  ROUND160_48_TO_63(c,d,e,a,b,h,i,j,f,g); \
335  ROUND160_48_TO_63(b,c,d,e,a,g,h,i,j,f); \
336  ROUND160_48_TO_63(a,b,c,d,e,f,g,h,i,j); \
337  ROUND160_48_TO_63(e,a,b,c,d,j,f,g,h,i); \
338  ROUND160_48_TO_63(d,e,a,b,c,i,j,f,g,h)
339 
340  R160_48; R160_48; R160_48;
341  ROUND160_48_TO_63(c,d,e,a,b,h,i,j,f,g);
342  SWAP(d,i)
343 
344 #define R160_64 \
345  ROUND160_64_TO_79(b,c,d,e,a,g,h,i,j,f); \
346  ROUND160_64_TO_79(a,b,c,d,e,f,g,h,i,j); \
347  ROUND160_64_TO_79(e,a,b,c,d,j,f,g,h,i); \
348  ROUND160_64_TO_79(d,e,a,b,c,i,j,f,g,h); \
349  ROUND160_64_TO_79(c,d,e,a,b,h,i,j,f,g)
350 
351  R160_64; R160_64; R160_64;
352  ROUND160_64_TO_79(b,c,d,e,a,g,h,i,j,f);
353  SWAP(e,j)
354 #endif
355 
356  if (ext) {
357  state[0] += a; state[1] += b; state[2] += c; state[3] += d; state[4] += e;
358  state[5] += f; state[6] += g; state[7] += h; state[8] += i; state[9] += j;
359  } else {
360  i += c + state[1];
361  state[1] = state[2] + d + j;
362  state[2] = state[3] + e + f;
363  state[3] = state[4] + a + g;
364  state[4] = state[0] + b + h;
365  state[0] = i;
366  }
367 }
368 
370 {
371  ctx->digest_len = bits >> 5;
372  switch (bits) {
373  case 128: // RIPEMD-128
374  ctx->state[0] = 0x67452301;
375  ctx->state[1] = 0xEFCDAB89;
376  ctx->state[2] = 0x98BADCFE;
377  ctx->state[3] = 0x10325476;
379  ctx->ext = 0;
380  break;
381  case 160: // RIPEMD-160
382  ctx->state[0] = 0x67452301;
383  ctx->state[1] = 0xEFCDAB89;
384  ctx->state[2] = 0x98BADCFE;
385  ctx->state[3] = 0x10325476;
386  ctx->state[4] = 0xC3D2E1F0;
388  ctx->ext = 0;
389  break;
390  case 256: // RIPEMD-256
391  ctx->state[0] = 0x67452301;
392  ctx->state[1] = 0xEFCDAB89;
393  ctx->state[2] = 0x98BADCFE;
394  ctx->state[3] = 0x10325476;
395  ctx->state[4] = 0x76543210;
396  ctx->state[5] = 0xFEDCBA98;
397  ctx->state[6] = 0x89ABCDEF;
398  ctx->state[7] = 0x01234567;
400  ctx->ext = 1;
401  break;
402  case 320: // RIPEMD-320
403  ctx->state[0] = 0x67452301;
404  ctx->state[1] = 0xEFCDAB89;
405  ctx->state[2] = 0x98BADCFE;
406  ctx->state[3] = 0x10325476;
407  ctx->state[4] = 0xC3D2E1F0;
408  ctx->state[5] = 0x76543210;
409  ctx->state[6] = 0xFEDCBA98;
410  ctx->state[7] = 0x89ABCDEF;
411  ctx->state[8] = 0x01234567;
412  ctx->state[9] = 0x3C2D1E0F;
414  ctx->ext = 1;
415  break;
416  default:
417  return -1;
418  }
419  ctx->count = 0;
420  return 0;
421 }
422 
423 void av_ripemd_update(AVRIPEMD* ctx, const uint8_t* data, unsigned int len)
424 {
425  unsigned int i, j;
426 
427  j = ctx->count & 63;
428  ctx->count += len;
429 #if CONFIG_SMALL
430  for (i = 0; i < len; i++) {
431  ctx->buffer[j++] = data[i];
432  if (64 == j) {
433  ctx->transform(ctx->state, ctx->buffer, ctx->ext);
434  j = 0;
435  }
436  }
437 #else
438  if ((j + len) > 63) {
439  memcpy(&ctx->buffer[j], data, (i = 64 - j));
440  ctx->transform(ctx->state, ctx->buffer, ctx->ext);
441  for (; i + 63 < len; i += 64)
442  ctx->transform(ctx->state, &data[i], ctx->ext);
443  j = 0;
444  } else
445  i = 0;
446  memcpy(&ctx->buffer[j], &data[i], len - i);
447 #endif
448 }
449 
450 void av_ripemd_final(AVRIPEMD* ctx, uint8_t *digest)
451 {
452  int i;
453  uint64_t finalcount = av_le2ne64(ctx->count << 3);
454 
455  av_ripemd_update(ctx, "\200", 1);
456  while ((ctx->count & 63) != 56)
457  av_ripemd_update(ctx, "", 1);
458  av_ripemd_update(ctx, (uint8_t *)&finalcount, 8); /* Should cause a transform() */
459  for (i = 0; i < ctx->digest_len; i++)
460  AV_WL32(digest + i*4, ctx->state[i]);
461 }
462 
463 #ifdef TEST
464 #include <stdio.h>
465 
466 int main(void)
467 {
468  int i, j, k;
469  AVRIPEMD ctx;
470  unsigned char digest[40];
471  static const int lengths[4] = { 128, 160, 256, 320 };
472 
473  for (j = 0; j < 4; j++) {
474  printf("Testing RIPEMD-%d\n", lengths[j]);
475  for (k = 0; k < 3; k++) {
476  av_ripemd_init(&ctx, lengths[j]);
477  if (k == 0)
478  av_ripemd_update(&ctx, "abc", 3);
479  else if (k == 1)
480  av_ripemd_update(&ctx, "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56);
481  else
482  for (i = 0; i < 1000*1000; i++)
483  av_ripemd_update(&ctx, "a", 1);
484  av_ripemd_final(&ctx, digest);
485  for (i = 0; i < lengths[j] >> 3; i++)
486  printf("%02X", digest[i]);
487  putchar('\n');
488  }
489  switch (j) { //test vectors (from ISO:IEC 10118-3 (2004) and http://homes.esat.kuleuven.be/~bosselae/ripemd160.html)
490  case 0:
491  printf("c14a1219 9c66e4ba 84636b0f 69144c77\n"
492  "a1aa0689 d0fafa2d dc22e88b 49133a06\n"
493  "4a7f5723 f954eba1 216c9d8f 6320431f\n");
494  break;
495  case 1:
496  printf("8eb208f7 e05d987a 9b044a8e 98c6b087 f15a0bfc\n"
497  "12a05338 4a9c0c88 e405a06c 27dcf49a da62eb2b\n"
498  "52783243 c1697bdb e16d37f9 7f68f083 25dc1528\n");
499  break;
500  case 2:
501  printf("afbd6e22 8b9d8cbb cef5ca2d 03e6dba1 0ac0bc7d cbe4680e 1e42d2e9 75459b65\n"
502  "38430455 83aac6c8 c8d91285 73e7a980 9afb2a0f 34ccc36e a9e72f16 f6368e3f\n"
503  "ac953744 e10e3151 4c150d4d 8d7b6773 42e33399 788296e4 3ae4850c e4f97978\n");
504  break;
505  case 3:
506  printf("de4c01b3 054f8930 a79d09ae 738e9230 1e5a1708 5beffdc1 b8d11671 3e74f82f a942d64c dbc4682d\n"
507  "d034a795 0cf72202 1ba4b84d f769a5de 2060e259 df4c9bb4 a4268c0e 935bbc74 70a969c9 d072a1ac\n"
508  "bdee37f4 371e2064 6b8b0d86 2dda1629 2ae36f40 965e8c85 09e63d1d bddecc50 3e2b63eb 9245bb66\n");
509  break;
510  }
511  }
512 
513  return 0;
514 }
515 #endif