commit 960b7568e31976e813f223068d74042b2d34dd84
parent 971bb01cef00e44a7fdb63b3408edf88c53815c1
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 1 Aug 2026 12:05:18 -0230
lib: reject out-of-range coordinates when parsing points
The field prime is within 2 ^ 32 of 2 ^ 256, so C.to silently reduces
a coordinate in [p, 2 ^ 256) to a small one, giving points with a
small x a second encoding. parse_point accepted it on the 32-byte and
65-byte paths, though not on the 33-byte one, which already checked.
BIP0340 requires "fail if x >= p" and SEC1-v2 requires both
coordinates in [0, p - 1]. No attack follows, since aliasing reaches
only x < 2 ^ 32 + 977 and nobody holds those discrete logs, but it is
a divergence for anything doing bitcoin validation: BIP0340 vector 14
covers precisely this and was passing only because the key parsed as
x = 1 and verification then failed on the signature instead.
fe also rejects zero, which costs nothing here: x = 0 has no lift, as
7 is a quadratic non-residue mod p, and y = 0 would be a point of
order two, which a prime-order group has none of.
Diffstat:
2 files changed, 32 insertions(+), 1 deletion(-)
diff --git a/lib/Crypto/Curve/Secp256k1.hs b/lib/Crypto/Curve/Secp256k1.hs
@@ -902,7 +902,9 @@ parse_point bs
-- input is guaranteed to be 32B in length
_parse_bip0340 :: BS.ByteString -> Maybe Projective
-_parse_bip0340 = fmap projective . lift_vartime . C.to . unsafe_roll32
+_parse_bip0340 (unsafe_roll32 -> x) = do
+ guard (fe x) -- bip0340 "fail if x >= p"; x == 0 has no lift anyway
+ fmap projective (lift_vartime (C.to x))
-- bytestring input is guaranteed to be 32B in length
_parse_compressed :: Word8 -> BS.ByteString -> Maybe Projective
@@ -924,6 +926,7 @@ _parse_uncompressed :: Word8 -> BS.ByteString -> Maybe Projective
_parse_uncompressed h bs = do
let (unsafe_roll32 -> x, unsafe_roll32 -> y) = BS.splitAt _CURVE_Q_BYTES bs
guard (h == 0x04)
+ guard (fe x && fe y) -- sec1-v2 requires both in [0, p - 1]
let !p = Projective (C.to x) (C.to y) 1
guard (valid p)
pure $! p
diff --git a/test/Main.hs b/test/Main.hs
@@ -10,6 +10,7 @@ import qualified Data.Aeson as A
import qualified Data.Attoparsec.ByteString as AT
import qualified Data.ByteString as BS
import qualified Data.ByteString.Base16 as B16
+import qualified Data.Maybe as M
import qualified Numeric.Montgomery.Secp256k1.Scalar as S
import Test.Tasty
import Test.Tasty.HUnit
@@ -140,8 +141,35 @@ parse_point_tests = testGroup "parse_point tests" [
parse_point_test_p
, parse_point_test_q
, parse_point_test_r
+ , noncanonical_tests
]
+-- The field prime is within 2 ^ 32 of 2 ^ 256, so a coordinate in
+-- [p, 2 ^ 256) reduces to a small one, giving a second encoding of a
+-- point with a small x. x = 1 is such a point.
+noncanonical_tests :: TestTree
+noncanonical_tests = testGroup "non-canonical coordinates" [
+ testCase "32-byte x-only, x = 1" $
+ assertBool mempty (M.isJust (parse_point (decodeLenient x1_hex)))
+ , testCase "32-byte x-only, x = p + 1" $
+ assertEqual mempty Nothing
+ (fmap serialize_point (parse_point (decodeLenient p1_hex)))
+ , testCase "65-byte uncompressed, x = 1" $
+ assertBool mempty
+ (M.isJust (parse_point (decodeLenient ("04" <> x1_hex <> y1_hex))))
+ , testCase "65-byte uncompressed, x = p + 1" $
+ assertEqual mempty Nothing
+ (fmap serialize_point
+ (parse_point (decodeLenient ("04" <> p1_hex <> y1_hex))))
+ ]
+
+-- x-coordinate of a curve point, and the field prime plus that
+-- coordinate, which must not parse
+x1_hex, p1_hex, y1_hex :: BS.ByteString
+x1_hex = "0000000000000000000000000000000000000000000000000000000000000001"
+p1_hex = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc30"
+y1_hex = "4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee"
+
serialize_point_tests :: TestTree
serialize_point_tests = testGroup "serialize_point tests" [
serialize_point_test_p
