RIPEMD160.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332
  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 "common.h"
  46. #include "endianess.h"
  47. FAKE_INIT(RIPEMD160)
  48. #define RIPEMD160_DIGEST_SIZE 20
  49. typedef struct {
  50. uint32_t h[5]; /* The current hash state */
  51. uint64_t length; /* Total number of _bits_ (not bytes) added to the
  52. hash. This includes bits that have been buffered
  53. but not not fed through the compression function yet. */
  54. uint8_t buf[64];
  55. unsigned bufpos; /* number of bytes currently in the buffer */
  56. } hash_state;
  57. /* cyclic left-shift the 32-bit word n left by s bits */
  58. #define ROL(s, n) (((n) << (s)) | ((n) >> (32-(s))))
  59. /* Ordering of message words. Based on the permutations rho(i) and pi(i), defined as follows:
  60. *
  61. * rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i] 0 <= i <= 15
  62. *
  63. * pi(i) := 9*i + 5 (mod 16)
  64. *
  65. * Line | Round 1 | Round 2 | Round 3 | Round 4 | Round 5
  66. * -------+-----------+-----------+-----------+-----------+-----------
  67. * left | id | rho | rho^2 | rho^3 | rho^4
  68. * right | pi | rho pi | rho^2 pi | rho^3 pi | rho^4 pi
  69. */
  70. /* Left line */
  71. static const uint8_t RL[5][16] = {
  72. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, /* Round 1: id */
  73. { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }, /* Round 2: rho */
  74. { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 }, /* Round 3: rho^2 */
  75. { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 }, /* Round 4: rho^3 */
  76. { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 } /* Round 5: rho^4 */
  77. };
  78. /* Right line */
  79. static const uint8_t RR[5][16] = {
  80. { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 }, /* Round 1: pi */
  81. { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 }, /* Round 2: rho pi */
  82. { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 }, /* Round 3: rho^2 pi */
  83. { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 }, /* Round 4: rho^3 pi */
  84. { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 } /* Round 5: rho^4 pi */
  85. };
  86. /*
  87. * Shifts - Since we don't actually re-order the message words according to
  88. * the permutations above (we could, but it would be slower), these tables
  89. * come with the permutations pre-applied.
  90. */
  91. /* Shifts, left line */
  92. static const uint8_t SL[5][16] = {
  93. { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */
  94. { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */
  95. { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */
  96. { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */
  97. { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 } /* Round 5 */
  98. };
  99. /* Shifts, right line */
  100. static const uint8_t SR[5][16] = {
  101. { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */
  102. { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */
  103. { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */
  104. { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */
  105. { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 } /* Round 5 */
  106. };
  107. /* Boolean functions */
  108. #define F1(x, y, z) ((x) ^ (y) ^ (z))
  109. #define F2(x, y, z) (((x) & (y)) | (~(x) & (z)))
  110. #define F3(x, y, z) (((x) | ~(y)) ^ (z))
  111. #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z)))
  112. #define F5(x, y, z) ((x) ^ ((y) | ~(z)))
  113. /* Round constants, left line */
  114. static const uint32_t KL[5] = {
  115. 0x00000000u, /* Round 1: 0 */
  116. 0x5A827999u, /* Round 2: floor(2**30 * sqrt(2)) */
  117. 0x6ED9EBA1u, /* Round 3: floor(2**30 * sqrt(3)) */
  118. 0x8F1BBCDCu, /* Round 4: floor(2**30 * sqrt(5)) */
  119. 0xA953FD4Eu /* Round 5: floor(2**30 * sqrt(7)) */
  120. };
  121. /* Round constants, right line */
  122. static const uint32_t KR[5] = {
  123. 0x50A28BE6u, /* Round 1: floor(2**30 * cubert(2)) */
  124. 0x5C4DD124u, /* Round 2: floor(2**30 * cubert(3)) */
  125. 0x6D703EF3u, /* Round 3: floor(2**30 * cubert(5)) */
  126. 0x7A6D76E9u, /* Round 4: floor(2**30 * cubert(7)) */
  127. 0x00000000u /* Round 5: 0 */
  128. };
  129. EXPORT_SYM int ripemd160_init(hash_state **ripemd160State)
  130. {
  131. hash_state *hs;
  132. /* Initial values for the chaining variables.
  133. * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */
  134. static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u };
  135. if (NULL == ripemd160State) {
  136. return ERR_NULL;
  137. }
  138. *ripemd160State = hs = (hash_state*) calloc(1, sizeof(hash_state));
  139. if (NULL == hs)
  140. return ERR_MEMORY;
  141. memcpy(hs->h, initial_h, RIPEMD160_DIGEST_SIZE);
  142. return 0;
  143. }
  144. EXPORT_SYM int ripemd160_destroy(hash_state *hs)
  145. {
  146. free(hs);
  147. return 0;
  148. }
  149. /* The RIPEMD160 compression function. Operates on self->buf */
  150. static void ripemd160_compress(hash_state *self)
  151. {
  152. unsigned w, round;
  153. uint32_t T;
  154. uint32_t AL, BL, CL, DL, EL; /* left line */
  155. uint32_t AR, BR, CR, DR, ER; /* right line */
  156. uint32_t bufw[16];
  157. for (w=0; w<16; w++)
  158. bufw[w] = LOAD_U32_LITTLE(&self->buf[w*4]);
  159. /* Load the left and right lines with the initial state */
  160. AL = AR = self->h[0];
  161. BL = BR = self->h[1];
  162. CL = CR = self->h[2];
  163. DL = DR = self->h[3];
  164. EL = ER = self->h[4];
  165. /* Round 1 */
  166. round = 0;
  167. for (w = 0; w < 16; w++) { /* left line */
  168. T = ROL(SL[round][w], AL + F1(BL, CL, DL) + bufw[RL[round][w]] + KL[round]) + EL;
  169. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  170. }
  171. for (w = 0; w < 16; w++) { /* right line */
  172. T = ROL(SR[round][w], AR + F5(BR, CR, DR) + bufw[RR[round][w]] + KR[round]) + ER;
  173. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  174. }
  175. /* Round 2 */
  176. round++;
  177. for (w = 0; w < 16; w++) { /* left line */
  178. T = ROL(SL[round][w], AL + F2(BL, CL, DL) + bufw[RL[round][w]] + KL[round]) + EL;
  179. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  180. }
  181. for (w = 0; w < 16; w++) { /* right line */
  182. T = ROL(SR[round][w], AR + F4(BR, CR, DR) + bufw[RR[round][w]] + KR[round]) + ER;
  183. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  184. }
  185. /* Round 3 */
  186. round++;
  187. for (w = 0; w < 16; w++) { /* left line */
  188. T = ROL(SL[round][w], AL + F3(BL, CL, DL) + bufw[RL[round][w]] + KL[round]) + EL;
  189. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  190. }
  191. for (w = 0; w < 16; w++) { /* right line */
  192. T = ROL(SR[round][w], AR + F3(BR, CR, DR) + bufw[RR[round][w]] + KR[round]) + ER;
  193. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  194. }
  195. /* Round 4 */
  196. round++;
  197. for (w = 0; w < 16; w++) { /* left line */
  198. T = ROL(SL[round][w], AL + F4(BL, CL, DL) + bufw[RL[round][w]] + KL[round]) + EL;
  199. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  200. }
  201. for (w = 0; w < 16; w++) { /* right line */
  202. T = ROL(SR[round][w], AR + F2(BR, CR, DR) + bufw[RR[round][w]] + KR[round]) + ER;
  203. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  204. }
  205. /* Round 5 */
  206. round++;
  207. for (w = 0; w < 16; w++) { /* left line */
  208. T = ROL(SL[round][w], AL + F5(BL, CL, DL) + bufw[RL[round][w]] + KL[round]) + EL;
  209. AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
  210. }
  211. for (w = 0; w < 16; w++) { /* right line */
  212. T = ROL(SR[round][w], AR + F1(BR, CR, DR) + bufw[RR[round][w]] + KR[round]) + ER;
  213. AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
  214. }
  215. /* Final mixing stage */
  216. T = self->h[1] + CL + DR;
  217. self->h[1] = self->h[2] + DL + ER;
  218. self->h[2] = self->h[3] + EL + AR;
  219. self->h[3] = self->h[4] + AL + BR;
  220. self->h[4] = self->h[0] + BL + CR;
  221. self->h[0] = T;
  222. /* Clear the buffer and wipe the temporary variables */
  223. T = AL = BL = CL = DL = EL = AR = BR = CR = DR = ER = 0;
  224. memset(&self->buf, 0, sizeof(self->buf));
  225. self->bufpos = 0;
  226. }
  227. EXPORT_SYM int ripemd160_update(hash_state *hs, const uint8_t *in, size_t len)
  228. {
  229. unsigned int bytes_needed;
  230. if (NULL==hs || NULL==in)
  231. return ERR_NULL;
  232. while (len > 0) {
  233. /* Figure out how many bytes we need to fill the internal buffer. */
  234. bytes_needed = 64 - hs->bufpos;
  235. if (len >= bytes_needed) {
  236. /* We have enough bytes, so copy them into the internal buffer and run
  237. * the compression function. */
  238. memcpy(&hs->buf[hs->bufpos], in, bytes_needed);
  239. hs->bufpos += bytes_needed;
  240. hs->length += bytes_needed * 8; /* length is in bits */
  241. in += bytes_needed;
  242. ripemd160_compress(hs);
  243. len -= bytes_needed;
  244. continue;
  245. }
  246. /* We do not have enough bytes to fill the internal buffer.
  247. * Copy what's there and return. */
  248. memcpy(&hs->buf[hs->bufpos], in, len);
  249. hs->bufpos += (unsigned)len;
  250. hs->length += (unsigned)(len * 8); /* length is in bits */
  251. return 0;
  252. }
  253. return 0;
  254. }
  255. EXPORT_SYM int ripemd160_copy(const hash_state *src, hash_state *dst)
  256. {
  257. if (NULL == src || NULL == dst) {
  258. return ERR_NULL;
  259. }
  260. *dst = *src;
  261. return 0;
  262. }
  263. EXPORT_SYM int ripemd160_digest(const hash_state *hs, uint8_t digest[RIPEMD160_DIGEST_SIZE])
  264. {
  265. hash_state tmp;
  266. unsigned i;
  267. if (NULL==hs || digest==NULL)
  268. return ERR_NULL;
  269. tmp = *hs;
  270. /* Append the padding */
  271. tmp.buf[tmp.bufpos++] = 0x80;
  272. if (tmp.bufpos > 56) {
  273. tmp.bufpos = 64;
  274. ripemd160_compress(&tmp);
  275. }
  276. /* Append the length */
  277. STORE_U64_LITTLE(&tmp.buf[sizeof tmp.buf - 8], tmp.length);
  278. tmp.bufpos = 64;
  279. ripemd160_compress(&tmp);
  280. /* Copy the final state into the output buffer */
  281. assert(RIPEMD160_DIGEST_SIZE == sizeof tmp.h);
  282. for (i=0; i<5; i++)
  283. STORE_U32_LITTLE(digest + i*sizeof tmp.h[0], tmp.h[i]);
  284. return 0;
  285. }