control stack memory allocation

[vladak]

The C functions produced by Karamel do not constrain memory allocation as far as I know. For example, the Hacl_P521.c file produced by HACL and used by Mozilla NSS contains various large stack allocations. In my environment, the resulting x64 object file contains multi-kilobyte sized stack allocations (e.g. the p521_qinv() function requests ~7.6 kibibytes) and the default maximum stack size in this environment is 20 KiB and cannot be changed on the fly. Running the HACL ECC code (e.g. ECDSA verify operation) in such environment leads to stack exhaustion.

Ideally, it would be nice to be able to switch to heap based allocation above given threshold, where possible. This would require the corresponding freeing of the resources, however looking at the biggest stack space consumers in the above referenced file this is doable, at least in some of the places. Not sure about the side channels.

[msprotz]

@karthikbhargavan you've been working on P-curves, any chance the stack consumption can be improved?
@vladak is there any large allocation somewhere that causes the stack to increase dramatically or is it a lot of small allocations?

[vladak]

It is actually both types. Some of the functions contain large tables (e.g. uint64_t table[288U] in p521_qinv() and such), sometimes the stack space compounds (like in the case of smaller allocations performed by the various functions inlined e.g. to point_add()). In the latter case the threshold would not help. The only way I can think of is to disable the inlining for the smaller functions (fadd0 and such), however I am not sure what is the security cost of this.