hash_md5_sha.c 39 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487
  1. /* vi: set sw=4 ts=4: */
  2. /*
  3. * Utility routines.
  4. *
  5. * Copyright (C) 2010 Denys Vlasenko
  6. *
  7. * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  8. */
  9. #include "libbb.h"
  10. #define NEED_SHA512 (ENABLE_SHA512SUM || ENABLE_USE_BB_CRYPT_SHA)
  11. /* gcc 4.2.1 optimizes rotr64 better with inline than with macro
  12. * (for rotX32, there is no difference). Why? My guess is that
  13. * macro requires clever common subexpression elimination heuristics
  14. * in gcc, while inline basically forces it to happen.
  15. */
  16. //#define rotl32(x,n) (((x) << (n)) | ((x) >> (32 - (n))))
  17. static ALWAYS_INLINE uint32_t rotl32(uint32_t x, unsigned n)
  18. {
  19. return (x << n) | (x >> (32 - n));
  20. }
  21. //#define rotr32(x,n) (((x) >> (n)) | ((x) << (32 - (n))))
  22. static ALWAYS_INLINE uint32_t rotr32(uint32_t x, unsigned n)
  23. {
  24. return (x >> n) | (x << (32 - n));
  25. }
  26. /* rotr64 in needed for sha512 only: */
  27. //#define rotr64(x,n) (((x) >> (n)) | ((x) << (64 - (n))))
  28. static ALWAYS_INLINE uint64_t rotr64(uint64_t x, unsigned n)
  29. {
  30. return (x >> n) | (x << (64 - n));
  31. }
  32. /* rotl64 only used for sha3 currently */
  33. static ALWAYS_INLINE uint64_t rotl64(uint64_t x, unsigned n)
  34. {
  35. return (x << n) | (x >> (64 - n));
  36. }
  37. /* Feed data through a temporary buffer.
  38. * The internal buffer remembers previous data until it has 64
  39. * bytes worth to pass on.
  40. */
  41. static void FAST_FUNC common64_hash(md5_ctx_t *ctx, const void *buffer, size_t len)
  42. {
  43. unsigned bufpos = ctx->total64 & 63;
  44. ctx->total64 += len;
  45. while (1) {
  46. unsigned remaining = 64 - bufpos;
  47. if (remaining > len)
  48. remaining = len;
  49. /* Copy data into aligned buffer */
  50. memcpy(ctx->wbuffer + bufpos, buffer, remaining);
  51. len -= remaining;
  52. buffer = (const char *)buffer + remaining;
  53. bufpos += remaining;
  54. /* Clever way to do "if (bufpos != N) break; ... ; bufpos = 0;" */
  55. bufpos -= 64;
  56. if (bufpos != 0)
  57. break;
  58. /* Buffer is filled up, process it */
  59. ctx->process_block(ctx);
  60. /*bufpos = 0; - already is */
  61. }
  62. }
  63. /* Process the remaining bytes in the buffer */
  64. static void FAST_FUNC common64_end(md5_ctx_t *ctx, int swap_needed)
  65. {
  66. unsigned bufpos = ctx->total64 & 63;
  67. /* Pad the buffer to the next 64-byte boundary with 0x80,0,0,0... */
  68. ctx->wbuffer[bufpos++] = 0x80;
  69. /* This loop iterates either once or twice, no more, no less */
  70. while (1) {
  71. unsigned remaining = 64 - bufpos;
  72. memset(ctx->wbuffer + bufpos, 0, remaining);
  73. /* Do we have enough space for the length count? */
  74. if (remaining >= 8) {
  75. /* Store the 64-bit counter of bits in the buffer */
  76. uint64_t t = ctx->total64 << 3;
  77. if (swap_needed)
  78. t = bb_bswap_64(t);
  79. /* wbuffer is suitably aligned for this */
  80. *(bb__aliased_uint64_t *) (&ctx->wbuffer[64 - 8]) = t;
  81. }
  82. ctx->process_block(ctx);
  83. if (remaining >= 8)
  84. break;
  85. bufpos = 0;
  86. }
  87. }
  88. /*
  89. * Compute MD5 checksum of strings according to the
  90. * definition of MD5 in RFC 1321 from April 1992.
  91. *
  92. * Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
  93. *
  94. * Copyright (C) 1995-1999 Free Software Foundation, Inc.
  95. * Copyright (C) 2001 Manuel Novoa III
  96. * Copyright (C) 2003 Glenn L. McGrath
  97. * Copyright (C) 2003 Erik Andersen
  98. *
  99. * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  100. */
  101. /* 0: fastest, 3: smallest */
  102. #if CONFIG_MD5_SMALL < 0
  103. # define MD5_SMALL 0
  104. #elif CONFIG_MD5_SMALL > 3
  105. # define MD5_SMALL 3
  106. #else
  107. # define MD5_SMALL CONFIG_MD5_SMALL
  108. #endif
  109. /* These are the four functions used in the four steps of the MD5 algorithm
  110. * and defined in the RFC 1321. The first function is a little bit optimized
  111. * (as found in Colin Plumbs public domain implementation).
  112. * #define FF(b, c, d) ((b & c) | (~b & d))
  113. */
  114. #undef FF
  115. #undef FG
  116. #undef FH
  117. #undef FI
  118. #define FF(b, c, d) (d ^ (b & (c ^ d)))
  119. #define FG(b, c, d) FF(d, b, c)
  120. #define FH(b, c, d) (b ^ c ^ d)
  121. #define FI(b, c, d) (c ^ (b | ~d))
  122. /* Hash a single block, 64 bytes long and 4-byte aligned */
  123. static void FAST_FUNC md5_process_block64(md5_ctx_t *ctx)
  124. {
  125. #if MD5_SMALL > 0
  126. /* Before we start, one word to the strange constants.
  127. They are defined in RFC 1321 as
  128. T[i] = (int)(2^32 * fabs(sin(i))), i=1..64
  129. */
  130. static const uint32_t C_array[] = {
  131. /* round 1 */
  132. 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
  133. 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
  134. 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
  135. 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
  136. /* round 2 */
  137. 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
  138. 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
  139. 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
  140. 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
  141. /* round 3 */
  142. 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
  143. 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
  144. 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
  145. 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
  146. /* round 4 */
  147. 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
  148. 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
  149. 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
  150. 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
  151. };
  152. static const char P_array[] ALIGN1 = {
  153. # if MD5_SMALL > 1
  154. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
  155. # endif
  156. 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
  157. 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
  158. 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
  159. };
  160. #endif
  161. uint32_t *words = (void*) ctx->wbuffer;
  162. uint32_t A = ctx->hash[0];
  163. uint32_t B = ctx->hash[1];
  164. uint32_t C = ctx->hash[2];
  165. uint32_t D = ctx->hash[3];
  166. #if MD5_SMALL >= 2 /* 2 or 3 */
  167. static const char S_array[] ALIGN1 = {
  168. 7, 12, 17, 22,
  169. 5, 9, 14, 20,
  170. 4, 11, 16, 23,
  171. 6, 10, 15, 21
  172. };
  173. const uint32_t *pc;
  174. const char *pp;
  175. const char *ps;
  176. int i;
  177. uint32_t temp;
  178. if (BB_BIG_ENDIAN)
  179. for (i = 0; i < 16; i++)
  180. words[i] = SWAP_LE32(words[i]);
  181. # if MD5_SMALL == 3
  182. pc = C_array;
  183. pp = P_array;
  184. ps = S_array - 4;
  185. for (i = 0; i < 64; i++) {
  186. if ((i & 0x0f) == 0)
  187. ps += 4;
  188. temp = A;
  189. switch (i >> 4) {
  190. case 0:
  191. temp += FF(B, C, D);
  192. break;
  193. case 1:
  194. temp += FG(B, C, D);
  195. break;
  196. case 2:
  197. temp += FH(B, C, D);
  198. break;
  199. default: /* case 3 */
  200. temp += FI(B, C, D);
  201. }
  202. temp += words[(int) (*pp++)] + *pc++;
  203. temp = rotl32(temp, ps[i & 3]);
  204. temp += B;
  205. A = D;
  206. D = C;
  207. C = B;
  208. B = temp;
  209. }
  210. # else /* MD5_SMALL == 2 */
  211. pc = C_array;
  212. pp = P_array;
  213. ps = S_array;
  214. for (i = 0; i < 16; i++) {
  215. temp = A + FF(B, C, D) + words[(int) (*pp++)] + *pc++;
  216. temp = rotl32(temp, ps[i & 3]);
  217. temp += B;
  218. A = D;
  219. D = C;
  220. C = B;
  221. B = temp;
  222. }
  223. ps += 4;
  224. for (i = 0; i < 16; i++) {
  225. temp = A + FG(B, C, D) + words[(int) (*pp++)] + *pc++;
  226. temp = rotl32(temp, ps[i & 3]);
  227. temp += B;
  228. A = D;
  229. D = C;
  230. C = B;
  231. B = temp;
  232. }
  233. ps += 4;
  234. for (i = 0; i < 16; i++) {
  235. temp = A + FH(B, C, D) + words[(int) (*pp++)] + *pc++;
  236. temp = rotl32(temp, ps[i & 3]);
  237. temp += B;
  238. A = D;
  239. D = C;
  240. C = B;
  241. B = temp;
  242. }
  243. ps += 4;
  244. for (i = 0; i < 16; i++) {
  245. temp = A + FI(B, C, D) + words[(int) (*pp++)] + *pc++;
  246. temp = rotl32(temp, ps[i & 3]);
  247. temp += B;
  248. A = D;
  249. D = C;
  250. C = B;
  251. B = temp;
  252. }
  253. # endif
  254. /* Add checksum to the starting values */
  255. ctx->hash[0] += A;
  256. ctx->hash[1] += B;
  257. ctx->hash[2] += C;
  258. ctx->hash[3] += D;
  259. #else /* MD5_SMALL == 0 or 1 */
  260. # if MD5_SMALL == 1
  261. const uint32_t *pc;
  262. const char *pp;
  263. int i;
  264. # endif
  265. /* First round: using the given function, the context and a constant
  266. the next context is computed. Because the algorithm's processing
  267. unit is a 32-bit word and it is determined to work on words in
  268. little endian byte order we perhaps have to change the byte order
  269. before the computation. To reduce the work for the next steps
  270. we save swapped words in WORDS array. */
  271. # undef OP
  272. # define OP(a, b, c, d, s, T) \
  273. do { \
  274. a += FF(b, c, d) + (*words IF_BIG_ENDIAN(= SWAP_LE32(*words))) + T; \
  275. words++; \
  276. a = rotl32(a, s); \
  277. a += b; \
  278. } while (0)
  279. /* Round 1 */
  280. # if MD5_SMALL == 1
  281. pc = C_array;
  282. for (i = 0; i < 4; i++) {
  283. OP(A, B, C, D, 7, *pc++);
  284. OP(D, A, B, C, 12, *pc++);
  285. OP(C, D, A, B, 17, *pc++);
  286. OP(B, C, D, A, 22, *pc++);
  287. }
  288. # else
  289. OP(A, B, C, D, 7, 0xd76aa478);
  290. OP(D, A, B, C, 12, 0xe8c7b756);
  291. OP(C, D, A, B, 17, 0x242070db);
  292. OP(B, C, D, A, 22, 0xc1bdceee);
  293. OP(A, B, C, D, 7, 0xf57c0faf);
  294. OP(D, A, B, C, 12, 0x4787c62a);
  295. OP(C, D, A, B, 17, 0xa8304613);
  296. OP(B, C, D, A, 22, 0xfd469501);
  297. OP(A, B, C, D, 7, 0x698098d8);
  298. OP(D, A, B, C, 12, 0x8b44f7af);
  299. OP(C, D, A, B, 17, 0xffff5bb1);
  300. OP(B, C, D, A, 22, 0x895cd7be);
  301. OP(A, B, C, D, 7, 0x6b901122);
  302. OP(D, A, B, C, 12, 0xfd987193);
  303. OP(C, D, A, B, 17, 0xa679438e);
  304. OP(B, C, D, A, 22, 0x49b40821);
  305. # endif
  306. words -= 16;
  307. /* For the second to fourth round we have the possibly swapped words
  308. in WORDS. Redefine the macro to take an additional first
  309. argument specifying the function to use. */
  310. # undef OP
  311. # define OP(f, a, b, c, d, k, s, T) \
  312. do { \
  313. a += f(b, c, d) + words[k] + T; \
  314. a = rotl32(a, s); \
  315. a += b; \
  316. } while (0)
  317. /* Round 2 */
  318. # if MD5_SMALL == 1
  319. pp = P_array;
  320. for (i = 0; i < 4; i++) {
  321. OP(FG, A, B, C, D, (int) (*pp++), 5, *pc++);
  322. OP(FG, D, A, B, C, (int) (*pp++), 9, *pc++);
  323. OP(FG, C, D, A, B, (int) (*pp++), 14, *pc++);
  324. OP(FG, B, C, D, A, (int) (*pp++), 20, *pc++);
  325. }
  326. # else
  327. OP(FG, A, B, C, D, 1, 5, 0xf61e2562);
  328. OP(FG, D, A, B, C, 6, 9, 0xc040b340);
  329. OP(FG, C, D, A, B, 11, 14, 0x265e5a51);
  330. OP(FG, B, C, D, A, 0, 20, 0xe9b6c7aa);
  331. OP(FG, A, B, C, D, 5, 5, 0xd62f105d);
  332. OP(FG, D, A, B, C, 10, 9, 0x02441453);
  333. OP(FG, C, D, A, B, 15, 14, 0xd8a1e681);
  334. OP(FG, B, C, D, A, 4, 20, 0xe7d3fbc8);
  335. OP(FG, A, B, C, D, 9, 5, 0x21e1cde6);
  336. OP(FG, D, A, B, C, 14, 9, 0xc33707d6);
  337. OP(FG, C, D, A, B, 3, 14, 0xf4d50d87);
  338. OP(FG, B, C, D, A, 8, 20, 0x455a14ed);
  339. OP(FG, A, B, C, D, 13, 5, 0xa9e3e905);
  340. OP(FG, D, A, B, C, 2, 9, 0xfcefa3f8);
  341. OP(FG, C, D, A, B, 7, 14, 0x676f02d9);
  342. OP(FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
  343. # endif
  344. /* Round 3 */
  345. # if MD5_SMALL == 1
  346. for (i = 0; i < 4; i++) {
  347. OP(FH, A, B, C, D, (int) (*pp++), 4, *pc++);
  348. OP(FH, D, A, B, C, (int) (*pp++), 11, *pc++);
  349. OP(FH, C, D, A, B, (int) (*pp++), 16, *pc++);
  350. OP(FH, B, C, D, A, (int) (*pp++), 23, *pc++);
  351. }
  352. # else
  353. OP(FH, A, B, C, D, 5, 4, 0xfffa3942);
  354. OP(FH, D, A, B, C, 8, 11, 0x8771f681);
  355. OP(FH, C, D, A, B, 11, 16, 0x6d9d6122);
  356. OP(FH, B, C, D, A, 14, 23, 0xfde5380c);
  357. OP(FH, A, B, C, D, 1, 4, 0xa4beea44);
  358. OP(FH, D, A, B, C, 4, 11, 0x4bdecfa9);
  359. OP(FH, C, D, A, B, 7, 16, 0xf6bb4b60);
  360. OP(FH, B, C, D, A, 10, 23, 0xbebfbc70);
  361. OP(FH, A, B, C, D, 13, 4, 0x289b7ec6);
  362. OP(FH, D, A, B, C, 0, 11, 0xeaa127fa);
  363. OP(FH, C, D, A, B, 3, 16, 0xd4ef3085);
  364. OP(FH, B, C, D, A, 6, 23, 0x04881d05);
  365. OP(FH, A, B, C, D, 9, 4, 0xd9d4d039);
  366. OP(FH, D, A, B, C, 12, 11, 0xe6db99e5);
  367. OP(FH, C, D, A, B, 15, 16, 0x1fa27cf8);
  368. OP(FH, B, C, D, A, 2, 23, 0xc4ac5665);
  369. # endif
  370. /* Round 4 */
  371. # if MD5_SMALL == 1
  372. for (i = 0; i < 4; i++) {
  373. OP(FI, A, B, C, D, (int) (*pp++), 6, *pc++);
  374. OP(FI, D, A, B, C, (int) (*pp++), 10, *pc++);
  375. OP(FI, C, D, A, B, (int) (*pp++), 15, *pc++);
  376. OP(FI, B, C, D, A, (int) (*pp++), 21, *pc++);
  377. }
  378. # else
  379. OP(FI, A, B, C, D, 0, 6, 0xf4292244);
  380. OP(FI, D, A, B, C, 7, 10, 0x432aff97);
  381. OP(FI, C, D, A, B, 14, 15, 0xab9423a7);
  382. OP(FI, B, C, D, A, 5, 21, 0xfc93a039);
  383. OP(FI, A, B, C, D, 12, 6, 0x655b59c3);
  384. OP(FI, D, A, B, C, 3, 10, 0x8f0ccc92);
  385. OP(FI, C, D, A, B, 10, 15, 0xffeff47d);
  386. OP(FI, B, C, D, A, 1, 21, 0x85845dd1);
  387. OP(FI, A, B, C, D, 8, 6, 0x6fa87e4f);
  388. OP(FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
  389. OP(FI, C, D, A, B, 6, 15, 0xa3014314);
  390. OP(FI, B, C, D, A, 13, 21, 0x4e0811a1);
  391. OP(FI, A, B, C, D, 4, 6, 0xf7537e82);
  392. OP(FI, D, A, B, C, 11, 10, 0xbd3af235);
  393. OP(FI, C, D, A, B, 2, 15, 0x2ad7d2bb);
  394. OP(FI, B, C, D, A, 9, 21, 0xeb86d391);
  395. # undef OP
  396. # endif
  397. /* Add checksum to the starting values */
  398. ctx->hash[0] += A;
  399. ctx->hash[1] += B;
  400. ctx->hash[2] += C;
  401. ctx->hash[3] += D;
  402. #endif
  403. }
  404. #undef FF
  405. #undef FG
  406. #undef FH
  407. #undef FI
  408. /* Initialize structure containing state of computation.
  409. * (RFC 1321, 3.3: Step 3)
  410. */
  411. void FAST_FUNC md5_begin(md5_ctx_t *ctx)
  412. {
  413. ctx->hash[0] = 0x67452301;
  414. ctx->hash[1] = 0xefcdab89;
  415. ctx->hash[2] = 0x98badcfe;
  416. ctx->hash[3] = 0x10325476;
  417. ctx->total64 = 0;
  418. ctx->process_block = md5_process_block64;
  419. }
  420. /* Used also for sha1 and sha256 */
  421. void FAST_FUNC md5_hash(md5_ctx_t *ctx, const void *buffer, size_t len)
  422. {
  423. common64_hash(ctx, buffer, len);
  424. }
  425. /* Process the remaining bytes in the buffer and put result from CTX
  426. * in first 16 bytes following RESBUF. The result is always in little
  427. * endian byte order, so that a byte-wise output yields to the wanted
  428. * ASCII representation of the message digest.
  429. */
  430. unsigned FAST_FUNC md5_end(md5_ctx_t *ctx, void *resbuf)
  431. {
  432. /* MD5 stores total in LE, need to swap on BE arches: */
  433. common64_end(ctx, /*swap_needed:*/ BB_BIG_ENDIAN);
  434. /* The MD5 result is in little endian byte order */
  435. if (BB_BIG_ENDIAN) {
  436. ctx->hash[0] = SWAP_LE32(ctx->hash[0]);
  437. ctx->hash[1] = SWAP_LE32(ctx->hash[1]);
  438. ctx->hash[2] = SWAP_LE32(ctx->hash[2]);
  439. ctx->hash[3] = SWAP_LE32(ctx->hash[3]);
  440. }
  441. memcpy(resbuf, ctx->hash, sizeof(ctx->hash[0]) * 4);
  442. return sizeof(ctx->hash[0]) * 4;
  443. }
  444. /*
  445. * SHA1 part is:
  446. * Copyright 2007 Rob Landley <rob@landley.net>
  447. *
  448. * Based on the public domain SHA-1 in C by Steve Reid <steve@edmweb.com>
  449. * from http://www.mirrors.wiretapped.net/security/cryptography/hashes/sha1/
  450. *
  451. * Licensed under GPLv2, see file LICENSE in this source tree.
  452. *
  453. * ---------------------------------------------------------------------------
  454. *
  455. * SHA256 and SHA512 parts are:
  456. * Released into the Public Domain by Ulrich Drepper <drepper@redhat.com>.
  457. * Shrank by Denys Vlasenko.
  458. *
  459. * ---------------------------------------------------------------------------
  460. *
  461. * The best way to test random blocksizes is to go to coreutils/md5_sha1_sum.c
  462. * and replace "4096" with something like "2000 + time(NULL) % 2097",
  463. * then rebuild and compare "shaNNNsum bigfile" results.
  464. */
  465. static void FAST_FUNC sha1_process_block64(sha1_ctx_t *ctx)
  466. {
  467. static const uint32_t rconsts[] = {
  468. 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6
  469. };
  470. int i, j;
  471. int cnt;
  472. uint32_t W[16+16];
  473. uint32_t a, b, c, d, e;
  474. /* On-stack work buffer frees up one register in the main loop
  475. * which otherwise will be needed to hold ctx pointer */
  476. for (i = 0; i < 16; i++)
  477. W[i] = W[i+16] = SWAP_BE32(((uint32_t*)ctx->wbuffer)[i]);
  478. a = ctx->hash[0];
  479. b = ctx->hash[1];
  480. c = ctx->hash[2];
  481. d = ctx->hash[3];
  482. e = ctx->hash[4];
  483. /* 4 rounds of 20 operations each */
  484. cnt = 0;
  485. for (i = 0; i < 4; i++) {
  486. j = 19;
  487. do {
  488. uint32_t work;
  489. work = c ^ d;
  490. if (i == 0) {
  491. work = (work & b) ^ d;
  492. if (j <= 3)
  493. goto ge16;
  494. /* Used to do SWAP_BE32 here, but this
  495. * requires ctx (see comment above) */
  496. work += W[cnt];
  497. } else {
  498. if (i == 2)
  499. work = ((b | c) & d) | (b & c);
  500. else /* i = 1 or 3 */
  501. work ^= b;
  502. ge16:
  503. W[cnt] = W[cnt+16] = rotl32(W[cnt+13] ^ W[cnt+8] ^ W[cnt+2] ^ W[cnt], 1);
  504. work += W[cnt];
  505. }
  506. work += e + rotl32(a, 5) + rconsts[i];
  507. /* Rotate by one for next time */
  508. e = d;
  509. d = c;
  510. c = /* b = */ rotl32(b, 30);
  511. b = a;
  512. a = work;
  513. cnt = (cnt + 1) & 15;
  514. } while (--j >= 0);
  515. }
  516. ctx->hash[0] += a;
  517. ctx->hash[1] += b;
  518. ctx->hash[2] += c;
  519. ctx->hash[3] += d;
  520. ctx->hash[4] += e;
  521. }
  522. /* Constants for SHA512 from FIPS 180-2:4.2.3.
  523. * SHA256 constants from FIPS 180-2:4.2.2
  524. * are the most significant half of first 64 elements
  525. * of the same array.
  526. */
  527. #undef K
  528. #if NEED_SHA512
  529. typedef uint64_t sha_K_int;
  530. # define K(v) v
  531. #else
  532. typedef uint32_t sha_K_int;
  533. # define K(v) (uint32_t)(v >> 32)
  534. #endif
  535. static const sha_K_int sha_K[] = {
  536. K(0x428a2f98d728ae22ULL), K(0x7137449123ef65cdULL),
  537. K(0xb5c0fbcfec4d3b2fULL), K(0xe9b5dba58189dbbcULL),
  538. K(0x3956c25bf348b538ULL), K(0x59f111f1b605d019ULL),
  539. K(0x923f82a4af194f9bULL), K(0xab1c5ed5da6d8118ULL),
  540. K(0xd807aa98a3030242ULL), K(0x12835b0145706fbeULL),
  541. K(0x243185be4ee4b28cULL), K(0x550c7dc3d5ffb4e2ULL),
  542. K(0x72be5d74f27b896fULL), K(0x80deb1fe3b1696b1ULL),
  543. K(0x9bdc06a725c71235ULL), K(0xc19bf174cf692694ULL),
  544. K(0xe49b69c19ef14ad2ULL), K(0xefbe4786384f25e3ULL),
  545. K(0x0fc19dc68b8cd5b5ULL), K(0x240ca1cc77ac9c65ULL),
  546. K(0x2de92c6f592b0275ULL), K(0x4a7484aa6ea6e483ULL),
  547. K(0x5cb0a9dcbd41fbd4ULL), K(0x76f988da831153b5ULL),
  548. K(0x983e5152ee66dfabULL), K(0xa831c66d2db43210ULL),
  549. K(0xb00327c898fb213fULL), K(0xbf597fc7beef0ee4ULL),
  550. K(0xc6e00bf33da88fc2ULL), K(0xd5a79147930aa725ULL),
  551. K(0x06ca6351e003826fULL), K(0x142929670a0e6e70ULL),
  552. K(0x27b70a8546d22ffcULL), K(0x2e1b21385c26c926ULL),
  553. K(0x4d2c6dfc5ac42aedULL), K(0x53380d139d95b3dfULL),
  554. K(0x650a73548baf63deULL), K(0x766a0abb3c77b2a8ULL),
  555. K(0x81c2c92e47edaee6ULL), K(0x92722c851482353bULL),
  556. K(0xa2bfe8a14cf10364ULL), K(0xa81a664bbc423001ULL),
  557. K(0xc24b8b70d0f89791ULL), K(0xc76c51a30654be30ULL),
  558. K(0xd192e819d6ef5218ULL), K(0xd69906245565a910ULL),
  559. K(0xf40e35855771202aULL), K(0x106aa07032bbd1b8ULL),
  560. K(0x19a4c116b8d2d0c8ULL), K(0x1e376c085141ab53ULL),
  561. K(0x2748774cdf8eeb99ULL), K(0x34b0bcb5e19b48a8ULL),
  562. K(0x391c0cb3c5c95a63ULL), K(0x4ed8aa4ae3418acbULL),
  563. K(0x5b9cca4f7763e373ULL), K(0x682e6ff3d6b2b8a3ULL),
  564. K(0x748f82ee5defb2fcULL), K(0x78a5636f43172f60ULL),
  565. K(0x84c87814a1f0ab72ULL), K(0x8cc702081a6439ecULL),
  566. K(0x90befffa23631e28ULL), K(0xa4506cebde82bde9ULL),
  567. K(0xbef9a3f7b2c67915ULL), K(0xc67178f2e372532bULL),
  568. #if NEED_SHA512 /* [64]+ are used for sha512 only */
  569. K(0xca273eceea26619cULL), K(0xd186b8c721c0c207ULL),
  570. K(0xeada7dd6cde0eb1eULL), K(0xf57d4f7fee6ed178ULL),
  571. K(0x06f067aa72176fbaULL), K(0x0a637dc5a2c898a6ULL),
  572. K(0x113f9804bef90daeULL), K(0x1b710b35131c471bULL),
  573. K(0x28db77f523047d84ULL), K(0x32caab7b40c72493ULL),
  574. K(0x3c9ebe0a15c9bebcULL), K(0x431d67c49c100d4cULL),
  575. K(0x4cc5d4becb3e42b6ULL), K(0x597f299cfc657e2aULL),
  576. K(0x5fcb6fab3ad6faecULL), K(0x6c44198c4a475817ULL),
  577. #endif
  578. };
  579. #undef K
  580. #undef Ch
  581. #undef Maj
  582. #undef S0
  583. #undef S1
  584. #undef R0
  585. #undef R1
  586. static void FAST_FUNC sha256_process_block64(sha256_ctx_t *ctx)
  587. {
  588. unsigned t;
  589. uint32_t W[64], a, b, c, d, e, f, g, h;
  590. const uint32_t *words = (uint32_t*) ctx->wbuffer;
  591. /* Operators defined in FIPS 180-2:4.1.2. */
  592. #define Ch(x, y, z) ((x & y) ^ (~x & z))
  593. #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
  594. #define S0(x) (rotr32(x, 2) ^ rotr32(x, 13) ^ rotr32(x, 22))
  595. #define S1(x) (rotr32(x, 6) ^ rotr32(x, 11) ^ rotr32(x, 25))
  596. #define R0(x) (rotr32(x, 7) ^ rotr32(x, 18) ^ (x >> 3))
  597. #define R1(x) (rotr32(x, 17) ^ rotr32(x, 19) ^ (x >> 10))
  598. /* Compute the message schedule according to FIPS 180-2:6.2.2 step 2. */
  599. for (t = 0; t < 16; ++t)
  600. W[t] = SWAP_BE32(words[t]);
  601. for (/*t = 16*/; t < 64; ++t)
  602. W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
  603. a = ctx->hash[0];
  604. b = ctx->hash[1];
  605. c = ctx->hash[2];
  606. d = ctx->hash[3];
  607. e = ctx->hash[4];
  608. f = ctx->hash[5];
  609. g = ctx->hash[6];
  610. h = ctx->hash[7];
  611. /* The actual computation according to FIPS 180-2:6.2.2 step 3. */
  612. for (t = 0; t < 64; ++t) {
  613. /* Need to fetch upper half of sha_K[t]
  614. * (I hope compiler is clever enough to just fetch
  615. * upper half)
  616. */
  617. uint32_t K_t = NEED_SHA512 ? (sha_K[t] >> 32) : sha_K[t];
  618. uint32_t T1 = h + S1(e) + Ch(e, f, g) + K_t + W[t];
  619. uint32_t T2 = S0(a) + Maj(a, b, c);
  620. h = g;
  621. g = f;
  622. f = e;
  623. e = d + T1;
  624. d = c;
  625. c = b;
  626. b = a;
  627. a = T1 + T2;
  628. }
  629. #undef Ch
  630. #undef Maj
  631. #undef S0
  632. #undef S1
  633. #undef R0
  634. #undef R1
  635. /* Add the starting values of the context according to FIPS 180-2:6.2.2
  636. step 4. */
  637. ctx->hash[0] += a;
  638. ctx->hash[1] += b;
  639. ctx->hash[2] += c;
  640. ctx->hash[3] += d;
  641. ctx->hash[4] += e;
  642. ctx->hash[5] += f;
  643. ctx->hash[6] += g;
  644. ctx->hash[7] += h;
  645. }
  646. #if NEED_SHA512
  647. static void FAST_FUNC sha512_process_block128(sha512_ctx_t *ctx)
  648. {
  649. unsigned t;
  650. uint64_t W[80];
  651. /* On i386, having assignments here (not later as sha256 does)
  652. * produces 99 bytes smaller code with gcc 4.3.1
  653. */
  654. uint64_t a = ctx->hash[0];
  655. uint64_t b = ctx->hash[1];
  656. uint64_t c = ctx->hash[2];
  657. uint64_t d = ctx->hash[3];
  658. uint64_t e = ctx->hash[4];
  659. uint64_t f = ctx->hash[5];
  660. uint64_t g = ctx->hash[6];
  661. uint64_t h = ctx->hash[7];
  662. const uint64_t *words = (uint64_t*) ctx->wbuffer;
  663. /* Operators defined in FIPS 180-2:4.1.2. */
  664. #define Ch(x, y, z) ((x & y) ^ (~x & z))
  665. #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
  666. #define S0(x) (rotr64(x, 28) ^ rotr64(x, 34) ^ rotr64(x, 39))
  667. #define S1(x) (rotr64(x, 14) ^ rotr64(x, 18) ^ rotr64(x, 41))
  668. #define R0(x) (rotr64(x, 1) ^ rotr64(x, 8) ^ (x >> 7))
  669. #define R1(x) (rotr64(x, 19) ^ rotr64(x, 61) ^ (x >> 6))
  670. /* Compute the message schedule according to FIPS 180-2:6.3.2 step 2. */
  671. for (t = 0; t < 16; ++t)
  672. W[t] = SWAP_BE64(words[t]);
  673. for (/*t = 16*/; t < 80; ++t)
  674. W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
  675. /* The actual computation according to FIPS 180-2:6.3.2 step 3. */
  676. for (t = 0; t < 80; ++t) {
  677. uint64_t T1 = h + S1(e) + Ch(e, f, g) + sha_K[t] + W[t];
  678. uint64_t T2 = S0(a) + Maj(a, b, c);
  679. h = g;
  680. g = f;
  681. f = e;
  682. e = d + T1;
  683. d = c;
  684. c = b;
  685. b = a;
  686. a = T1 + T2;
  687. }
  688. #undef Ch
  689. #undef Maj
  690. #undef S0
  691. #undef S1
  692. #undef R0
  693. #undef R1
  694. /* Add the starting values of the context according to FIPS 180-2:6.3.2
  695. step 4. */
  696. ctx->hash[0] += a;
  697. ctx->hash[1] += b;
  698. ctx->hash[2] += c;
  699. ctx->hash[3] += d;
  700. ctx->hash[4] += e;
  701. ctx->hash[5] += f;
  702. ctx->hash[6] += g;
  703. ctx->hash[7] += h;
  704. }
  705. #endif /* NEED_SHA512 */
  706. void FAST_FUNC sha1_begin(sha1_ctx_t *ctx)
  707. {
  708. ctx->hash[0] = 0x67452301;
  709. ctx->hash[1] = 0xefcdab89;
  710. ctx->hash[2] = 0x98badcfe;
  711. ctx->hash[3] = 0x10325476;
  712. ctx->hash[4] = 0xc3d2e1f0;
  713. ctx->total64 = 0;
  714. ctx->process_block = sha1_process_block64;
  715. }
  716. static const uint32_t init256[] = {
  717. 0,
  718. 0,
  719. 0x6a09e667,
  720. 0xbb67ae85,
  721. 0x3c6ef372,
  722. 0xa54ff53a,
  723. 0x510e527f,
  724. 0x9b05688c,
  725. 0x1f83d9ab,
  726. 0x5be0cd19,
  727. };
  728. #if NEED_SHA512
  729. static const uint32_t init512_lo[] = {
  730. 0,
  731. 0,
  732. 0xf3bcc908,
  733. 0x84caa73b,
  734. 0xfe94f82b,
  735. 0x5f1d36f1,
  736. 0xade682d1,
  737. 0x2b3e6c1f,
  738. 0xfb41bd6b,
  739. 0x137e2179,
  740. };
  741. #endif /* NEED_SHA512 */
  742. // Note: SHA-384 is identical to SHA-512, except that initial hash values are
  743. // 0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939,
  744. // 0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4,
  745. // and the output is constructed by omitting last two 64-bit words of it.
  746. /* Initialize structure containing state of computation.
  747. (FIPS 180-2:5.3.2) */
  748. void FAST_FUNC sha256_begin(sha256_ctx_t *ctx)
  749. {
  750. memcpy(&ctx->total64, init256, sizeof(init256));
  751. /*ctx->total64 = 0; - done by prepending two 32-bit zeros to init256 */
  752. ctx->process_block = sha256_process_block64;
  753. }
  754. #if NEED_SHA512
  755. /* Initialize structure containing state of computation.
  756. (FIPS 180-2:5.3.3) */
  757. void FAST_FUNC sha512_begin(sha512_ctx_t *ctx)
  758. {
  759. int i;
  760. /* Two extra iterations zero out ctx->total64[2] */
  761. uint64_t *tp = ctx->total64;
  762. for (i = 0; i < 2+8; i++)
  763. tp[i] = ((uint64_t)(init256[i]) << 32) + init512_lo[i];
  764. /*ctx->total64[0] = ctx->total64[1] = 0; - already done */
  765. }
  766. void FAST_FUNC sha512_hash(sha512_ctx_t *ctx, const void *buffer, size_t len)
  767. {
  768. unsigned bufpos = ctx->total64[0] & 127;
  769. unsigned remaining;
  770. /* First increment the byte count. FIPS 180-2 specifies the possible
  771. length of the file up to 2^128 _bits_.
  772. We compute the number of _bytes_ and convert to bits later. */
  773. ctx->total64[0] += len;
  774. if (ctx->total64[0] < len)
  775. ctx->total64[1]++;
  776. # if 0
  777. remaining = 128 - bufpos;
  778. /* Hash whole blocks */
  779. while (len >= remaining) {
  780. memcpy(ctx->wbuffer + bufpos, buffer, remaining);
  781. buffer = (const char *)buffer + remaining;
  782. len -= remaining;
  783. remaining = 128;
  784. bufpos = 0;
  785. sha512_process_block128(ctx);
  786. }
  787. /* Save last, partial blosk */
  788. memcpy(ctx->wbuffer + bufpos, buffer, len);
  789. # else
  790. while (1) {
  791. remaining = 128 - bufpos;
  792. if (remaining > len)
  793. remaining = len;
  794. /* Copy data into aligned buffer */
  795. memcpy(ctx->wbuffer + bufpos, buffer, remaining);
  796. len -= remaining;
  797. buffer = (const char *)buffer + remaining;
  798. bufpos += remaining;
  799. /* Clever way to do "if (bufpos != N) break; ... ; bufpos = 0;" */
  800. bufpos -= 128;
  801. if (bufpos != 0)
  802. break;
  803. /* Buffer is filled up, process it */
  804. sha512_process_block128(ctx);
  805. /*bufpos = 0; - already is */
  806. }
  807. # endif
  808. }
  809. #endif /* NEED_SHA512 */
  810. /* Used also for sha256 */
  811. unsigned FAST_FUNC sha1_end(sha1_ctx_t *ctx, void *resbuf)
  812. {
  813. unsigned hash_size;
  814. /* SHA stores total in BE, need to swap on LE arches: */
  815. common64_end(ctx, /*swap_needed:*/ BB_LITTLE_ENDIAN);
  816. hash_size = (ctx->process_block == sha1_process_block64) ? 5 : 8;
  817. /* This way we do not impose alignment constraints on resbuf: */
  818. if (BB_LITTLE_ENDIAN) {
  819. unsigned i;
  820. for (i = 0; i < hash_size; ++i)
  821. ctx->hash[i] = SWAP_BE32(ctx->hash[i]);
  822. }
  823. hash_size *= sizeof(ctx->hash[0]);
  824. memcpy(resbuf, ctx->hash, hash_size);
  825. return hash_size;
  826. }
  827. #if NEED_SHA512
  828. unsigned FAST_FUNC sha512_end(sha512_ctx_t *ctx, void *resbuf)
  829. {
  830. unsigned bufpos = ctx->total64[0] & 127;
  831. /* Pad the buffer to the next 128-byte boundary with 0x80,0,0,0... */
  832. ctx->wbuffer[bufpos++] = 0x80;
  833. while (1) {
  834. unsigned remaining = 128 - bufpos;
  835. memset(ctx->wbuffer + bufpos, 0, remaining);
  836. if (remaining >= 16) {
  837. /* Store the 128-bit counter of bits in the buffer in BE format */
  838. uint64_t t;
  839. t = ctx->total64[0] << 3;
  840. t = SWAP_BE64(t);
  841. *(bb__aliased_uint64_t *) (&ctx->wbuffer[128 - 8]) = t;
  842. t = (ctx->total64[1] << 3) | (ctx->total64[0] >> 61);
  843. t = SWAP_BE64(t);
  844. *(bb__aliased_uint64_t *) (&ctx->wbuffer[128 - 16]) = t;
  845. }
  846. sha512_process_block128(ctx);
  847. if (remaining >= 16)
  848. break;
  849. bufpos = 0;
  850. }
  851. if (BB_LITTLE_ENDIAN) {
  852. unsigned i;
  853. for (i = 0; i < ARRAY_SIZE(ctx->hash); ++i)
  854. ctx->hash[i] = SWAP_BE64(ctx->hash[i]);
  855. }
  856. memcpy(resbuf, ctx->hash, sizeof(ctx->hash));
  857. return sizeof(ctx->hash);
  858. }
  859. #endif /* NEED_SHA512 */
  860. /*
  861. * The Keccak sponge function, designed by Guido Bertoni, Joan Daemen,
  862. * Michael Peeters and Gilles Van Assche. For more information, feedback or
  863. * questions, please refer to our website: http://keccak.noekeon.org/
  864. *
  865. * Implementation by Ronny Van Keer,
  866. * hereby denoted as "the implementer".
  867. *
  868. * To the extent possible under law, the implementer has waived all copyright
  869. * and related or neighboring rights to the source code in this file.
  870. * http://creativecommons.org/publicdomain/zero/1.0/
  871. *
  872. * Busybox modifications (C) Lauri Kasanen, under the GPLv2.
  873. */
  874. #if CONFIG_SHA3_SMALL < 0
  875. # define SHA3_SMALL 0
  876. #elif CONFIG_SHA3_SMALL > 1
  877. # define SHA3_SMALL 1
  878. #else
  879. # define SHA3_SMALL CONFIG_SHA3_SMALL
  880. #endif
  881. #define OPTIMIZE_SHA3_FOR_32 0
  882. /*
  883. * SHA3 can be optimized for 32-bit CPUs with bit-slicing:
  884. * every 64-bit word of state[] can be split into two 32-bit words
  885. * by even/odd bits. In this form, all rotations of sha3 round
  886. * are 32-bit - and there are lots of them.
  887. * However, it requires either splitting/combining state words
  888. * before/after sha3 round (code does this now)
  889. * or shuffling bits before xor'ing them into state and in sha3_end.
  890. * Without shuffling, bit-slicing results in -130 bytes of code
  891. * and marginal speedup (but of course it gives wrong result).
  892. * With shuffling it works, but +260 code bytes, and slower.
  893. * Disabled for now:
  894. */
  895. #if 0 /* LONG_MAX == 0x7fffffff */
  896. # undef OPTIMIZE_SHA3_FOR_32
  897. # define OPTIMIZE_SHA3_FOR_32 1
  898. #endif
  899. #if OPTIMIZE_SHA3_FOR_32
  900. /* This splits every 64-bit word into a pair of 32-bit words,
  901. * even bits go into first word, odd bits go to second one.
  902. * The conversion is done in-place.
  903. */
  904. static void split_halves(uint64_t *state)
  905. {
  906. /* Credit: Henry S. Warren, Hacker's Delight, Addison-Wesley, 2002 */
  907. uint32_t *s32 = (uint32_t*)state;
  908. uint32_t t, x0, x1;
  909. int i;
  910. for (i = 24; i >= 0; --i) {
  911. x0 = s32[0];
  912. t = (x0 ^ (x0 >> 1)) & 0x22222222; x0 = x0 ^ t ^ (t << 1);
  913. t = (x0 ^ (x0 >> 2)) & 0x0C0C0C0C; x0 = x0 ^ t ^ (t << 2);
  914. t = (x0 ^ (x0 >> 4)) & 0x00F000F0; x0 = x0 ^ t ^ (t << 4);
  915. t = (x0 ^ (x0 >> 8)) & 0x0000FF00; x0 = x0 ^ t ^ (t << 8);
  916. x1 = s32[1];
  917. t = (x1 ^ (x1 >> 1)) & 0x22222222; x1 = x1 ^ t ^ (t << 1);
  918. t = (x1 ^ (x1 >> 2)) & 0x0C0C0C0C; x1 = x1 ^ t ^ (t << 2);
  919. t = (x1 ^ (x1 >> 4)) & 0x00F000F0; x1 = x1 ^ t ^ (t << 4);
  920. t = (x1 ^ (x1 >> 8)) & 0x0000FF00; x1 = x1 ^ t ^ (t << 8);
  921. *s32++ = (x0 & 0x0000FFFF) | (x1 << 16);
  922. *s32++ = (x0 >> 16) | (x1 & 0xFFFF0000);
  923. }
  924. }
  925. /* The reverse operation */
  926. static void combine_halves(uint64_t *state)
  927. {
  928. uint32_t *s32 = (uint32_t*)state;
  929. uint32_t t, x0, x1;
  930. int i;
  931. for (i = 24; i >= 0; --i) {
  932. x0 = s32[0];
  933. x1 = s32[1];
  934. t = (x0 & 0x0000FFFF) | (x1 << 16);
  935. x1 = (x0 >> 16) | (x1 & 0xFFFF0000);
  936. x0 = t;
  937. t = (x0 ^ (x0 >> 8)) & 0x0000FF00; x0 = x0 ^ t ^ (t << 8);
  938. t = (x0 ^ (x0 >> 4)) & 0x00F000F0; x0 = x0 ^ t ^ (t << 4);
  939. t = (x0 ^ (x0 >> 2)) & 0x0C0C0C0C; x0 = x0 ^ t ^ (t << 2);
  940. t = (x0 ^ (x0 >> 1)) & 0x22222222; x0 = x0 ^ t ^ (t << 1);
  941. *s32++ = x0;
  942. t = (x1 ^ (x1 >> 8)) & 0x0000FF00; x1 = x1 ^ t ^ (t << 8);
  943. t = (x1 ^ (x1 >> 4)) & 0x00F000F0; x1 = x1 ^ t ^ (t << 4);
  944. t = (x1 ^ (x1 >> 2)) & 0x0C0C0C0C; x1 = x1 ^ t ^ (t << 2);
  945. t = (x1 ^ (x1 >> 1)) & 0x22222222; x1 = x1 ^ t ^ (t << 1);
  946. *s32++ = x1;
  947. }
  948. }
  949. #endif
  950. /*
  951. * In the crypto literature this function is usually called Keccak-f().
  952. */
  953. static void sha3_process_block72(uint64_t *state)
  954. {
  955. enum { NROUNDS = 24 };
  956. #if OPTIMIZE_SHA3_FOR_32
  957. /*
  958. static const uint32_t IOTA_CONST_0[NROUNDS] = {
  959. 0x00000001UL,
  960. 0x00000000UL,
  961. 0x00000000UL,
  962. 0x00000000UL,
  963. 0x00000001UL,
  964. 0x00000001UL,
  965. 0x00000001UL,
  966. 0x00000001UL,
  967. 0x00000000UL,
  968. 0x00000000UL,
  969. 0x00000001UL,
  970. 0x00000000UL,
  971. 0x00000001UL,
  972. 0x00000001UL,
  973. 0x00000001UL,
  974. 0x00000001UL,
  975. 0x00000000UL,
  976. 0x00000000UL,
  977. 0x00000000UL,
  978. 0x00000000UL,
  979. 0x00000001UL,
  980. 0x00000000UL,
  981. 0x00000001UL,
  982. 0x00000000UL,
  983. };
  984. ** bits are in lsb: 0101 0000 1111 0100 1111 0001
  985. */
  986. uint32_t IOTA_CONST_0bits = (uint32_t)(0x0050f4f1);
  987. static const uint32_t IOTA_CONST_1[NROUNDS] = {
  988. 0x00000000UL,
  989. 0x00000089UL,
  990. 0x8000008bUL,
  991. 0x80008080UL,
  992. 0x0000008bUL,
  993. 0x00008000UL,
  994. 0x80008088UL,
  995. 0x80000082UL,
  996. 0x0000000bUL,
  997. 0x0000000aUL,
  998. 0x00008082UL,
  999. 0x00008003UL,
  1000. 0x0000808bUL,
  1001. 0x8000000bUL,
  1002. 0x8000008aUL,
  1003. 0x80000081UL,
  1004. 0x80000081UL,
  1005. 0x80000008UL,
  1006. 0x00000083UL,
  1007. 0x80008003UL,
  1008. 0x80008088UL,
  1009. 0x80000088UL,
  1010. 0x00008000UL,
  1011. 0x80008082UL,
  1012. };
  1013. uint32_t *const s32 = (uint32_t*)state;
  1014. unsigned round;
  1015. split_halves(state);
  1016. for (round = 0; round < NROUNDS; round++) {
  1017. unsigned x;
  1018. /* Theta */
  1019. {
  1020. uint32_t BC[20];
  1021. for (x = 0; x < 10; ++x) {
  1022. BC[x+10] = BC[x] = s32[x]^s32[x+10]^s32[x+20]^s32[x+30]^s32[x+40];
  1023. }
  1024. for (x = 0; x < 10; x += 2) {
  1025. uint32_t ta, tb;
  1026. ta = BC[x+8] ^ rotl32(BC[x+3], 1);
  1027. tb = BC[x+9] ^ BC[x+2];
  1028. s32[x+0] ^= ta;
  1029. s32[x+1] ^= tb;
  1030. s32[x+10] ^= ta;
  1031. s32[x+11] ^= tb;
  1032. s32[x+20] ^= ta;
  1033. s32[x+21] ^= tb;
  1034. s32[x+30] ^= ta;
  1035. s32[x+31] ^= tb;
  1036. s32[x+40] ^= ta;
  1037. s32[x+41] ^= tb;
  1038. }
  1039. }
  1040. /* RhoPi */
  1041. {
  1042. uint32_t t0a,t0b, t1a,t1b;
  1043. t1a = s32[1*2+0];
  1044. t1b = s32[1*2+1];
  1045. #define RhoPi(PI_LANE, ROT_CONST) \
  1046. t0a = s32[PI_LANE*2+0];\
  1047. t0b = s32[PI_LANE*2+1];\
  1048. if (ROT_CONST & 1) {\
  1049. s32[PI_LANE*2+0] = rotl32(t1b, ROT_CONST/2+1);\
  1050. s32[PI_LANE*2+1] = ROT_CONST == 1 ? t1a : rotl32(t1a, ROT_CONST/2+0);\
  1051. } else {\
  1052. s32[PI_LANE*2+0] = rotl32(t1a, ROT_CONST/2);\
  1053. s32[PI_LANE*2+1] = rotl32(t1b, ROT_CONST/2);\
  1054. }\
  1055. t1a = t0a; t1b = t0b;
  1056. RhoPi(10, 1)
  1057. RhoPi( 7, 3)
  1058. RhoPi(11, 6)
  1059. RhoPi(17,10)
  1060. RhoPi(18,15)
  1061. RhoPi( 3,21)
  1062. RhoPi( 5,28)
  1063. RhoPi(16,36)
  1064. RhoPi( 8,45)
  1065. RhoPi(21,55)
  1066. RhoPi(24, 2)
  1067. RhoPi( 4,14)
  1068. RhoPi(15,27)
  1069. RhoPi(23,41)
  1070. RhoPi(19,56)
  1071. RhoPi(13, 8)
  1072. RhoPi(12,25)
  1073. RhoPi( 2,43)
  1074. RhoPi(20,62)
  1075. RhoPi(14,18)
  1076. RhoPi(22,39)
  1077. RhoPi( 9,61)
  1078. RhoPi( 6,20)
  1079. RhoPi( 1,44)
  1080. #undef RhoPi
  1081. }
  1082. /* Chi */
  1083. for (x = 0; x <= 40;) {
  1084. uint32_t BC0, BC1, BC2, BC3, BC4;
  1085. BC0 = s32[x + 0*2];
  1086. BC1 = s32[x + 1*2];
  1087. BC2 = s32[x + 2*2];
  1088. s32[x + 0*2] = BC0 ^ ((~BC1) & BC2);
  1089. BC3 = s32[x + 3*2];
  1090. s32[x + 1*2] = BC1 ^ ((~BC2) & BC3);
  1091. BC4 = s32[x + 4*2];
  1092. s32[x + 2*2] = BC2 ^ ((~BC3) & BC4);
  1093. s32[x + 3*2] = BC3 ^ ((~BC4) & BC0);
  1094. s32[x + 4*2] = BC4 ^ ((~BC0) & BC1);
  1095. x++;
  1096. BC0 = s32[x + 0*2];
  1097. BC1 = s32[x + 1*2];
  1098. BC2 = s32[x + 2*2];
  1099. s32[x + 0*2] = BC0 ^ ((~BC1) & BC2);
  1100. BC3 = s32[x + 3*2];
  1101. s32[x + 1*2] = BC1 ^ ((~BC2) & BC3);
  1102. BC4 = s32[x + 4*2];
  1103. s32[x + 2*2] = BC2 ^ ((~BC3) & BC4);
  1104. s32[x + 3*2] = BC3 ^ ((~BC4) & BC0);
  1105. s32[x + 4*2] = BC4 ^ ((~BC0) & BC1);
  1106. x += 9;
  1107. }
  1108. /* Iota */
  1109. s32[0] ^= IOTA_CONST_0bits & 1;
  1110. IOTA_CONST_0bits >>= 1;
  1111. s32[1] ^= IOTA_CONST_1[round];
  1112. }
  1113. combine_halves(state);
  1114. #else
  1115. /* Native 64-bit algorithm */
  1116. static const uint16_t IOTA_CONST[NROUNDS] = {
  1117. /* Elements should be 64-bit, but top half is always zero
  1118. * or 0x80000000. We encode 63rd bits in a separate word below.
  1119. * Same is true for 31th bits, which lets us use 16-bit table
  1120. * instead of 64-bit. The speed penalty is lost in the noise.
  1121. */
  1122. 0x0001,
  1123. 0x8082,
  1124. 0x808a,
  1125. 0x8000,
  1126. 0x808b,
  1127. 0x0001,
  1128. 0x8081,
  1129. 0x8009,
  1130. 0x008a,
  1131. 0x0088,
  1132. 0x8009,
  1133. 0x000a,
  1134. 0x808b,
  1135. 0x008b,
  1136. 0x8089,
  1137. 0x8003,
  1138. 0x8002,
  1139. 0x0080,
  1140. 0x800a,
  1141. 0x000a,
  1142. 0x8081,
  1143. 0x8080,
  1144. 0x0001,
  1145. 0x8008,
  1146. };
  1147. /* bit for CONST[0] is in msb: 0011 0011 0000 0111 1101 1101 */
  1148. const uint32_t IOTA_CONST_bit63 = (uint32_t)(0x3307dd00);
  1149. /* bit for CONST[0] is in msb: 0001 0110 0011 1000 0001 1011 */
  1150. const uint32_t IOTA_CONST_bit31 = (uint32_t)(0x16381b00);
  1151. static const uint8_t ROT_CONST[24] = {
  1152. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14,
  1153. 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44,
  1154. };
  1155. static const uint8_t PI_LANE[24] = {
  1156. 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4,
  1157. 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1,
  1158. };
  1159. /*static const uint8_t MOD5[10] = { 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, };*/
  1160. unsigned x;
  1161. unsigned round;
  1162. if (BB_BIG_ENDIAN) {
  1163. for (x = 0; x < 25; x++) {
  1164. state[x] = SWAP_LE64(state[x]);
  1165. }
  1166. }
  1167. for (round = 0; round < NROUNDS; ++round) {
  1168. /* Theta */
  1169. {
  1170. uint64_t BC[10];
  1171. for (x = 0; x < 5; ++x) {
  1172. BC[x + 5] = BC[x] = state[x]
  1173. ^ state[x + 5] ^ state[x + 10]
  1174. ^ state[x + 15] ^ state[x + 20];
  1175. }
  1176. /* Using 2x5 vector above eliminates the need to use
  1177. * BC[MOD5[x+N]] trick below to fetch BC[(x+N) % 5],
  1178. * and the code is a bit _smaller_.
  1179. */
  1180. for (x = 0; x < 5; ++x) {
  1181. uint64_t temp = BC[x + 4] ^ rotl64(BC[x + 1], 1);
  1182. state[x] ^= temp;
  1183. state[x + 5] ^= temp;
  1184. state[x + 10] ^= temp;
  1185. state[x + 15] ^= temp;
  1186. state[x + 20] ^= temp;
  1187. }
  1188. }
  1189. /* Rho Pi */
  1190. if (SHA3_SMALL) {
  1191. uint64_t t1 = state[1];
  1192. for (x = 0; x < 24; ++x) {
  1193. uint64_t t0 = state[PI_LANE[x]];
  1194. state[PI_LANE[x]] = rotl64(t1, ROT_CONST[x]);
  1195. t1 = t0;
  1196. }
  1197. } else {
  1198. /* Especially large benefit for 32-bit arch (75% faster):
  1199. * 64-bit rotations by non-constant usually are SLOW on those.
  1200. * We resort to unrolling here.
  1201. * This optimizes out PI_LANE[] and ROT_CONST[],
  1202. * but generates 300-500 more bytes of code.
  1203. */
  1204. uint64_t t0;
  1205. uint64_t t1 = state[1];
  1206. #define RhoPi_twice(x) \
  1207. t0 = state[PI_LANE[x ]]; \
  1208. state[PI_LANE[x ]] = rotl64(t1, ROT_CONST[x ]); \
  1209. t1 = state[PI_LANE[x+1]]; \
  1210. state[PI_LANE[x+1]] = rotl64(t0, ROT_CONST[x+1]);
  1211. RhoPi_twice(0); RhoPi_twice(2);
  1212. RhoPi_twice(4); RhoPi_twice(6);
  1213. RhoPi_twice(8); RhoPi_twice(10);
  1214. RhoPi_twice(12); RhoPi_twice(14);
  1215. RhoPi_twice(16); RhoPi_twice(18);
  1216. RhoPi_twice(20); RhoPi_twice(22);
  1217. #undef RhoPi_twice
  1218. }
  1219. /* Chi */
  1220. # if LONG_MAX > 0x7fffffff
  1221. for (x = 0; x <= 20; x += 5) {
  1222. uint64_t BC0, BC1, BC2, BC3, BC4;
  1223. BC0 = state[x + 0];
  1224. BC1 = state[x + 1];
  1225. BC2 = state[x + 2];
  1226. state[x + 0] = BC0 ^ ((~BC1) & BC2);
  1227. BC3 = state[x + 3];
  1228. state[x + 1] = BC1 ^ ((~BC2) & BC3);
  1229. BC4 = state[x + 4];
  1230. state[x + 2] = BC2 ^ ((~BC3) & BC4);
  1231. state[x + 3] = BC3 ^ ((~BC4) & BC0);
  1232. state[x + 4] = BC4 ^ ((~BC0) & BC1);
  1233. }
  1234. # else
  1235. /* Reduced register pressure version
  1236. * for register-starved 32-bit arches
  1237. * (i386: -95 bytes, and it is _faster_)
  1238. */
  1239. for (x = 0; x <= 40;) {
  1240. uint32_t BC0, BC1, BC2, BC3, BC4;
  1241. uint32_t *const s32 = (uint32_t*)state;
  1242. # if SHA3_SMALL
  1243. do_half:
  1244. # endif
  1245. BC0 = s32[x + 0*2];
  1246. BC1 = s32[x + 1*2];
  1247. BC2 = s32[x + 2*2];
  1248. s32[x + 0*2] = BC0 ^ ((~BC1) & BC2);
  1249. BC3 = s32[x + 3*2];
  1250. s32[x + 1*2] = BC1 ^ ((~BC2) & BC3);
  1251. BC4 = s32[x + 4*2];
  1252. s32[x + 2*2] = BC2 ^ ((~BC3) & BC4);
  1253. s32[x + 3*2] = BC3 ^ ((~BC4) & BC0);
  1254. s32[x + 4*2] = BC4 ^ ((~BC0) & BC1);
  1255. x++;
  1256. # if SHA3_SMALL
  1257. if (x & 1)
  1258. goto do_half;
  1259. x += 8;
  1260. # else
  1261. BC0 = s32[x + 0*2];
  1262. BC1 = s32[x + 1*2];
  1263. BC2 = s32[x + 2*2];
  1264. s32[x + 0*2] = BC0 ^ ((~BC1) & BC2);
  1265. BC3 = s32[x + 3*2];
  1266. s32[x + 1*2] = BC1 ^ ((~BC2) & BC3);
  1267. BC4 = s32[x + 4*2];
  1268. s32[x + 2*2] = BC2 ^ ((~BC3) & BC4);
  1269. s32[x + 3*2] = BC3 ^ ((~BC4) & BC0);
  1270. s32[x + 4*2] = BC4 ^ ((~BC0) & BC1);
  1271. x += 9;
  1272. # endif
  1273. }
  1274. # endif /* long is 32-bit */
  1275. /* Iota */
  1276. state[0] ^= IOTA_CONST[round]
  1277. | (uint32_t)((IOTA_CONST_bit31 << round) & 0x80000000)
  1278. | (uint64_t)((IOTA_CONST_bit63 << round) & 0x80000000) << 32;
  1279. }
  1280. if (BB_BIG_ENDIAN) {
  1281. for (x = 0; x < 25; x++) {
  1282. state[x] = SWAP_LE64(state[x]);
  1283. }
  1284. }
  1285. #endif
  1286. }
  1287. void FAST_FUNC sha3_begin(sha3_ctx_t *ctx)
  1288. {
  1289. memset(ctx, 0, sizeof(*ctx));
  1290. /* SHA3-512, user can override */
  1291. ctx->input_block_bytes = (1600 - 512*2) / 8; /* 72 bytes */
  1292. }
  1293. void FAST_FUNC sha3_hash(sha3_ctx_t *ctx, const void *buffer, size_t len)
  1294. {
  1295. #if SHA3_SMALL
  1296. const uint8_t *data = buffer;
  1297. unsigned bufpos = ctx->bytes_queued;
  1298. while (1) {
  1299. unsigned remaining = ctx->input_block_bytes - bufpos;
  1300. if (remaining > len)
  1301. remaining = len;
  1302. len -= remaining;
  1303. /* XOR data into buffer */
  1304. while (remaining != 0) {
  1305. uint8_t *buf = (uint8_t*)ctx->state;
  1306. buf[bufpos] ^= *data++;
  1307. bufpos++;
  1308. remaining--;
  1309. }
  1310. /* Clever way to do "if (bufpos != N) break; ... ; bufpos = 0;" */
  1311. bufpos -= ctx->input_block_bytes;
  1312. if (bufpos != 0)
  1313. break;
  1314. /* Buffer is filled up, process it */
  1315. sha3_process_block72(ctx->state);
  1316. /*bufpos = 0; - already is */
  1317. }
  1318. ctx->bytes_queued = bufpos + ctx->input_block_bytes;
  1319. #else
  1320. /* +50 bytes code size, but a bit faster because of long-sized XORs */
  1321. const uint8_t *data = buffer;
  1322. unsigned bufpos = ctx->bytes_queued;
  1323. unsigned iblk_bytes = ctx->input_block_bytes;
  1324. /* If already data in queue, continue queuing first */
  1325. if (bufpos != 0) {
  1326. while (len != 0) {
  1327. uint8_t *buf = (uint8_t*)ctx->state;
  1328. buf[bufpos] ^= *data++;
  1329. len--;
  1330. bufpos++;
  1331. if (bufpos == iblk_bytes) {
  1332. bufpos = 0;
  1333. goto do_block;
  1334. }
  1335. }
  1336. }
  1337. /* Absorb complete blocks */
  1338. while (len >= iblk_bytes) {
  1339. /* XOR data onto beginning of state[].
  1340. * We try to be efficient - operate one word at a time, not byte.
  1341. * Careful wrt unaligned access: can't just use "*(long*)data"!
  1342. */
  1343. unsigned count = iblk_bytes / sizeof(long);
  1344. long *buf = (long*)ctx->state;
  1345. do {
  1346. long v;
  1347. move_from_unaligned_long(v, (long*)data);
  1348. *buf++ ^= v;
  1349. data += sizeof(long);
  1350. } while (--count);
  1351. len -= iblk_bytes;
  1352. do_block:
  1353. sha3_process_block72(ctx->state);
  1354. }
  1355. /* Queue remaining data bytes */
  1356. while (len != 0) {
  1357. uint8_t *buf = (uint8_t*)ctx->state;
  1358. buf[bufpos] ^= *data++;
  1359. bufpos++;
  1360. len--;
  1361. }
  1362. ctx->bytes_queued = bufpos;
  1363. #endif
  1364. }
  1365. unsigned FAST_FUNC sha3_end(sha3_ctx_t *ctx, void *resbuf)
  1366. {
  1367. /* Padding */
  1368. uint8_t *buf = (uint8_t*)ctx->state;
  1369. /*
  1370. * Keccak block padding is: add 1 bit after last bit of input,
  1371. * then add zero bits until the end of block, and add the last 1 bit
  1372. * (the last bit in the block) - the "10*1" pattern.
  1373. * SHA3 standard appends additional two bits, 01, before that padding:
  1374. *
  1375. * SHA3-224(M) = KECCAK[448](M||01, 224)
  1376. * SHA3-256(M) = KECCAK[512](M||01, 256)
  1377. * SHA3-384(M) = KECCAK[768](M||01, 384)
  1378. * SHA3-512(M) = KECCAK[1024](M||01, 512)
  1379. * (M is the input, || is bit concatenation)
  1380. *
  1381. * The 6 below contains 01 "SHA3" bits and the first 1 "Keccak" bit:
  1382. */
  1383. buf[ctx->bytes_queued] ^= 6; /* bit pattern 00000110 */
  1384. buf[ctx->input_block_bytes - 1] ^= 0x80;
  1385. sha3_process_block72(ctx->state);
  1386. /* Output */
  1387. memcpy(resbuf, ctx->state, 64);
  1388. return 64;
  1389. }