3
0

sha1.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480
  1. /* vi: set sw=4 ts=4: */
  2. /*
  3. * Based on shasum from http://www.netsw.org/crypto/hash/
  4. * Majorly hacked up to use Dr Brian Gladman's sha1 code
  5. *
  6. * Copyright (C) 2002 Dr Brian Gladman <brg@gladman.me.uk>, Worcester, UK.
  7. * Copyright (C) 2003 Glenn L. McGrath
  8. * Copyright (C) 2003 Erik Andersen
  9. *
  10. * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
  11. *
  12. * ---------------------------------------------------------------------------
  13. * Issue Date: 10/11/2002
  14. *
  15. * This is a byte oriented version of SHA1 that operates on arrays of bytes
  16. * stored in memory. It runs at 22 cycles per byte on a Pentium P4 processor
  17. *
  18. * ---------------------------------------------------------------------------
  19. *
  20. * SHA256 and SHA512 parts are:
  21. * Released into the Public Domain by Ulrich Drepper <drepper@redhat.com>.
  22. * Shrank by Denys Vlasenko.
  23. *
  24. * ---------------------------------------------------------------------------
  25. *
  26. * The best way to test random blocksizes is to go to coreutils/md5_sha1_sum.c
  27. * and replace "4096" with something like "2000 + time(NULL) % 2097",
  28. * then rebuild and compare "shaNNNsum bigfile" results.
  29. */
  30. #include "libbb.h"
  31. #define rotl32(x,n) (((x) << (n)) | ((x) >> (32 - (n))))
  32. #define rotr32(x,n) (((x) >> (n)) | ((x) << (32 - (n))))
  33. /* for sha512: */
  34. #define rotr64(x,n) (((x) >> (n)) | ((x) << (64 - (n))))
  35. #if BB_LITTLE_ENDIAN
  36. static inline uint64_t hton64(uint64_t v)
  37. {
  38. return (((uint64_t)htonl(v)) << 32) | htonl(v >> 32);
  39. }
  40. #else
  41. #define hton64(v) (v)
  42. #endif
  43. #define ntoh64(v) hton64(v)
  44. /* To check alignment gcc has an appropriate operator. Other
  45. compilers don't. */
  46. #if defined(__GNUC__) && __GNUC__ >= 2
  47. # define UNALIGNED_P(p,type) (((uintptr_t) p) % __alignof__(type) != 0)
  48. #else
  49. # define UNALIGNED_P(p,type) (((uintptr_t) p) % sizeof(type) != 0)
  50. #endif
  51. /* Some arch headers have conflicting defines */
  52. #undef ch
  53. #undef parity
  54. #undef maj
  55. #undef rnd
  56. static void FAST_FUNC sha1_process_block64(sha1_ctx_t *ctx)
  57. {
  58. unsigned t;
  59. uint32_t W[80], a, b, c, d, e;
  60. const uint32_t *words = (uint32_t*) ctx->wbuffer;
  61. for (t = 0; t < 16; ++t) {
  62. W[t] = ntohl(*words);
  63. words++;
  64. }
  65. for (/*t = 16*/; t < 80; ++t) {
  66. uint32_t T = W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16];
  67. W[t] = rotl32(T, 1);
  68. }
  69. a = ctx->hash[0];
  70. b = ctx->hash[1];
  71. c = ctx->hash[2];
  72. d = ctx->hash[3];
  73. e = ctx->hash[4];
  74. /* Reverse byte order in 32-bit words */
  75. #define ch(x,y,z) ((z) ^ ((x) & ((y) ^ (z))))
  76. #define parity(x,y,z) ((x) ^ (y) ^ (z))
  77. #define maj(x,y,z) (((x) & (y)) | ((z) & ((x) | (y))))
  78. /* A normal version as set out in the FIPS. This version uses */
  79. /* partial loop unrolling and is optimised for the Pentium 4 */
  80. #define rnd(f,k) \
  81. do { \
  82. uint32_t T = a; \
  83. a = rotl32(a, 5) + f(b, c, d) + e + k + W[t]; \
  84. e = d; \
  85. d = c; \
  86. c = rotl32(b, 30); \
  87. b = T; \
  88. } while (0)
  89. for (t = 0; t < 20; ++t)
  90. rnd(ch, 0x5a827999);
  91. for (/*t = 20*/; t < 40; ++t)
  92. rnd(parity, 0x6ed9eba1);
  93. for (/*t = 40*/; t < 60; ++t)
  94. rnd(maj, 0x8f1bbcdc);
  95. for (/*t = 60*/; t < 80; ++t)
  96. rnd(parity, 0xca62c1d6);
  97. #undef ch
  98. #undef parity
  99. #undef maj
  100. #undef rnd
  101. ctx->hash[0] += a;
  102. ctx->hash[1] += b;
  103. ctx->hash[2] += c;
  104. ctx->hash[3] += d;
  105. ctx->hash[4] += e;
  106. }
  107. /* Constants for SHA512 from FIPS 180-2:4.2.3.
  108. * SHA256 constants from FIPS 180-2:4.2.2
  109. * are the most significant half of first 64 elements
  110. * of the same array.
  111. */
  112. static const uint64_t sha_K[80] = {
  113. 0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL,
  114. 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
  115. 0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL,
  116. 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
  117. 0xd807aa98a3030242ULL, 0x12835b0145706fbeULL,
  118. 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
  119. 0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL,
  120. 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
  121. 0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL,
  122. 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
  123. 0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL,
  124. 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
  125. 0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL,
  126. 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
  127. 0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL,
  128. 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
  129. 0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL,
  130. 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
  131. 0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL,
  132. 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
  133. 0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL,
  134. 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
  135. 0xd192e819d6ef5218ULL, 0xd69906245565a910ULL,
  136. 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
  137. 0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL,
  138. 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
  139. 0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL,
  140. 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
  141. 0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL,
  142. 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
  143. 0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL,
  144. 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
  145. 0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, /* [64]+ are used for sha512 only */
  146. 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
  147. 0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL,
  148. 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
  149. 0x28db77f523047d84ULL, 0x32caab7b40c72493ULL,
  150. 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
  151. 0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL,
  152. 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
  153. };
  154. #undef Ch
  155. #undef Maj
  156. #undef S0
  157. #undef S1
  158. #undef R0
  159. #undef R1
  160. static void FAST_FUNC sha256_process_block64(sha256_ctx_t *ctx)
  161. {
  162. unsigned t;
  163. uint32_t W[64], a, b, c, d, e, f, g, h;
  164. const uint32_t *words = (uint32_t*) ctx->wbuffer;
  165. /* Operators defined in FIPS 180-2:4.1.2. */
  166. #define Ch(x, y, z) ((x & y) ^ (~x & z))
  167. #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
  168. #define S0(x) (rotr32(x, 2) ^ rotr32(x, 13) ^ rotr32(x, 22))
  169. #define S1(x) (rotr32(x, 6) ^ rotr32(x, 11) ^ rotr32(x, 25))
  170. #define R0(x) (rotr32(x, 7) ^ rotr32(x, 18) ^ (x >> 3))
  171. #define R1(x) (rotr32(x, 17) ^ rotr32(x, 19) ^ (x >> 10))
  172. /* Compute the message schedule according to FIPS 180-2:6.2.2 step 2. */
  173. for (t = 0; t < 16; ++t) {
  174. W[t] = ntohl(*words);
  175. words++;
  176. }
  177. for (/*t = 16*/; t < 64; ++t)
  178. W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
  179. a = ctx->hash[0];
  180. b = ctx->hash[1];
  181. c = ctx->hash[2];
  182. d = ctx->hash[3];
  183. e = ctx->hash[4];
  184. f = ctx->hash[5];
  185. g = ctx->hash[6];
  186. h = ctx->hash[7];
  187. /* The actual computation according to FIPS 180-2:6.2.2 step 3. */
  188. for (t = 0; t < 64; ++t) {
  189. /* Need to fetch upper half of sha_K[t]
  190. * (I hope compiler is clever enough to just fetch
  191. * upper half)
  192. */
  193. uint32_t K_t = sha_K[t] >> 32;
  194. uint32_t T1 = h + S1(e) + Ch(e, f, g) + K_t + W[t];
  195. uint32_t T2 = S0(a) + Maj(a, b, c);
  196. h = g;
  197. g = f;
  198. f = e;
  199. e = d + T1;
  200. d = c;
  201. c = b;
  202. b = a;
  203. a = T1 + T2;
  204. }
  205. #undef Ch
  206. #undef Maj
  207. #undef S0
  208. #undef S1
  209. #undef R0
  210. #undef R1
  211. /* Add the starting values of the context according to FIPS 180-2:6.2.2
  212. step 4. */
  213. ctx->hash[0] += a;
  214. ctx->hash[1] += b;
  215. ctx->hash[2] += c;
  216. ctx->hash[3] += d;
  217. ctx->hash[4] += e;
  218. ctx->hash[5] += f;
  219. ctx->hash[6] += g;
  220. ctx->hash[7] += h;
  221. }
  222. static void FAST_FUNC sha512_process_block128(sha512_ctx_t *ctx)
  223. {
  224. unsigned t;
  225. uint64_t W[80];
  226. /* On i386, having assignments here (not later as sha256 does)
  227. * produces 99 bytes smaller code with gcc 4.3.1
  228. */
  229. uint64_t a = ctx->hash[0];
  230. uint64_t b = ctx->hash[1];
  231. uint64_t c = ctx->hash[2];
  232. uint64_t d = ctx->hash[3];
  233. uint64_t e = ctx->hash[4];
  234. uint64_t f = ctx->hash[5];
  235. uint64_t g = ctx->hash[6];
  236. uint64_t h = ctx->hash[7];
  237. const uint64_t *words = (uint64_t*) ctx->wbuffer;
  238. /* Operators defined in FIPS 180-2:4.1.2. */
  239. #define Ch(x, y, z) ((x & y) ^ (~x & z))
  240. #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
  241. #define S0(x) (rotr64(x, 28) ^ rotr64(x, 34) ^ rotr64(x, 39))
  242. #define S1(x) (rotr64(x, 14) ^ rotr64(x, 18) ^ rotr64(x, 41))
  243. #define R0(x) (rotr64(x, 1) ^ rotr64(x, 8) ^ (x >> 7))
  244. #define R1(x) (rotr64(x, 19) ^ rotr64(x, 61) ^ (x >> 6))
  245. /* Compute the message schedule according to FIPS 180-2:6.3.2 step 2. */
  246. for (t = 0; t < 16; ++t) {
  247. W[t] = ntoh64(*words);
  248. words++;
  249. }
  250. for (/*t = 16*/; t < 80; ++t)
  251. W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
  252. /* The actual computation according to FIPS 180-2:6.3.2 step 3. */
  253. for (t = 0; t < 80; ++t) {
  254. uint64_t T1 = h + S1(e) + Ch(e, f, g) + sha_K[t] + W[t];
  255. uint64_t T2 = S0(a) + Maj(a, b, c);
  256. h = g;
  257. g = f;
  258. f = e;
  259. e = d + T1;
  260. d = c;
  261. c = b;
  262. b = a;
  263. a = T1 + T2;
  264. }
  265. #undef Ch
  266. #undef Maj
  267. #undef S0
  268. #undef S1
  269. #undef R0
  270. #undef R1
  271. /* Add the starting values of the context according to FIPS 180-2:6.3.2
  272. step 4. */
  273. ctx->hash[0] += a;
  274. ctx->hash[1] += b;
  275. ctx->hash[2] += c;
  276. ctx->hash[3] += d;
  277. ctx->hash[4] += e;
  278. ctx->hash[5] += f;
  279. ctx->hash[6] += g;
  280. ctx->hash[7] += h;
  281. }
  282. void FAST_FUNC sha1_begin(sha1_ctx_t *ctx)
  283. {
  284. ctx->hash[0] = 0x67452301;
  285. ctx->hash[1] = 0xefcdab89;
  286. ctx->hash[2] = 0x98badcfe;
  287. ctx->hash[3] = 0x10325476;
  288. ctx->hash[4] = 0xc3d2e1f0;
  289. ctx->total64 = 0;
  290. ctx->process_block = sha1_process_block64;
  291. }
  292. static const uint32_t init256[] = {
  293. 0x6a09e667,
  294. 0xbb67ae85,
  295. 0x3c6ef372,
  296. 0xa54ff53a,
  297. 0x510e527f,
  298. 0x9b05688c,
  299. 0x1f83d9ab,
  300. 0x5be0cd19
  301. };
  302. static const uint32_t init512_lo[] = {
  303. 0xf3bcc908,
  304. 0x84caa73b,
  305. 0xfe94f82b,
  306. 0x5f1d36f1,
  307. 0xade682d1,
  308. 0x2b3e6c1f,
  309. 0xfb41bd6b,
  310. 0x137e2179
  311. };
  312. /* Initialize structure containing state of computation.
  313. (FIPS 180-2:5.3.2) */
  314. void FAST_FUNC sha256_begin(sha256_ctx_t *ctx)
  315. {
  316. memcpy(ctx->hash, init256, sizeof(init256));
  317. ctx->total64 = 0;
  318. ctx->process_block = sha256_process_block64;
  319. }
  320. /* Initialize structure containing state of computation.
  321. (FIPS 180-2:5.3.3) */
  322. void FAST_FUNC sha512_begin(sha512_ctx_t *ctx)
  323. {
  324. int i;
  325. for (i = 0; i < 8; i++)
  326. ctx->hash[i] = ((uint64_t)(init256[i]) << 32) + init512_lo[i];
  327. ctx->total64[0] = ctx->total64[1] = 0;
  328. }
  329. /* Used also for sha256 */
  330. void FAST_FUNC sha1_hash(const void *buffer, size_t len, sha1_ctx_t *ctx)
  331. {
  332. unsigned in_buf = ctx->total64 & 63;
  333. unsigned add = 64 - in_buf;
  334. ctx->total64 += len;
  335. while (len >= add) { /* transfer whole blocks while possible */
  336. memcpy(ctx->wbuffer + in_buf, buffer, add);
  337. buffer = (const char *)buffer + add;
  338. len -= add;
  339. add = 64;
  340. in_buf = 0;
  341. ctx->process_block(ctx);
  342. }
  343. memcpy(ctx->wbuffer + in_buf, buffer, len);
  344. }
  345. void FAST_FUNC sha512_hash(const void *buffer, size_t len, sha512_ctx_t *ctx)
  346. {
  347. unsigned in_buf = ctx->total64[0] & 127;
  348. unsigned add = 128 - in_buf;
  349. /* First increment the byte count. FIPS 180-2 specifies the possible
  350. length of the file up to 2^128 _bits_.
  351. We compute the number of _bytes_ and convert to bits later. */
  352. ctx->total64[0] += len;
  353. if (ctx->total64[0] < len)
  354. ctx->total64[1]++;
  355. while (len >= add) { /* transfer whole blocks while possible */
  356. memcpy(ctx->wbuffer + in_buf, buffer, add);
  357. buffer = (const char *)buffer + add;
  358. len -= add;
  359. add = 128;
  360. in_buf = 0;
  361. sha512_process_block128(ctx);
  362. }
  363. memcpy(ctx->wbuffer + in_buf, buffer, len);
  364. }
  365. /* Used also for sha256 */
  366. void FAST_FUNC sha1_end(void *resbuf, sha1_ctx_t *ctx)
  367. {
  368. unsigned pad, in_buf;
  369. in_buf = ctx->total64 & 63;
  370. /* Pad the buffer to the next 64-byte boundary with 0x80,0,0,0... */
  371. ctx->wbuffer[in_buf++] = 0x80;
  372. /* This loop iterates either once or twice, no more, no less */
  373. while (1) {
  374. pad = 64 - in_buf;
  375. memset(ctx->wbuffer + in_buf, 0, pad);
  376. in_buf = 0;
  377. /* Do we have enough space for the length count? */
  378. if (pad >= 8) {
  379. /* Store the 64-bit counter of bits in the buffer in BE format */
  380. uint64_t t = ctx->total64 << 3;
  381. t = hton64(t);
  382. /* wbuffer is suitably aligned for this */
  383. *(uint64_t *) (&ctx->wbuffer[64 - 8]) = t;
  384. }
  385. ctx->process_block(ctx);
  386. if (pad >= 8)
  387. break;
  388. }
  389. in_buf = (ctx->process_block == sha1_process_block64) ? 5 : 8;
  390. /* This way we do not impose alignment constraints on resbuf: */
  391. if (BB_LITTLE_ENDIAN) {
  392. unsigned i;
  393. for (i = 0; i < in_buf; ++i)
  394. ctx->hash[i] = htonl(ctx->hash[i]);
  395. }
  396. memcpy(resbuf, ctx->hash, sizeof(ctx->hash[0]) * in_buf);
  397. }
  398. void FAST_FUNC sha512_end(void *resbuf, sha512_ctx_t *ctx)
  399. {
  400. unsigned pad, in_buf;
  401. in_buf = ctx->total64[0] & 127;
  402. /* Pad the buffer to the next 128-byte boundary with 0x80,0,0,0...
  403. * (FIPS 180-2:5.1.2)
  404. */
  405. ctx->wbuffer[in_buf++] = 0x80;
  406. while (1) {
  407. pad = 128 - in_buf;
  408. memset(ctx->wbuffer + in_buf, 0, pad);
  409. in_buf = 0;
  410. if (pad >= 16) {
  411. /* Store the 128-bit counter of bits in the buffer in BE format */
  412. uint64_t t;
  413. t = ctx->total64[0] << 3;
  414. t = hton64(t);
  415. *(uint64_t *) (&ctx->wbuffer[128 - 8]) = t;
  416. t = (ctx->total64[1] << 3) | (ctx->total64[0] >> 61);
  417. t = hton64(t);
  418. *(uint64_t *) (&ctx->wbuffer[128 - 16]) = t;
  419. }
  420. sha512_process_block128(ctx);
  421. if (pad >= 16)
  422. break;
  423. }
  424. if (BB_LITTLE_ENDIAN) {
  425. unsigned i;
  426. for (i = 0; i < ARRAY_SIZE(ctx->hash); ++i)
  427. ctx->hash[i] = hton64(ctx->hash[i]);
  428. }
  429. memcpy(resbuf, ctx->hash, sizeof(ctx->hash));
  430. }