ocb128.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562
  1. /*
  2. * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (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 <string.h>
  10. #include <openssl/crypto.h>
  11. #include <openssl/err.h>
  12. #include "modes_lcl.h"
  13. #ifndef OPENSSL_NO_OCB
  14. /*
  15. * Calculate the number of binary trailing zero's in any given number
  16. */
  17. static u32 ocb_ntz(u64 n)
  18. {
  19. u32 cnt = 0;
  20. /*
  21. * We do a right-to-left simple sequential search. This is surprisingly
  22. * efficient as the distribution of trailing zeros is not uniform,
  23. * e.g. the number of possible inputs with no trailing zeros is equal to
  24. * the number with 1 or more; the number with exactly 1 is equal to the
  25. * number with 2 or more, etc. Checking the last two bits covers 75% of
  26. * all numbers. Checking the last three covers 87.5%
  27. */
  28. while (!(n & 1)) {
  29. n >>= 1;
  30. cnt++;
  31. }
  32. return cnt;
  33. }
  34. /*
  35. * Shift a block of 16 bytes left by shift bits
  36. */
  37. static void ocb_block_lshift(const unsigned char *in, size_t shift,
  38. unsigned char *out)
  39. {
  40. int i;
  41. unsigned char carry = 0, carry_next;
  42. for (i = 15; i >= 0; i--) {
  43. carry_next = in[i] >> (8 - shift);
  44. out[i] = (in[i] << shift) | carry;
  45. carry = carry_next;
  46. }
  47. }
  48. /*
  49. * Perform a "double" operation as per OCB spec
  50. */
  51. static void ocb_double(OCB_BLOCK *in, OCB_BLOCK *out)
  52. {
  53. unsigned char mask;
  54. /*
  55. * Calculate the mask based on the most significant bit. There are more
  56. * efficient ways to do this - but this way is constant time
  57. */
  58. mask = in->c[0] & 0x80;
  59. mask >>= 7;
  60. mask = (0 - mask) & 0x87;
  61. ocb_block_lshift(in->c, 1, out->c);
  62. out->c[15] ^= mask;
  63. }
  64. /*
  65. * Perform an xor on in1 and in2 - each of len bytes. Store result in out
  66. */
  67. static void ocb_block_xor(const unsigned char *in1,
  68. const unsigned char *in2, size_t len,
  69. unsigned char *out)
  70. {
  71. size_t i;
  72. for (i = 0; i < len; i++) {
  73. out[i] = in1[i] ^ in2[i];
  74. }
  75. }
  76. /*
  77. * Lookup L_index in our lookup table. If we haven't already got it we need to
  78. * calculate it
  79. */
  80. static OCB_BLOCK *ocb_lookup_l(OCB128_CONTEXT *ctx, size_t idx)
  81. {
  82. size_t l_index = ctx->l_index;
  83. if (idx <= l_index) {
  84. return ctx->l + idx;
  85. }
  86. /* We don't have it - so calculate it */
  87. if (idx >= ctx->max_l_index) {
  88. void *tmp_ptr;
  89. /*
  90. * Each additional entry allows to process almost double as
  91. * much data, so that in linear world the table will need to
  92. * be expanded with smaller and smaller increments. Originally
  93. * it was doubling in size, which was a waste. Growing it
  94. * linearly is not formally optimal, but is simpler to implement.
  95. * We grow table by minimally required 4*n that would accommodate
  96. * the index.
  97. */
  98. ctx->max_l_index += (idx - ctx->max_l_index + 4) & ~3;
  99. tmp_ptr = OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK));
  100. if (tmp_ptr == NULL) /* prevent ctx->l from being clobbered */
  101. return NULL;
  102. ctx->l = tmp_ptr;
  103. }
  104. while (l_index < idx) {
  105. ocb_double(ctx->l + l_index, ctx->l + l_index + 1);
  106. l_index++;
  107. }
  108. ctx->l_index = l_index;
  109. return ctx->l + idx;
  110. }
  111. /*
  112. * Create a new OCB128_CONTEXT
  113. */
  114. OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec,
  115. block128_f encrypt, block128_f decrypt,
  116. ocb128_f stream)
  117. {
  118. OCB128_CONTEXT *octx;
  119. int ret;
  120. if ((octx = OPENSSL_malloc(sizeof(*octx))) != NULL) {
  121. ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt,
  122. stream);
  123. if (ret)
  124. return octx;
  125. OPENSSL_free(octx);
  126. }
  127. return NULL;
  128. }
  129. /*
  130. * Initialise an existing OCB128_CONTEXT
  131. */
  132. int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec,
  133. block128_f encrypt, block128_f decrypt,
  134. ocb128_f stream)
  135. {
  136. memset(ctx, 0, sizeof(*ctx));
  137. ctx->l_index = 0;
  138. ctx->max_l_index = 5;
  139. if ((ctx->l = OPENSSL_malloc(ctx->max_l_index * 16)) == NULL) {
  140. CRYPTOerr(CRYPTO_F_CRYPTO_OCB128_INIT, ERR_R_MALLOC_FAILURE);
  141. return 0;
  142. }
  143. /*
  144. * We set both the encryption and decryption key schedules - decryption
  145. * needs both. Don't really need decryption schedule if only doing
  146. * encryption - but it simplifies things to take it anyway
  147. */
  148. ctx->encrypt = encrypt;
  149. ctx->decrypt = decrypt;
  150. ctx->stream = stream;
  151. ctx->keyenc = keyenc;
  152. ctx->keydec = keydec;
  153. /* L_* = ENCIPHER(K, zeros(128)) */
  154. ctx->encrypt(ctx->l_star.c, ctx->l_star.c, ctx->keyenc);
  155. /* L_$ = double(L_*) */
  156. ocb_double(&ctx->l_star, &ctx->l_dollar);
  157. /* L_0 = double(L_$) */
  158. ocb_double(&ctx->l_dollar, ctx->l);
  159. /* L_{i} = double(L_{i-1}) */
  160. ocb_double(ctx->l, ctx->l+1);
  161. ocb_double(ctx->l+1, ctx->l+2);
  162. ocb_double(ctx->l+2, ctx->l+3);
  163. ocb_double(ctx->l+3, ctx->l+4);
  164. ctx->l_index = 4; /* enough to process up to 496 bytes */
  165. return 1;
  166. }
  167. /*
  168. * Copy an OCB128_CONTEXT object
  169. */
  170. int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src,
  171. void *keyenc, void *keydec)
  172. {
  173. memcpy(dest, src, sizeof(OCB128_CONTEXT));
  174. if (keyenc)
  175. dest->keyenc = keyenc;
  176. if (keydec)
  177. dest->keydec = keydec;
  178. if (src->l) {
  179. if ((dest->l = OPENSSL_malloc(src->max_l_index * 16)) == NULL) {
  180. CRYPTOerr(CRYPTO_F_CRYPTO_OCB128_COPY_CTX, ERR_R_MALLOC_FAILURE);
  181. return 0;
  182. }
  183. memcpy(dest->l, src->l, (src->l_index + 1) * 16);
  184. }
  185. return 1;
  186. }
  187. /*
  188. * Set the IV to be used for this operation. Must be 1 - 15 bytes.
  189. */
  190. int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv,
  191. size_t len, size_t taglen)
  192. {
  193. unsigned char ktop[16], tmp[16], mask;
  194. unsigned char stretch[24], nonce[16];
  195. size_t bottom, shift;
  196. /*
  197. * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths.
  198. * We don't support this at this stage
  199. */
  200. if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) {
  201. return -1;
  202. }
  203. /* Reset nonce-dependent variables */
  204. memset(&ctx->sess, 0, sizeof(ctx->sess));
  205. /* Nonce = num2str(TAGLEN mod 128,7) || zeros(120-bitlen(N)) || 1 || N */
  206. nonce[0] = ((taglen * 8) % 128) << 1;
  207. memset(nonce + 1, 0, 15);
  208. memcpy(nonce + 16 - len, iv, len);
  209. nonce[15 - len] |= 1;
  210. /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */
  211. memcpy(tmp, nonce, 16);
  212. tmp[15] &= 0xc0;
  213. ctx->encrypt(tmp, ktop, ctx->keyenc);
  214. /* Stretch = Ktop || (Ktop[1..64] xor Ktop[9..72]) */
  215. memcpy(stretch, ktop, 16);
  216. ocb_block_xor(ktop, ktop + 1, 8, stretch + 16);
  217. /* bottom = str2num(Nonce[123..128]) */
  218. bottom = nonce[15] & 0x3f;
  219. /* Offset_0 = Stretch[1+bottom..128+bottom] */
  220. shift = bottom % 8;
  221. ocb_block_lshift(stretch + (bottom / 8), shift, ctx->sess.offset.c);
  222. mask = 0xff;
  223. mask <<= 8 - shift;
  224. ctx->sess.offset.c[15] |=
  225. (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift);
  226. return 1;
  227. }
  228. /*
  229. * Provide any AAD. This can be called multiple times. Only the final time can
  230. * have a partial block
  231. */
  232. int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad,
  233. size_t len)
  234. {
  235. u64 i, all_num_blocks;
  236. size_t num_blocks, last_len;
  237. OCB_BLOCK tmp;
  238. /* Calculate the number of blocks of AAD provided now, and so far */
  239. num_blocks = len / 16;
  240. all_num_blocks = num_blocks + ctx->sess.blocks_hashed;
  241. /* Loop through all full blocks of AAD */
  242. for (i = ctx->sess.blocks_hashed + 1; i <= all_num_blocks; i++) {
  243. OCB_BLOCK *lookup;
  244. /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
  245. lookup = ocb_lookup_l(ctx, ocb_ntz(i));
  246. if (lookup == NULL)
  247. return 0;
  248. ocb_block16_xor(&ctx->sess.offset_aad, lookup, &ctx->sess.offset_aad);
  249. memcpy(tmp.c, aad, 16);
  250. aad += 16;
  251. /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */
  252. ocb_block16_xor(&ctx->sess.offset_aad, &tmp, &tmp);
  253. ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
  254. ocb_block16_xor(&tmp, &ctx->sess.sum, &ctx->sess.sum);
  255. }
  256. /*
  257. * Check if we have any partial blocks left over. This is only valid in the
  258. * last call to this function
  259. */
  260. last_len = len % 16;
  261. if (last_len > 0) {
  262. /* Offset_* = Offset_m xor L_* */
  263. ocb_block16_xor(&ctx->sess.offset_aad, &ctx->l_star,
  264. &ctx->sess.offset_aad);
  265. /* CipherInput = (A_* || 1 || zeros(127-bitlen(A_*))) xor Offset_* */
  266. memset(tmp.c, 0, 16);
  267. memcpy(tmp.c, aad, last_len);
  268. tmp.c[last_len] = 0x80;
  269. ocb_block16_xor(&ctx->sess.offset_aad, &tmp, &tmp);
  270. /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */
  271. ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
  272. ocb_block16_xor(&tmp, &ctx->sess.sum, &ctx->sess.sum);
  273. }
  274. ctx->sess.blocks_hashed = all_num_blocks;
  275. return 1;
  276. }
  277. /*
  278. * Provide any data to be encrypted. This can be called multiple times. Only
  279. * the final time can have a partial block
  280. */
  281. int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx,
  282. const unsigned char *in, unsigned char *out,
  283. size_t len)
  284. {
  285. u64 i, all_num_blocks;
  286. size_t num_blocks, last_len;
  287. /*
  288. * Calculate the number of blocks of data to be encrypted provided now, and
  289. * so far
  290. */
  291. num_blocks = len / 16;
  292. all_num_blocks = num_blocks + ctx->sess.blocks_processed;
  293. if (num_blocks && all_num_blocks == (size_t)all_num_blocks
  294. && ctx->stream != NULL) {
  295. size_t max_idx = 0, top = (size_t)all_num_blocks;
  296. /*
  297. * See how many L_{i} entries we need to process data at hand
  298. * and pre-compute missing entries in the table [if any]...
  299. */
  300. while (top >>= 1)
  301. max_idx++;
  302. if (ocb_lookup_l(ctx, max_idx) == NULL)
  303. return 0;
  304. ctx->stream(in, out, num_blocks, ctx->keyenc,
  305. (size_t)ctx->sess.blocks_processed + 1, ctx->sess.offset.c,
  306. (const unsigned char (*)[16])ctx->l, ctx->sess.checksum.c);
  307. } else {
  308. /* Loop through all full blocks to be encrypted */
  309. for (i = ctx->sess.blocks_processed + 1; i <= all_num_blocks; i++) {
  310. OCB_BLOCK *lookup;
  311. OCB_BLOCK tmp;
  312. /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
  313. lookup = ocb_lookup_l(ctx, ocb_ntz(i));
  314. if (lookup == NULL)
  315. return 0;
  316. ocb_block16_xor(&ctx->sess.offset, lookup, &ctx->sess.offset);
  317. memcpy(tmp.c, in, 16);
  318. in += 16;
  319. /* Checksum_i = Checksum_{i-1} xor P_i */
  320. ocb_block16_xor(&tmp, &ctx->sess.checksum, &ctx->sess.checksum);
  321. /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */
  322. ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp);
  323. ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
  324. ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp);
  325. memcpy(out, tmp.c, 16);
  326. out += 16;
  327. }
  328. }
  329. /*
  330. * Check if we have any partial blocks left over. This is only valid in the
  331. * last call to this function
  332. */
  333. last_len = len % 16;
  334. if (last_len > 0) {
  335. OCB_BLOCK pad;
  336. /* Offset_* = Offset_m xor L_* */
  337. ocb_block16_xor(&ctx->sess.offset, &ctx->l_star, &ctx->sess.offset);
  338. /* Pad = ENCIPHER(K, Offset_*) */
  339. ctx->encrypt(ctx->sess.offset.c, pad.c, ctx->keyenc);
  340. /* C_* = P_* xor Pad[1..bitlen(P_*)] */
  341. ocb_block_xor(in, pad.c, last_len, out);
  342. /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
  343. memset(pad.c, 0, 16); /* borrow pad */
  344. memcpy(pad.c, in, last_len);
  345. pad.c[last_len] = 0x80;
  346. ocb_block16_xor(&pad, &ctx->sess.checksum, &ctx->sess.checksum);
  347. }
  348. ctx->sess.blocks_processed = all_num_blocks;
  349. return 1;
  350. }
  351. /*
  352. * Provide any data to be decrypted. This can be called multiple times. Only
  353. * the final time can have a partial block
  354. */
  355. int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx,
  356. const unsigned char *in, unsigned char *out,
  357. size_t len)
  358. {
  359. u64 i, all_num_blocks;
  360. size_t num_blocks, last_len;
  361. /*
  362. * Calculate the number of blocks of data to be decrypted provided now, and
  363. * so far
  364. */
  365. num_blocks = len / 16;
  366. all_num_blocks = num_blocks + ctx->sess.blocks_processed;
  367. if (num_blocks && all_num_blocks == (size_t)all_num_blocks
  368. && ctx->stream != NULL) {
  369. size_t max_idx = 0, top = (size_t)all_num_blocks;
  370. /*
  371. * See how many L_{i} entries we need to process data at hand
  372. * and pre-compute missing entries in the table [if any]...
  373. */
  374. while (top >>= 1)
  375. max_idx++;
  376. if (ocb_lookup_l(ctx, max_idx) == NULL)
  377. return 0;
  378. ctx->stream(in, out, num_blocks, ctx->keydec,
  379. (size_t)ctx->sess.blocks_processed + 1, ctx->sess.offset.c,
  380. (const unsigned char (*)[16])ctx->l, ctx->sess.checksum.c);
  381. } else {
  382. OCB_BLOCK tmp;
  383. /* Loop through all full blocks to be decrypted */
  384. for (i = ctx->sess.blocks_processed + 1; i <= all_num_blocks; i++) {
  385. /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
  386. OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
  387. if (lookup == NULL)
  388. return 0;
  389. ocb_block16_xor(&ctx->sess.offset, lookup, &ctx->sess.offset);
  390. memcpy(tmp.c, in, 16);
  391. in += 16;
  392. /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */
  393. ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp);
  394. ctx->decrypt(tmp.c, tmp.c, ctx->keydec);
  395. ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp);
  396. /* Checksum_i = Checksum_{i-1} xor P_i */
  397. ocb_block16_xor(&tmp, &ctx->sess.checksum, &ctx->sess.checksum);
  398. memcpy(out, tmp.c, 16);
  399. out += 16;
  400. }
  401. }
  402. /*
  403. * Check if we have any partial blocks left over. This is only valid in the
  404. * last call to this function
  405. */
  406. last_len = len % 16;
  407. if (last_len > 0) {
  408. OCB_BLOCK pad;
  409. /* Offset_* = Offset_m xor L_* */
  410. ocb_block16_xor(&ctx->sess.offset, &ctx->l_star, &ctx->sess.offset);
  411. /* Pad = ENCIPHER(K, Offset_*) */
  412. ctx->encrypt(ctx->sess.offset.c, pad.c, ctx->keyenc);
  413. /* P_* = C_* xor Pad[1..bitlen(C_*)] */
  414. ocb_block_xor(in, pad.c, last_len, out);
  415. /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
  416. memset(pad.c, 0, 16); /* borrow pad */
  417. memcpy(pad.c, out, last_len);
  418. pad.c[last_len] = 0x80;
  419. ocb_block16_xor(&pad, &ctx->sess.checksum, &ctx->sess.checksum);
  420. }
  421. ctx->sess.blocks_processed = all_num_blocks;
  422. return 1;
  423. }
  424. static int ocb_finish(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len,
  425. int write)
  426. {
  427. OCB_BLOCK tmp;
  428. if (len > 16 || len < 1) {
  429. return -1;
  430. }
  431. /*
  432. * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
  433. */
  434. ocb_block16_xor(&ctx->sess.checksum, &ctx->sess.offset, &tmp);
  435. ocb_block16_xor(&ctx->l_dollar, &tmp, &tmp);
  436. ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
  437. ocb_block16_xor(&tmp, &ctx->sess.sum, &tmp);
  438. if (write) {
  439. memcpy(tag, &tmp, len);
  440. return 1;
  441. } else {
  442. return CRYPTO_memcmp(&tmp, tag, len);
  443. }
  444. }
  445. /*
  446. * Calculate the tag and verify it against the supplied tag
  447. */
  448. int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag,
  449. size_t len)
  450. {
  451. return ocb_finish(ctx, (unsigned char*)tag, len, 0);
  452. }
  453. /*
  454. * Retrieve the calculated tag
  455. */
  456. int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len)
  457. {
  458. return ocb_finish(ctx, tag, len, 1);
  459. }
  460. /*
  461. * Release all resources
  462. */
  463. void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx)
  464. {
  465. if (ctx) {
  466. OPENSSL_clear_free(ctx->l, ctx->max_l_index * 16);
  467. OPENSSL_cleanse(ctx, sizeof(*ctx));
  468. }
  469. }
  470. #endif /* OPENSSL_NO_OCB */