2
0

bn_ctx.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364
  1. /*
  2. * Copyright 2000-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 <openssl/trace.h>
  10. #include "internal/cryptlib.h"
  11. #include "bn_local.h"
  12. /* How many bignums are in each "pool item"; */
  13. #define BN_CTX_POOL_SIZE 16
  14. /* The stack frame info is resizing, set a first-time expansion size; */
  15. #define BN_CTX_START_FRAMES 32
  16. /***********/
  17. /* BN_POOL */
  18. /***********/
  19. /* A bundle of bignums that can be linked with other bundles */
  20. typedef struct bignum_pool_item {
  21. /* The bignum values */
  22. BIGNUM vals[BN_CTX_POOL_SIZE];
  23. /* Linked-list admin */
  24. struct bignum_pool_item *prev, *next;
  25. } BN_POOL_ITEM;
  26. /* A linked-list of bignums grouped in bundles */
  27. typedef struct bignum_pool {
  28. /* Linked-list admin */
  29. BN_POOL_ITEM *head, *current, *tail;
  30. /* Stack depth and allocation size */
  31. unsigned used, size;
  32. } BN_POOL;
  33. static void BN_POOL_init(BN_POOL *);
  34. static void BN_POOL_finish(BN_POOL *);
  35. static BIGNUM *BN_POOL_get(BN_POOL *, int);
  36. static void BN_POOL_release(BN_POOL *, unsigned int);
  37. /************/
  38. /* BN_STACK */
  39. /************/
  40. /* A wrapper to manage the "stack frames" */
  41. typedef struct bignum_ctx_stack {
  42. /* Array of indexes into the bignum stack */
  43. unsigned int *indexes;
  44. /* Number of stack frames, and the size of the allocated array */
  45. unsigned int depth, size;
  46. } BN_STACK;
  47. static void BN_STACK_init(BN_STACK *);
  48. static void BN_STACK_finish(BN_STACK *);
  49. static int BN_STACK_push(BN_STACK *, unsigned int);
  50. static unsigned int BN_STACK_pop(BN_STACK *);
  51. /**********/
  52. /* BN_CTX */
  53. /**********/
  54. /* The opaque BN_CTX type */
  55. struct bignum_ctx {
  56. /* The bignum bundles */
  57. BN_POOL pool;
  58. /* The "stack frames", if you will */
  59. BN_STACK stack;
  60. /* The number of bignums currently assigned */
  61. unsigned int used;
  62. /* Depth of stack overflow */
  63. int err_stack;
  64. /* Block "gets" until an "end" (compatibility behaviour) */
  65. int too_many;
  66. /* Flags. */
  67. int flags;
  68. /* The library context */
  69. OSSL_LIB_CTX *libctx;
  70. };
  71. #ifndef FIPS_MODULE
  72. /* Debugging functionality */
  73. static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx)
  74. {
  75. unsigned int bnidx = 0, fpidx = 0;
  76. BN_POOL_ITEM *item = ctx->pool.head;
  77. BN_STACK *stack = &ctx->stack;
  78. BIO_printf(channel, "%s\n", text);
  79. BIO_printf(channel, " (%16p): ", (void*)ctx);
  80. while (bnidx < ctx->used) {
  81. BIO_printf(channel, "%03x ",
  82. item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
  83. if (!(bnidx % BN_CTX_POOL_SIZE))
  84. item = item->next;
  85. }
  86. BIO_printf(channel, "\n");
  87. bnidx = 0;
  88. BIO_printf(channel, " %16s : ", "");
  89. while (fpidx < stack->depth) {
  90. while (bnidx++ < stack->indexes[fpidx])
  91. BIO_printf(channel, " ");
  92. BIO_printf(channel, "^^^ ");
  93. bnidx++;
  94. fpidx++;
  95. }
  96. BIO_printf(channel, "\n");
  97. }
  98. # define CTXDBG(str, ctx) \
  99. OSSL_TRACE_BEGIN(BN_CTX) { \
  100. ctxdbg(trc_out, str, ctx); \
  101. } OSSL_TRACE_END(BN_CTX)
  102. #else
  103. /* We do not want tracing in FIPS module */
  104. # define CTXDBG(str, ctx) do {} while(0)
  105. #endif /* FIPS_MODULE */
  106. BN_CTX *BN_CTX_new_ex(OSSL_LIB_CTX *ctx)
  107. {
  108. BN_CTX *ret;
  109. if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
  110. return NULL;
  111. /* Initialise the structure */
  112. BN_POOL_init(&ret->pool);
  113. BN_STACK_init(&ret->stack);
  114. ret->libctx = ctx;
  115. return ret;
  116. }
  117. #ifndef FIPS_MODULE
  118. BN_CTX *BN_CTX_new(void)
  119. {
  120. return BN_CTX_new_ex(NULL);
  121. }
  122. #endif
  123. BN_CTX *BN_CTX_secure_new_ex(OSSL_LIB_CTX *ctx)
  124. {
  125. BN_CTX *ret = BN_CTX_new_ex(ctx);
  126. if (ret != NULL)
  127. ret->flags = BN_FLG_SECURE;
  128. return ret;
  129. }
  130. #ifndef FIPS_MODULE
  131. BN_CTX *BN_CTX_secure_new(void)
  132. {
  133. return BN_CTX_secure_new_ex(NULL);
  134. }
  135. #endif
  136. void BN_CTX_free(BN_CTX *ctx)
  137. {
  138. if (ctx == NULL)
  139. return;
  140. #ifndef FIPS_MODULE
  141. OSSL_TRACE_BEGIN(BN_CTX) {
  142. BN_POOL_ITEM *pool = ctx->pool.head;
  143. BIO_printf(trc_out,
  144. "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n",
  145. ctx->stack.size, ctx->pool.size);
  146. BIO_printf(trc_out, " dmaxs: ");
  147. while (pool) {
  148. unsigned loop = 0;
  149. while (loop < BN_CTX_POOL_SIZE)
  150. BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax);
  151. pool = pool->next;
  152. }
  153. BIO_printf(trc_out, "\n");
  154. } OSSL_TRACE_END(BN_CTX);
  155. #endif
  156. BN_STACK_finish(&ctx->stack);
  157. BN_POOL_finish(&ctx->pool);
  158. OPENSSL_free(ctx);
  159. }
  160. void BN_CTX_start(BN_CTX *ctx)
  161. {
  162. CTXDBG("ENTER BN_CTX_start()", ctx);
  163. /* If we're already overflowing ... */
  164. if (ctx->err_stack || ctx->too_many)
  165. ctx->err_stack++;
  166. /* (Try to) get a new frame pointer */
  167. else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
  168. ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
  169. ctx->err_stack++;
  170. }
  171. CTXDBG("LEAVE BN_CTX_start()", ctx);
  172. }
  173. void BN_CTX_end(BN_CTX *ctx)
  174. {
  175. if (ctx == NULL)
  176. return;
  177. CTXDBG("ENTER BN_CTX_end()", ctx);
  178. if (ctx->err_stack)
  179. ctx->err_stack--;
  180. else {
  181. unsigned int fp = BN_STACK_pop(&ctx->stack);
  182. /* Does this stack frame have anything to release? */
  183. if (fp < ctx->used)
  184. BN_POOL_release(&ctx->pool, ctx->used - fp);
  185. ctx->used = fp;
  186. /* Unjam "too_many" in case "get" had failed */
  187. ctx->too_many = 0;
  188. }
  189. CTXDBG("LEAVE BN_CTX_end()", ctx);
  190. }
  191. BIGNUM *BN_CTX_get(BN_CTX *ctx)
  192. {
  193. BIGNUM *ret;
  194. CTXDBG("ENTER BN_CTX_get()", ctx);
  195. if (ctx->err_stack || ctx->too_many)
  196. return NULL;
  197. if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) {
  198. /*
  199. * Setting too_many prevents repeated "get" attempts from cluttering
  200. * the error stack.
  201. */
  202. ctx->too_many = 1;
  203. ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
  204. return NULL;
  205. }
  206. /* OK, make sure the returned bignum is "zero" */
  207. BN_zero(ret);
  208. /* clear BN_FLG_CONSTTIME if leaked from previous frames */
  209. ret->flags &= (~BN_FLG_CONSTTIME);
  210. ctx->used++;
  211. CTXDBG("LEAVE BN_CTX_get()", ctx);
  212. return ret;
  213. }
  214. OSSL_LIB_CTX *ossl_bn_get_libctx(BN_CTX *ctx)
  215. {
  216. if (ctx == NULL)
  217. return NULL;
  218. return ctx->libctx;
  219. }
  220. /************/
  221. /* BN_STACK */
  222. /************/
  223. static void BN_STACK_init(BN_STACK *st)
  224. {
  225. st->indexes = NULL;
  226. st->depth = st->size = 0;
  227. }
  228. static void BN_STACK_finish(BN_STACK *st)
  229. {
  230. OPENSSL_free(st->indexes);
  231. st->indexes = NULL;
  232. }
  233. static int BN_STACK_push(BN_STACK *st, unsigned int idx)
  234. {
  235. if (st->depth == st->size) {
  236. /* Need to expand */
  237. unsigned int newsize =
  238. st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES;
  239. unsigned int *newitems;
  240. if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL)
  241. return 0;
  242. if (st->depth)
  243. memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth);
  244. OPENSSL_free(st->indexes);
  245. st->indexes = newitems;
  246. st->size = newsize;
  247. }
  248. st->indexes[(st->depth)++] = idx;
  249. return 1;
  250. }
  251. static unsigned int BN_STACK_pop(BN_STACK *st)
  252. {
  253. return st->indexes[--(st->depth)];
  254. }
  255. /***********/
  256. /* BN_POOL */
  257. /***********/
  258. static void BN_POOL_init(BN_POOL *p)
  259. {
  260. p->head = p->current = p->tail = NULL;
  261. p->used = p->size = 0;
  262. }
  263. static void BN_POOL_finish(BN_POOL *p)
  264. {
  265. unsigned int loop;
  266. BIGNUM *bn;
  267. while (p->head) {
  268. for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++)
  269. if (bn->d)
  270. BN_clear_free(bn);
  271. p->current = p->head->next;
  272. OPENSSL_free(p->head);
  273. p->head = p->current;
  274. }
  275. }
  276. static BIGNUM *BN_POOL_get(BN_POOL *p, int flag)
  277. {
  278. BIGNUM *bn;
  279. unsigned int loop;
  280. /* Full; allocate a new pool item and link it in. */
  281. if (p->used == p->size) {
  282. BN_POOL_ITEM *item;
  283. if ((item = OPENSSL_malloc(sizeof(*item))) == NULL)
  284. return NULL;
  285. for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) {
  286. bn_init(bn);
  287. if ((flag & BN_FLG_SECURE) != 0)
  288. BN_set_flags(bn, BN_FLG_SECURE);
  289. }
  290. item->prev = p->tail;
  291. item->next = NULL;
  292. if (p->head == NULL)
  293. p->head = p->current = p->tail = item;
  294. else {
  295. p->tail->next = item;
  296. p->tail = item;
  297. p->current = item;
  298. }
  299. p->size += BN_CTX_POOL_SIZE;
  300. p->used++;
  301. /* Return the first bignum from the new pool */
  302. return item->vals;
  303. }
  304. if (!p->used)
  305. p->current = p->head;
  306. else if ((p->used % BN_CTX_POOL_SIZE) == 0)
  307. p->current = p->current->next;
  308. return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
  309. }
  310. static void BN_POOL_release(BN_POOL *p, unsigned int num)
  311. {
  312. unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
  313. p->used -= num;
  314. while (num--) {
  315. bn_check_top(p->current->vals + offset);
  316. if (offset == 0) {
  317. offset = BN_CTX_POOL_SIZE - 1;
  318. p->current = p->current->prev;
  319. } else
  320. offset--;
  321. }
  322. }