Attacks.hs (6395B)
1 module Cryptopals.DSA.Attacks ( 2 fromsub 3 , recoverNonce 4 ) where 5 6 import qualified Control.Monad.ST as ST 7 import qualified Cryptopals.DH as DH 8 import qualified Cryptopals.Digest.Pure.SHA as CS 9 import Cryptopals.DSA 10 import qualified Cryptopals.RSA as RSA 11 import qualified Data.ByteString as BS 12 import qualified Data.ByteString.Base16 as B16 13 import qualified Data.ByteString.Lazy as BL 14 import GHC.Word (Word16) 15 import Numeric.Natural 16 import qualified System.Random.MWC as MWC 17 18 fi :: (Integral a, Num b) => a -> b 19 fi = fromIntegral 20 21 -- key recovery from nonce ---------------------------------------------------- 22 23 -- recover private key given a subkey 24 fromsub :: Params -> BS.ByteString -> Sig -> Natural -> Key 25 fromsub Params {..} msg Sig {..} k = 26 let h = fi . CS.integerDigest . CS.sha1 $ BL.fromStrict msg 27 num = (sigs * k - h) `rem` dsaq 28 den = RSA.modinv' sigr dsaq 29 in Sec $ (num * den) `rem` dsaq 30 31 -- brute-force a private key with a Word16 subkey 32 recover :: Params -> BS.ByteString -> Sig -> Key -> Key 33 recover ps@Params {..} msg sig pub = ST.runST $ do 34 gen <- MWC.create 35 loop 2 gen 36 where 37 p = case pub of 38 Sec {} -> error "recover: need public key" 39 Pub pb -> pb 40 loop :: forall s. Word16 -> MWC.Gen s -> ST.ST s Key 41 loop k g = do 42 let sk@(Sec x) = fromsub ps msg sig (fi k) 43 sig' <- sign ps sk msg g 44 if DH.modexp dsag x dsap == p && verify ps pub msg sig' 45 then pure sk 46 else loop (succ k) g 47 48 rawmsg :: BS.ByteString 49 rawmsg = mconcat [ 50 "For those that envy a MC it can be hazardous to your health " 51 , "So be friendly, a matter of life and death, just like a etch-a-sketch " 52 ] 53 54 rawpub :: Key 55 rawpub = Pub 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17 56 57 rawsig :: Sig 58 rawsig = Sig { 59 sigr = 548099063082341131477253921760299949438196259240 60 , sigs = 857042759984254168557880549501802188789837994940 61 } 62 63 -- nonce recovery from repeated nonce ----------------------------------------- 64 65 recoverNonce :: Params -> Sig -> Sig -> Natural -> Natural -> Natural 66 recoverNonce Params {..} (Sig _ s1) (Sig _ s2) h1 h2 = 67 let num = (fi h1 - fi h2) `mod` (fi dsaq :: Integer) 68 den = (fi s1 - fi s2) `mod` (fi dsaq :: Integer) 69 in (fi num * RSA.modinv' (fi den) dsaq) `mod` dsaq 70 71 tarpub :: Key 72 tarpub = Pub 0x2d026f4bf30195ede3a088da85e398ef869611d0f68f0713d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b85519b1c23cc3ecdc6062650462e3063bd179c2a6581519f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d32971c3de5084cce04a2e147821 73 74 -- msg: Listen for me, you better listen for me now. 75 -- s: 1267396447369736888040262262183731677867615804316 76 -- r: 1105520928110492191417703162650245113664610474875 77 -- m: a4db3de27e2db3e5ef085ced2bced91b82e0df19 78 r1 :: Natural 79 r1 = 1105520928110492191417703162650245113664610474875 80 81 s1 :: Natural 82 s1 = 1267396447369736888040262262183731677867615804316 83 84 m1 :: BS.ByteString 85 m1 = "Listen for me, you better listen for me now. " 86 87 sig1 :: Sig 88 sig1 = Sig r1 s1 89 90 h1 :: Natural 91 h1 = 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19 92 93 -- msg: Pure black people mon is all I mon know. 94 -- s: 1021643638653719618255840562522049391608552714967 95 -- r: 1105520928110492191417703162650245113664610474875 96 -- m: d22804c4899b522b23eda34d2137cd8cc22b9ce8 97 r2 :: Natural 98 r2 = 1105520928110492191417703162650245113664610474875 99 100 s2 :: Natural 101 s2 = 1021643638653719618255840562522049391608552714967 102 103 m2 :: BS.ByteString 104 m2 = "Pure black people mon is all I mon know. " 105 106 sig2 :: Sig 107 sig2 = Sig r2 s2 108 109 h2 :: Natural 110 h2 = 0xd22804c4899b522b23eda34d2137cd8cc22b9ce8 111 112 -- msg: Listen for me, you better listen for me now. 113 -- s: 29097472083055673620219739525237952924429516683 114 -- r: 51241962016175933742870323080382366896234169532 115 -- m: a4db3de27e2db3e5ef085ced2bced91b82e0df19 116 117 m3 :: BS.ByteString 118 m3 = "Listen for me, you better listen for me now. " 119 120 s3 :: Natural 121 s3 = 29097472083055673620219739525237952924429516683 122 123 r3 :: Natural 124 r3 = 51241962016175933742870323080382366896234169532 125 126 sig3 :: Sig 127 sig3 = Sig r3 s3 128 129 h3 :: Natural 130 h3 = 0xa4db3de27e2db3e5ef085ced2bced91b82e0df19 131 132 -- msg: Yeah me shoes a an tear up an' now me toes is a show a 133 -- s: 506591325247687166499867321330657300306462367256 134 -- r: 51241962016175933742870323080382366896234169532 135 -- m: bc7ec371d951977cba10381da08fe934dea80314 136 137 m4 :: BS.ByteString 138 m4 = "Yeah me shoes a an tear up an' now me toes is a show a " 139 140 s4 :: Natural 141 s4 = 506591325247687166499867321330657300306462367256 142 143 r4 :: Natural 144 r4 = 51241962016175933742870323080382366896234169532 145 146 sig4 :: Sig 147 sig4 = Sig r4 s4 148 149 h4 :: Natural 150 h4 = 0xbc7ec371d951977cba10381da08fe934dea80314 151 152 -- msg: When me rockin' the microphone me rock on steady, 153 -- s: 277954141006005142760672187124679727147013405915 154 -- r: 228998983350752111397582948403934722619745721541 155 -- m: 21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4 156 157 m5 :: BS.ByteString 158 m5 = "When me rockin' the microphone me rock on steady, " 159 160 s5 :: Natural 161 s5 = 277954141006005142760672187124679727147013405915 162 163 r5 :: Natural 164 r5 = 228998983350752111397582948403934722619745721541 165 166 sig5 :: Sig 167 sig5 = Sig r5 s5 168 169 h5 :: Natural 170 h5 = 0x21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4 171 172 -- msg: Where me a born in are de one Toronto, so 173 -- s: 458429062067186207052865988429747640462282138703 174 -- r: 228998983350752111397582948403934722619745721541 175 -- m: d6340bfcda59b6b75b59ca634813d572de800e8f 176 177 m6 :: BS.ByteString 178 m6 = "Where me a born in are de one Toronto, so " 179 180 s6 :: Natural 181 s6 = 458429062067186207052865988429747640462282138703 182 183 r6 :: Natural 184 r6 = 228998983350752111397582948403934722619745721541 185 186 sig6 :: Sig 187 sig6 = Sig r6 s6 188 189 h6 :: Natural 190 h6 = 0xd6340bfcda59b6b75b59ca634813d572de800e8f 191 192 -- parameter tampering -------------------------------------------------------- 193 194 badParams :: Params 195 badParams = defaultParams { 196 dsag = 0 197 } 198 199 otherBadParams :: Params 200 otherBadParams = defaultParams { 201 dsag = dsap + 1 202 } 203 where 204 Params {..} = defaultParams 205 206 magicsig :: Params -> Key -> Sig 207 magicsig Params {..} key = case key of 208 Sec {} -> error "magicsig: need public key" 209 Pub pk -> 210 let r = (DH.modexp pk 3 dsap) `mod` dsaq 211 s = (r * RSA.modinv' 3 dsaq) `mod` dsaq 212 in Sig r s