sha.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2007 Michael Niedermayer <michaelni@gmx.at>
3  * Copyright (C) 2009 Konstantin Shishkov
4  * based on public domain SHA-1 code by Steve Reid <steve@edmweb.com>
5  * and on BSD-licensed SHA-2 code by Aaron D. Gifford
6  *
7  * This file is part of Libav.
8  *
9  * Libav is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * Libav is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with Libav; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22  */
23 
24 #include <string.h>
25 #include "avutil.h"
26 #include "bswap.h"
27 #include "sha.h"
28 #include "intreadwrite.h"
29 
31 typedef struct AVSHA {
32  uint8_t digest_len;
33  uint64_t count;
34  uint8_t buffer[64];
35  uint32_t state[8];
36 
37  void (*transform)(uint32_t *state, const uint8_t buffer[64]);
38 } AVSHA;
39 
40 const int av_sha_size = sizeof(AVSHA);
41 
42 #define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
43 
44 /* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
45 #define blk0(i) (block[i] = AV_RB32(buffer + 4 * (i)))
46 #define blk(i) (block[i] = rol(block[i-3] ^ block[i-8] ^ block[i-14] ^ block[i-16], 1))
47 
48 #define R0(v,w,x,y,z,i) z += ((w&(x^y))^y) + blk0(i) + 0x5A827999 + rol(v, 5); w = rol(w, 30);
49 #define R1(v,w,x,y,z,i) z += ((w&(x^y))^y) + blk (i) + 0x5A827999 + rol(v, 5); w = rol(w, 30);
50 #define R2(v,w,x,y,z,i) z += ( w^x ^y) + blk (i) + 0x6ED9EBA1 + rol(v, 5); w = rol(w, 30);
51 #define R3(v,w,x,y,z,i) z += (((w|x)&y)|(w&x)) + blk (i) + 0x8F1BBCDC + rol(v, 5); w = rol(w, 30);
52 #define R4(v,w,x,y,z,i) z += ( w^x ^y) + blk (i) + 0xCA62C1D6 + rol(v, 5); w = rol(w, 30);
53 
54 /* Hash a single 512-bit block. This is the core of the algorithm. */
55 
56 static void sha1_transform(uint32_t state[5], const uint8_t buffer[64])
57 {
58  uint32_t block[80];
59  unsigned int i, a, b, c, d, e;
60 
61  a = state[0];
62  b = state[1];
63  c = state[2];
64  d = state[3];
65  e = state[4];
66 #if CONFIG_SMALL
67  for (i = 0; i < 80; i++) {
68  int t;
69  if (i < 16)
70  t = AV_RB32(buffer + 4 * i);
71  else
72  t = rol(block[i-3] ^ block[i-8] ^ block[i-14] ^ block[i-16], 1);
73  block[i] = t;
74  t += e + rol(a, 5);
75  if (i < 40) {
76  if (i < 20)
77  t += ((b&(c^d))^d) + 0x5A827999;
78  else
79  t += ( b^c ^d) + 0x6ED9EBA1;
80  } else {
81  if (i < 60)
82  t += (((b|c)&d)|(b&c)) + 0x8F1BBCDC;
83  else
84  t += ( b^c ^d) + 0xCA62C1D6;
85  }
86  e = d;
87  d = c;
88  c = rol(b, 30);
89  b = a;
90  a = t;
91  }
92 #else
93  for (i = 0; i < 15; i += 5) {
94  R0(a, b, c, d, e, 0 + i);
95  R0(e, a, b, c, d, 1 + i);
96  R0(d, e, a, b, c, 2 + i);
97  R0(c, d, e, a, b, 3 + i);
98  R0(b, c, d, e, a, 4 + i);
99  }
100  R0(a, b, c, d, e, 15);
101  R1(e, a, b, c, d, 16);
102  R1(d, e, a, b, c, 17);
103  R1(c, d, e, a, b, 18);
104  R1(b, c, d, e, a, 19);
105  for (i = 20; i < 40; i += 5) {
106  R2(a, b, c, d, e, 0 + i);
107  R2(e, a, b, c, d, 1 + i);
108  R2(d, e, a, b, c, 2 + i);
109  R2(c, d, e, a, b, 3 + i);
110  R2(b, c, d, e, a, 4 + i);
111  }
112  for (; i < 60; i += 5) {
113  R3(a, b, c, d, e, 0 + i);
114  R3(e, a, b, c, d, 1 + i);
115  R3(d, e, a, b, c, 2 + i);
116  R3(c, d, e, a, b, 3 + i);
117  R3(b, c, d, e, a, 4 + i);
118  }
119  for (; i < 80; i += 5) {
120  R4(a, b, c, d, e, 0 + i);
121  R4(e, a, b, c, d, 1 + i);
122  R4(d, e, a, b, c, 2 + i);
123  R4(c, d, e, a, b, 3 + i);
124  R4(b, c, d, e, a, 4 + i);
125  }
126 #endif
127  state[0] += a;
128  state[1] += b;
129  state[2] += c;
130  state[3] += d;
131  state[4] += e;
132 }
133 
134 static const uint32_t K256[64] = {
135  0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
136  0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
137  0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
138  0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
139  0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
140  0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
141  0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
142  0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
143  0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
144  0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
145  0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
146  0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
147  0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
148  0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
149  0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
150  0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
151 };
152 
153 
154 #define Ch(x,y,z) (((x) & ((y) ^ (z))) ^ (z))
155 #define Maj(x,y,z) ((((x) | (y)) & (z)) | ((x) & (y)))
156 
157 #define Sigma0_256(x) (rol((x), 30) ^ rol((x), 19) ^ rol((x), 10))
158 #define Sigma1_256(x) (rol((x), 26) ^ rol((x), 21) ^ rol((x), 7))
159 #define sigma0_256(x) (rol((x), 25) ^ rol((x), 14) ^ ((x) >> 3))
160 #define sigma1_256(x) (rol((x), 15) ^ rol((x), 13) ^ ((x) >> 10))
161 
162 #undef blk
163 #define blk(i) (block[i] = block[i - 16] + sigma0_256(block[i - 15]) + \
164  sigma1_256(block[i - 2]) + block[i - 7])
165 
166 #define ROUND256(a,b,c,d,e,f,g,h) \
167  T1 += (h) + Sigma1_256(e) + Ch((e), (f), (g)) + K256[i]; \
168  (d) += T1; \
169  (h) = T1 + Sigma0_256(a) + Maj((a), (b), (c)); \
170  i++
171 
172 #define ROUND256_0_TO_15(a,b,c,d,e,f,g,h) \
173  T1 = blk0(i); \
174  ROUND256(a,b,c,d,e,f,g,h)
175 
176 #define ROUND256_16_TO_63(a,b,c,d,e,f,g,h) \
177  T1 = blk(i); \
178  ROUND256(a,b,c,d,e,f,g,h)
179 
180 static void sha256_transform(uint32_t *state, const uint8_t buffer[64])
181 {
182  unsigned int i, a, b, c, d, e, f, g, h;
183  uint32_t block[64];
184  uint32_t T1, av_unused(T2);
185 
186  a = state[0];
187  b = state[1];
188  c = state[2];
189  d = state[3];
190  e = state[4];
191  f = state[5];
192  g = state[6];
193  h = state[7];
194 #if CONFIG_SMALL
195  for (i = 0; i < 64; i++) {
196  if (i < 16)
197  T1 = blk0(i);
198  else
199  T1 = blk(i);
200  T1 += h + Sigma1_256(e) + Ch(e, f, g) + K256[i];
201  T2 = Sigma0_256(a) + Maj(a, b, c);
202  h = g;
203  g = f;
204  f = e;
205  e = d + T1;
206  d = c;
207  c = b;
208  b = a;
209  a = T1 + T2;
210  }
211 #else
212  for (i = 0; i < 16;) {
213  ROUND256_0_TO_15(a, b, c, d, e, f, g, h);
214  ROUND256_0_TO_15(h, a, b, c, d, e, f, g);
215  ROUND256_0_TO_15(g, h, a, b, c, d, e, f);
216  ROUND256_0_TO_15(f, g, h, a, b, c, d, e);
217  ROUND256_0_TO_15(e, f, g, h, a, b, c, d);
218  ROUND256_0_TO_15(d, e, f, g, h, a, b, c);
219  ROUND256_0_TO_15(c, d, e, f, g, h, a, b);
220  ROUND256_0_TO_15(b, c, d, e, f, g, h, a);
221  }
222 
223  for (; i < 64;) {
224  ROUND256_16_TO_63(a, b, c, d, e, f, g, h);
225  ROUND256_16_TO_63(h, a, b, c, d, e, f, g);
226  ROUND256_16_TO_63(g, h, a, b, c, d, e, f);
227  ROUND256_16_TO_63(f, g, h, a, b, c, d, e);
228  ROUND256_16_TO_63(e, f, g, h, a, b, c, d);
229  ROUND256_16_TO_63(d, e, f, g, h, a, b, c);
230  ROUND256_16_TO_63(c, d, e, f, g, h, a, b);
231  ROUND256_16_TO_63(b, c, d, e, f, g, h, a);
232  }
233 #endif
234  state[0] += a;
235  state[1] += b;
236  state[2] += c;
237  state[3] += d;
238  state[4] += e;
239  state[5] += f;
240  state[6] += g;
241  state[7] += h;
242 }
243 
244 
245 int av_sha_init(AVSHA* ctx, int bits)
246 {
247  ctx->digest_len = bits >> 5;
248  switch (bits) {
249  case 160: // SHA-1
250  ctx->state[0] = 0x67452301;
251  ctx->state[1] = 0xEFCDAB89;
252  ctx->state[2] = 0x98BADCFE;
253  ctx->state[3] = 0x10325476;
254  ctx->state[4] = 0xC3D2E1F0;
255  ctx->transform = sha1_transform;
256  break;
257  case 224: // SHA-224
258  ctx->state[0] = 0xC1059ED8;
259  ctx->state[1] = 0x367CD507;
260  ctx->state[2] = 0x3070DD17;
261  ctx->state[3] = 0xF70E5939;
262  ctx->state[4] = 0xFFC00B31;
263  ctx->state[5] = 0x68581511;
264  ctx->state[6] = 0x64F98FA7;
265  ctx->state[7] = 0xBEFA4FA4;
267  break;
268  case 256: // SHA-256
269  ctx->state[0] = 0x6A09E667;
270  ctx->state[1] = 0xBB67AE85;
271  ctx->state[2] = 0x3C6EF372;
272  ctx->state[3] = 0xA54FF53A;
273  ctx->state[4] = 0x510E527F;
274  ctx->state[5] = 0x9B05688C;
275  ctx->state[6] = 0x1F83D9AB;
276  ctx->state[7] = 0x5BE0CD19;
278  break;
279  default:
280  return -1;
281  }
282  ctx->count = 0;
283  return 0;
284 }
285 
286 void av_sha_update(AVSHA* ctx, const uint8_t* data, unsigned int len)
287 {
288  unsigned int i, j;
289 
290  j = ctx->count & 63;
291  ctx->count += len;
292 #if CONFIG_SMALL
293  for (i = 0; i < len; i++) {
294  ctx->buffer[j++] = data[i];
295  if (64 == j) {
296  ctx->transform(ctx->state, ctx->buffer);
297  j = 0;
298  }
299  }
300 #else
301  if ((j + len) > 63) {
302  memcpy(&ctx->buffer[j], data, (i = 64 - j));
303  ctx->transform(ctx->state, ctx->buffer);
304  for (; i + 63 < len; i += 64)
305  ctx->transform(ctx->state, &data[i]);
306  j = 0;
307  } else
308  i = 0;
309  memcpy(&ctx->buffer[j], &data[i], len - i);
310 #endif
311 }
312 
313 void av_sha_final(AVSHA* ctx, uint8_t *digest)
314 {
315  int i;
316  uint64_t finalcount = av_be2ne64(ctx->count << 3);
317 
318  av_sha_update(ctx, "\200", 1);
319  while ((ctx->count & 63) != 56)
320  av_sha_update(ctx, "", 1);
321  av_sha_update(ctx, (uint8_t *)&finalcount, 8); /* Should cause a transform() */
322  for (i = 0; i < ctx->digest_len; i++)
323  AV_WB32(digest + i*4, ctx->state[i]);
324 }
325 
326 #ifdef TEST
327 #include <stdio.h>
328 #undef printf
329 
330 int main(void)
331 {
332  int i, j, k;
333  AVSHA ctx;
334  unsigned char digest[32];
335  const int lengths[3] = { 160, 224, 256 };
336 
337  for (j = 0; j < 3; j++) {
338  printf("Testing SHA-%d\n", lengths[j]);
339  for (k = 0; k < 3; k++) {
340  av_sha_init(&ctx, lengths[j]);
341  if (k == 0)
342  av_sha_update(&ctx, "abc", 3);
343  else if (k == 1)
344  av_sha_update(&ctx, "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56);
345  else
346  for (i = 0; i < 1000*1000; i++)
347  av_sha_update(&ctx, "a", 1);
348  av_sha_final(&ctx, digest);
349  for (i = 0; i < lengths[j] >> 3; i++)
350  printf("%02X", digest[i]);
351  putchar('\n');
352  }
353  switch (j) {
354  case 0:
355  //test vectors (from FIPS PUB 180-1)
356  printf("A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D\n"
357  "84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1\n"
358  "34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F\n");
359  break;
360  case 1:
361  //test vectors (from FIPS PUB 180-2 Appendix A)
362  printf("23097d22 3405d822 8642a477 bda255b3 2aadbce4 bda0b3f7 e36c9da7\n"
363  "75388b16 512776cc 5dba5da1 fd890150 b0c6455c b4f58b19 52522525\n"
364  "20794655 980c91d8 bbb4c1ea 97618a4b f03f4258 1948b2ee 4ee7ad67\n");
365  break;
366  case 2:
367  //test vectors (from FIPS PUB 180-2)
368  printf("ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad\n"
369  "248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1\n"
370  "cdc76e5c 9914fb92 81a1c7e2 84d73e67 f1809a48 a497200e 046d39cc c7112cd0\n");
371  break;
372  }
373  }
374 
375  return 0;
376 }
377 #endif