commit 4fff017ccb0717ebe0bf4247beb429469caece1b
parent af0409f74e34ebbd042b50bd3f2bdd85d6124bd1
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 19 Oct 2024 09:23:27 +0400
bench: remQ benchmark and notes
Also misc. commentary.
Diffstat:
3 files changed, 57 insertions(+), 17 deletions(-)
diff --git a/README.md b/README.md
@@ -28,10 +28,8 @@ A sample GHCi session:
> Secp256k1.verify_schnorr msg pub sig0
True
>
- > -- create a low-S ECDSA signature for the message
+ > -- create and verify a low-S ECDSA signature for the message
> let sig1 = Secp256k1.sign_ecdsa sec msg
- >
- > -- verify it
> Secp256k1.verify_ecdsa msg pub sig1
> True
```
@@ -90,8 +88,8 @@ BIP0340 vectors][ut340], and ECDSA has been tested against the relevant
accurate and safe from attacks targeting e.g. faulty nonce generation or
malicious inputs for signature parameters. Timing-sensitive operations,
e.g. elliptic curve scalar multiplication, have been explicitly written
-so as to execute algorithmically in time constant with respect to secret
-data:
+so as to execute *algorithmically* in time constant with respect to
+secret data:
```
benchmarking derive_public/sk = 2
@@ -131,11 +129,30 @@ data:
std dev 48.99 μs (40.83 μs .. 62.77 μs)
```
-Despite all that, take reasonable security precautions as appropriate.
-You probably shouldn't deploy the implementations within in any
-situation where they could easily be used as an oracle to construct a
-[timing attack][timea], and you shouldn't give sophisticated malicious
-actors [access to your computer][flurl].
+Be aware that integer division modulo the elliptic curve group order,
+when benchmarked on its own, does display persistent substantial timing
+differences on the order of 2 ns when the inputs are dramatically
+different in size:
+
+```
+ benchmarking remQ (remainder modulo _CURVE_Q)/remQ 2
+ time 27.44 ns (27.19 ns .. 27.72 ns)
+ 1.000 R² (0.999 R² .. 1.000 R²)
+ mean 27.23 ns (27.03 ns .. 27.43 ns)
+ std dev 669.1 ps (539.9 ps .. 860.2 ps)
+
+ benchmarking remQ (remainder modulo _CURVE_Q)/remQ (2 ^ 255 - 19)
+ time 29.11 ns (28.87 ns .. 29.33 ns)
+ 0.999 R² (0.999 R² .. 1.000 R²)
+ mean 29.04 ns (28.82 ns .. 29.40 ns)
+ std dev 882.9 ps (647.8 ps .. 1.317 ns)
+```
+
+Because we don't make "hard" guarantees of constant-time execution, take
+reasonable security precautions as appropriate. You shouldn't deploy the
+implementations within in any situation where they could easily be used
+as an oracle to construct a [timing attack][timea], and you shouldn't
+give sophisticated malicious actors [access to your computer][flurl].
If you discover any vulnerabilities, please disclose them via
security@ppad.tech.
diff --git a/bench/Main.hs b/bench/Main.hs
@@ -25,6 +25,16 @@ main = defaultMain [
, ecdsa
]
+remQ :: Benchmark
+remQ = env setup $ \x ->
+ bgroup "remQ (remainder modulo _CURVE_Q)" [
+ bench "remQ (2 ^ 255 - 19)" $ nf S.remQ x
+ , bench "remQ 2 " $ nf S.remQ 2
+ ]
+ where
+ setup = pure . S.parse_int256 $ B16.decodeLenient
+ "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed"
+
parse_point :: Benchmark
parse_point = bgroup "parse_point" [
bench "compressed" $ nf S.parse_point p_bs
diff --git a/lib/Crypto/Curve/Secp256k1.hs b/lib/Crypto/Curve/Secp256k1.hs
@@ -32,8 +32,11 @@ module Crypto.Curve.Secp256k1 (
, verify_ecdsa
, verify_ecdsa_unrestricted
+ -- * secp256k1 points
+ , Pub
+ , derive_pub
+
-- * Parsing
- , Word256(..)
, parse_int256
, parse_point
@@ -43,21 +46,22 @@ module Crypto.Curve.Secp256k1 (
, double
, mul
, mul_unsafe
- , derive_pub
-- Coordinate systems and transformations
, Affine(..)
, Projective(..)
- , Pub
, affine
, projective
, valid
- -- for testing
+ -- for testing/benchmarking
+ , Word256(..)
, _sign_ecdsa_no_hash
, _CURVE_P
, _CURVE_Q
, _CURVE_G
+ , remQ
+ , modQ
) where
import Control.Monad (when)
@@ -592,14 +596,20 @@ derive_pub _SECRET
-- parsing --------------------------------------------------------------------
+-- | Parse a positive 256-bit 'Integer', /e.g./ a Schnorr or ECDSA
+-- secret key.
+--
+-- >>> import qualified Data.ByteString as BS
+-- >>> parse_int256 (BS.replicate 32 0xFF)
+-- <2 ^ 256 - 1>
parse_int256 :: BS.ByteString -> Integer
parse_int256 bs
| BS.length bs /= 32 =
error "ppad-secp256k1 (parse_int256): requires exactly 32-byte input"
| otherwise = roll32 bs
--- | Parse compressed point (33 bytes), uncompressed point (65 bytes),
--- or BIP0340-style point (32 bytes).
+-- | Parse compressed secp256k1 point (33 bytes), uncompressed point (65
+-- bytes), or BIP0340-style point (32 bytes).
parse_point :: BS.ByteString -> Maybe Projective
parse_point bs
| len == 32 = _parse_bip0340 bs
@@ -842,7 +852,10 @@ _sign_ecdsa ty hf _SECRET m
Affine (modQ -> r) _ = affine kg
s = case modinv k (fi _CURVE_Q) of
Nothing -> error "ppad-secp256k1 (sign_ecdsa): bad k value"
- -- XX timing concern
+ -- note that modular division is not timing-safe when it
+ -- involves arbitrary-sized integers; benchmarks indicate about
+ -- a 2 ns difference in remQ execution time when input sizes
+ -- are extremely different
Just kinv -> remQ (remQ (h_modQ + remQ (_SECRET * r)) * kinv)
if r == 0 -- negligible probability
then sign_loop g