Closed tarcieri closed 10 months ago
Currently
num-traits
is only indev-dependencies
.As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the
rsa
crate to use eithercrypto-bigint
ornum-bigint-dig
.Though
num-traits
probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.
Is the absence of num-traits
the reason for not using crypto-bigint in rsa
, k256
etc.?
I am now compiling a list of all dependencies for the MPC project I am building, and obviously a bigint library is a prerequisite for many higher-level primitives (like the actual group code, for both Paillier and the elliptic curves k256
, ed25519
etc. that I need).
I am very careful in my analysis, as for me it is important to know exactly the building blocks both theory and implementation wise. It is important for me to not have duplication, so e.g. relying on both crypto-bigint and num-bigint is something I'd go a long way to avoid. There is enough attack surface as it is, I don't want to be exposed to double the attack surface.
Now, regarding choosing which bigint library to use, crypto-bigint seemed the obvious choice for me:
k256
, and the hash functions, and maybe other tools). But finding out crypto-bigint
isn't even used internally within RustCrypto made me wonder how production-ready it is, and what was the reasons behind you choosing to work with num-bigint
(is it purely for historical reasons? num-bigint was ready before crypto-bigint was, and you need to do the switch now? will supporting num-traits
allow that transition?)
Thanks
Is the absence of num-traits the reason for not using crypto-bigint in
rsa
,k256
etc.?
k256
uses it via the elliptic-curve
crate, at least using Uint
for the internal Scalar
implementation. The base field implementations in k256
use unsaturated limbs, so retrofitting it into the existing arithmetic is somewhat problematic.
All of the other elliptic curve libraries we maintain (e.g. p256
, p384
) use it for both the scalar and field implementations, although that's generally leveraging purpose-dedicated field arithmetic on saturated limbs, either implemented specific to a particular modulus or synthesized via fiat-crypto
. Support for Montgomery form in crypto-bigint
(i.e. Residue
) is relatively new, shipping in v0.5.0 about a month ago, and we haven't attempted migrating yet.
crypto-bigint
has 10 million downloads largely due to its use in the elliptic-curve
crate and all of its downstream consumers.
The reason rsa
(and dsa
) don't use it is lack of heap-backed integers, which are needed to accommodate the widely varying key sizes used by these algorithms (as opposed to monomorphizing for multiple key sizes, or only monomorphizing for the largest supported key size and bailing out for slower ones).
It's something we plan to add but just haven't had time for.
It would be nice to be able to use traits to abstract between stack and heap-based big integers, so RSA and DSA can be implemented generically and the stack-based big integers used on heapless platforms.
Is the absence of num-traits the reason for not using crypto-bigint in
rsa
,k256
etc.?
k256
uses it via theelliptic-curve
crate, at least usingUint
for the internalScalar
implementation. The base field implementations ink256
use unsaturated limbs, so retrofitting it into the existing arithmetic is somewhat problematic.All of the other elliptic curve libraries we maintain (e.g.
p256
,p384
) use it for both the scalar and field implementations, although that's generally leveraging purpose-dedicated field arithmetic on saturated limbs, either implemented specific to a particular modulus or synthesized viafiat-crypto
. Support for Montgomery form incrypto-bigint
(i.e.Residue
) is relatively new, shipping in v0.5.0 about a month ago, and we haven't attempted migrating yet.
crypto-bigint
has 10 million downloads largely due to its use in theelliptic-curve
crate and all of its downstream consumers.The reason
rsa
(anddsa
) don't use it is lack of heap-backed integers, which are needed to accommodate the widely varying key sizes used by these algorithms (as opposed to monomorphizing for multiple key sizes, or only monomorphizing for the largest supported key size and bailing out for slower ones).It's something we plan to add but just haven't had time for.
It would be nice to be able to use traits to abstract between stack and heap-based big integers, so RSA and DSA can be implemented generically and the stack-based big integers used on heapless platforms.
Thanks for the detailed reply, however I was left even more confused because an apparent lack of knowledge on my side, I'd love if you'll clarify:
BigInt
object, or also for U256
etc.?Thank you very much
what are saturated and unsaturated limbs?
Some bigint libraries do not use all of the bits of a limb. This is an unsaturated representation. There are a few different reasons for this: sometimes the unsaturated implementation can be more efficient, especially when leveraging e.g. special properties of the field modulus.
However, one of the most common reasons was better carry handling. Unsaturated representations could use part of a limb represent carry bits. The need for this has largely been obviated by using machine instructions which provide access to the carry bit, like add-and-carry (ADC), subtraction-with-borrow (SBB), and multiply-and-carry (MAC), all of which are emitted by crypto-bigint
on x86/x86_64 when using a saturated representation.
what do you mean by monomorphizing for a key size?
The size of a Uint
is a const generic parameter, and thus determined at compile time.
With RSA, it'd be nice to use a 2048-bit Uint for 2048-bit keys, and a 4096-bit Uint for 4096-bit keys. In other words: to pick the number of limbs on the fly at runtime to match the key size.
Without a heap, the best you could do is having an enum over a U2048
, U4096
, and possibly others. This monomorphizes the arithmetic implementations specific to each size. Great for efficiency, less so for code bloat.
Heap-backed integers would allow dynamic sizes, reusing the same code regardless of the size, at the cost of efficiency.
with Montgomery support in crypto-bigint, what can change?
We could potentially use Residue
as the internal type of various field elements, replacing various modulus-specific arithmetic implementations.
which code is now generated via fiat-crypto?
The arithmetic operations on the base and scalar fields for p224
, p384
, and p521
are all generated via fiat-crypto
. We'll likely extend that to p192
, bp256
, and bp384
at some point too.
and how do you imagine num-traits support in crypto-bigint? Is that for the generic BigInt object, or also for U256 etc.?
Hopefully a generic implementation would work for all Uint
regardless of the size.
what are saturated and unsaturated limbs?
Some bigint libraries do not use all of the bits of a limb. This is an unsaturated representation. There are a few different reasons for this: sometimes the unsaturated implementation can be more efficient, especially when leveraging e.g. special properties of the field modulus.
However, one of the most common reasons was better carry handling. Unsaturated representations could use part of a limb represent carry bits. The need for this has largely been obviated by using machine instructions which provide access to the carry bit, like add-and-carry (ADC), subtraction-with-borrow (SBB), and multiply-and-carry (MAC), all of which are emitted by
crypto-bigint
on x86/x86_64 when using a saturated representation.what do you mean by monomorphizing for a key size?
The size of a
Uint
is a const generic parameter, and thus determined at compile time.With RSA, it'd be nice to use a 2048-bit Uint for 2048-bit keys, and a 4096-bit Uint for 4096-bit keys. In other words: to pick the number of limbs on the fly at runtime to match the key size.
Without a heap, the best you could do is having an enum over a
U2048
,U4096
, and possibly others. This monomorphizes the arithmetic implementations specific to each size. Great for efficiency, less so for code bloat.Heap-backed integers would allow dynamic sizes, reusing the same code regardless of the size, at the cost of efficiency.
with Montgomery support in crypto-bigint, what can change?
We could potentially use
Residue
as the internal type of various field elements, replacing various modulus-specific arithmetic implementations.which code is now generated via fiat-crypto?
The arithmetic operations on the base and scalar fields for
p224
,p384
, andp521
are all generated viafiat-crypto
. We'll likely extend that top192
,bp256
, andbp384
at some point too.and how do you imagine num-traits support in crypto-bigint? Is that for the generic BigInt object, or also for U256 etc.?
Hopefully a generic implementation would work for all
Uint
regardless of the size.
Wow, that's an amazing answer.
I'll take a deeper look at Residue
and num-traits
with these new understandings.
One thing however, why use fiat-crypto
in several libraries and not others?
Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto
?
One thing however, why use fiat-crypto in several libraries and not others?
The libraries that don't use fiat-crypto have handwritten field arithmetic implementations which outperform the fiat-crypto synthesized code, namely k256
and p256
.
k256
in particular supports lazy normalization which helps performance significantly. To my knowledge this is only supported in fiat-crypto
for fields modulo Solinas primes.
Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto?
What would it be generic around? The modulus? (like Residue
?)
fiat-crypto
takes the field modulus as input, and generates code specific to that modulus. It doesn't have support for generic parameters in the synthesized implementations.
One thing however, why use fiat-crypto in several libraries and not others?
The libraries that don't use fiat-crypto have handwritten field arithmetic implementations which outperform the fiat-crypto synthesized code, namely
k256
andp256
.
k256
in particular supports lazy normalization which helps performance significantly. To my knowledge this is only supported infiat-crypto
for fields modulo Solinas primes.Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto?
What would it be generic around? The modulus? (like
Residue
?)
fiat-crypto
takes the field modulus as input, and generates code specific to that modulus. It doesn't have support for generic parameters in the synthesized implementations.
Sorry that was a problem in my wording. What I meant by generic is that it is not special-purpose for e.g. a specific curve but just a standard 128,256,2024,2048,4096 etc. bits long.
I guess that won't suffice for elliptic curves because they are not really using u256 but a ~256-bit (prime sometimes) modulos right?
Also, from your questions there seems to be a tradeoff between performance and security here? if you want the formal security grantees of fiat-crypto, you lose a little on performance?
fiat-crypto
synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.
There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.
Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.
fiat-crypto
synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.
Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.
I definitely am on the other side, and if formal verification is possible it is worth performance penalties. Esp when performance optimizations in these fields tend to be a factor under 2, at least from what I've seen so far.
However, from a brief look on fiat-crypto it seems that the Rust generated code isn't formally verified (no proof).
Also, I'm not sure what are the guarantees fiat-crypto formally proves: is it purely correctness, or also side-channel resistance (e.g. constant-time)
So I'd have to dig deeper, read the fiat-crypto papers before I decide the path to go.
Assuming that I end up deciding to go with fiat-crypto, what would be the best way to assure all my cryptographic building blocks rely on it?
My thoughts (although I need to take a deeper look into num-traits) are to rely on num-traits, and to adapt the fiat-crypto generated code to it later upon instantiation.
My question to you is - could we in the future rely on num-traits for elliptic-curve and k256? just asking if it's a possibility, not whether you are willing to do it ( I might decide to contribute it myself if I find it necessary, for now I just want to know if it's a valid option)?
Most of our downstream users would disagree I think, especially about k256
.
The most common requests we get on k256
are for improved performance, particularly from prospective users who are using the C implementation.
We try to improve the performance with each release. The last release shipped variable-time inversions for verification, and the next will hopefully ship wNAF.
Another option is to provide both, ala curve25519-dalek
which has a fiat
backend, though that would also be a lot of work.
I'm honestly not sure about using num-traits
as an abstraction for the purposes of the @RustCrypto crates. crypto-bigint
already has its own traits which e.g. elliptic-curve
uses.
For dsa
and rsa
, I'd probably rather add a heap-allocated equivalent of Uint
like DynUint
, which could implement the crypto-bigint
internal traits. That would let us take advantage of other work being done within the crypto-bigint
ecosystem, like crypto-primes
.
fiat-crypto
synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.
Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.
I ran some benchmarking, and was really surprised at the results. I published the code so you can see that I haven't made any mistakes.
But results are (full trace is found in the readme file of the repo):
fiat-crypto
field arithmetic is faster (add
: 3.6ns vs 5.2ns, mul
: 22ns vs 28ns) than k256
crypto-bigint::Residue
arithmetic faster (add
: 3.8ns vs 5.2ns, mul
: 27ns vs 28ns) than k256
(but slower than fiat-crypto
How can this be explained? perhaps there's some error on my side?
Perhaps open an issue on https://github.com/rustcrypto/elliptic-curves
@tarcieri getting back to the subject of this issue, is this feature something we are planning on delivering? specifically, I care about implementing Num
forDynResidue
, so I can support multiple backend implementations when writing my code (as I'm doing Paillier, I need a dynamic modulus and the arithmetic operations defined for it.)
I think a num-traits
impl would be great, but per the issue title I think it should be an optional rather than hard dependency
I think a
num-traits
impl would be great, but per the issue title I think it should be an optional rather than hard dependency
Optional as in a crate feature? that works for me. If so, I'll write my code assuming it and might contribute this feature later on.
Yep
Started to develop my code based on num-traits
, but found an obstacle that I cannot overcome; the Num
trait offers basic arithmetic operation over some field, probably meant to be over \Z
. Whilst I do need that functionality, in order to perform Paillier operations we also need to sometime think of those numbers as over \Z_{N^2}
or \Z_N
.
My original thinking was to implement Num
for DynResidue
, which I think could work:
specifically, I care about implementing
Num
forDynResidue
, so I can support multiple backend implementations when writing my code (as I'm doing Paillier, I need a dynamic modulus and the arithmetic operations defined for it.)
But not only that this won't work in-tandem with normal (over $\Z
) Uint
operations, I'm not even sure how to implement Num
for Uint
: for example, Mul expects to output Self
, which is not the case for Uint
which outputs Self::Concat
which is the "next-size" type (so we'd have U128
outputting U256
, which makes sense but does not comply with the Num
interface.)
So:
num-traits
.num-traits
interface could supply me with the operations I need for Paillier.An interface that does, however, comply with what I need for Paillier is curv::BasicOps
+ curv::Modulo
.
However, this trait has the same restriction as Num
- it operates on the same type for both input and output of arithmetic operations so that I believe that it can't be implemented for Uint
.
Would love to hear your thoughts on this @tarcieri
You should be able to implement Mul
for e.g. Wrapping<Uint<LIMBS>>
.
crypto-bigint
deviates from core
in that all operations are explicitly wide, wrapping, or checked, and there is no "checked at debug time, wrapping at compile time" behavior.
You should be able to implement
Mul
for e.g.Wrapping<Uint<LIMBS>>
.
crypto-bigint
deviates fromcore
in that all operations are explicitly wide, wrapping, or checked, and there is no "checked at debug time, wrapping at compile time" behavior.
I see, so your suggestion is to actually use the output size (i.e. the largest integer I'll work with, e.g. the size of $N^2$ for Paillier which is 4096-bit) to represent all numbers and do operations there, so instead of multiplying two smaller numbers (e.g. the size of $P, Q$ so 1024-bit long) and getting their output size (e.g. the size of $N$ which is 2048-bit) I'll treat them all as numbers in $Z$ so-long that no operation overflows (and in my example, multiplying $P*Q$ where both P and Q take 1024-bit but are stored in a U4096, there will be no overflow -- will it also be as efficient as in wide-multiplication of U1024 by U1024 though?)
I believe this approach works, but still the num-traits
traits are missing modular arithmetics so that will not be of use to me. The curv
traits could work, but this issue is not about support curv
traits nor do I think there is wide interest in that.
Therefore, I believe the best approach for me is to use the crypto_bigint::Integer
traits with corresponding MulMod
etc. traits, and if I'd need to implement them for different libraries in the future (e.g. for benchmarking) I'll adapt them to the crypto-bigint
traits and not vise-versa as was intended by this issue.
Thank you in any-case; if you agree with my reasoning, I guess I wouldn't be requiring this feature anymore.
num-traits
is now a hard dependency. #433 added quite a few trait impls.
It would be nice to impl Num
, and there are a few PRs open to do that, but to really do that properly I think we need to finish up #246 and/or #247.
I'm going to close this and suggest #218 as a place to follow up on Num
support for now.
Currently
num-traits
is only indev-dependencies
.As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the
rsa
crate to use eithercrypto-bigint
ornum-bigint-dig
.Though
num-traits
probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.