poly1305.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442
  1. /* ===================================================================
  2. *
  3. * Copyright (c) 2018, Helder Eijs <helderijs@gmail.com>
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions
  8. * are met:
  9. *
  10. * 1. Redistributions of source code must retain the above copyright
  11. * notice, this list of conditions and the following disclaimer.
  12. * 2. Redistributions in binary form must reproduce the above copyright
  13. * notice, this list of conditions and the following disclaimer in
  14. * the documentation and/or other materials provided with the
  15. * distribution.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  20. * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  21. * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  22. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  23. * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  25. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  27. * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28. * POSSIBILITY OF SUCH DAMAGE.
  29. * ===================================================================
  30. */
  31. #include "common.h"
  32. #include "endianess.h"
  33. FAKE_INIT(poly1305)
  34. typedef struct mac_state_t {
  35. uint32_t r[4], rr[4]; /** first key - variable in polynomial **/
  36. uint32_t s[5]; /** second key - fixed term in polynomial **/
  37. uint32_t h[5]; /** state **/
  38. uint8_t buffer[16]; /** temp input **/
  39. unsigned buffer_used;
  40. } mac_state;
  41. /*
  42. * Load 16 bytes as the secret r, which is the value we evaluate the polynomial
  43. * with, modulo 2^130-5.
  44. *
  45. * The secret gets encoded into four 32-bit words (r[]), after appropriate clamping
  46. * (reset) is applied to 22 of its bits.
  47. *
  48. * Additionaly, reduce modulo 2^130-5 the value 2^130*r into rr[], which we can
  49. * reuse several times later during each multiplication.
  50. *
  51. * @param[out] r: The 4-word array with the r value (little-endian)
  52. * @param[out] rr: The 4-word array with the value (r * 2^130) modulo 2^130-5 (little-endian)
  53. * @param[in] secret: The 16 bytes encoding r (not necessarily clamped already)
  54. */
  55. STATIC void poly1305_load_r(uint32_t r[4], uint32_t rr[4], const uint8_t secret[16])
  56. {
  57. unsigned i;
  58. uint32_t mask;
  59. for (i=0; i<4; i++) {
  60. /**
  61. * The 4 most significant bits in a word are reset.
  62. * The 2 least significant bits in a word are reset, except for r[0]
  63. */
  64. mask = (i==0) ? 0x0FFFFFFFU : 0x0FFFFFFCU;
  65. r[i] = LOAD_U32_LITTLE(secret+i*4) & mask;
  66. rr[i] = (r[i] >> 2)*5;
  67. }
  68. }
  69. /*
  70. * Load the next chunk of message as an integer.
  71. *
  72. * @param[out] m: The 5-word array the chunk will be read into (little-endian)
  73. * @param[in] data: The next chunk of message, at most 16 bytes. It is
  74. * smaller than 16 only if it is the last chunk.
  75. * @param[in] len: The length of the chunk (<=16)
  76. */
  77. STATIC void poly1305_load_m(uint32_t m[5], const uint8_t data[], size_t len)
  78. {
  79. uint8_t copy[sizeof(uint32_t)*5];
  80. assert(len<=16);
  81. memset(copy, 0, sizeof(copy));
  82. memcpy(copy, data, len);
  83. copy[len] = 1; /** 2^128 or 2^{8*(l mod 16)} **/
  84. m[0] = LOAD_U32_LITTLE(copy);
  85. m[1] = LOAD_U32_LITTLE(copy+4);
  86. m[2] = LOAD_U32_LITTLE(copy+8);
  87. m[3] = LOAD_U32_LITTLE(copy+12);
  88. m[4] = LOAD_U32_LITTLE(copy+16);
  89. }
  90. /*
  91. * Load 16 bytes as the secret s, which is the fixed term for the polynomial, modulo 2^130-5.
  92. *
  93. * @param[out] m: The 5-word array that will contain the secret s (little-endian)
  94. * @param[in] s: The 16 bytes that encode the value s. It is typically the
  95. * result of an AES of ChaCha20 encryption.
  96. */
  97. static void poly1305_load_s(uint32_t m[5], const uint8_t s[16])
  98. {
  99. m[0] = LOAD_U32_LITTLE(s);
  100. m[1] = LOAD_U32_LITTLE(s+4);
  101. m[2] = LOAD_U32_LITTLE(s+8);
  102. m[3] = LOAD_U32_LITTLE(s+12);
  103. m[4] = 0;
  104. }
  105. /**
  106. * Multiply a value by the secret r, "almost" modulo 2^130-5.
  107. *
  108. * @param[in,out] h: The 5-word array with the value to multiply (little-endian).
  109. * The result is stored back here.
  110. * The result is guaranteed to be smaller than 2^131 (not 2^130-5,
  111. * hence the "almost" modulo) for any value of h[] in input.
  112. * @param[in] r: The 4-word array with the multiplier, as generated by
  113. * poly1305_load_r() (little-endian).
  114. * @param[in] rr: The 4-word array with the other value generated by
  115. * poly1305__load_r() for the same multipler (little-endian).
  116. */
  117. STATIC void poly1305_multiply(uint32_t h[5], const uint32_t r[4], const uint32_t rr[4])
  118. {
  119. uint64_t a0, a1, a2, a3;
  120. uint64_t aa0, aa1, aa2, aa3;
  121. uint64_t x0, x1, x2, x3, x4;
  122. uint64_t carry;
  123. /*
  124. * Boundaries
  125. * - h[0..4] < 2^32
  126. * - r[0..3] < 2^28 < 5*2^26
  127. * - rr[0..3] < 5*2^26
  128. */
  129. a0 = r[0];
  130. a1 = r[1];
  131. a2 = r[2];
  132. a3 = r[3];
  133. aa0 = rr[0];
  134. aa1 = rr[1];
  135. aa2 = rr[2];
  136. aa3 = rr[3];
  137. /**
  138. * Schoolbook multiplication between h[] and r[], with the caveat that
  139. * the components exceeding 2^130 are folded back with a right shift and
  140. * a multiplication by 5 (already precomputed in rr[]).
  141. *
  142. * Each sum is guaranteed to be smaller than 2^63 (x0 being the worst case).
  143. */
  144. x0 = a0*h[0] + aa0*h[4] + aa1*h[3] + aa2*h[2] + aa3*h[1];
  145. x1 = a0*h[1] + a1*h[0] + aa1*h[4] + aa2*h[3] + aa3*h[2];
  146. x2 = a0*h[2] + a1*h[1] + a2*h[0] + aa2*h[4] + aa3*h[3];
  147. x3 = a0*h[3] + a1*h[2] + a2*h[1] + a3*h[0] + aa3*h[4];
  148. x4 = (a0 & 3)*h[4]; /** < 2^34 **/
  149. /** Clear upper half of x3 **/
  150. x4 += x3 >> 32;
  151. x3 &= UINT32_MAX;
  152. /** Clear the 62 most significant bits of x4 and
  153. * create carry for x0 **/
  154. carry = (x4 >> 2)*5; /** < 2^35 **/
  155. x4 &= 3;
  156. /** Reduce x0 to 32 bits and store into h0 **/
  157. x0 += carry;
  158. h[0] = x0 & UINT32_MAX;
  159. carry = x0 >> 32;
  160. /** Reduce x1 to 32 bits and store into h1 **/
  161. x1 += carry;
  162. h[1] = x1 & UINT32_MAX;
  163. carry = x1 >> 32;
  164. /** Reduce x2 to 32 bits and store into h2 **/
  165. x2 += carry;
  166. h[2] = x2 & UINT32_MAX;
  167. carry = x2 >> 32;
  168. /** Reduce x3 to 32 bits and store into h3 **/
  169. x3 += carry;
  170. h[3] = x3 & UINT32_MAX;
  171. carry = x3 >> 32; /** < 1 **/
  172. /** Reduce x4 to 32 bits and store into h4 **/
  173. x4 += carry; /** < 2^3 **/
  174. assert(x4 < 8);
  175. h[4] = (uint32_t)x4;
  176. }
  177. /*
  178. * Reduce a value h[] modulo 2^130-5.
  179. *
  180. * @param[in,out] h: The 5-word array with the value to reduce (little-endian).
  181. * The result is stored back here and it is guaranteed to
  182. * be smaller than 2^130- 5.
  183. * The incoming value h must be smaller than 2^131.
  184. */
  185. STATIC void poly1305_reduce(uint32_t h[5])
  186. {
  187. unsigned i;
  188. assert(h[4]<8);
  189. for (i=0; i<2; i++) {
  190. uint32_t mask, carry;
  191. uint32_t g[5];
  192. /** Compute h+(-p) by adding and removing 2^130 **/
  193. g[0] = h[0] + 5; carry = g[0] < h[0];
  194. g[1] = h[1] + carry; carry = g[1] < h[1];
  195. g[2] = h[2] + carry; carry = g[2] < h[2];
  196. g[3] = h[3] + carry; carry = g[3] < h[3];
  197. g[4] = h[4] + carry - 4;
  198. mask = (g[4] >> 31) - 1U; /** All 1s if g[] is a valid reduction **/
  199. h[0] = (h[0] & ~mask) ^ (g[0] & mask);
  200. h[1] = (h[1] & ~mask) ^ (g[1] & mask);
  201. h[2] = (h[2] & ~mask) ^ (g[2] & mask);
  202. h[3] = (h[3] & ~mask) ^ (g[3] & mask);
  203. h[4] = (h[4] & ~mask) ^ (g[4] & mask);
  204. }
  205. }
  206. /**
  207. * Add two values.
  208. *
  209. * It must be assured that the sum does not exceed 2^160.
  210. *
  211. * @param[in,out] h: The 5-word variable to accumulate into (little-endian).
  212. * @param[in] m: The other 5-word term to add (little-endian).
  213. */
  214. STATIC void poly1305_accumulate(uint32_t h[5], const uint32_t m[5])
  215. {
  216. #if 0
  217. // 128-bit type exist and little-endian
  218. uint32_t carry;
  219. __uint128_t a, b, c;
  220. memcpy(&a, h, 16);
  221. memcpy(&b, m, 16);
  222. c = a + b; carry = c < a;
  223. memcpy(h, &c, 16);
  224. h[4] += m[4] + carry;
  225. #else
  226. uint8_t carry;
  227. uint64_t tmp;
  228. h[0] += m[0];
  229. carry = h[0] < m[0];
  230. tmp = (uint64_t)h[1] + m[1] + carry;
  231. h[1] = (uint32_t) tmp;
  232. carry = (tmp >> 32) & 1;
  233. tmp = (uint64_t)h[2] + m[2] + carry;
  234. h[2] = (uint32_t) tmp;
  235. carry = (tmp >> 32) & 1;
  236. tmp = (uint64_t)h[3] + m[3] + carry;
  237. h[3] = (uint32_t) tmp;
  238. carry = (tmp >> 32) & 1;
  239. tmp = (uint64_t)h[4] + m[4] + carry;
  240. h[4] = (uint32_t) tmp;
  241. assert((tmp >> 32) == 0);
  242. #endif
  243. }
  244. /**
  245. * Process the next chunk of the message.
  246. *
  247. * This procedure performs the following operation (assuming that msg is 16 byte long):
  248. *
  249. * h = r * (h + (2^128 + little_endian_int(msg))) quasi-modulo 2^130-5
  250. *
  251. * Quasi-modulo means that the computations are performed modulo 2^130-5 but the
  252. * result is still only guaranteed to be smaller than 2^131.
  253. *
  254. * @param[in,out] h: The 5-word variable to accumulate into.
  255. * In input, it must be smaller than 2^131.
  256. * In output, it is guranteed to remain smaller than 2^131.
  257. * @param[in] r: The 4-word array with the multiplier, as generated by
  258. * poly1305_load_r()
  259. * @param[in] rr: The 4-word array with the other value generated by
  260. * poly1305__load_r() for the same multipler.
  261. * @param[in] data: The next chunk of message, at most 16 bytes. It is
  262. * smaller than 16 only if it is the last chunk.
  263. * @param[in] len: The length of chunk (<=16)
  264. */
  265. static void poly1305_process(uint32_t h[5], uint32_t r[4], uint32_t rr[4], uint8_t msg[], size_t len)
  266. {
  267. uint32_t m[5];
  268. if (len == 0)
  269. return;
  270. poly1305_load_m(m, msg, len);
  271. poly1305_accumulate(h, m); /** We add two values that don't exceed 2^131, so
  272. * this addition will not overflow 2^160.
  273. */
  274. poly1305_multiply(h, r, rr);
  275. }
  276. /*
  277. * Terminate processing of the message and create the final MAC tag.
  278. *
  279. * @param[in,out] h: The 5-word variable where the resulting MAC must be put into,
  280. * truncated to 128 bits.
  281. * In input, it contains the value the polynomial has been evaluated at,
  282. * without the fixed term. The input is smaller than 2^131.
  283. * @param[in] s: The 5-word value s, that is, the fixed term of the
  284. * polynomial, as created by poly1305_load_s().
  285. */
  286. static void poly1305_finalize(uint32_t h[5], const uint32_t s[5])
  287. {
  288. poly1305_reduce(h);
  289. poly1305_accumulate(h, s);
  290. h[4] = 0; /** modulo 2**128 **/
  291. }
  292. /* --------------------------------------------------------- */
  293. EXPORT_SYM int poly1305_init(mac_state **pState,
  294. const uint8_t r[16],
  295. size_t r_len,
  296. const uint8_t s[16],
  297. size_t s_len)
  298. {
  299. mac_state *ms;
  300. if (NULL == pState || NULL == r || NULL == s)
  301. return ERR_NULL;
  302. if (r_len != 16 || s_len != 16)
  303. return ERR_KEY_SIZE;
  304. *pState = ms = (mac_state*) calloc(1, sizeof(mac_state));
  305. if (NULL == ms)
  306. return ERR_MEMORY;
  307. poly1305_load_r(ms->r, ms->rr, r);
  308. poly1305_load_s(ms->s, s);
  309. return 0;
  310. }
  311. EXPORT_SYM int poly1305_destroy(mac_state *state)
  312. {
  313. if (NULL == state)
  314. return ERR_NULL;
  315. free(state);
  316. return 0;
  317. }
  318. EXPORT_SYM int poly1305_update(mac_state *state,
  319. const uint8_t *in,
  320. size_t len)
  321. {
  322. if (NULL == state || NULL == in)
  323. return ERR_NULL;
  324. while (len>0) {
  325. unsigned btc;
  326. btc = (unsigned)MIN(len, 16 - state->buffer_used);
  327. memcpy(state->buffer + state->buffer_used, in, btc);
  328. state->buffer_used += btc;
  329. in += btc;
  330. len -= btc;
  331. if (state->buffer_used == 16) {
  332. poly1305_process(state->h, state->r, state->rr, state->buffer, 16);
  333. state->buffer_used = 0;
  334. }
  335. }
  336. return 0;
  337. }
  338. EXPORT_SYM int poly1305_digest(const mac_state *state,
  339. uint8_t digest[16],
  340. size_t len)
  341. {
  342. mac_state temp;
  343. unsigned i;
  344. if (NULL == state || NULL == digest) {
  345. return ERR_NULL;
  346. }
  347. if (len != 16)
  348. return ERR_DIGEST_SIZE;
  349. temp = *state;
  350. if (temp.buffer_used > 0) {
  351. poly1305_process(temp.h, temp.r, temp.rr, temp.buffer, temp.buffer_used);
  352. }
  353. poly1305_finalize(temp.h, temp.s);
  354. for (i=0; i<4; i++) {
  355. STORE_U32_LITTLE(digest+i*4, temp.h[i]);
  356. }
  357. return 0;
  358. }
  359. #ifdef PROFILE
  360. int main(void)
  361. {
  362. const unsigned data_size = 1024*1024;
  363. mac_state *state;
  364. const uint8_t r[16] = "1234567890123456";
  365. const uint8_t s[16] = "1234567890123456";
  366. uint8_t *data;
  367. data = malloc(data_size);
  368. for (int i=0; i<data_size; i++) {
  369. data[i] = (uint8_t) i;
  370. }
  371. poly1305_init(&state, r, 16, s, 16);
  372. for (int i=0; i<1024; i++)
  373. poly1305_update(state, data, 1024*1024);
  374. poly1305_destroy(state);
  375. free(data);
  376. }
  377. #endif