poly1305.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529
  1. /*
  2. * Copyright 2015-2021 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <openssl/crypto.h>
  12. #include "crypto/poly1305.h"
  13. size_t Poly1305_ctx_size(void)
  14. {
  15. return sizeof(struct poly1305_context);
  16. }
  17. /* pick 32-bit unsigned integer in little endian order */
  18. static unsigned int U8TOU32(const unsigned char *p)
  19. {
  20. return (((unsigned int)(p[0] & 0xff)) |
  21. ((unsigned int)(p[1] & 0xff) << 8) |
  22. ((unsigned int)(p[2] & 0xff) << 16) |
  23. ((unsigned int)(p[3] & 0xff) << 24));
  24. }
  25. /*
  26. * Implementations can be classified by amount of significant bits in
  27. * words making up the multi-precision value, or in other words radix
  28. * or base of numerical representation, e.g. base 2^64, base 2^32,
  29. * base 2^26. Complementary characteristic is how wide is the result of
  30. * multiplication of pair of digits, e.g. it would take 128 bits to
  31. * accommodate multiplication result in base 2^64 case. These are used
  32. * interchangeably. To describe implementation that is. But interface
  33. * is designed to isolate this so that low-level primitives implemented
  34. * in assembly can be self-contained/self-coherent.
  35. */
  36. #ifndef POLY1305_ASM
  37. /*
  38. * Even though there is __int128 reference implementation targeting
  39. * 64-bit platforms provided below, it's not obvious that it's optimal
  40. * choice for every one of them. Depending on instruction set overall
  41. * amount of instructions can be comparable to one in __int64
  42. * implementation. Amount of multiplication instructions would be lower,
  43. * but not necessarily overall. And in out-of-order execution context,
  44. * it is the latter that can be crucial...
  45. *
  46. * On related note. Poly1305 author, D. J. Bernstein, discusses and
  47. * provides floating-point implementations of the algorithm in question.
  48. * It made a lot of sense by the time of introduction, because most
  49. * then-modern processors didn't have pipelined integer multiplier.
  50. * [Not to mention that some had non-constant timing for integer
  51. * multiplications.] Floating-point instructions on the other hand could
  52. * be issued every cycle, which allowed to achieve better performance.
  53. * Nowadays, with SIMD and/or out-or-order execution, shared or
  54. * even emulated FPU, it's more complicated, and floating-point
  55. * implementation is not necessarily optimal choice in every situation,
  56. * rather contrary...
  57. *
  58. * <appro@openssl.org>
  59. */
  60. typedef unsigned int u32;
  61. /*
  62. * poly1305_blocks processes a multiple of POLY1305_BLOCK_SIZE blocks
  63. * of |inp| no longer than |len|. Behaviour for |len| not divisible by
  64. * block size is unspecified in general case, even though in reference
  65. * implementation the trailing chunk is simply ignored. Per algorithm
  66. * specification, every input block, complete or last partial, is to be
  67. * padded with a bit past most significant byte. The latter kind is then
  68. * padded with zeros till block size. This last partial block padding
  69. * is caller(*)'s responsibility, and because of this the last partial
  70. * block is always processed with separate call with |len| set to
  71. * POLY1305_BLOCK_SIZE and |padbit| to 0. In all other cases |padbit|
  72. * should be set to 1 to perform implicit padding with 128th bit.
  73. * poly1305_blocks does not actually check for this constraint though,
  74. * it's caller(*)'s responsibility to comply.
  75. *
  76. * (*) In the context "caller" is not application code, but higher
  77. * level Poly1305_* from this very module, so that quirks are
  78. * handled locally.
  79. */
  80. static void
  81. poly1305_blocks(void *ctx, const unsigned char *inp, size_t len, u32 padbit);
  82. /*
  83. * Type-agnostic "rip-off" from constant_time.h
  84. */
  85. # define CONSTANT_TIME_CARRY(a,b) ( \
  86. (a ^ ((a ^ b) | ((a - b) ^ b))) >> (sizeof(a) * 8 - 1) \
  87. )
  88. # if defined(INT64_MAX) && defined(INT128_MAX)
  89. typedef unsigned long u64;
  90. typedef uint128_t u128;
  91. typedef struct {
  92. u64 h[3];
  93. u64 r[2];
  94. } poly1305_internal;
  95. /* pick 32-bit unsigned integer in little endian order */
  96. static u64 U8TOU64(const unsigned char *p)
  97. {
  98. return (((u64)(p[0] & 0xff)) |
  99. ((u64)(p[1] & 0xff) << 8) |
  100. ((u64)(p[2] & 0xff) << 16) |
  101. ((u64)(p[3] & 0xff) << 24) |
  102. ((u64)(p[4] & 0xff) << 32) |
  103. ((u64)(p[5] & 0xff) << 40) |
  104. ((u64)(p[6] & 0xff) << 48) |
  105. ((u64)(p[7] & 0xff) << 56));
  106. }
  107. /* store a 32-bit unsigned integer in little endian */
  108. static void U64TO8(unsigned char *p, u64 v)
  109. {
  110. p[0] = (unsigned char)((v) & 0xff);
  111. p[1] = (unsigned char)((v >> 8) & 0xff);
  112. p[2] = (unsigned char)((v >> 16) & 0xff);
  113. p[3] = (unsigned char)((v >> 24) & 0xff);
  114. p[4] = (unsigned char)((v >> 32) & 0xff);
  115. p[5] = (unsigned char)((v >> 40) & 0xff);
  116. p[6] = (unsigned char)((v >> 48) & 0xff);
  117. p[7] = (unsigned char)((v >> 56) & 0xff);
  118. }
  119. static void poly1305_init(void *ctx, const unsigned char key[16])
  120. {
  121. poly1305_internal *st = (poly1305_internal *) ctx;
  122. /* h = 0 */
  123. st->h[0] = 0;
  124. st->h[1] = 0;
  125. st->h[2] = 0;
  126. /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
  127. st->r[0] = U8TOU64(&key[0]) & 0x0ffffffc0fffffff;
  128. st->r[1] = U8TOU64(&key[8]) & 0x0ffffffc0ffffffc;
  129. }
  130. static void
  131. poly1305_blocks(void *ctx, const unsigned char *inp, size_t len, u32 padbit)
  132. {
  133. poly1305_internal *st = (poly1305_internal *)ctx;
  134. u64 r0, r1;
  135. u64 s1;
  136. u64 h0, h1, h2, c;
  137. u128 d0, d1;
  138. r0 = st->r[0];
  139. r1 = st->r[1];
  140. s1 = r1 + (r1 >> 2);
  141. h0 = st->h[0];
  142. h1 = st->h[1];
  143. h2 = st->h[2];
  144. while (len >= POLY1305_BLOCK_SIZE) {
  145. /* h += m[i] */
  146. h0 = (u64)(d0 = (u128)h0 + U8TOU64(inp + 0));
  147. h1 = (u64)(d1 = (u128)h1 + (d0 >> 64) + U8TOU64(inp + 8));
  148. /*
  149. * padbit can be zero only when original len was
  150. * POLY1305_BLOCK_SIZE, but we don't check
  151. */
  152. h2 += (u64)(d1 >> 64) + padbit;
  153. /* h *= r "%" p, where "%" stands for "partial remainder" */
  154. d0 = ((u128)h0 * r0) +
  155. ((u128)h1 * s1);
  156. d1 = ((u128)h0 * r1) +
  157. ((u128)h1 * r0) +
  158. (h2 * s1);
  159. h2 = (h2 * r0);
  160. /* last reduction step: */
  161. /* a) h2:h0 = h2<<128 + d1<<64 + d0 */
  162. h0 = (u64)d0;
  163. h1 = (u64)(d1 += d0 >> 64);
  164. h2 += (u64)(d1 >> 64);
  165. /* b) (h2:h0 += (h2:h0>>130) * 5) %= 2^130 */
  166. c = (h2 >> 2) + (h2 & ~3UL);
  167. h2 &= 3;
  168. h0 += c;
  169. h1 += (c = CONSTANT_TIME_CARRY(h0,c));
  170. h2 += CONSTANT_TIME_CARRY(h1,c);
  171. /*
  172. * Occasional overflows to 3rd bit of h2 are taken care of
  173. * "naturally". If after this point we end up at the top of
  174. * this loop, then the overflow bit will be accounted for
  175. * in next iteration. If we end up in poly1305_emit, then
  176. * comparison to modulus below will still count as "carry
  177. * into 131st bit", so that properly reduced value will be
  178. * picked in conditional move.
  179. */
  180. inp += POLY1305_BLOCK_SIZE;
  181. len -= POLY1305_BLOCK_SIZE;
  182. }
  183. st->h[0] = h0;
  184. st->h[1] = h1;
  185. st->h[2] = h2;
  186. }
  187. static void poly1305_emit(void *ctx, unsigned char mac[16],
  188. const u32 nonce[4])
  189. {
  190. poly1305_internal *st = (poly1305_internal *) ctx;
  191. u64 h0, h1, h2;
  192. u64 g0, g1, g2;
  193. u128 t;
  194. u64 mask;
  195. h0 = st->h[0];
  196. h1 = st->h[1];
  197. h2 = st->h[2];
  198. /* compare to modulus by computing h + -p */
  199. g0 = (u64)(t = (u128)h0 + 5);
  200. g1 = (u64)(t = (u128)h1 + (t >> 64));
  201. g2 = h2 + (u64)(t >> 64);
  202. /* if there was carry into 131st bit, h1:h0 = g1:g0 */
  203. mask = 0 - (g2 >> 2);
  204. g0 &= mask;
  205. g1 &= mask;
  206. mask = ~mask;
  207. h0 = (h0 & mask) | g0;
  208. h1 = (h1 & mask) | g1;
  209. /* mac = (h + nonce) % (2^128) */
  210. h0 = (u64)(t = (u128)h0 + nonce[0] + ((u64)nonce[1]<<32));
  211. h1 = (u64)(t = (u128)h1 + nonce[2] + ((u64)nonce[3]<<32) + (t >> 64));
  212. U64TO8(mac + 0, h0);
  213. U64TO8(mac + 8, h1);
  214. }
  215. # else
  216. # if defined(_WIN32) && !defined(__MINGW32__)
  217. typedef unsigned __int64 u64;
  218. # elif defined(__arch64__)
  219. typedef unsigned long u64;
  220. # else
  221. typedef unsigned long long u64;
  222. # endif
  223. typedef struct {
  224. u32 h[5];
  225. u32 r[4];
  226. } poly1305_internal;
  227. /* store a 32-bit unsigned integer in little endian */
  228. static void U32TO8(unsigned char *p, unsigned int v)
  229. {
  230. p[0] = (unsigned char)((v) & 0xff);
  231. p[1] = (unsigned char)((v >> 8) & 0xff);
  232. p[2] = (unsigned char)((v >> 16) & 0xff);
  233. p[3] = (unsigned char)((v >> 24) & 0xff);
  234. }
  235. static void poly1305_init(void *ctx, const unsigned char key[16])
  236. {
  237. poly1305_internal *st = (poly1305_internal *) ctx;
  238. /* h = 0 */
  239. st->h[0] = 0;
  240. st->h[1] = 0;
  241. st->h[2] = 0;
  242. st->h[3] = 0;
  243. st->h[4] = 0;
  244. /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
  245. st->r[0] = U8TOU32(&key[0]) & 0x0fffffff;
  246. st->r[1] = U8TOU32(&key[4]) & 0x0ffffffc;
  247. st->r[2] = U8TOU32(&key[8]) & 0x0ffffffc;
  248. st->r[3] = U8TOU32(&key[12]) & 0x0ffffffc;
  249. }
  250. static void
  251. poly1305_blocks(void *ctx, const unsigned char *inp, size_t len, u32 padbit)
  252. {
  253. poly1305_internal *st = (poly1305_internal *)ctx;
  254. u32 r0, r1, r2, r3;
  255. u32 s1, s2, s3;
  256. u32 h0, h1, h2, h3, h4, c;
  257. u64 d0, d1, d2, d3;
  258. r0 = st->r[0];
  259. r1 = st->r[1];
  260. r2 = st->r[2];
  261. r3 = st->r[3];
  262. s1 = r1 + (r1 >> 2);
  263. s2 = r2 + (r2 >> 2);
  264. s3 = r3 + (r3 >> 2);
  265. h0 = st->h[0];
  266. h1 = st->h[1];
  267. h2 = st->h[2];
  268. h3 = st->h[3];
  269. h4 = st->h[4];
  270. while (len >= POLY1305_BLOCK_SIZE) {
  271. /* h += m[i] */
  272. h0 = (u32)(d0 = (u64)h0 + U8TOU32(inp + 0));
  273. h1 = (u32)(d1 = (u64)h1 + (d0 >> 32) + U8TOU32(inp + 4));
  274. h2 = (u32)(d2 = (u64)h2 + (d1 >> 32) + U8TOU32(inp + 8));
  275. h3 = (u32)(d3 = (u64)h3 + (d2 >> 32) + U8TOU32(inp + 12));
  276. h4 += (u32)(d3 >> 32) + padbit;
  277. /* h *= r "%" p, where "%" stands for "partial remainder" */
  278. d0 = ((u64)h0 * r0) +
  279. ((u64)h1 * s3) +
  280. ((u64)h2 * s2) +
  281. ((u64)h3 * s1);
  282. d1 = ((u64)h0 * r1) +
  283. ((u64)h1 * r0) +
  284. ((u64)h2 * s3) +
  285. ((u64)h3 * s2) +
  286. (h4 * s1);
  287. d2 = ((u64)h0 * r2) +
  288. ((u64)h1 * r1) +
  289. ((u64)h2 * r0) +
  290. ((u64)h3 * s3) +
  291. (h4 * s2);
  292. d3 = ((u64)h0 * r3) +
  293. ((u64)h1 * r2) +
  294. ((u64)h2 * r1) +
  295. ((u64)h3 * r0) +
  296. (h4 * s3);
  297. h4 = (h4 * r0);
  298. /* last reduction step: */
  299. /* a) h4:h0 = h4<<128 + d3<<96 + d2<<64 + d1<<32 + d0 */
  300. h0 = (u32)d0;
  301. h1 = (u32)(d1 += d0 >> 32);
  302. h2 = (u32)(d2 += d1 >> 32);
  303. h3 = (u32)(d3 += d2 >> 32);
  304. h4 += (u32)(d3 >> 32);
  305. /* b) (h4:h0 += (h4:h0>>130) * 5) %= 2^130 */
  306. c = (h4 >> 2) + (h4 & ~3U);
  307. h4 &= 3;
  308. h0 += c;
  309. h1 += (c = CONSTANT_TIME_CARRY(h0,c));
  310. h2 += (c = CONSTANT_TIME_CARRY(h1,c));
  311. h3 += (c = CONSTANT_TIME_CARRY(h2,c));
  312. h4 += CONSTANT_TIME_CARRY(h3,c);
  313. /*
  314. * Occasional overflows to 3rd bit of h4 are taken care of
  315. * "naturally". If after this point we end up at the top of
  316. * this loop, then the overflow bit will be accounted for
  317. * in next iteration. If we end up in poly1305_emit, then
  318. * comparison to modulus below will still count as "carry
  319. * into 131st bit", so that properly reduced value will be
  320. * picked in conditional move.
  321. */
  322. inp += POLY1305_BLOCK_SIZE;
  323. len -= POLY1305_BLOCK_SIZE;
  324. }
  325. st->h[0] = h0;
  326. st->h[1] = h1;
  327. st->h[2] = h2;
  328. st->h[3] = h3;
  329. st->h[4] = h4;
  330. }
  331. static void poly1305_emit(void *ctx, unsigned char mac[16],
  332. const u32 nonce[4])
  333. {
  334. poly1305_internal *st = (poly1305_internal *) ctx;
  335. u32 h0, h1, h2, h3, h4;
  336. u32 g0, g1, g2, g3, g4;
  337. u64 t;
  338. u32 mask;
  339. h0 = st->h[0];
  340. h1 = st->h[1];
  341. h2 = st->h[2];
  342. h3 = st->h[3];
  343. h4 = st->h[4];
  344. /* compare to modulus by computing h + -p */
  345. g0 = (u32)(t = (u64)h0 + 5);
  346. g1 = (u32)(t = (u64)h1 + (t >> 32));
  347. g2 = (u32)(t = (u64)h2 + (t >> 32));
  348. g3 = (u32)(t = (u64)h3 + (t >> 32));
  349. g4 = h4 + (u32)(t >> 32);
  350. /* if there was carry into 131st bit, h3:h0 = g3:g0 */
  351. mask = 0 - (g4 >> 2);
  352. g0 &= mask;
  353. g1 &= mask;
  354. g2 &= mask;
  355. g3 &= mask;
  356. mask = ~mask;
  357. h0 = (h0 & mask) | g0;
  358. h1 = (h1 & mask) | g1;
  359. h2 = (h2 & mask) | g2;
  360. h3 = (h3 & mask) | g3;
  361. /* mac = (h + nonce) % (2^128) */
  362. h0 = (u32)(t = (u64)h0 + nonce[0]);
  363. h1 = (u32)(t = (u64)h1 + (t >> 32) + nonce[1]);
  364. h2 = (u32)(t = (u64)h2 + (t >> 32) + nonce[2]);
  365. h3 = (u32)(t = (u64)h3 + (t >> 32) + nonce[3]);
  366. U32TO8(mac + 0, h0);
  367. U32TO8(mac + 4, h1);
  368. U32TO8(mac + 8, h2);
  369. U32TO8(mac + 12, h3);
  370. }
  371. # endif
  372. #else
  373. int poly1305_init(void *ctx, const unsigned char key[16], void *func);
  374. void poly1305_blocks(void *ctx, const unsigned char *inp, size_t len,
  375. unsigned int padbit);
  376. void poly1305_emit(void *ctx, unsigned char mac[16],
  377. const unsigned int nonce[4]);
  378. #endif
  379. void Poly1305_Init(POLY1305 *ctx, const unsigned char key[32])
  380. {
  381. ctx->nonce[0] = U8TOU32(&key[16]);
  382. ctx->nonce[1] = U8TOU32(&key[20]);
  383. ctx->nonce[2] = U8TOU32(&key[24]);
  384. ctx->nonce[3] = U8TOU32(&key[28]);
  385. #ifndef POLY1305_ASM
  386. poly1305_init(ctx->opaque, key);
  387. #else
  388. /*
  389. * Unlike reference poly1305_init assembly counterpart is expected
  390. * to return a value: non-zero if it initializes ctx->func, and zero
  391. * otherwise. Latter is to simplify assembly in cases when there no
  392. * multiple code paths to switch between.
  393. */
  394. if (!poly1305_init(ctx->opaque, key, &ctx->func)) {
  395. ctx->func.blocks = poly1305_blocks;
  396. ctx->func.emit = poly1305_emit;
  397. }
  398. #endif
  399. ctx->num = 0;
  400. }
  401. #ifdef POLY1305_ASM
  402. /*
  403. * This "eclipses" poly1305_blocks and poly1305_emit, but it's
  404. * conscious choice imposed by -Wshadow compiler warnings.
  405. */
  406. # define poly1305_blocks (*poly1305_blocks_p)
  407. # define poly1305_emit (*poly1305_emit_p)
  408. #endif
  409. void Poly1305_Update(POLY1305 *ctx, const unsigned char *inp, size_t len)
  410. {
  411. #ifdef POLY1305_ASM
  412. /*
  413. * As documented, poly1305_blocks is never called with input
  414. * longer than single block and padbit argument set to 0. This
  415. * property is fluently used in assembly modules to optimize
  416. * padbit handling on loop boundary.
  417. */
  418. poly1305_blocks_f poly1305_blocks_p = ctx->func.blocks;
  419. #endif
  420. size_t rem, num;
  421. if ((num = ctx->num)) {
  422. rem = POLY1305_BLOCK_SIZE - num;
  423. if (len >= rem) {
  424. memcpy(ctx->data + num, inp, rem);
  425. poly1305_blocks(ctx->opaque, ctx->data, POLY1305_BLOCK_SIZE, 1);
  426. inp += rem;
  427. len -= rem;
  428. } else {
  429. /* Still not enough data to process a block. */
  430. memcpy(ctx->data + num, inp, len);
  431. ctx->num = num + len;
  432. return;
  433. }
  434. }
  435. rem = len % POLY1305_BLOCK_SIZE;
  436. len -= rem;
  437. if (len >= POLY1305_BLOCK_SIZE) {
  438. poly1305_blocks(ctx->opaque, inp, len, 1);
  439. inp += len;
  440. }
  441. if (rem)
  442. memcpy(ctx->data, inp, rem);
  443. ctx->num = rem;
  444. }
  445. void Poly1305_Final(POLY1305 *ctx, unsigned char mac[16])
  446. {
  447. #ifdef POLY1305_ASM
  448. poly1305_blocks_f poly1305_blocks_p = ctx->func.blocks;
  449. poly1305_emit_f poly1305_emit_p = ctx->func.emit;
  450. #endif
  451. size_t num;
  452. if ((num = ctx->num)) {
  453. ctx->data[num++] = 1; /* pad bit */
  454. while (num < POLY1305_BLOCK_SIZE)
  455. ctx->data[num++] = 0;
  456. poly1305_blocks(ctx->opaque, ctx->data, POLY1305_BLOCK_SIZE, 0);
  457. }
  458. poly1305_emit(ctx->opaque, mac, ctx->nonce);
  459. /* zero out the state */
  460. OPENSSL_cleanse(ctx, sizeof(*ctx));
  461. }