RIPEMD160.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372
  1. /*
  2. *
  3. * RIPEMD160.c : RIPEMD-160 implementation
  4. *
  5. * Written in 2008 by Dwayne C. Litzenberger <dlitz@dlitz.net>
  6. *
  7. * ===================================================================
  8. * The contents of this file are dedicated to the public domain. To
  9. * the extent that dedication to the public domain is not available,
  10. * everyone is granted a worldwide, perpetual, royalty-free,
  11. * non-exclusive license to exercise all rights associated with the
  12. * contents of this file for any purpose whatsoever.
  13. * No rights are reserved.
  14. *
  15. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16. * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17. * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18. * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19. * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20. * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22. * SOFTWARE.
  23. * ===================================================================
  24. *
  25. * Country of origin: Canada
  26. *
  27. * This implementation (written in C) is based on an implementation the author
  28. * wrote in Python.
  29. *
  30. * This implementation was written with reference to the RIPEMD-160
  31. * specification, which is available at:
  32. * http://homes.esat.kuleuven.be/~cosicart/pdf/AB-9601/
  33. *
  34. * It is also documented in the _Handbook of Applied Cryptography_, as
  35. * Algorithm 9.55. It's on page 30 of the following PDF file:
  36. * http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf
  37. *
  38. * The RIPEMD-160 specification doesn't really tell us how to do padding, but
  39. * since RIPEMD-160 is inspired by MD4, you can use the padding algorithm from
  40. * RFC 1320.
  41. *
  42. * According to http://www.users.zetnet.co.uk/hopwood/crypto/scan/md.html:
  43. * "RIPEMD-160 is big-bit-endian, little-byte-endian, and left-justified."
  44. */
  45. #include "pycrypto_common.h"
  46. FAKE_INIT(RIPEMD160)
  47. #define RIPEMD160_DIGEST_SIZE 20
  48. typedef struct {
  49. uint32_t h[5]; /* The current hash state */
  50. uint64_t length; /* Total number of _bits_ (not bytes) added to the
  51. hash. This includes bits that have been buffered
  52. but not not fed through the compression function yet. */
  53. union {
  54. uint32_t w[16];
  55. uint8_t b[64];
  56. } buf;
  57. uint8_t bufpos; /* number of bytes currently in the buffer */
  58. } hash_state;
  59. /* cyclic left-shift the 32-bit word n left by s bits */
  60. #define ROL(s, n) (((n) << (s)) | ((n) >> (32-(s))))
  61. /* Ordering of message words. Based on the permutations rho(i) and pi(i), defined as follows:
  62. *
  63. * rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i] 0 <= i <= 15
  64. *
  65. * pi(i) := 9*i + 5 (mod 16)
  66. *
  67. * Line | Round 1 | Round 2 | Round 3 | Round 4 | Round 5
  68. * -------+-----------+-----------+-----------+-----------+-----------
  69. * left | id | rho | rho^2 | rho^3 | rho^4
  70. * right | pi | rho pi | rho^2 pi | rho^3 pi | rho^4 pi
  71. */
  72. /* Left line */
  73. static const uint8_t RL[5][16] = {
  74. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, /* Round 1: id */
  75. { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }, /* Round 2: rho */
  76. { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 }, /* Round 3: rho^2 */
  77. { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 }, /* Round 4: rho^3 */
  78. { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 } /* Round 5: rho^4 */
  79. };
  80. /* Right line */
  81. static const uint8_t RR[5][16] = {
  82. { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 }, /* Round 1: pi */
  83. { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 }, /* Round 2: rho pi */
  84. { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 }, /* Round 3: rho^2 pi */
  85. { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 }, /* Round 4: rho^3 pi */
  86. { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 } /* Round 5: rho^4 pi */
  87. };
  88. /*
  89. * Shifts - Since we don't actually re-order the message words according to
  90. * the permutations above (we could, but it would be slower), these tables
  91. * come with the permutations pre-applied.
  92. */
  93. /* Shifts, left line */
  94. static const uint8_t SL[5][16] = {
  95. { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */
  96. { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */
  97. { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */
  98. { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */
  99. { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 } /* Round 5 */
  100. };
  101. /* Shifts, right line */
  102. static const uint8_t SR[5][16] = {
  103. { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */
  104. { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */
  105. { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */
  106. { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */
  107. { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 } /* Round 5 */
  108. };
  109. /* Boolean functions */
  110. #define F1(x, y, z) ((x) ^ (y) ^ (z))
  111. #define F2(x, y, z) (((x) & (y)) | (~(x) & (z)))
  112. #define F3(x, y, z) (((x) | ~(y)) ^ (z))
  113. #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z)))
  114. #define F5(x, y, z) ((x) ^ ((y) | ~(z)))
  115. /* Round constants, left line */
  116. static const uint32_t KL[5] = {
  117. 0x00000000u, /* Round 1: 0 */
  118. 0x5A827999u, /* Round 2: floor(2**30 * sqrt(2)) */
  119. 0x6ED9EBA1u, /* Round 3: floor(2**30 * sqrt(3)) */
  120. 0x8F1BBCDCu, /* Round 4: floor(2**30 * sqrt(5)) */
  121. 0xA953FD4Eu /* Round 5: floor(2**30 * sqrt(7)) */
  122. };
  123. /* Round constants, right line */
  124. static const uint32_t KR[5] = {
  125. 0x50A28BE6u, /* Round 1: floor(2**30 * cubert(2)) */
  126. 0x5C4DD124u, /* Round 2: floor(2**30 * cubert(3)) */
  127. 0x6D703EF3u, /* Round 3: floor(2**30 * cubert(5)) */
  128. 0x7A6D76E9u, /* Round 4: floor(2**30 * cubert(7)) */
  129. 0x00000000u /* Round 5: 0 */
  130. };
  131. EXPORT_SYM int ripemd160_init(hash_state **ripemd160State)
  132. {
  133. hash_state *hs;
  134. /* Initial values for the chaining variables.
  135. * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */
  136. static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u };
  137. if (NULL == ripemd160State) {
  138. return ERR_NULL;
  139. }
  140. *ripemd160State = hs = (hash_state*) calloc(1, sizeof(hash_state));
  141. if (NULL == hs)
  142. return ERR_MEMORY;
  143. memcpy(hs->h, initial_h, RIPEMD160_DIGEST_SIZE);
  144. return 0;
  145. }
  146. EXPORT_SYM int ripemd160_destroy(hash_state *hs)
  147. {
  148. free(hs);
  149. return 0;
  150. }
  151. static int little_endian(void) {
  152. int test = 1;
  153. return *((uint8_t*)&test) == 1;
  154. }
  155. static void byteswap32(uint32_t *v)
  156. {
  157. union { uint32_t w; uint8_t b[4]; } x, y;
  158. if (little_endian())
  159. return;
  160. x.w = *v;
  161. y.b[0] = x.b[3];
  162. y.b[1] = x.b[2];
  163. y.b[2] = x.b[1];
  164. y.b[3] = x.b[0];
  165. *v = y.w;
  166. /* Wipe temporary variables */
  167. x.w = y.w = 0;
  168. }
  169. static void byteswap_digest(uint32_t *p)
  170. {
  171. unsigned int i;
  172. if (little_endian())
  173. return;
  174. for (i = 0; i < 4; i++) {
  175. byteswap32(p++);
  176. byteswap32(p++);
  177. byteswap32(p++);
  178. byteswap32(p++);
  179. }
  180. }
  181. /* The RIPEMD160 compression function. Operates on self->buf */
  182. static void ripemd160_compress(hash_state *self)
  183. {
  184. uint8_t w, round;
  185. uint32_t T;
  186. uint32_t AL, BL, CL, DL, EL; /* left line */
  187. uint32_t AR, BR, CR, DR, ER; /* right line */
  188. /* Byte-swap the buffer if we're on a big-endian machine */
  189. byteswap_digest(self->buf.w);
  190. /* Load the left and right lines with the initial state */
  191. AL = AR = self->h[0];
  192. BL = BR = self->h[1];
  193. CL = CR = self->h[2];
  194. DL = DR = self->h[3];
  195. EL = ER = self->h[4];
  196. /* Round 1 */
  197. round = 0;
  198. for (w = 0; w < 16; w++) { /* left line */
  199. T = ROL(SL[round][w], AL + F1(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  200. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  201. }
  202. for (w = 0; w < 16; w++) { /* right line */
  203. T = ROL(SR[round][w], AR + F5(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  204. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  205. }
  206. /* Round 2 */
  207. round++;
  208. for (w = 0; w < 16; w++) { /* left line */
  209. T = ROL(SL[round][w], AL + F2(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  210. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  211. }
  212. for (w = 0; w < 16; w++) { /* right line */
  213. T = ROL(SR[round][w], AR + F4(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  214. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  215. }
  216. /* Round 3 */
  217. round++;
  218. for (w = 0; w < 16; w++) { /* left line */
  219. T = ROL(SL[round][w], AL + F3(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  220. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  221. }
  222. for (w = 0; w < 16; w++) { /* right line */
  223. T = ROL(SR[round][w], AR + F3(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  224. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  225. }
  226. /* Round 4 */
  227. round++;
  228. for (w = 0; w < 16; w++) { /* left line */
  229. T = ROL(SL[round][w], AL + F4(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  230. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  231. }
  232. for (w = 0; w < 16; w++) { /* right line */
  233. T = ROL(SR[round][w], AR + F2(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  234. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  235. }
  236. /* Round 5 */
  237. round++;
  238. for (w = 0; w < 16; w++) { /* left line */
  239. T = ROL(SL[round][w], AL + F5(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  240. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  241. }
  242. for (w = 0; w < 16; w++) { /* right line */
  243. T = ROL(SR[round][w], AR + F1(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  244. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  245. }
  246. /* Final mixing stage */
  247. T = self->h[1] + CL + DR;
  248. self->h[1] = self->h[2] + DL + ER;
  249. self->h[2] = self->h[3] + EL + AR;
  250. self->h[3] = self->h[4] + AL + BR;
  251. self->h[4] = self->h[0] + BL + CR;
  252. self->h[0] = T;
  253. /* Clear the buffer and wipe the temporary variables */
  254. T = AL = BL = CL = DL = EL = AR = BR = CR = DR = ER = 0;
  255. memset(&self->buf, 0, sizeof(self->buf));
  256. self->bufpos = 0;
  257. }
  258. EXPORT_SYM int ripemd160_update(hash_state *hs, const uint8_t *buf, size_t len)
  259. {
  260. unsigned int bytes_needed;
  261. if (NULL==hs || NULL==buf)
  262. return ERR_NULL;
  263. while (len > 0) {
  264. /* Figure out how many bytes we need to fill the internal buffer. */
  265. bytes_needed = 64 - hs->bufpos;
  266. if (len >= bytes_needed) {
  267. /* We have enough bytes, so copy them into the internal buffer and run
  268. * the compression function. */
  269. memcpy(&hs->buf.b[hs->bufpos], buf, bytes_needed);
  270. hs->bufpos += bytes_needed;
  271. hs->length += bytes_needed * 8; /* length is in bits */
  272. buf += bytes_needed;
  273. ripemd160_compress(hs);
  274. len -= bytes_needed;
  275. continue;
  276. }
  277. /* We do not have enough bytes to fill the internal buffer.
  278. * Copy what's there and return. */
  279. memcpy(&hs->buf.b[hs->bufpos], buf, len);
  280. hs->bufpos += len;
  281. hs->length += len * 8; /* length is in bits */
  282. return 0;
  283. }
  284. return 0;
  285. }
  286. EXPORT_SYM int ripemd160_copy(const hash_state *src, hash_state *dst)
  287. {
  288. if (NULL == src || NULL == dst) {
  289. return ERR_NULL;
  290. }
  291. *dst = *src;
  292. return 0;
  293. }
  294. EXPORT_SYM int ripemd160_digest(const hash_state *hs, uint8_t digest[RIPEMD160_DIGEST_SIZE])
  295. {
  296. hash_state tmp;
  297. if (NULL==hs || digest==NULL)
  298. return ERR_NULL;
  299. tmp = *hs;
  300. /* Append the padding */
  301. tmp.buf.b[tmp.bufpos++] = 0x80;
  302. if (tmp.bufpos > 56) {
  303. tmp.bufpos = 64;
  304. ripemd160_compress(&tmp);
  305. }
  306. /* Append the length */
  307. tmp.buf.w[14] = (uint32_t) (tmp.length & 0xFFFFffffu);
  308. tmp.buf.w[15] = (uint32_t) ((tmp.length >> 32) & 0xFFFFffffu);
  309. byteswap32(&tmp.buf.w[14]);
  310. byteswap32(&tmp.buf.w[15]);
  311. tmp.bufpos = 64;
  312. ripemd160_compress(&tmp);
  313. /* Copy the final state into the output buffer */
  314. byteswap_digest(tmp.h);
  315. memcpy(digest, &tmp.h, RIPEMD160_DIGEST_SIZE);
  316. return 0;
  317. }