-
-
Notifications
You must be signed in to change notification settings - Fork 655
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Re-enable secp256k1-zkp and make it default #1534
Comments
I did some experiments in the secp256k1-zkp branch Currently, So the following secp256k1.foo() turns into this: with secp256k1_zkp.Context() as secp256k1:
secp256k1.foo() However, we might want to make this a drop-in replacement (so it looks and behaves like a module with static methods) and hide the context creation behind the scenes. There are (at least) two ways how to do this:
|
TLDR
Suggestion
ReportConstants
|
ECMULT_WINDOW_SIZE |
secp256k1_ecdsa_sig_verify |
secp256k1_ecmult_context_build |
secp256k1_ecmult_context |
---|---|---|---|
2 | 16.1 ms | 5.9 ms | 128 B |
4 | 14.3 ms | 6.4 ms | 512 B |
6 | 13.5 ms | 8.3 ms | 2 kB |
8 | 12.9 ms | 16.2 ms | 8 kB |
10 | 12.6 ms | 47 ms | 32 kB |
ECMULT_GEN_PREC_BITS
The constant is 2, 4 or 8. The bigger the constant is
- the faster is
secp256k1_ecmult_gen
(andsecp256k1_ecdsa_sig_sign
,secp256k1_ec_pubkey_create
) - the bigger is the size of
secp256k1_ecmult_gen_context
(andsecp256k1_context
) - the slower is
secp256k1_ecmult_gen_context_build
(andsecp256k1_context_preallocated_create
), provided the context is not precomputed in compile-time using the flagUSE_ECMULT_STATIC_PRECOMPUTATION
.
ECMULT_GEN_PREC_BITS |
secp256k1_ecdsa_sig_sign |
secp256k1_ec_pubkey_create |
secp256k1_ecmult_gen_context |
---|---|---|---|
2 | 23.4 ms | 14.4 ms | 32 kB |
4 | 11.7 ms | 7.2 ms | 64 kB |
8 | 5.9 ms | 3.6 ms | 512 kB |
Only the times for ECMULT_GEN_PREC_BITS = 4
in the table were measured, other times are estimated.
WINDOW_A
The constant has a fixed value of 5 which is optimal in terms of speed of functions secp256k1_ecmult
(and secp256k1_ecdsa_sig_verify
) and secp256k1_ecmult_const
(and secp256k1_ecdh
). The bigger the constant is the more memory on stack these functions needs.
WINDOW_A |
secp256k1_ecdsa_sig_verify |
secp256k1_ecdh |
||
---|---|---|---|---|
2 | 1440 B | 14.7 ms | 168 B | 23.7 ms |
3 | 1772 B | 13.6 ms | 336 B | 15.1 ms |
4 | 2436 B | 13.1 ms | 672 B | 12.7 ms |
5 | 3764 B | 12.9 ms | 1344 B | 11.8 ms |
6 | 6420 B | 13.2 ms | 2688 B | 12.2 ms |
The times were measured for ECMULT_GEN_PREC_BITS = 4
and ECMULT_WINDOW_SIZE = 8
, bytes are a lower estimate.
Contexts
secp256k1_context
The context consists of secp256k1_ecmult_context
and secp256k1_ecmult_gen
.
secp256k1_ecmult_gen_context
The context is used by secp256k1_ecmult_gen
(and secp256k1_ecdsa_sig_sign
, secp256k1_ec_pubkey_create
).
The context consists of:
- A read-only two-dimensional table.
- It consists of
2^ECMULT_GEN_PREC_BITS
rows and256 / ECMULT_GEN_PREC_BITS
columns. - Its total size is
sizeof(secp256k1_ge_storage) * 2^ECMULT_GEN_PREC_BITS * 256 / (ECMULT_GEN_PREC_BITS) = 16384 * 2^ECMULT_GEN_PREC_BITS / ECMULT_GEN_PREC_BITS
. - If the flag
USE_ECMULT_STATIC_PRECOMPUTATION
, the table is precomputed in compile-tile. This works only forECMULT_GEN_PREC_BITS = 8
. - It consists of points with unknown discrete logarithms. This should prevent some attack I don't quite understand.
- It is a kind of duplication of the table in
secp256k1_table.h
.
- It consists of
- A point
initial
and a scalarblind
such thatinitial = blind * G
.- The values are used in
secp256k1_ecmult_gen
(andsecp256k1_ecdsa_sig_sign
,secp256k1_ec_pubkey_create
) as a protection against differential power analysis. - The values should be refreshed by
secp256k1_context_randomize
(orsecp256k1_ecmult_gen_blind
) before every call ofsecp256k1_ecmult_gen
(that is before every call ofsecp256k1_ecdsa_sig_sign
andsecp256k1_ec_pubkey_create
), which makes the operation twice as long. - This kind of blinding is not implemented in
trezor-crypto
(which uses randomized coordinates instead of that).
- The values are used in
secp256k1_ecmult_context
The context is used in secp256k1_ecdsa_sig_verify
.
It consists of two read-only tables:
- Each table consists of
2^(ECMULT_WINDOW_SIZE - 2)
elements. - The total size of the tables is
sizeof(secp256k1_ge_storage) * 2 * 2^(ECMULT_WINDOW_SIZE - 2) = 32 * 2^ECMULT_WINDOW_SIZE
. - The tables cannot be precomputed in compile-time. On the other hand, there is no reason to rebuild every time
secp256k1_ecdsa_sig_verify
is called.
Functions
secp256k1_ecmult_gen
Computes lambda b : b * G
, where G
is the generator and b
is a scalar.
- It is used by
secp256k1_ecdsa_sig_sign
andsecp256k1_ec_pubkey_create
. - It is constant time.
- It computes
b * G
as(b - initial) * G + blind
, whereinitial
andblind
are generated so thatblind = initial * G
. This is a protection against differential power analysis. - It uses
ECMULT_WINDOW_SIZE
-ary representation ofb
, that isb
is represented by digitsb_i
such thatb = sum(b_i * 2^(i * ECMULT_WINDOW_SIZE))
0 <= b_i < 2^ECMULT_WINDOW_SIZE
- It uses a precomputed table that is contained in
secp256k1_ecmult_gen_context
. The table consists of points with unknown discrete logarithms. This should prevent a kind of attack I don't quite understand. - A similar method is used by
scalar_multiply
intrezor-crypto
, which differs in these points:- It uses the constant
ECMULT_WINDOW_SIZE = 4
. b
is represented by digitsb_i
such that-2^(WINDOW_A - 1) < b_i < 2^(WINDOW_A - 1)
b_i % 2 == 1
- It uses a table that is half in size but it consists of points with known discrete logarithm.
- It uses the constant
secp256k1_ecmult
Computes lambda a, b, P : a * P + b * G
, where G
is the generator, a
and b
are scalars and P
is a point.
- It is used by
secp256k1_ecdsa_sig_verify
. - It uses the fast endomorphism (see bellow).
- It uses Shamir's trick.
- It uses sliding-window method.
- It uses
ECMULT_WINDOW_SIZE
-ary non-adjacent form ofa
, that isa
is represented by digitsa_i
such thata = sum(a_i * 2^i)
-2^(WINDOW_A - 1) < a_i < 2^(WINDOW_A - 1)
a_i % 2 = 1 or a_i = 0
- It uses
WINDOW_A
-ary non-adjacent form ofb
- It uses a precomputed table that is contained in
secp256k1_ecmult_context
. - It uses around
2^(WINDOW_A - 2) * (2 * sizeof(secp256k1_ge) + sizeof(secp256k1_gej) + 40) + 260 * sizeof(int) + 68 = 83 * 2^WINDOW_A + 1108
bytes on the stack. - It is non constant time, which should be all right since the method is used only in verification which usually does not work with secret information.
secp256k1_ecmult_const
Computes lambda a, P : a * P
, where a
is a scalar and P
is a point.
- It is used by
secp256k1_ecdh
. - It uses the fast endomorphism.
- It is constant time.
- It uses window method.
- It uses a kind of
WINDOW_A - 1
-ary form ofa
, to be precise,a
is represented by digitsa_i
such thata = sum(a_i * 2^((WINDOW_A - 1)* i))
-2^(WINDOW_A - 1) < a_i < 2^(WINDOW_A - 1)
a_i % 2 == 1
- It uses around
2^(WINDOW_A - 2) * sizeof(secp256k1_ge) * 2 = 42 * 2^WINDOW_A
bytes on the stack. - The same method with the same constant (
WINDOW_A - 1 = 4
) is used bypoint_multiply
intrezor-crypto
. - It seems to me that it doesn't use any kind of randomization as a protection against differential power analysis.
Fast endomorphism
All the curves secp{192,224,256}k1 were generated so that there is an effectively computable endomorphism that can be utilized to speed up point multiplication. The method appeared in https://www.iacr.org/archive/crypto2001/21390189.pdf for the first time.
The endomorphism phi
for secp256k1 is defined as
phi : (x, y) -> (beta * x mod p, y)
where
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
and p
is the prime the coordinates are reduced with. If (x, y)
lies on the curve, the point phi((x, y))
lies on the curve as well and this surprising formula holds true:
phi(P) = lambda * P
where
lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
Suppose we want to compute k * P
, the algorithm that makes use of the endomorphism is the following:
- Find
k1
andk2
such thatk = (k1 + k2 * lambda) mod n
, wheren
is the order of the curve, andk1
andk2
are about half in length compared tok
. - Compute
k1 * P + k2 * phi(P)
using Shamir's trick. If double-and-add method is used, the speed-up is about 40 %.
Other facts
trezor-crypto
uses a blinding inecdsa_sign_digest
when computingprivate_nonce^-1 * (public_nonce * private_key + digest)
as a protection against side-channel attacks (see https://github.com/trezor/trezor-firmware/blob/master/crypto/ecdsa.c#L706-L715), whereassecp256k1-zkp
does not.trezor-crypto
uses a randomization when performing points arithmetic in jacobian coordinates as a protection against differential power analysis (see https://github.com/trezor/trezor-firmware/blob/master/crypto/ecdsa.c#L186-L197), whereassecp256k1-zkp
does not.trezor-crypto
rejects signatures of zero digest as a protection against a fault injection attack since its easy to forge a signature of zero digest (see https://github.com/trezor/trezor-firmware/blob/master/crypto/ecdsa.c#L1044-L1051), whereassecp256k1-zkp
does not.- It seems to me that
secp256k1_ecmult_const
(andsecp256k1_ecdh
) insecp256k1-zkp
doesn't use any kind of randomization as a protection against differential power analysis.
@onvej-sl WOW, great work Ondrej! Thank you for the very thorough analysis! |
Just rebased |
I've started integrating the new mainlined zkp functionality into the T1 fuzzer and noticed some API issues. I'm not sure if this closed ticket is the right place to bring it up, so feel free to move it or respond to it elsewhere. (#1864 feels like a different scope, though.)
The most straightforward approach is to expose the initialization check and actually null the context pointer on destroy, but I haven't looked into this very deeply and may be missing some logic or side effects. |
Next time please open a new issue. It is easier to track it. |
Will do, thanks! |
secp256k1(-zkp) performs better for signature verification and contains schnorr algo
The text was updated successfully, but these errors were encountered: