tls_chacha20.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423
  1. /* ChaCha20 + Poly1305 (RFC 8439): see tls_chacha20.h.
  2. * Poly1305 uses 5 x 26-bit limbs with 64-bit products (no __int128). */
  3. #include "tls_chacha20.h"
  4. static unsigned int rotl32(unsigned int x, int n)
  5. {
  6. return (x << n) | (x >> (32 - n));
  7. }
  8. #define QR(a, b, c, d) \
  9. do { \
  10. a += b; d ^= a; d = rotl32(d, 16); \
  11. c += d; b ^= c; b = rotl32(b, 12); \
  12. a += b; d ^= a; d = rotl32(d, 8); \
  13. c += d; b ^= c; b = rotl32(b, 7); \
  14. } while (0)
  15. static void chacha_block(const unsigned int in[16], unsigned char out[64])
  16. {
  17. unsigned int x[16];
  18. int i;
  19. for (i = 0; i < 16; i++)
  20. x[i] = in[i];
  21. for (i = 0; i < 10; i++) {
  22. QR(x[0], x[4], x[8], x[12]);
  23. QR(x[1], x[5], x[9], x[13]);
  24. QR(x[2], x[6], x[10], x[14]);
  25. QR(x[3], x[7], x[11], x[15]);
  26. QR(x[0], x[5], x[10], x[15]);
  27. QR(x[1], x[6], x[11], x[12]);
  28. QR(x[2], x[7], x[8], x[13]);
  29. QR(x[3], x[4], x[9], x[14]);
  30. }
  31. for (i = 0; i < 16; i++)
  32. x[i] += in[i];
  33. for (i = 0; i < 16; i++) {
  34. unsigned int v = x[i];
  35. out[i * 4] = (unsigned char)v;
  36. out[i * 4 + 1] = (unsigned char)(v >> 8);
  37. out[i * 4 + 2] = (unsigned char)(v >> 16);
  38. out[i * 4 + 3] = (unsigned char)(v >> 24);
  39. }
  40. }
  41. void chacha20_init(struct chacha20_ctx *c, const unsigned char key[32],
  42. const unsigned char nonce[12], unsigned int counter)
  43. {
  44. unsigned int i;
  45. c->st[0] = 0x61707865;
  46. c->st[1] = 0x3320646e;
  47. c->st[2] = 0x79622d32;
  48. c->st[3] = 0x6b206574;
  49. for (i = 0; i < 8; i++) {
  50. c->st[4 + i] = (unsigned int)key[i * 4] |
  51. ((unsigned int)key[i * 4 + 1] << 8) |
  52. ((unsigned int)key[i * 4 + 2] << 16) |
  53. ((unsigned int)key[i * 4 + 3] << 24);
  54. }
  55. c->st[12] = counter;
  56. for (i = 0; i < 3; i++) {
  57. c->st[13 + i] = (unsigned int)nonce[i * 4] |
  58. ((unsigned int)nonce[i * 4 + 1] << 8) |
  59. ((unsigned int)nonce[i * 4 + 2] << 16) |
  60. ((unsigned int)nonce[i * 4 + 3] << 24);
  61. }
  62. c->used = 64;
  63. }
  64. void chacha20_xor(struct chacha20_ctx *c, unsigned char *out,
  65. const unsigned char *in, unsigned int len)
  66. {
  67. while (len) {
  68. unsigned int n, i;
  69. if (c->used == 64) {
  70. chacha_block(c->st, c->block);
  71. c->st[12]++;
  72. c->used = 0;
  73. }
  74. n = 64 - c->used;
  75. if (n > len)
  76. n = len;
  77. for (i = 0; i < n; i++)
  78. out[i] = (unsigned char)(in[i] ^ c->block[c->used + i]);
  79. c->used += n;
  80. out += n;
  81. in += n;
  82. len -= n;
  83. }
  84. }
  85. /* ---- Poly1305 (donna-32 style) ---- */
  86. #define P1305_MASK 0x3ffffff
  87. static unsigned int pl_le32(const unsigned char *p)
  88. {
  89. return (unsigned int)p[0] | ((unsigned int)p[1] << 8) |
  90. ((unsigned int)p[2] << 16) | ((unsigned int)p[3] << 24);
  91. }
  92. static void pl_store32(unsigned char *p, unsigned int v)
  93. {
  94. p[0] = (unsigned char)v;
  95. p[1] = (unsigned char)(v >> 8);
  96. p[2] = (unsigned char)(v >> 16);
  97. p[3] = (unsigned char)(v >> 24);
  98. }
  99. static void poly1305_blocks(struct poly1305_ctx *c, const unsigned char *m,
  100. unsigned int len, unsigned int hibit)
  101. {
  102. unsigned int h0 = c->h[0], h1 = c->h[1], h2 = c->h[2];
  103. unsigned int h3 = c->h[3], h4 = c->h[4];
  104. unsigned int r0 = c->r[0], r1 = c->r[1], r2 = c->r[2];
  105. unsigned int r3 = c->r[3], r4 = c->r[4];
  106. unsigned int s1 = r1 * 5, s2 = r2 * 5, s3 = r3 * 5, s4 = r4 * 5;
  107. while (len >= 16) {
  108. unsigned int t0 = pl_le32(m), t1 = pl_le32(m + 4);
  109. unsigned int t2 = pl_le32(m + 8), t3 = pl_le32(m + 12);
  110. unsigned long long d0, d1, d2, d3, d4;
  111. unsigned int carry;
  112. h0 += t0 & P1305_MASK;
  113. h1 += ((t0 >> 26) | (t1 << 6)) & P1305_MASK;
  114. h2 += ((t1 >> 20) | (t2 << 12)) & P1305_MASK;
  115. h3 += ((t2 >> 14) | (t3 << 18)) & P1305_MASK;
  116. h4 += (t3 >> 8) | hibit;
  117. d0 = (unsigned long long)h0 * r0 +
  118. (unsigned long long)h1 * s4 +
  119. (unsigned long long)h2 * s3 +
  120. (unsigned long long)h3 * s2 +
  121. (unsigned long long)h4 * s1;
  122. d1 = (unsigned long long)h0 * r1 +
  123. (unsigned long long)h1 * r0 +
  124. (unsigned long long)h2 * s4 +
  125. (unsigned long long)h3 * s3 +
  126. (unsigned long long)h4 * s2;
  127. d2 = (unsigned long long)h0 * r2 +
  128. (unsigned long long)h1 * r1 +
  129. (unsigned long long)h2 * r0 +
  130. (unsigned long long)h3 * s4 +
  131. (unsigned long long)h4 * s3;
  132. d3 = (unsigned long long)h0 * r3 +
  133. (unsigned long long)h1 * r2 +
  134. (unsigned long long)h2 * r1 +
  135. (unsigned long long)h3 * r0 +
  136. (unsigned long long)h4 * s4;
  137. d4 = (unsigned long long)h0 * r4 +
  138. (unsigned long long)h1 * r3 +
  139. (unsigned long long)h2 * r2 +
  140. (unsigned long long)h3 * r1 +
  141. (unsigned long long)h4 * r0;
  142. carry = (unsigned int)(d0 >> 26);
  143. h0 = (unsigned int)d0 & P1305_MASK;
  144. d1 += carry;
  145. carry = (unsigned int)(d1 >> 26);
  146. h1 = (unsigned int)d1 & P1305_MASK;
  147. d2 += carry;
  148. carry = (unsigned int)(d2 >> 26);
  149. h2 = (unsigned int)d2 & P1305_MASK;
  150. d3 += carry;
  151. carry = (unsigned int)(d3 >> 26);
  152. h3 = (unsigned int)d3 & P1305_MASK;
  153. d4 += carry;
  154. carry = (unsigned int)(d4 >> 26);
  155. h4 = (unsigned int)d4 & P1305_MASK;
  156. h0 += carry * 5;
  157. carry = h0 >> 26;
  158. h0 &= P1305_MASK;
  159. h1 += carry;
  160. m += 16;
  161. len -= 16;
  162. }
  163. c->h[0] = h0;
  164. c->h[1] = h1;
  165. c->h[2] = h2;
  166. c->h[3] = h3;
  167. c->h[4] = h4;
  168. }
  169. void poly1305_init(struct poly1305_ctx *c, const unsigned char key[32])
  170. {
  171. unsigned int t0 = pl_le32(key), t1 = pl_le32(key + 4);
  172. unsigned int t2 = pl_le32(key + 8), t3 = pl_le32(key + 12);
  173. c->r[0] = t0 & 0x3ffffff;
  174. c->r[1] = ((t0 >> 26) | (t1 << 6)) & 0x3ffff03;
  175. c->r[2] = ((t1 >> 20) | (t2 << 12)) & 0x3ffc0ff;
  176. c->r[3] = ((t2 >> 14) | (t3 << 18)) & 0x3f03fff;
  177. c->r[4] = (t3 >> 8) & 0x00fffff;
  178. c->pad[0] = pl_le32(key + 16);
  179. c->pad[1] = pl_le32(key + 20);
  180. c->pad[2] = pl_le32(key + 24);
  181. c->pad[3] = pl_le32(key + 28);
  182. c->h[0] = c->h[1] = c->h[2] = c->h[3] = c->h[4] = 0;
  183. c->leftover = 0;
  184. }
  185. void poly1305_update(struct poly1305_ctx *c, const unsigned char *m,
  186. unsigned int len)
  187. {
  188. unsigned int i;
  189. if (c->leftover) {
  190. unsigned int want = 16 - c->leftover;
  191. if (want > len)
  192. want = len;
  193. for (i = 0; i < want; i++)
  194. c->buf[c->leftover + i] = m[i];
  195. c->leftover += want;
  196. m += want;
  197. len -= want;
  198. if (c->leftover < 16)
  199. return;
  200. poly1305_blocks(c, c->buf, 16, 1u << 24);
  201. c->leftover = 0;
  202. }
  203. if (len >= 16) {
  204. unsigned int want = len & ~15u;
  205. poly1305_blocks(c, m, want, 1u << 24);
  206. m += want;
  207. len -= want;
  208. }
  209. if (len) {
  210. for (i = 0; i < len; i++)
  211. c->buf[i] = m[i];
  212. c->leftover = len;
  213. }
  214. }
  215. void poly1305_final(struct poly1305_ctx *c, unsigned char tag[16])
  216. {
  217. unsigned int h0, h1, h2, h3, h4, g0, g1, g2, g3, g4, mask, i;
  218. unsigned long long d;
  219. if (c->leftover) {
  220. c->buf[c->leftover] = 1;
  221. for (i = c->leftover + 1; i < 16; i++)
  222. c->buf[i] = 0;
  223. poly1305_blocks(c, c->buf, 16, 0);
  224. }
  225. h0 = c->h[0];
  226. h1 = c->h[1];
  227. h2 = c->h[2];
  228. h3 = c->h[3];
  229. h4 = c->h[4];
  230. {
  231. unsigned int carry = h1 >> 26;
  232. h1 &= P1305_MASK;
  233. h2 += carry;
  234. carry = h2 >> 26;
  235. h2 &= P1305_MASK;
  236. h3 += carry;
  237. carry = h3 >> 26;
  238. h3 &= P1305_MASK;
  239. h4 += carry;
  240. carry = h4 >> 26;
  241. h4 &= P1305_MASK;
  242. h0 += carry * 5;
  243. carry = h0 >> 26;
  244. h0 &= P1305_MASK;
  245. h1 += carry;
  246. }
  247. g0 = h0 + 5;
  248. {
  249. unsigned int carry = g0 >> 26;
  250. g0 &= P1305_MASK;
  251. g1 = h1 + carry;
  252. carry = g1 >> 26;
  253. g1 &= P1305_MASK;
  254. g2 = h2 + carry;
  255. carry = g2 >> 26;
  256. g2 &= P1305_MASK;
  257. g3 = h3 + carry;
  258. carry = g3 >> 26;
  259. g3 &= P1305_MASK;
  260. g4 = h4 + carry - (1u << 26);
  261. }
  262. mask = (g4 >> 31) - 1; /* all ones when no borrow (g4 valid) */
  263. g0 &= mask;
  264. g1 &= mask;
  265. g2 &= mask;
  266. g3 &= mask;
  267. g4 &= mask;
  268. mask = ~mask;
  269. h0 = (h0 & mask) | g0;
  270. h1 = (h1 & mask) | g1;
  271. h2 = (h2 & mask) | g2;
  272. h3 = (h3 & mask) | g3;
  273. h4 = (h4 & mask) | g4;
  274. h0 = (h0 | (h1 << 26)) & 0xffffffffu;
  275. h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffffu;
  276. h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffffu;
  277. h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffffu;
  278. d = (unsigned long long)h0 + c->pad[0];
  279. h0 = (unsigned int)d;
  280. d = (unsigned long long)h1 + c->pad[1] + (d >> 32);
  281. h1 = (unsigned int)d;
  282. d = (unsigned long long)h2 + c->pad[2] + (d >> 32);
  283. h2 = (unsigned int)d;
  284. d = (unsigned long long)h3 + c->pad[3] + (d >> 32);
  285. h3 = (unsigned int)d;
  286. pl_store32(tag, h0);
  287. pl_store32(tag + 4, h1);
  288. pl_store32(tag + 8, h2);
  289. pl_store32(tag + 12, h3);
  290. }
  291. /* ---- AEAD ---- */
  292. static void poly_key_from_chacha(const unsigned char key[32],
  293. const unsigned char nonce[12],
  294. unsigned char out[32])
  295. {
  296. struct chacha20_ctx c;
  297. unsigned char zero[64];
  298. unsigned int i;
  299. for (i = 0; i < 64; i++)
  300. zero[i] = 0;
  301. chacha20_init(&c, key, nonce, 0);
  302. chacha20_xor(&c, zero, zero, 64);
  303. for (i = 0; i < 32; i++)
  304. out[i] = zero[i];
  305. }
  306. void aead_open_init(struct aead_open_ctx *a, const unsigned char key[32],
  307. const unsigned char nonce[12],
  308. const unsigned char *aad, unsigned int aad_len)
  309. {
  310. unsigned char pk[32];
  311. static const unsigned char zeros[16];
  312. poly_key_from_chacha(key, nonce, pk);
  313. poly1305_init(&a->poly, pk);
  314. poly1305_update(&a->poly, aad, aad_len);
  315. if (aad_len & 15)
  316. poly1305_update(&a->poly, zeros, 16 - (aad_len & 15));
  317. chacha20_init(&a->ch, key, nonce, 1);
  318. a->aad_len = aad_len;
  319. a->ct_len = 0;
  320. }
  321. void aead_open_update(struct aead_open_ctx *a, unsigned char *out,
  322. const unsigned char *in, unsigned int len)
  323. {
  324. poly1305_update(&a->poly, in, len);
  325. chacha20_xor(&a->ch, out, in, len);
  326. a->ct_len += len;
  327. }
  328. void aead_open_tag(struct aead_open_ctx *a, unsigned char tag[16])
  329. {
  330. static const unsigned char zeros[16];
  331. unsigned char lens[16];
  332. unsigned int pad, i;
  333. pad = (16 - (a->ct_len & 15)) & 15;
  334. if (pad)
  335. poly1305_update(&a->poly, zeros, pad);
  336. for (i = 0; i < 8; i++)
  337. lens[i] = (unsigned char)((unsigned long long)a->aad_len >>
  338. (i * 8));
  339. for (i = 0; i < 8; i++)
  340. lens[8 + i] = (unsigned char)((unsigned long long)a->ct_len >>
  341. (i * 8));
  342. poly1305_update(&a->poly, lens, 16);
  343. poly1305_final(&a->poly, tag);
  344. }
  345. void aead_seal(const unsigned char key[32], const unsigned char nonce[12],
  346. const unsigned char *aad, unsigned int aad_len,
  347. const unsigned char *pt, unsigned int len,
  348. unsigned char *ct, unsigned char tag[16])
  349. {
  350. unsigned char pk[32];
  351. struct poly1305_ctx poly;
  352. struct chacha20_ctx ch;
  353. static const unsigned char zeros[16];
  354. unsigned char lens[16];
  355. unsigned int pad, i;
  356. poly_key_from_chacha(key, nonce, pk);
  357. poly1305_init(&poly, pk);
  358. poly1305_update(&poly, aad, aad_len);
  359. if (aad_len & 15)
  360. poly1305_update(&poly, zeros, 16 - (aad_len & 15));
  361. chacha20_init(&ch, key, nonce, 1);
  362. chacha20_xor(&ch, ct, pt, len);
  363. poly1305_update(&poly, ct, len);
  364. pad = (16 - (len & 15)) & 15;
  365. if (pad)
  366. poly1305_update(&poly, zeros, pad);
  367. for (i = 0; i < 8; i++)
  368. lens[i] = (unsigned char)((unsigned long long)aad_len >>
  369. (i * 8));
  370. for (i = 0; i < 8; i++)
  371. lens[8 + i] = (unsigned char)((unsigned long long)len >>
  372. (i * 8));
  373. poly1305_update(&poly, lens, 16);
  374. poly1305_final(&poly, tag);
  375. }