have you seen the np = alloca(top * sizeof(BN_ULONG)); down below ?

heh, no. Now that is SPARC only code. Not sure what to do with that. Change it to OPENSSL_malloc() for some value of top? Can be a separate PR.

Could we solve this differently, like when the modulus size is larger than RSA_MAX_MODULUS then ignore the constant time flag, since that large numbers are usually just used for denial of service attacks?

I mean the non-constant time code will be orders of magnitude faster than this, and will not have these alloca problem.

Yeah, that is a good idea.

If you're concerned about the alloca, note that bn_mul_mont itself, used also by BN_mod_exp_mont, internally does a similar alloca, hidden away in assembly. It may be worth just cutting down the largest BIGNUM a little. (I'll probably go that route in BoringSSL.)

If we do that, this actually won't be able to overflow. The largest BIGNUM is capped here. It's INT_MAX / (4 * BN_BITS2) words, or INT_MAX / 4 bits, or INT_MAX / 32 bytes, or 64MiB.

Scrolling down, powerbufLen increases from two places, a top * sizeof(mont->N.d[0]) term (which, if it happens, forces window to 5), and the more complex term:

    powerbufLen += sizeof(m->d[0]) * (top * numPowers +
                                      ((2 * top) >
                                       numPowers ? (2 * top) : numPowers));

(Incidentally, I believe the (2 * top) > numPowers ? (2 * top) : numPowers bit is a remnant of older versions of mont5 which used to overread the table by one row. Unreasonably clever scheduling. It no longer does this and probably can be replaced with 2 * top now, though I haven't carefully analyzed all the files in OpenSSL, just the subset we have.)

numPowers is at most 64, so we're looking at 64 BIGNUMs, plus change, or a bit over 4GiB. That won't fit in int, but it's close enough that we don't need to bring it down too much further to make it always fit.

It may be worth just cutting down the largest BIGNUM a little. (I'll probably go that route in BoringSSL.)

Update: this almost works, except we found one project that relies on making 8MiB bignums, and some others that needed 32-64KiB. 32-64KiB is plausible to alloca, but 8MiB is too much. So we're probably going to apply the cap Montgomery moduli instead.

Hmm, isn't a kernel task stack just 64 K large?

Hmm yeah that's possibly also a bit large. Regardless, the 8MiB one means solving it with a bn-wide limit doesn't seem viable for us. My plan was to do a 8KiB limit in BN_MONT_CTX, which is enough for the maximum of all our cryptographic primitives, with a little additional leeway. (The callers that needed 32-64KiB also don't use Montgomery reduction.)

Take a look at #19735 is that acceptable, or did I miss something?

Given this depends on BN_window_bits_for_ctime_exponent_size, perhaps this should be based on BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE.

If you're concerned about the alloca, note that bn_mul_mont itself, used also by BN_mod_exp_mont, internally does a similar alloca, hidden away in assembly. It may be worth just cutting down the largest BIGNUM a little. (I'll probably go that route in BoringSSL.)

If we do that, this actually won't be able to overflow. The largest BIGNUM is capped here. It's INT_MAX / (4 * BN_BITS2) words, or INT_MAX / 4 bits, or INT_MAX / 32 bytes, or 64MiB.

Scrolling down, powerbufLen increases from two places, a top * sizeof(mont->N.d[0]) term (which, if it happens, forces window to 5), and the more complex term:

    powerbufLen += sizeof(m->d[0]) * (top * numPowers +
                                      ((2 * top) >
                                       numPowers ? (2 * top) : numPowers));

(Incidentally, I believe the (2 * top) > numPowers ? (2 * top) : numPowers bit is a remnant of older versions of mont5 which used to overread the table by one row. Unreasonably clever scheduling. It no longer does this and probably can be replaced with 2 * top now, though I haven't carefully analyzed all the files in OpenSSL, just the subset we have.)

numPowers is at most 64, so we're looking at 64 BIGNUMs, plus change, or a bit over 4GiB. That won't fit in int, but it's close enough that we don't need to bring it down too much further to make it always fit.