OpenSSL BN_CTX usage

Question

From here I understand that BN_CTX is a structure that holds BIGNUM temporary variables. When will those BIGNUM variables enter BN_CTX's BN_POOL? If I have a bignum_ctx BN_CTX *ctx (either declared at the top of my function, or passed in as an argument), when should I do

ctx = BN_CTX_new();
/* Do something */
BN_CTX_free(ctx);

and when should I do the following instead?

BN_CTX_start(ctx);
/* Do something */
BN_CTX_end(ctx);

And if I have a bignum BIGNUM *bn, in what circumstances should I use

BN_CTX_start(ctx);
bn = BN_CTX_get(ctx);
BN_CTX_end(ctx);

instead of just new and free the instance?

bn = BN_new();
if (bn)
    BN_free(bn);

Uncle

Answer 1

Here I am answering my own question. I guess it happens all the time in SO.

BIGNUM in OpenSSL is a complicated structure that holds an arbitrarily big number, and hence creating and freeing BIGNUM instances repeatedly will result in a considerable overhead. BIGNUM context, or BN_CTX, is created and used to save this overhead.

Structure

The BN_CTX structure contains two structures: BN_POOL and BN_STACK. The BN_POOL keeps a bundle of temporary bignums with a linked-list, while the BN_STACK manages the stack frame.

On Create

A BN_CTX instance ctx is created with BN_CTX_new(). A function must call BN_CTX_start() to get a new stack frame first. By calling BN_CTX_get(ctx), OpenSSL looks for an unused bignum in the BN_POOL of ctx. If there isn't any available temp bignum, OpenSSL will create one and link to the linked-list. This must be done before passing ctx as argument to other functions.

Of course there's a mechanism for preventing user creating too many temporary bignums. The predefined number of bignums you can create within a BN_POOL is 16. Once the limit is exceeded, probable segmentation fault will occur at random location in OpenSSL library.

On Exit

After the function is done with the BIGNUM instance it got from ctx and is ready to exit, BN_CTX_end() is called to release temporary bignums, meaning that these bignums become "unused" and can be requested by the next BN_CTX_get().

Finally, probably after several times of BN_CTX_start() and BN_CTX_end(), BN_CTX_end() is called to free BN_STACK structure, and clear free bignums in BN_POOL.

Example Code

void foo(){
    BN_CTX* ctx;
    ctx = BN_CTX_new();

    /* Using BIGNUM context in a series of BIGNUM operations */
    bar(ctx);
    bar(ctx);
    bar(ctx);

    /* Using BIGNUM context in a function called in loops */
    while(/*condition*/){
        bar(ctx);
    }

    BN_CTX_free(ctx);
}

And here's the function bar( )

void bar(BN_CTX* ctx){
    BIGNUM *bn;
    BN_CTX_start(ctx);
    bn = BN_CTX_get(ctx);

    /* Do something with bn */

    BN_CTX_end(ctx);
}

The function foo() creates a new BIGNUM context and pass it as argument to function bar(). Upon the first time bar() calls BN_CTX_get(), a temporary bignum is created and stored in the BN_POOL and is returned. BN_CTX_get() in the subsequent bar() will not create new bignum but instead returns the one it created in the first place. This temporary bignum will finally be clear-freed by BN_CTX_free() in foo().

Conclusion

When performance is in concern, use BN_CTX to save the overhead of BIGNUM creation by passing it to functions that

1. require BIGNUM structures to hold temporary big numbers, and
2. are called sequentially to perform certain bignum operations, or
3. are repeatedly called in loops.

Be aware that there is a limitation for the number of bignums stored in BN_CTX. If performance is not an issue, then using

bn = BN_new();
if (bn)
    BN_free(bn);

is just fine.

Uncle

What's the stack frame for? – Raynata

Since a BN_CTX object ctx can be pass from functions to functions, stack frame is a bunch of information used to track the depth of these function calls(which pass ctx as argument), and the size of the memory allocated to ctx. – Uncle

I guess it is for releasing tmp variables function by function. If there is a function uses two tmp BIGNUMs bn1 = BN_CTX_get(ctx); bn2 = BN_CTX_get(ctx); There is no way (to me) to release bn1 but not bn2. They can only be released together on BN_CTX_end. The stack frame information is to remember this function is using two tmps bn1 and bn2, I guess. – Raynata

I think you're right. Stack frame keeps the number of bignums assigned to this ctx. – Uncle