2
0

bn_ctx.c 9.6 KB

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