packages feed

secp256k1-haskell-3.0.0: test/Crypto/Secp256k1/RecoverySpec.hs

{-# LANGUAGE CPP #-}
{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE OverloadedRecordDot #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}

-- | ECDSA public key recovery. The module under test only exists when the
-- @recovery@ flag of the package is on, so the whole specification is behind
-- the same flag. This module avoids string gaps, because CPP would join
-- their lines.
module Crypto.Secp256k1.RecoverySpec (spec) where

import Test.Hspec

#ifdef RECOVERY

import Control.DeepSeq (deepseq)
import Control.Exception (evaluate)
import Control.Monad (forM_)
import Control.Monad.Par qualified as P
import Crypto.Secp256k1
import Crypto.Secp256k1.Fixtures
import Crypto.Secp256k1.Internal.Base (CompactSig (CompactSig), Msg (Msg), SecKey (SecKey))
import Crypto.Secp256k1.Internal.Recovery (RecSig (RecSig))
import Crypto.Secp256k1.Recovery
import Data.Bits (xor)
import Data.ByteString qualified as BS
import Data.Hashable (hash)
import Data.Maybe (fromJust, isJust)
import Data.String (fromString)
import Data.Word (Word8)
import Test.QuickCheck
import Text.Read (readMaybe)

spec :: Spec
spec = describe "public key recovery" $ do
  signingSpec
  recoverySpec
  formulaSpec
  compactSpec
  valueSpec
  rawValueSpec
  instanceSpec

-- * Fixtures
--
-- As in "Crypto.Secp256k1.Fixtures", every expected value is a literal from
-- an independent source, recomputed with an independent implementation of
-- the curve.

-- Bitcoin Core key_tests.cpp: the SignCompact signature of coreKey over
-- coreMsg is 20 ++ coreR ++ coreS. The header byte 0x20 = 32 = 27 + 1 + 4
-- says recovery id 1 and a compressed key. coreDer is 30440220 ++ coreR ++
-- 0220 ++ coreS.
coreR, coreS :: String
coreR = "5dbbddda71772d95ce91cd2d14b592cfbc1dd0aabd6a394b6c2d377bbe59d31d"
coreS = "14ddda21494a4e221f0824f0b8b924c43fa43c0ad57dccdaa11f81a6bd4582f6"

coreRecId :: Word8
coreRecId = 1

-- The compressed public key of coreKey, and the key that recovery id 0 gives
-- for the same signature.
corePub, coreOtherPub :: String
corePub = "030b4c866585dd868a9d62348a9cd008d6a312937048fff31670e7e920cfc7a744"
coreOtherPub = "02818f8ef9ebd82871789a39ea0385398c267d3d6bb6f537166bd813135870c8ec"

-- Bitcoin Core util_tests.cpp, message_sign: the key of the address
-- 15CRxFdyRpGZLW9w8HnHvVduizdL5jKNbs signs the message "Trust no one".
messageKey :: SecKey
messageKey = "d97f5108f11cda6eeebaaa420fef0726b1f898060b98489fa3098463c0032866"

-- sha256d of the varstrings "Bitcoin Signed Message:\n" and "Trust no one".
messageHash :: Msg
messageHash = "aa8215d723ecd2f14867eeb7e19f192be7bc15a2352a24b991d4f5870cbaf6e8"

-- The expected signature, base64
-- IPojfrX2dfPnH26UegfbGQQLrdK844DlHq5157/P6h57WyuS/Qsl+h/WSVGDF4MUi4rWSswW38oimDYfNNUBUOk=
-- decoded: the header byte 0x20, recovery id 1 and a compressed key, then r
-- and s.
messageR, messageS :: String
messageR = "fa237eb5f675f3e71f6e947a07db19040badd2bce380e51eae75e7bfcfea1e7b"
messageS = "5b2b92fd0b25fa1fd64951831783148b8ad64acc16dfca2298361f34d50150e9"

-- The compressed public key of messageKey.
messagePub :: String
messagePub = "03d2be3dddb497c7c4388cfcb941e14a222cf3e26fe5e2cc260da1821e60d26022"

-- The RFC 6979 vector has recovery id 1. Recovery id 0 gives this other key.
satoshiOtherPub :: String
satoshiOtherPub = "0354d58835e07b996d6378eafa930ae9d2211e767381f1d52aedc67f48c8886f0b"

-- Key 1 signing sha256 "4" (highRDer): r, s and recovery id 0.
highRR, highRS :: String
highRR = "d479c93a086bf5f4ae1fed7eaf2604a4da2007d851c5409961c81dd7f0600194"
highRS = "1cd7a196454152f5b8d19865d49b4fa71e314ebff9c59e2f7b2295bf80331be8"

-- Values for the formula Q = r⁻¹(s·R − e·G).
two, five :: String
two = "0000000000000000000000000000000000000000000000000000000000000002"
-- 5³ + 7 = 132 is not a square modulo p, so no point has x = 5.
five = "0000000000000000000000000000000000000000000000000000000000000005"

-- x = 1 is on the curve: 1 + 7 = 8 is a square modulo p. pointOne is the
-- point with x = 1 and an even y, so its compressed encoding is 02 ++ one and
-- that of its negation is 03 ++ one.
pointOne, pointOneMinusG, twicePointOne :: String
pointOne = "02" ++ one
pointOneMinusG = "02871e0c836ec675e07395aef58d72b646f77e0e33ce1622dfaa0fb8e131f3fe12"
twicePointOne = "03c7ffffffffffffffffffffffffffffffffffffffffffffffffffffff37fffd03"

-- x = n + 2 is on the curve, x = n + 1 is not.
orderPlusTwo :: String
orderPlusTwo = "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364143"

-- Half of the point with x = n + 2 and an even y.
halfPointOrderPlusTwo :: String
halfPointOrderPlusTwo = "02ad802f2145df548ce1fc418b851cb32669c5a6bb939e6caf744de90310f8f1ff"

-- p − n and p − n − 1. With the recovery id 2, the first gives x = p, which
-- is outside the field, and the second x = p − 1, which is not on the curve.
fieldMinusOrder, fieldMinusOrderMinusOne :: String
fieldMinusOrder = "000000000000000000000000000000014551231950b75fc4402da1722fc9baee"
fieldMinusOrderMinusOne = "000000000000000000000000000000014551231950b75fc4402da1722fc9baed"

-- The x coordinate of G, and the key −(x⁻¹)·G.
genX, genNegatedOverX :: String
genX = drop 2 genCompressed
genNegatedOverX = "028ff83d8cf12121491609c4939dc11c4aa35503508fe432dc5a5c1905608b9218"

-- * Signing

signingSpec :: Spec
signingSpec = describe "signing" $ do
  it "produces Bitcoin Core's SignCompact signature of sha256d 'Very deterministic message'" $
    exportCompactRecSig (signRecMsg coreKey coreMsg)
      `shouldBe` (fromString (coreR ++ coreS), coreRecId)
  it "produces Bitcoin Core's signmessage signature of 'Trust no one'" $
    exportCompactRecSig (signRecMsg messageKey messageHash)
      `shouldBe` (fromString (messageR ++ messageS), 1)
  it "produces the RFC 6979 vector with recovery id 1" $
    exportCompactRecSig (signRecMsg keyOne satoshiMsg)
      `shouldBe` (fromString (satoshiR ++ satoshiS), 1)
  it "keeps a high r, as Bitcoin Core's message signing does" $ do
    exportCompactRecSig (signRecMsg keyOne highRMsg)
      `shouldBe` (fromString (highRR ++ highRS), 0)
    convertRecSig (signRecMsg keyOne highRMsg) `shouldNotBe` signMsgLowR keyOne highRMsg
  it "signs with the r and s of signMsg" $
    property $ \(m :: Msg, k :: SecKey) -> convertRecSig (signRecMsg k m) == signMsg k m
  it "is deterministic" $
    property $ \(m :: Msg, k :: SecKey) -> signRecMsg k m == signRecMsg k m
  it "gives a recovery id of 0 or 1" $
    -- The ids 2 and 3 need r below p - n, about one signature in 2^128.
    property $ \(m :: Msg, k :: SecKey) ->
      snd (exportCompactRecSig (signRecMsg k m)) `elem` [0, 1]
  it "produces lower-S signatures" $
    property $ \(m :: Msg, k :: SecKey) -> isLowS (convertRecSig (signRecMsg k m))
  it "signs and recovers in parallel" $
    property $ \(xs :: [(Msg, SecKey)]) -> P.runPar $ do
      results <- mapM (P.spawnP . signsAndRecovers) xs
      and <$> mapM P.get results
  where
    signsAndRecovers (m, k) =
      recover (signRecMsg k m) m == Just (derivePubKey k)

-- * Recovery

recoverySpec :: Spec
recoverySpec = describe "recovery" $ do
  it "recovers the key of Bitcoin Core's SignCompact vector" $
    recovered (coreR ++ coreS ++ "01") coreMsg `shouldBe` Just corePub
  it "recovers another key with the other recovery id" $
    recovered (coreR ++ coreS ++ "00") coreMsg `shouldBe` Just coreOtherPub
  it "recovers the signer of Bitcoin Core's 'Trust no one' message" $
    recovered (messageR ++ messageS ++ "01") messageHash `shouldBe` Just messagePub
  it "recovers G from the RFC 6979 vector" $ do
    recovered (satoshiR ++ satoshiS ++ "01") satoshiMsg `shouldBe` Just genCompressed
    recovered (satoshiR ++ satoshiS ++ "00") satoshiMsg `shouldBe` Just satoshiOtherPub
  it "recovers the signing key" $
    property $ \(m :: Msg, k :: SecKey) ->
      recover (signRecMsg k m) m == Just (derivePubKey k)
  it "recovers a different key for another message" $
    property $ \(m :: Msg, m' :: Msg, k :: SecKey) ->
      m /= m' ==> recover (signRecMsg k m) m' /= Just (derivePubKey k)
  it "recovers the same key from the high-S form with the parity bit flipped" $ do
    -- The RFC 6979 vector with s replaced by n - s and the id 1 turned into 0.
    recovered (satoshiR ++ satoshiHighS ++ "00") satoshiMsg `shouldBe` Just genCompressed
    recovered (satoshiR ++ satoshiHighS ++ "01") satoshiMsg `shouldNotBe` Just genCompressed
  it "does not apply the lower-S rule" $
    property $ \(m :: Msg, k :: SecKey) ->
      let (compact, i) = exportCompactRecSig (signRecMsg k m)
          (r, s) = BS.splitAt 32 compact.get
          -- n - s, through the negation of a tweak.
          highS = (fromJust (tweakNegate (fromJust (tweak s)))).get
          high = fromJust (importCompactRecSig (fromJust (compactSig (r <> highS))) (i `xor` 1))
       in recover high m == Just (derivePubKey k)
  where
    recovered sigHex m = bytesToHex . exportPubKey True <$> recover (fromString sigHex) m

-- * The formula

formulaSpec :: Spec
formulaSpec = describe "the formula Q = r⁻¹(s·R − e·G)" $ do
  it "gives R itself for r = 1, s = 1 and a zero hash" $
    recovered (one ++ one ++ "00") zero `shouldBe` Just pointOne
  it "takes the parity of y from the recovery id" $
    recovered (one ++ one ++ "01") zero `shouldBe` Just ("03" ++ one)
  it "reduces the hash modulo n" $
    recovered (one ++ one ++ "00") order `shouldBe` Just pointOne
  it "subtracts e·G" $
    recovered (one ++ one ++ "00") one `shouldBe` Just pointOneMinusG
  it "multiplies by s" $ do
    recovered (one ++ two ++ "00") zero `shouldBe` Just twicePointOne
    recovered (one ++ orderMinusOne ++ "00") zero `shouldBe` Just ("03" ++ one)
  it "divides by r" $
    recovered (two ++ one ++ "02") zero `shouldBe` Just halfPointOrderPlusTwo
  it "uses r + n as the x coordinate for the ids 2 and 3" $ do
    recovered (two ++ two ++ "02") zero `shouldBe` Just ("02" ++ orderPlusTwo)
    recovered (two ++ two ++ "03") zero `shouldBe` Just ("03" ++ orderPlusTwo)
  it "gives nothing when no point has the x coordinate" $ do
    recovered (five ++ one ++ "00") zero `shouldBe` Nothing
    recovered (one ++ one ++ "02") zero `shouldBe` Nothing
    recovered (fieldMinusOrderMinusOne ++ one ++ "02") zero `shouldBe` Nothing
  it "gives nothing when r + n reaches the field size" $
    recovered (fieldMinusOrder ++ one ++ "02") zero `shouldBe` Nothing
  it "gives nothing when s·R − e·G is the point at infinity" $ do
    -- R = G, s = 1 and e = 1: G - G.
    recovered (genX ++ one ++ "00") one `shouldBe` Nothing
    -- With e = 2 instead: (G - 2G) / x = -(x⁻¹)·G.
    recovered (genX ++ one ++ "00") two `shouldBe` Just genNegatedOverX
  where
    recovered sigHex msgHex =
      bytesToHex . exportPubKey True <$> recover (fromString sigHex) (fromString msgHex)

-- * Compact encoding

compactSpec :: Spec
compactSpec = describe "compact encoding" $ do
  it "imports and exports back the same signature" $
    property $ \(m :: Msg, k :: SecKey) ->
      let s = signRecMsg k m
          (compact, i) = exportCompactRecSig s
       in importCompactRecSig compact i == Just s
  it "accepts the recovery ids 0 to 3 and rejects 4 and 255" $ do
    forM_ [0 .. 3] $ \i -> importCompactRecSig (fromString (one ++ one)) i `shouldSatisfy` isJust
    importCompactRecSig (fromString (one ++ one)) 4 `shouldBe` Nothing
    importCompactRecSig (fromString (one ++ one)) 255 `shouldBe` Nothing
  it "accepts components of 1 and n - 1 and rejects 0 and n" $ do
    importCompactRecSig (fromString (one ++ one)) 0 `shouldSatisfy` isJust
    importCompactRecSig (fromString (orderMinusOne ++ orderMinusOne)) 0 `shouldSatisfy` isJust
    importCompactRecSig (fromString (order ++ one)) 0 `shouldBe` Nothing
    importCompactRecSig (fromString (one ++ order)) 0 `shouldBe` Nothing
    importCompactRecSig (fromString (zero ++ one)) 0 `shouldBe` Nothing
    importCompactRecSig (fromString (one ++ zero)) 0 `shouldBe` Nothing
  it "imports a high-S signature" $
    importCompactRecSig (fromString (satoshiR ++ satoshiHighS)) 0 `shouldSatisfy` isJust
  it "converts to the signature without the id" $ do
    bytesToHex (exportSig (convertRecSig (fromString (coreR ++ coreS ++ "01")))) `shouldBe` coreDer
    convertRecSig (fromString (coreR ++ coreS ++ "00"))
      `shouldBe` convertRecSig (fromString (coreR ++ coreS ++ "01"))
  it "converts to a signature that verifies" $
    property $ \(m :: Msg, k :: SecKey) ->
      verifySig (derivePubKey k) (convertRecSig (signRecMsg k m)) m

-- * Signature values

valueSpec :: Spec
valueSpec = describe "signature values" $ do
  it "rebuild from their internal bytes" $
    property $ \(m :: Msg, k :: SecKey) -> let s = signRecMsg k m in recSig s.get == Just s
  it "reject internal bytes that are not a signature" $ do
    recSig (BS.replicate 65 0) `shouldBe` Nothing
    recSig (BS.replicate 65 0xff) `shouldBe` Nothing
    recSig (BS.replicate 64 1) `shouldBe` Nothing
    recSig (BS.replicate 66 1) `shouldBe` Nothing
  it "reject an internal recovery id above 3" $ do
    -- libsecp256k1 keeps the id in the last byte of the representation.
    let bytes = (signRecMsg keyOne satoshiMsg).get
    recSig (BS.init bytes `BS.snoc` 4) `shouldBe` Nothing
  it "show r, s and the recovery id in hex" $
    show (signRecMsg coreKey coreMsg) `shouldBe` quoted (coreR ++ coreS ++ "01")
  it "read that encoding" $ do
    read (quoted (coreR ++ coreS ++ "01")) `shouldBe` signRecMsg coreKey coreMsg
    (fromString (coreR ++ coreS ++ "01") :: RecSig) `shouldBe` signRecMsg coreKey coreMsg
  it "show and read" $
    property $ \(m :: Msg, k :: SecKey) -> showRead (signRecMsg k m)
  it "do not read an invalid signature" $ do
    (readMaybe (quoted (coreR ++ coreS)) :: Maybe RecSig) `shouldBe` Nothing
    (readMaybe (quoted (coreR ++ coreS ++ "04")) :: Maybe RecSig) `shouldBe` Nothing
    (readMaybe (quoted (zero ++ coreS ++ "01")) :: Maybe RecSig) `shouldBe` Nothing
    (readMaybe (quoted (order ++ coreS ++ "01")) :: Maybe RecSig) `shouldBe` Nothing
    (readMaybe (quoted (coreR ++ coreS ++ "0")) :: Maybe RecSig) `shouldBe` Nothing
    evaluate (fromString (coreR ++ coreS) :: RecSig) `shouldThrow` anyErrorCall

-- * Values built with the raw constructors of the Internal modules

rawValueSpec :: Spec
rawValueSpec = describe "raw values from the Internal modules" $ do
  it "a signature of 65 zero bytes recovers nothing, instead of aborting the process" $
    recover (RecSig (BS.replicate 65 0)) satoshiMsg `shouldBe` Nothing
  it "a zero secret key throws instead of signing" $
    evaluate (signRecMsg (SecKey (BS.replicate 32 0)) satoshiMsg) `shouldThrow` anyErrorCall
  it "values of the wrong length throw before reaching the library" $ do
    evaluate (signRecMsg (SecKey "a") satoshiMsg) `shouldThrow` anyErrorCall
    evaluate (signRecMsg keyOne (Msg "a")) `shouldThrow` anyErrorCall
    evaluate (recover (RecSig "a") satoshiMsg) `shouldThrow` anyErrorCall
    evaluate (recover (signRecMsg keyOne satoshiMsg) (Msg "a")) `shouldThrow` anyErrorCall
    evaluate (convertRecSig (RecSig "a")) `shouldThrow` anyErrorCall
    evaluate (exportCompactRecSig (RecSig "a")) `shouldThrow` anyErrorCall
    evaluate (importCompactRecSig (CompactSig "a") 0) `shouldThrow` anyErrorCall
    evaluate (length (show (RecSig "a"))) `shouldThrow` anyErrorCall

-- * Derived instances

instanceSpec :: Spec
instanceSpec = describe "derived instances" $ do
  it "equal values hash equally, whichever way they were built" $
    property $ \(m :: Msg, k :: SecKey) ->
      let s = signRecMsg k m
          (compact, i) = exportCompactRecSig s
       in hash s == hash (fromJust (importCompactRecSig compact i))
            && hash s == hash (fromJust (recSig s.get))
  it "can be fully evaluated" $
    (signRecMsg keyOne satoshiMsg `deepseq` ()) `shouldBe` ()

#else

spec :: Spec
spec =
  describe "public key recovery" $
    it "needs the recovery flag of the package" $
      pendingWith "the package was built with -f -recovery"

#endif