cryptopals

s6.md (9986B)

---

 #### 6.41
 
 For this one we'll just simulate the network stuff.
 Cryptopals.RSA.Attacks implements 'umrOracle', the simulated
 client/server interaction, as well as 'umrperturb', a function for
 'perturbing' collected ciphertexts, and 'umrrecover', a function for
 recovering plaintexts from the oracle's response.
 
 The more interesting part of this challenge is understanding the modular
 arithmetic going on. We have, for plaintext p and ciphertext c:
 
     c = p ^ e mod n
     p = c ^ d mod n
 
 Now, encrypt a random 's' under the same pubkey. We have:
 
     t = s ^ e mod n
     s = t ^ d mod n
 
 and now note that:
 
     (c t) mod n = (m ^ e mod n) (s ^ e mod n)
                 = (m s) ^ e mod n
 
 since exponentiation distributes over multiplication. If we have an
 arbitrary decryption oracle, then we can get:
 
     p' = (c t) ^ d mod n
        = ((c ^ d mod n) (t ^ d mod n)) mod n
        = (p s) mod n
 
 such that, for q the multiplicative inverse of s = t ^ d modulo n:
 
     p = p' q mod n.
 
 So, let's generate a keypair and kick off the oracle. There are a lot of
 really long lines here so I'll abbreviate the logs accordingly:
 
     > per <- keygen 1024
     > evalStateT (runEffect (umrOracle per)) mempty
 
 It prints out the generated public key for convenience:
 
     (cryptopals) umr-oracle: running with public key
     Pub 3 22513321964659585055936315428684912055916908912276341574563352485..
     (cryptopals) umr-oracle: awaiting hex-encoded input
 
 In another GHCi session we can mimic a user inputting their deepest, darkest
 secrets:
 
     > let msg = "my secret crush is so-and-so"
     > let pub = <above logged pubkey>
     > let cip = encrypt pub msg
 
 Hex-encoding the ciphertext and submitting it, the oracle spits out the
 hex-encoded plaintext:
 
     (cryptopals) umr-oracle: decrypted text
     6d792073656372657420637275736820697320736f2d616e642d736f
 
 and submitting it again (say, now, we're Mallory) yields nothing:
 
     (cryptopals) umr-oracle: rejecting request
     (cryptopals) umr-oracle: awaiting hex-encoded input
 
 So now we go and adjust the ciphertext via 'umrperturb', which returns
 the randomly generated number and the perturbed ciphertext (both of
 which are way too long to print here):
 
     > gen <- MWC.createSystemRandom
     > (s, c') <- umrperturb pub cip gen
 
 We hex-encode c' and submit it to the oracle again, this time receiving
 a different hex-encoded plaintext back. This one is very long, since,
 via our math above, it's a product of big integers:
 
     (cryptopals) umr-server: decrypted text
     c49c9dac3b7b4a86bf29eebafb3650469a5b91bf23c5339043ff9b72895953a21ff157f8..
 
 Calling the hex-decoded bytestring p', we can feed it into 'umrrecover'
 to crack the juicy secret:
 
     > umrrecover pub s p'
     "my secret crush is so-and-so"
 
 Shame, shame.
 
 #### 6.42
 
 The idea here is simple, but clever: assemble something that, to a
 sloppy verifier, looks to be validly PKCS#1 v1.5-encoded, put a bunch
 of junk bytes at the end of it, and manipulate everything such that
 the result is a cube (or at least has an approximate cube root). Then
 calculate the approximate cube root and pass that off as a signature.
 
 Cryptopals.RSA implements some functions for PKCS#1 v1.5 encoding (as
 defined in [RFC-2313](https://datatracker.ietf.org/doc/html/rfc2313)),
 and, in particular, the requisite broken verification. 'sign' and
 'verify' implement a signature scheme using that encoding and SHA512.
 'forge' in Cryptopals.RSA.Attacks implements the desired forging
 function.
 
 Let's test out the basic signing and verification functionality:
 
     > Keypair sec pub@(Pub e n) <- keygen 1024
     > let msg = "hi mom"
     > let (_, sig) = sign sec msg
     > verify pub msg sig
     True
     > verify pub "hi mum" sig
     False
 
 and now the forgery, produced of course without the secret key:
 
     > let gis = forge n msg
     > verify pub msg gis
     True
     > verify pub "hi mum" gis
     False
 
 #### 6.43
 
 Parameter generation for DSA as detailed in
 [FIPS.186-4](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=40)
 seems to be particularly annoying and unrewarding to implement, so I
 didn't bother with it. The rest of the protocol is pretty standard 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:
 
     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 (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
 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. "
     > 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
 
 #### 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 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 the signature will verify for every message 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
 innocuous 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
 
 Bad group!
 
 #### 6.46
 
 This one is super fun, as advertised, and another good illustration of
 how the slightest information leak can compromise an otherwise secure
 cryptographic scheme.
 
 Cryptopals.RSA.Attacks.parityOracle implements the oracle, and
 parityAttack the loop:
 
     parityOracle :: BS.ByteString -> Bool
     parityOracle cip =
       let msg = decrypt (sec consistentKey) cip
       in  B.testBit (roll msg) 0
 
     parityAttack :: Key -> BS.ByteString -> IO BS.ByteString
     parityAttack (Pub e n) cip = loop 0 n (roll cip) where
       loop i j c
         | j == i || j - i == 1 = pure (unroll j)
         | otherwise = do
             B8.putStrLn (unroll j)
             let d = (c * DH.modexp 2 e n) `mod` n
             if   parityOracle (unroll d)
             then loop (i + (j - i) `quot` 2) j d
             else loop i (j - (j - i) `quot` 2) d
 
 For 'mystery' our base64-encoded input, we get (via our "Hollywood
 decryption"):
 
     > let cip = encrypt (pub consistentKey) (B64.decodeBase64Lenient mystery)
     > parityAttack (pub consistentKey) cip
     [..]
     "That's why I found you don't play around with the Funky Cold Medin\\"