RIPEMD160.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427
  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 "config.h"
  46. #if HAVE_STDINT_H
  47. # include <stdint.h>
  48. #elif defined(__sun) || defined(__sun__)
  49. # include <sys/inttypes.h>
  50. #else
  51. # error "stdint.h not found"
  52. #endif
  53. #include <assert.h>
  54. #include <string.h>
  55. #include "Python.h"
  56. #include "pycrypto_compat.h"
  57. #define RIPEMD160_DIGEST_SIZE 20
  58. #define BLOCK_SIZE 64
  59. #define RIPEMD160_MAGIC 0x9f19dd68u
  60. typedef struct {
  61. uint32_t magic;
  62. uint32_t h[5]; /* The current hash state */
  63. uint64_t length; /* Total number of _bits_ (not bytes) added to the
  64. hash. This includes bits that have been buffered
  65. but not not fed through the compression function yet. */
  66. union {
  67. uint32_t w[16];
  68. uint8_t b[64];
  69. } buf;
  70. uint8_t bufpos; /* number of bytes currently in the buffer */
  71. } ripemd160_state;
  72. /* cyclic left-shift the 32-bit word n left by s bits */
  73. #define ROL(s, n) (((n) << (s)) | ((n) >> (32-(s))))
  74. /* Initial values for the chaining variables.
  75. * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */
  76. static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u };
  77. /* Ordering of message words. Based on the permutations rho(i) and pi(i), defined as follows:
  78. *
  79. * rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i] 0 <= i <= 15
  80. *
  81. * pi(i) := 9*i + 5 (mod 16)
  82. *
  83. * Line | Round 1 | Round 2 | Round 3 | Round 4 | Round 5
  84. * -------+-----------+-----------+-----------+-----------+-----------
  85. * left | id | rho | rho^2 | rho^3 | rho^4
  86. * right | pi | rho pi | rho^2 pi | rho^3 pi | rho^4 pi
  87. */
  88. /* Left line */
  89. static const uint8_t RL[5][16] = {
  90. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, /* Round 1: id */
  91. { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }, /* Round 2: rho */
  92. { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 }, /* Round 3: rho^2 */
  93. { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 }, /* Round 4: rho^3 */
  94. { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 } /* Round 5: rho^4 */
  95. };
  96. /* Right line */
  97. static const uint8_t RR[5][16] = {
  98. { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 }, /* Round 1: pi */
  99. { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 }, /* Round 2: rho pi */
  100. { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 }, /* Round 3: rho^2 pi */
  101. { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 }, /* Round 4: rho^3 pi */
  102. { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 } /* Round 5: rho^4 pi */
  103. };
  104. /*
  105. * Shifts - Since we don't actually re-order the message words according to
  106. * the permutations above (we could, but it would be slower), these tables
  107. * come with the permutations pre-applied.
  108. */
  109. /* Shifts, left line */
  110. static const uint8_t SL[5][16] = {
  111. { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */
  112. { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */
  113. { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */
  114. { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */
  115. { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 } /* Round 5 */
  116. };
  117. /* Shifts, right line */
  118. static const uint8_t SR[5][16] = {
  119. { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */
  120. { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */
  121. { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */
  122. { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */
  123. { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 } /* Round 5 */
  124. };
  125. /* Boolean functions */
  126. #define F1(x, y, z) ((x) ^ (y) ^ (z))
  127. #define F2(x, y, z) (((x) & (y)) | (~(x) & (z)))
  128. #define F3(x, y, z) (((x) | ~(y)) ^ (z))
  129. #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z)))
  130. #define F5(x, y, z) ((x) ^ ((y) | ~(z)))
  131. /* Round constants, left line */
  132. static const uint32_t KL[5] = {
  133. 0x00000000u, /* Round 1: 0 */
  134. 0x5A827999u, /* Round 2: floor(2**30 * sqrt(2)) */
  135. 0x6ED9EBA1u, /* Round 3: floor(2**30 * sqrt(3)) */
  136. 0x8F1BBCDCu, /* Round 4: floor(2**30 * sqrt(5)) */
  137. 0xA953FD4Eu /* Round 5: floor(2**30 * sqrt(7)) */
  138. };
  139. /* Round constants, right line */
  140. static const uint32_t KR[5] = {
  141. 0x50A28BE6u, /* Round 1: floor(2**30 * cubert(2)) */
  142. 0x5C4DD124u, /* Round 2: floor(2**30 * cubert(3)) */
  143. 0x6D703EF3u, /* Round 3: floor(2**30 * cubert(5)) */
  144. 0x7A6D76E9u, /* Round 4: floor(2**30 * cubert(7)) */
  145. 0x00000000u /* Round 5: 0 */
  146. };
  147. static void ripemd160_init(ripemd160_state *self)
  148. {
  149. memcpy(self->h, initial_h, RIPEMD160_DIGEST_SIZE);
  150. memset(&self->buf, 0, sizeof(self->buf));
  151. self->length = 0;
  152. self->bufpos = 0;
  153. self->magic = RIPEMD160_MAGIC;
  154. }
  155. /* NB: This is not currently called in the hash object's destructor. */
  156. static void ripemd160_wipe(ripemd160_state *self)
  157. {
  158. memset(self, 0, sizeof(ripemd160_state));
  159. self->magic = 0;
  160. }
  161. static inline void byteswap32(uint32_t *v)
  162. {
  163. union { uint32_t w; uint8_t b[4]; } x, y;
  164. x.w = *v;
  165. y.b[0] = x.b[3];
  166. y.b[1] = x.b[2];
  167. y.b[2] = x.b[1];
  168. y.b[3] = x.b[0];
  169. *v = y.w;
  170. /* Wipe temporary variables */
  171. x.w = y.w = 0;
  172. }
  173. static inline void byteswap_digest(uint32_t *p)
  174. {
  175. unsigned int i;
  176. for (i = 0; i < 4; i++) {
  177. byteswap32(p++);
  178. byteswap32(p++);
  179. byteswap32(p++);
  180. byteswap32(p++);
  181. }
  182. }
  183. /* The RIPEMD160 compression function. Operates on self->buf */
  184. static void ripemd160_compress(ripemd160_state *self)
  185. {
  186. uint8_t w, round;
  187. uint32_t T;
  188. uint32_t AL, BL, CL, DL, EL; /* left line */
  189. uint32_t AR, BR, CR, DR, ER; /* right line */
  190. /* Sanity check */
  191. assert(self->magic == RIPEMD160_MAGIC);
  192. assert(self->bufpos == 64);
  193. if (self->magic != RIPEMD160_MAGIC || self->bufpos != 64) {
  194. ripemd160_wipe(self);
  195. return; /* error */
  196. }
  197. /* Byte-swap the buffer if we're on a big-endian machine */
  198. #ifdef PCT_BIG_ENDIAN
  199. byteswap_digest(self->buf.w);
  200. #endif
  201. /* Load the left and right lines with the initial state */
  202. AL = AR = self->h[0];
  203. BL = BR = self->h[1];
  204. CL = CR = self->h[2];
  205. DL = DR = self->h[3];
  206. EL = ER = self->h[4];
  207. /* Round 1 */
  208. round = 0;
  209. for (w = 0; w < 16; w++) { /* left line */
  210. T = ROL(SL[round][w], AL + F1(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  211. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  212. }
  213. for (w = 0; w < 16; w++) { /* right line */
  214. T = ROL(SR[round][w], AR + F5(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  215. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  216. }
  217. /* Round 2 */
  218. round++;
  219. for (w = 0; w < 16; w++) { /* left line */
  220. T = ROL(SL[round][w], AL + F2(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  221. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  222. }
  223. for (w = 0; w < 16; w++) { /* right line */
  224. T = ROL(SR[round][w], AR + F4(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  225. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  226. }
  227. /* Round 3 */
  228. round++;
  229. for (w = 0; w < 16; w++) { /* left line */
  230. T = ROL(SL[round][w], AL + F3(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  231. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  232. }
  233. for (w = 0; w < 16; w++) { /* right line */
  234. T = ROL(SR[round][w], AR + F3(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  235. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  236. }
  237. /* Round 4 */
  238. round++;
  239. for (w = 0; w < 16; w++) { /* left line */
  240. T = ROL(SL[round][w], AL + F4(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  241. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  242. }
  243. for (w = 0; w < 16; w++) { /* right line */
  244. T = ROL(SR[round][w], AR + F2(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  245. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  246. }
  247. /* Round 5 */
  248. round++;
  249. for (w = 0; w < 16; w++) { /* left line */
  250. T = ROL(SL[round][w], AL + F5(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
  251. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  252. }
  253. for (w = 0; w < 16; w++) { /* right line */
  254. T = ROL(SR[round][w], AR + F1(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
  255. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  256. }
  257. /* Final mixing stage */
  258. T = self->h[1] + CL + DR;
  259. self->h[1] = self->h[2] + DL + ER;
  260. self->h[2] = self->h[3] + EL + AR;
  261. self->h[3] = self->h[4] + AL + BR;
  262. self->h[4] = self->h[0] + BL + CR;
  263. self->h[0] = T;
  264. /* Clear the buffer and wipe the temporary variables */
  265. T = AL = BL = CL = DL = EL = AR = BR = CR = DR = ER = 0;
  266. memset(&self->buf, 0, sizeof(self->buf));
  267. self->bufpos = 0;
  268. }
  269. static void ripemd160_update(ripemd160_state *self, const unsigned char *p, int length)
  270. {
  271. unsigned int bytes_needed;
  272. /* Some assertions */
  273. assert(self->magic == RIPEMD160_MAGIC);
  274. assert(p != NULL && length >= 0);
  275. /* NDEBUG is probably defined, so check for invalid inputs explicitly. */
  276. if (self->magic != RIPEMD160_MAGIC || p == NULL || length < 0) {
  277. /* error */
  278. ripemd160_wipe(self);
  279. return;
  280. }
  281. /* We never leave a full buffer */
  282. assert(self->bufpos < 64);
  283. while (length > 0) {
  284. /* Figure out how many bytes we need to fill the internal buffer. */
  285. bytes_needed = 64 - self->bufpos;
  286. if ((unsigned int) length >= bytes_needed) {
  287. /* We have enough bytes, so copy them into the internal buffer and run
  288. * the compression function. */
  289. memcpy(&self->buf.b[self->bufpos], p, bytes_needed);
  290. self->bufpos += bytes_needed;
  291. self->length += bytes_needed << 3; /* length is in bits */
  292. p += bytes_needed;
  293. ripemd160_compress(self);
  294. length -= bytes_needed;
  295. continue;
  296. }
  297. /* We do not have enough bytes to fill the internal buffer.
  298. * Copy what's there and return. */
  299. memcpy(&self->buf.b[self->bufpos], p, length);
  300. self->bufpos += length;
  301. self->length += length << 3; /* length is in bits */
  302. return;
  303. }
  304. }
  305. static void ripemd160_copy(const ripemd160_state *source, ripemd160_state *dest)
  306. {
  307. memcpy(dest, source, sizeof(ripemd160_state));
  308. }
  309. static int ripemd160_digest(const ripemd160_state *self, unsigned char *out)
  310. {
  311. ripemd160_state tmp;
  312. assert(self->magic == RIPEMD160_MAGIC);
  313. assert(out != NULL);
  314. if (self->magic != RIPEMD160_MAGIC || out == NULL) {
  315. return 0;
  316. }
  317. ripemd160_copy(self, &tmp);
  318. /* Append the padding */
  319. tmp.buf.b[tmp.bufpos++] = 0x80;
  320. if (tmp.bufpos > 56) {
  321. tmp.bufpos = 64;
  322. ripemd160_compress(&tmp);
  323. }
  324. /* Append the length */
  325. tmp.buf.w[14] = (uint32_t) (tmp.length & 0xFFFFffffu);
  326. tmp.buf.w[15] = (uint32_t) ((tmp.length >> 32) & 0xFFFFffffu);
  327. #ifdef PCT_BIG_ENDIAN
  328. byteswap32(&tmp.buf.w[14]);
  329. byteswap32(&tmp.buf.w[15]);
  330. #endif
  331. tmp.bufpos = 64;
  332. ripemd160_compress(&tmp);
  333. /* Copy the final state into the output buffer */
  334. #ifdef PCT_BIG_ENDIAN
  335. byteswap_digest(tmp.h);
  336. #endif
  337. memcpy(out, &tmp.h, RIPEMD160_DIGEST_SIZE);
  338. if (tmp.magic == RIPEMD160_MAGIC) {
  339. /* success */
  340. ripemd160_wipe(&tmp);
  341. return 1;
  342. } else {
  343. /* error */
  344. ripemd160_wipe(&tmp);
  345. memset(out, 0, RIPEMD160_DIGEST_SIZE);
  346. return 0;
  347. }
  348. }
  349. /* Template definitions */
  350. #define MODULE_NAME _RIPEMD160
  351. #define DIGEST_SIZE RIPEMD160_DIGEST_SIZE
  352. #define hash_state ripemd160_state
  353. #define hash_init ripemd160_init
  354. #define hash_update ripemd160_update
  355. #define hash_copy ripemd160_copy
  356. static PyObject *hash_digest(hash_state *self)
  357. {
  358. char buf[DIGEST_SIZE];
  359. PyObject *retval;
  360. if (ripemd160_digest(self, (unsigned char *) buf)) {
  361. retval = PyBytes_FromStringAndSize(buf, DIGEST_SIZE);
  362. } else {
  363. PyErr_SetString(PyExc_RuntimeError, "Internal error occurred while executing ripemd160_digest");
  364. retval = NULL;
  365. }
  366. memset(buf, 0, DIGEST_SIZE);
  367. return retval;
  368. }
  369. #include "hash_template.c"
  370. /* vim:set ts=4 sw=4 sts=4 expandtab: */