Open randombit opened 2 months ago
We should consider compile time configuration of which curves get instantiated (as pointed out here). Much like the compile-time configuration of having "kyber" and/or "kyber_90s", for instance.
Adding one build module per curve should do the trick, and probably provides the best affordance for users. On the other hand, it produces quite a bit of boilerplate due to subdirectories, info.txt
files and code machinery.
Alternatively, I could see this as a dedicated compile-time switch: Like:
./configure.py --enable-elliptic-curves=all
(the default)./configure.py --enable-elliptic-curves=p256,brainpool256
(a restricted set)and then simply #ifdef
the instantiations in pcurves.cpp
accordingly.
The --enable-elliptic-curves
approach is potentially confusing since even if you disable the pcurves module entirely, the elliptic curves still exist. All that ends up happening is you fall back to the slower BigInt code. [*]
[*] I mean right now ECDSA etc still use BigInt, even after both #3979 and #4042 land. There are several more steps here until the whole thing hangs together. But in the end state, we'll have fast ECC for specific curves, plus fallback code for weird curves, application curves, etc. If you disable the fast curve, it doesn't disable the curve, just disables it going fast.
That said there may be environments where the code size becomes an issue. I tried out a module per curve and it was not so bad. There are likely to not be more than ~5 new curves added here over time so I don't think it's an issue in an ongoing way.
In the end we could consider also having a way of disabling the slowpath BigInt stuff, which would benefit environments that are using just P-256 or something.
Nice! I saw that you split the curve into compile-time modules. Indeed the boilerplate isn't so bad. Also provides a nice place to keep curve-specific special cases. :+1:
I added a few minor suggestions, in which the type -> "Internal"
might need some extra attention. Perhaps have a new module type "Feature" (which might also be better suited for "Kyber" vs. "Kyber90s", and similar situations...)?
Botan 3.5.0
In this release pcurves is really just used for hash to curve
EC_Scalar
andEC_AffinePoint
types and implement algorithms using them #4042BigInt
, egmod_sub
,ct_reduce_below
, many more.Botan 3.6.0
In this release, we tie together
EC_Scalar
/EC_AffinePoint
to pcurves so that everything goes fast :rocket:EC_Scalar
/EC_AffinePoint
and pcurves (#4143)EC_Scalar
version to avoidEC_Scalar<->BigInt
conversions. (Now in #4042)EC_Scalar
andEC_AffinePoint
instead ofBigInt
/EC_Point
Botan 3.6.0 or later. Nice optimizations / cleanups but not critical
mul2_vartime
. Based on some reading and experimentation best option for parameters of our size is a wNAF with w==4 which should hit on average 80% dual 0s and requiring a table of 80 group elements.