Optimize HACL* Raw RSA Encryption to use non-constant-time operations.

Question

franziskuskiefer opened this issue 8 months ago · 9 comments

Answer 1 · 2024-05-06T07:53:12.000Z

PR coming for HACL this week.

Answer 2 · 2024-05-13T06:56:02.000Z

Did not manage to get this done last week. This week is the target (for sure this time!)

Answer 3 · 2024-05-22T06:40:42.000Z

Finally made good progress on this, after many disproved hypotheses.
Now, we have a 2-3x perf improvement.

Answer 4 · 2024-05-27T03:36:43.000Z

Made the modifications, now looking into CRT decryption before sending to CF

Answer 5 · 2024-06-03T05:33:36.000Z

Tested on multiple platforms and compilers.

Some observations:

compiling with gcc on x64 does not appear to enable HACL_CAN_COMPILE_INTRINSICS in lib_intrinsics.h, leading to a performance degradation. enabling this flag provides a significant boos.
optimizing at -O2 (like the Linux Kernel) vs -O3 does not make much difference to this code
recent GCCs (e.g. 13) are better at optimizing this code than GCC-11
recent clang is still about 10-15% faster than recent GCC
the optimizations that work differ for x64 and ARM likely because of the difference in mul instructions and pipelining
with targeted optimizations for ARM our enc code is within 10-20% of optimized OpenSSL assembly on M1 Max
with intrinsics for x64, our code is within 75-90% of optimized OpenSSL on core i7

Answer 6 · 2024-06-03T05:42:27.000Z

Next steps: Send update to CF by June 5th on status and plans.

Answer 7 · 2024-06-24T07:52:01.000Z

Next steps: push upstream to HACL and to consumers

Answer 8 · 2024-07-28T14:08:12.000Z

This will only get done later in August, after ML-KEM proofs are in shape.