commit e2a32696c8959fdb36698752f4460a67657a75b2
parent e6045d135be3962917e9fa53ede96a08fb1a17ec
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 26 Aug 2023 18:35:43 -0230
Add 6.45.
Diffstat:
3 files changed, 152 insertions(+), 4 deletions(-)
diff --git a/docs/s6.md b/docs/s6.md
@@ -162,9 +162,9 @@ private key 'x', we have:
= k^{-1} (h1 - h2) (mod q)
k = (s1 - s2)^{-1} (h1 - h2) (mod q)
-There are a few pairs of messages here with identical 'r' values. Shove
-any pair of them into the Cryptopals.DSA.Attacks.recoverNonce function
-to recover the nonce used:
+There are a few pairs of messages here with identical 'r' values
+in the associated signatures. Shove any pair of them into the
+Cryptopals.DSA.Attacks.recoverNonce function to recover the nonce used:
> m1
"Listen for me, you better listen for me now. "
@@ -176,3 +176,89 @@ to recover the nonce used:
> CS.sha1 . BL.fromStrict . B16.encodeBase16' $ RSA.unroll sk
ca8f6f7c66fa362d40760d135b763eb8527d3d52
+#### 6.45
+
+(N.b., my original signing / verification code actually checked for
+bad signature values, so Cryptopals.DSA also exports 'unsafeSign' and
+'unsafeVerify' that don't do any checking.)
+
+If g = 0 then we trivially have that every signature will include an
+r = 0 (and an 's' that doesn't depend on the private key, but this is
+ancillary). Every signature will verify for every message.
+
+As an illustration, if badParams contains g = 0, then:
+
+ > per <- keygen badParams gen
+ > sig <- unsafeSign badParams (sec per) "hi there" gen
+ Sig {sigr = 0, sigs = 840728545249248021778225505261898025031268238630}
+ > unsafeVerify badParams (pub per) "hi there" sig
+ True
+ > unsafeVerify badParams (pub per) "hi there?" sig
+ True
+ > unsafeVerify badParams (pub per) "uh oh" sig
+ True
+
+The case is much the same for g = p + 1, since r = 1 for every signature
+produced. Any public key generated with these parameters will equal 1,
+but the "magic signature" will work for DSA pubkeys generated with other
+'g' parameters, so long as they use g = p + 1 when actually signing and
+verifying. For the magicsig and arbitrary k, and arbitrary pubkey y, we
+have that:
+
+ r = y^k mod p (mod q)
+
+ s = k^{-1} r (mod q)
+
+So, when verifying:
+
+ w = s^{-1} (mod q)
+ = r^{-1} k (mod q)
+
+ u2 = r w (mod q)
+ = r r^{-1} k (mod q)
+ = k (mod q)
+
+and then for any u, we have:
+
+ v = (g^u y^u2) mod p (mod q)
+ = (g^u y^k) mod p (mod q)
+ = ((p + 1)^u y^k) mod p
+ = y^k mod p (mod q)
+ = r
+
+so that every signature will verify by construction.
+
+An illustration. First generate a keypair with normal, God-fearing
+parameters:
+
+ > per <- keygen defaultParams gen
+
+Here's the magic signature-making function:
+
+ magicsig :: Params -> Key -> Sig
+ magicsig Params {..} key = case key of
+ Sec {} -> error "magicsig: need public key"
+ Pub pk ->
+ let r = (DH.modexp pk 3 dsap) `mod` dsaq
+ s = (r * RSA.modinv' 3 dsaq) `mod` dsaq
+ in Sig r s
+
+Here's a magic signature, again created with good parameters. It looks
+convincing enough:
+
+ > let mag = magicsig defaultParams (pub per)
+ > mag
+ Sig {
+ , sigr = 133287944151296049966935050695452535070249494052
+ , sigs = 976726778072038851349123290347619105095879778206
+ }
+
+Now let's verify that signature against some strings, using bad
+parameters in which g = p + 1:
+
+ > unsafeVerify otherBadParams (pub per) "Hello, world" mag
+ True
+ > unsafeVerify otherBadParams (pub per) "Goodbye, world" mag
+ True
+
+
diff --git a/lib/Cryptopals/DSA.hs b/lib/Cryptopals/DSA.hs
@@ -10,6 +10,9 @@ module Cryptopals.DSA (
, sign
, sign'
, verify
+
+ , unsafeSign
+ , unsafeVerify
) where
import Control.Monad.Primitive
@@ -104,6 +107,23 @@ sign' ps@Params {..} key k msg = case key of
then error "sign': invalid nonce (s)"
else Sig r s
+-- don't check for bad signature values
+unsafeSign
+ :: PrimMonad m
+ => Params
+ -> Key
+ -> BS.ByteString
+ -> MWC.Gen (PrimState m)
+ -> m Sig
+unsafeSign ps@Params {..} key msg gen = case key of
+ Pub {} -> error "sign: need secret key"
+ Sec x -> do
+ k <- MWC.uniformRM (1, dsaq - 1) gen
+ let r = DH.modexp dsag k p `rem` dsaq
+ h = fi . CS.integerDigest . CS.sha1 $ BL.fromStrict msg
+ s = (RSA.modinv' k dsaq * (h + x * r)) `rem` dsaq
+ pure (Sig r s)
+
verify
:: Params
-> Key
@@ -123,3 +143,21 @@ verify Params {..} key msg Sig {..} = case key of
`rem` dsaq
in v == sigr
+-- don't check for bad signature parameters
+unsafeVerify
+ :: Params
+ -> Key
+ -> BS.ByteString
+ -> Sig
+ -> Bool
+unsafeVerify Params {..} key msg Sig {..} = case key of
+ Sec {} -> error "verify: need public key"
+ Pub y ->
+ let w = RSA.modinv' sigs dsaq
+ h = fi . CS.integerDigest . CS.sha1 $ BL.fromStrict msg
+ u1 = (h * w) `rem` dsaq
+ u2 = (sigr * w) `rem` dsaq
+ v = (((DH.modexp dsag u1 dsap) * (DH.modexp y u2 dsap)) `rem` dsap)
+ `rem` dsaq
+ in v == sigr
+
diff --git a/lib/Cryptopals/DSA/Attacks.hs b/lib/Cryptopals/DSA/Attacks.hs
@@ -1,4 +1,7 @@
-module Cryptopals.DSA.Attacks where
+module Cryptopals.DSA.Attacks (
+ fromsub
+ , recoverNonce
+ ) where
import qualified Control.Monad.ST as ST
import qualified Cryptopals.DH as DH
@@ -186,3 +189,24 @@ sig6 = Sig r6 s6
h6 :: Natural
h6 = 0xd6340bfcda59b6b75b59ca634813d572de800e8f
+-- parameter tampering --------------------------------------------------------
+
+badParams :: Params
+badParams = defaultParams {
+ dsag = 0
+ }
+
+otherBadParams :: Params
+otherBadParams = defaultParams {
+ dsag = dsap + 1
+ }
+ where
+ Params {..} = defaultParams
+
+magicsig :: Params -> Key -> Sig
+magicsig Params {..} key = case key of
+ Sec {} -> error "magicsig: need public key"
+ Pub pk ->
+ let r = (DH.modexp pk 3 dsap) `mod` dsaq
+ s = (r * RSA.modinv' 3 dsaq) `mod` dsaq
+ in Sig r s
