commit e6045d135be3962917e9fa53ede96a08fb1a17ec
parent 981c2bde42fda3d5de966e2bd7a72aa552234735
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 26 Aug 2023 16:59:20 -0230
Add 6.44.
Diffstat:
4 files changed, 242 insertions(+), 9 deletions(-)
diff --git a/data/s6/44.txt b/data/s6/44.txt
@@ -0,0 +1,44 @@
+msg: Listen for me, you better listen for me now.
+s: 1267396447369736888040262262183731677867615804316
+r: 1105520928110492191417703162650245113664610474875
+m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
+msg: Listen for me, you better listen for me now.
+s: 29097472083055673620219739525237952924429516683
+r: 51241962016175933742870323080382366896234169532
+m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
+msg: When me rockin' the microphone me rock on steady,
+s: 277954141006005142760672187124679727147013405915
+r: 228998983350752111397582948403934722619745721541
+m: 21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4
+msg: Yes a Daddy me Snow me are de article dan.
+s: 1013310051748123261520038320957902085950122277350
+r: 1099349585689717635654222811555852075108857446485
+m: 1d7aaaa05d2dee2f7dabdc6fa70b6ddab9c051c5
+msg: But in a in an' a out de dance em
+s: 203941148183364719753516612269608665183595279549
+r: 425320991325990345751346113277224109611205133736
+m: 6bc188db6e9e6c7d796f7fdd7fa411776d7a9ff
+msg: Aye say where you come from a,
+s: 502033987625712840101435170279955665681605114553
+r: 486260321619055468276539425880393574698069264007
+m: 5ff4d4e8be2f8aae8a5bfaabf7408bd7628f43c9
+msg: People em say ya come from Jamaica,
+s: 1133410958677785175751131958546453870649059955513
+r: 537050122560927032962561247064393639163940220795
+m: 7d9abd18bbecdaa93650ecc4da1b9fcae911412
+msg: But me born an' raised in the ghetto that I want yas to know,
+s: 559339368782867010304266546527989050544914568162
+r: 826843595826780327326695197394862356805575316699
+m: 88b9e184393408b133efef59fcef85576d69e249
+msg: Pure black people mon is all I mon know.
+s: 1021643638653719618255840562522049391608552714967
+r: 1105520928110492191417703162650245113664610474875
+m: d22804c4899b522b23eda34d2137cd8cc22b9ce8
+msg: Yeah me shoes a an tear up an' now me toes is a show a
+s: 506591325247687166499867321330657300306462367256
+r: 51241962016175933742870323080382366896234169532
+m: bc7ec371d951977cba10381da08fe934dea80314
+msg: Where me a born in are de one Toronto, so
+s: 458429062067186207052865988429747640462282138703
+r: 228998983350752111397582948403934722619745721541
+m: d6340bfcda59b6b75b59ca634813d572de800e8f
+\ No newline at end of file
diff --git a/docs/s6.md b/docs/s6.md
@@ -128,19 +128,51 @@ fare; Cryptopals.DSA implements 'keygen', 'sign', and 'verify'
functionality.
As for the attack here, if one knows the subkey/nonce he can trivially
-recover the private key via the relation given. Since the nonce is a
-16-bit word, it can easily be brute-forced. The 'fromsub' and 'recover'
-functions in Cryptopals.DSA.Attacks handle this:
+recover the private key:
+
+ s = k^{-1} (h + x r) (mod q)
+ s k = h + x r (mod q)
+ x r = s k - h (mod q)
+ x = r^{-1} (s k - h) (mod q)
+
+Since the nonce here is a 16-bit word, it can easily be brute-forced.
+The 'fromsub' and 'recover' functions in Cryptopals.DSA.Attacks handle
+this:
> let sec@(Sec sk) = recover defaultParams rawmsg rawsig rawpub
> CS.sha1 . BL.fromStrict . B16.encodeBase16' $ RSA.unroll sk
0954edd5e0afe5542a4adf012611a91912a3ec16
-We can log the nonce/subkey found and hardcode that in the 'sign'
-function to check that we get the same signature as well (it's 16575):
+We can log the nonce/subkey found (it's 16575) and hardcode that in the
+'sign' function to check that we get the same signature as well:
> sig <- sign defaultParams sec rawmsg gen
> sig == rawsig
True
+#### 6.44
+
+A reused nonce results in an identical 'r' in the DSA signature
+produced, since 'r' depends only on the nonce and DSA domain parameters.
+Then for two signatures s1 and s2, "integerized" digests h1 and h2, and
+private key 'x', we have:
+
+ s1 - s2 = k^{-1} (h1 + x r) - k^{-1} (h2 + x r) (mod q)
+ = k^{-1} (h1 + x r - h2 - x r) (mod q)
+ = 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:
+
+ > m1
+ "Listen for me, you better listen for me now. "
+ > m2
+ "Pure black people mon is all I mon know. "
+ > let k = recoverNonce defaultParams sig1 sig2 h1 h2
+ 108994997653034620063305500641348549625
+ > let Sec sk = fromsub defaultParams m1 sig1 k
+ > CS.sha1 . BL.fromStrict . B16.encodeBase16' $ RSA.unroll sk
+ ca8f6f7c66fa362d40760d135b763eb8527d3d52
diff --git a/lib/Cryptopals/DSA.hs b/lib/Cryptopals/DSA.hs
@@ -8,6 +8,7 @@ module Cryptopals.DSA (
, Sig(..)
, sign
+ , sign'
, verify
) where
@@ -83,6 +84,26 @@ sign ps@Params {..} key msg gen = case key of
then sign ps key msg gen
else pure (Sig r s)
+-- sign with provided subkey/nonce
+sign'
+ :: Params
+ -> Key
+ -> Natural
+ -> BS.ByteString
+ -> Sig
+sign' ps@Params {..} key k msg = case key of
+ Pub {} -> error "sign: need secret key"
+ Sec x ->
+ let r = DH.modexp dsag k p `rem` dsaq
+ in if r == 0
+ then error "sign': invalid nonce (r)"
+ else
+ let h = fi . CS.integerDigest . CS.sha1 $ BL.fromStrict msg
+ s = (RSA.modinv' k dsaq * (h + x * r)) `rem` dsaq
+ in if s == 0
+ then error "sign': invalid nonce (s)"
+ else Sig r s
+
verify
:: Params
-> Key
diff --git a/lib/Cryptopals/DSA/Attacks.hs b/lib/Cryptopals/DSA/Attacks.hs
@@ -6,15 +6,21 @@ import qualified Cryptopals.Digest.Pure.SHA as CS
import Cryptopals.DSA
import qualified Cryptopals.RSA as RSA
import qualified Data.ByteString as BS
+import qualified Data.ByteString.Base16 as B16
import qualified Data.ByteString.Lazy as BL
import GHC.Word (Word16)
import Numeric.Natural
import qualified System.Random.MWC as MWC
+fi :: (Integral a, Num b) => a -> b
+fi = fromIntegral
+
+-- key recovery from nonce ----------------------------------------------------
+
-- recover private key given a subkey
fromsub :: Params -> BS.ByteString -> Sig -> Natural -> Key
fromsub Params {..} msg Sig {..} k =
- let h = fromIntegral . CS.integerDigest . CS.sha1 $ BL.fromStrict msg
+ let h = fi . CS.integerDigest . CS.sha1 $ BL.fromStrict msg
num = (sigs * k - h) `rem` dsaq
den = RSA.modinv' sigr dsaq
in Sec $ (num * den) `rem` dsaq
@@ -30,7 +36,7 @@ recover ps@Params {..} msg sig pub = ST.runST $ do
Pub pb -> pb
loop :: forall s. Word16 -> MWC.Gen s -> ST.ST s Key
loop k g = do
- let sk@(Sec x) = fromsub ps msg sig (fromIntegral k)
+ let sk@(Sec x) = fromsub ps msg sig (fi k)
sig' <- sign ps sk msg g
if DH.modexp dsag x dsap == p && verify ps pub msg sig'
then pure sk
@@ -38,8 +44,8 @@ recover ps@Params {..} msg sig pub = ST.runST $ do
rawmsg :: BS.ByteString
rawmsg = mconcat [
- "For those that envy a MC it can be hazardous to your health\n"
- , "So be friendly, a matter of life and death, just like a etch-a-sketch\n"
+ "For those that envy a MC it can be hazardous to your health "
+ , "So be friendly, a matter of life and death, just like a etch-a-sketch "
]
rawpub :: Key
@@ -51,3 +57,132 @@ rawsig = Sig {
, sigs = 857042759984254168557880549501802188789837994940
}
+-- nonce recovery from repeated nonce -----------------------------------------
+
+recoverNonce :: Params -> Sig -> Sig -> Natural -> Natural -> Natural
+recoverNonce Params {..} (Sig _ s1) (Sig _ s2) h1 h2 =
+ let num = (fi h1 - fi h2) `mod` (fi dsaq :: Integer)
+ den = (fi s1 - fi s2) `mod` (fi dsaq :: Integer)
+ in (fi num * RSA.modinv' (fi den) dsaq) `mod` dsaq
+
+tarpub :: Key
+tarpub = Pub 0x2d026f4bf30195ede3a088da85e398ef869611d0f68f0713d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b85519b1c23cc3ecdc6062650462e3063bd179c2a6581519f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d32971c3de5084cce04a2e147821
+
+-- msg: Listen for me, you better listen for me now.
+-- s: 1267396447369736888040262262183731677867615804316
+-- r: 1105520928110492191417703162650245113664610474875
+-- m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
+r1 :: Natural
+r1 = 1105520928110492191417703162650245113664610474875
+
+s1 :: Natural
+s1 = 1267396447369736888040262262183731677867615804316
+
+m1 :: BS.ByteString
+m1 = "Listen for me, you better listen for me now. "
+
+sig1 :: Sig
+sig1 = Sig r1 s1
+
+h1 :: Natural
+h1 = 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19
+
+-- msg: Pure black people mon is all I mon know.
+-- s: 1021643638653719618255840562522049391608552714967
+-- r: 1105520928110492191417703162650245113664610474875
+-- m: d22804c4899b522b23eda34d2137cd8cc22b9ce8
+r2 :: Natural
+r2 = 1105520928110492191417703162650245113664610474875
+
+s2 :: Natural
+s2 = 1021643638653719618255840562522049391608552714967
+
+m2 :: BS.ByteString
+m2 = "Pure black people mon is all I mon know. "
+
+sig2 :: Sig
+sig2 = Sig r2 s2
+
+h2 :: Natural
+h2 = 0xd22804c4899b522b23eda34d2137cd8cc22b9ce8
+
+-- msg: Listen for me, you better listen for me now.
+-- s: 29097472083055673620219739525237952924429516683
+-- r: 51241962016175933742870323080382366896234169532
+-- m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
+
+m3 :: BS.ByteString
+m3 = "Listen for me, you better listen for me now. "
+
+s3 :: Natural
+s3 = 29097472083055673620219739525237952924429516683
+
+r3 :: Natural
+r3 = 51241962016175933742870323080382366896234169532
+
+sig3 :: Sig
+sig3 = Sig r3 s3
+
+h3 :: Natural
+h3 = 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19
+
+-- msg: Yeah me shoes a an tear up an' now me toes is a show a
+-- s: 506591325247687166499867321330657300306462367256
+-- r: 51241962016175933742870323080382366896234169532
+-- m: bc7ec371d951977cba10381da08fe934dea80314
+
+m4 :: BS.ByteString
+m4 = "Yeah me shoes a an tear up an' now me toes is a show a "
+
+s4 :: Natural
+s4 = 506591325247687166499867321330657300306462367256
+
+r4 :: Natural
+r4 = 51241962016175933742870323080382366896234169532
+
+sig4 :: Sig
+sig4 = Sig r4 s4
+
+h4 :: Natural
+h4 = 0xbc7ec371d951977cba10381da08fe934dea80314
+
+-- msg: When me rockin' the microphone me rock on steady,
+-- s: 277954141006005142760672187124679727147013405915
+-- r: 228998983350752111397582948403934722619745721541
+-- m: 21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4
+
+m5 :: BS.ByteString
+m5 = "When me rockin' the microphone me rock on steady, "
+
+s5 :: Natural
+s5 = 277954141006005142760672187124679727147013405915
+
+r5 :: Natural
+r5 = 228998983350752111397582948403934722619745721541
+
+sig5 :: Sig
+sig5 = Sig r5 s5
+
+h5 :: Natural
+h5 = 0x21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4
+
+-- msg: Where me a born in are de one Toronto, so
+-- s: 458429062067186207052865988429747640462282138703
+-- r: 228998983350752111397582948403934722619745721541
+-- m: d6340bfcda59b6b75b59ca634813d572de800e8f
+
+m6 :: BS.ByteString
+m6 = "Where me a born in are de one Toronto, so "
+
+s6 :: Natural
+s6 = 458429062067186207052865988429747640462282138703
+
+r6 :: Natural
+r6 = 228998983350752111397582948403934722619745721541
+
+sig6 :: Sig
+sig6 = Sig r6 s6
+
+h6 :: Natural
+h6 = 0xd6340bfcda59b6b75b59ca634813d572de800e8f
+
