cryptopals

s5.md (19453B)

---

 #### 5.33
 
 The basic Diffie-Hellman algorithm for key exchange between Alice and
 Bob goes as follows. Alice and Bob agree on a finite cyclic group of
 some particular order to use. They each randomly and independently pick
 some number of times to perform the group operation (which must be
 greater than zero, and less than the order of the group) and perform the
 group operation on the generator that number of times, publishing their
 results. For generator g, Alice's number x, and Bob's number y: Alice
 publishes g ^ x, and Bob publishes g ^ y.
 
 Each then performs his or her own secret number of additional group
 operations on the other's public result, establishing the key g ^ xy.
 Since the discrete logarithm problem is hard, an eavesdropper can't (for
 an appropriate group) determine how many times either has performed the
 individual group operations, even given g; he can only naïvely calculate
 g ^ (x + y).
 
 For the initial illustration here we're using a decidedly insecure
 group, i.e. the multiplicative group of 16-bit words modulo 37:
 
     > gen <- MWC.create
     > let p = 37
     > let g = 5
     > a <- fmap (`mod` p) (MWC.uniformR (1, p - 1) gen) :: IO Word16
     > b <- fmap (`mod` p) (MWC.uniformR (1, p - 1) gen) :: IO Word16
     > let bigA = g ^ a `mod` p
     > let bigB = g ^ b `mod` p
     > let s = bigB ^ a `mod` p
     > let t = bigA ^ b `mod` p
     > s == t
     True
     > let k = S.sha1 . BP.runPut $ BP.putWord16be s
     > k
     ace6f761db204030c1a65c0930bd01fd55ecc429
 
 For the big guns, we can pull out GHC's Natural type, for which
 mwc-random (our preferred random library) can generate something in a
 range. First a modular exponentiation routine:
 
     -- modified from https://gist.github.com/trevordixon/6788535
     modexp :: Natural -> Natural -> Natural -> Natural
     modexp b e m
       | e == 0    = 1
       | otherwise =
           let t = if B.testBit e 0 then b `mod` m else 1
           in  t * modexp ((b * b) `mod` m) (B.shiftR e 1) m `mod` m
 
 and given that (and appropriate p, g), the key exchange:
 
     > gen <- MWC.create
     > a <- fmap (`mod` p) (MWC.uniformRM (1, p - 1) gen)
     > b <- fmap (`mod` p) (MWC.uniformRM (1, p - 1) gen)
     > let bigA = modexp g a p
     > let bigB = modexp g b p
     > let s = modexp bigB a p
     > let t = modexp bigA b p
     > s == t
     True
 
 That's all well and good, but let's have a bit of fun.
 
 Cryptopals.DH implements the Diffie-Hellman protocol over TCP. Two
 functions, 'bob' and 'alice', will initiate a TCP server and client,
 respectively. Each takes as argument a port to bind to and a protocol to
 follow, with Alice also taking an argument specifying the initial action
 she'll take. The two will then perform the specified protocol.
 
 The 'dh' protocol specifies Diffie-Hellman, and for the lulz Alice and
 Bob will exchange a message, AES128-encrypted with the shared key, à la
 the initial illustration in the next challenge.
 
 Opening two instances of GHCi, we can run e.g.:
 
     > bob "3000" dh
 
 in one, and:
 
     > alice "3000" dh
 
 in the other and watch the logs for fun. Here I'll interleave the
 relevant parts of the logs for readability:
 
     (cryptopals) bob: listening..
     (cryptopals) alice: session established
     (cryptopals) alice: sending group parameters and public key
     (cryptopals) bob: received group parameters and public key
     (cryptopals) bob: sending public key
     (cryptopals) alice: received public key
     (cryptopals) alice: sending ciphertext fQwcd2smXxBojyEDLrIdySNLAV3UHhl8/X2F/x4FIb0=
     (cryptopals) bob: received ciphertext fQwcd2smXxBojyEDLrIdySNLAV3UHhl8/X2F/x4FIb0=
     (cryptopals) bob: decrypted ciphertext: "attack at 10pm"
     (cryptopals) bob: replying with ciphertext NaObgnz4rNShMKRGdGv+OGnI2gZnWOoXuYmCZhlcyymRbHPaprFVOz4Ls5eH9y/W
     (cryptopals) alice: received ciphertext NaObgnz4rNShMKRGdGv+OGnI2gZnWOoXuYmCZhlcyymRbHPaprFVOz4Ls5eH9y/W
     (cryptopals) alice: decrypted ciphertext: "confirmed, attacking at 10pm"
     (cryptopals) bob: ending session
 
 #### 5.34
 
 If B = p in s = B ^ a mod p, then s = p ^ a mod p, which is zero for any
 'a' in the group. Our shared key is thus going to be the first 16 bytes
 of the SHA1 hash of an appropriately-serialized 0x00.
 
 Cryptopals.DH includes a 'mallory' agent that requires a port to listen
 on, a port to bind to, and a protocol to follow. By using the 'dhmitm'
 protocol, we get our man-in-the-middle attack on Alice and Bob's DH key
 exchange.
 
 You can get this going by opening three GHCi's, then launching e.g.:
 
     > bob "3000" dh
 
 in one, then:
 
     > mallory "3001" "3000" dhmitm
 
 in another, and finally:
 
     > alice "3001" dh sendParams
 
 in the third. Again, I'm interleaving the logs for readability:
 
     (cryptopals) bob: listening..
     (cryptopals) mallory: LiSteNIng..
     (cryptopals) alice: session established
     (cryptopals) mallory: eStabLisHed coNNecTion
     (cryptopals) alice: sending group parameters and public key
     (cryptopals) mallory: reCEiVed GRoUp pArAmeTErs And pUBliC kEy
     (cryptopals) mallory: sEnDinG BOguS paRaMeTeRs
     (cryptopals) bob: received group parameters and public key
     (cryptopals) bob: sending public key
     (cryptopals) mallory: REceIvED pUBlic keY
     (cryptopals) mallory: seNDINg boGus kEy
     (cryptopals) alice: received public key
     (cryptopals) alice: sending ciphertext tM4Y5fpafrsf9+A4UB5UaudkAVzwMtjsjDIwShPKHcU=
     (cryptopals) mallory: rECeIveD CiPHeRTexT tM4Y5fpafrsf9+A4UB5UaudkAVzwMtjsjDIwShPKHcU=
     (cryptopals) mallory: DEcRyptEd cIPheRTeXt: "attack at 10pm"
     (cryptopals) mallory: reLayINg cIpheRtExt
     (cryptopals) bob: received ciphertext tM4Y5fpafrsf9+A4UB5UaudkAVzwMtjsjDIwShPKHcU=
     (cryptopals) bob: decrypted ciphertext: "attack at 10pm"
     (cryptopals) bob: replying with ciphertext ux4PoPTCS7pz5H4IQ11AuZkMBHmEcT9Waz68y/a9nggIY38Z6mbwSrCwNO3OKcDQ
     (cryptopals) mallory: reCeiVeD CipHeRtExt ux4PoPTCS7pz5H4IQ11AuZkMBHmEcT9Waz68y/a9nggIY38Z6mbwSrCwNO3OKcDQ
     (cryptopals) mallory: DeCrYpteD cIphErteXt: "confirmed, attacking at 10pm"
     (cryptopals) mallory: ReLaYINg CiPHeRTexT
     (cryptopals) alice: received ciphertext ux4PoPTCS7pz5H4IQ11AuZkMBHmEcT9Waz68y/a9nggIY38Z6mbwSrCwNO3OKcDQ
     (cryptopals) alice: decrypted ciphertext: "confirmed, attacking at 10pm"
 
 #### 5.35
 
 Cryptopals.DH.dhng implements the negotiated-groups DH protocol, so that
 can be run by firing off e.g.:
 
     > bob "3000" dhng
 
 in one GHCi session, and:
 
     > alice "3000" dhng sendGroup
 
 in the other. In the meantime, we can figure out the outcomes of using
 the different malicious group parameters analytically.
 
 For g = 1, the MITM attack starts as follows:
 
     alice sends      p, g
     bob gets         p, 1
 
 If Bob receives g = 1, then Mallory knows his public key will equal 1 ^
 b mod p = 1, as will the shared key from Alice's perspective (since 1 ^
 a mod p = 1). Mallory thus needs to forward a 1 as Alice's public key in
 order for Bob to agree on the shared key.
 
 For g = p, Bob computes B = p ^ b mod p = 0, so Mallory can forward p as
 Alice's public key in order for them to agree on the shared key.
 
 Finally, the case of g = p - 1. Note that for any p > 1 and any even b, we
 have (for appropriate coefficients a, c, etc.):
 
     (p - 1) ^ b mod p
       = (p^b + .. + ap^2 + cp + 1) mod p
       = (p^b mod p + .. + ap^2 mod p + cp mod p + 1 mod p) mod p
       = (0 + .. + 0 + 1 mod p) mod p
       = 1
 
 whereas for any odd b, we have:
 
     (p - 1) ^ b mod p
       = (p^b - .. - cp^2 + dp - 1) mod p
       = (p^b mod p - .. - ap^2 mod p + cp mod p - 1 mod p) mod p
       = (0 + .. + 0 - 1 mod p) mod p
       = p - 1.
 
 So Bob's public key will be either 1 or p - 1 depending on whether his
 secret key is even or odd. Alice will thus compute:
 
     s = B ^ a mod p
       = 1               } b even or a even  (p = 3/4)
         p - 1           } b odd and a odd.  (p = 1/4).
 
 If Mallory then forwards A = g = p - 1 to Bob, we have:
 
     t = A ^ b mod p
       = 1               } b even  (p = 1/2)
       = p - 1           } b odd   (p = 1/2).
 
 This all yields the following table:
 
                             a
                 even              odd
         even   s = 1, t = 1      s = 1, t = 1
     b
         odd    s = 1, t = p - 1  s = p - 1, t = p - 1
 
 such that Alice and Bob will agree on the shared key with probability
 3/4. Mallory also has to choose which shared key value he uses; if he
 uses 1, then the attack succeeds with probability 1/2, and if he uses
 p - 1, then it succeeds with probability 1/4.
 
 Here are the interleaved logs of a successful attack. Start mallory with
 e.g. the `dhngmitm 1`, `dhngmitm p`, or `dhngmitm (p - 1)` protocol:
 
     (cryptopals) bob: listening..
     (cryptopals) mallory: LiSteNIng..
     (cryptopals) alice: session established
     (cryptopals) mallory: eStabLisHed MiTm coNNecTion
     (cryptopals) alice: sending group parameters
     (cryptopals) mallory: reCEiVed GRoUp pArAmeTErs
     (cryptopals) mallory: sEnDinG BOguS GRoUp paRaMeTeRs
     (cryptopals) bob: received group parameters
     (cryptopals) bob: acking group parameters
     (cryptopals) mallory: rECeiVed aCK
     (cryptopals) mallory: ReLaYINg ACk
     (cryptopals) alice: received ack
     (cryptopals) alice: sending public key 3f44f49421cbb3b2ed40aa8f068236affba15335
     (cryptopals) mallory: REceIvED pUBlic keY 3f44f49421cbb3b2ed40aa8f068236affba15335
     (cryptopals) mallory: SeNDing BoGuS kEy d14952314d5de233ef0dd0a178617f7f07ea082c
     (cryptopals) bob: received public key d14952314d5de233ef0dd0a178617f7f07ea082c
     (cryptopals) bob: sending public key
     (cryptopals) mallory: REceIvED pUBlic keY d14952314d5de233ef0dd0a178617f7f07ea082c
     (cryptopals) mallory: ReLAyINg pUbliC KeY d14952314d5de233ef0dd0a178617f7f07ea082c
     (cryptopals) alice: received public key d14952314d5de233ef0dd0a178617f7f07ea082c
     (cryptopals) alice: sending ciphertext +nbU0t3nLX3WmKoY3+pdmilVcd2I6fJfGuC3RTn0h5E=
     (cryptopals) mallory: rECeIveD CiPHeRTexT +nbU0t3nLX3WmKoY3+pdmilVcd2I6fJfGuC3RTn0h5E=
     (cryptopals) mallory: DEcRyptEd cIPheRTeXt: "attack at 10pm"
     (cryptopals) mallory: reLayINg cIpheRtExt
     (cryptopals) bob: received ciphertext +nbU0t3nLX3WmKoY3+pdmilVcd2I6fJfGuC3RTn0h5E=
     (cryptopals) bob: decrypted ciphertext: "attack at 10pm"
     (cryptopals) bob: replying with ciphertext 3i7fLAZXJv7+cr3qrI8KDKhfe6FpJq62yVtaCt9dlrUodMiRVtJ7ZmKtJ8ku0r4x
     (cryptopals) mallory: reCeiVeD CipHeRtExt 3i7fLAZXJv7+cr3qrI8KDKhfe6FpJq62yVtaCt9dlrUodMiRVtJ7ZmKtJ8ku0r4x
     (cryptopals) mallory: DeCrYpteD cIphErteXt: "confirmed, attacking at 10pm"
     (cryptopals) mallory: ReLaYINg CiPHeRTexT
     (cryptopals) alice: received ciphertext 3i7fLAZXJv7+cr3qrI8KDKhfe6FpJq62yVtaCt9dlrUodMiRVtJ7ZmKtJ8ku0r4x
     (cryptopals) alice: decrypted ciphertext: "confirmed, attacking at 10pm"
     (cryptopals) mallory: ending session
 
 #### 5.36
 
 SRP (Secure Remote Password) is an authentication protocol for which
 a client authenticates with a server via a zero-knowledge proof.
 Cryptopals.SRP implements it much in the same way that Cryptopals.DH
 implements Diffie-Hellman; here one can perform the protocol via the
 'server' and 'client' functions analogously.
 
 Some interleaved logs for 'server "3000" srp' and 'client "3000" srp
 auth':
 
     (cryptopals) server: listening..
     (cryptopals) client: session established
     (cryptopals) client: sending authentication request
     (cryptopals) server: received authentication request for l33th4x0r@hotmail.com
     (cryptopals) server: acking authentication request for l33th4x0r@hotmail.com
     (cryptopals) client: received authentication request ack
     (cryptopals) client: sending MAC 6p7eE/pTSijdReePtswOKDZZUFYhLkJfeKps0GD4Yc4=
     (cryptopals) server: received MAC 6p7eE/pTSijdReePtswOKDZZUFYhLkJfeKps0GD4Yc4=
     (cryptopals) server: OK
 
 #### 5.37
 
 If the client forwards A = 0 (or anything congruent modulo N to 0) as
 its public key, then the server will compute S = 0 as its shared secret.
 Whoops! The client can then just pass along the appropriate MAC to
 authenticate.
 
 Example, with the client using the 'srpzero' protocol and 'authZero'
 initial action:
 
     -- GHCi instance one
     > server "3000" srp
     -- GHCi instance two
     > client "3000" srpZero authZero
     (cryptopals) server: listening..
     (cryptopals) client: session established
     (cryptopals) client: sending authentication request with a zero key
     (cryptopals) server: received authentication request for l33th4x0r@hotmail.com
     (cryptopals) server: acking authentication request for l33th4x0r@hotmail.com
     (cryptopals) client: received authentication request ack
     (cryptopals) client: sending MAC 5xO9hEUJOTX5EIU+DmYV0QOs1L1oVp3fphREooN/8L4=
     (cryptopals) server: received MAC 5xO9hEUJOTX5EIU+DmYV0QOs1L1oVp3fphREooN/8L4=
     (cryptopals) server: OK
 
 #### 5.38
 
 The simplified protocol can be run with the 'server' and 'client'
 functions in Cryptopals.SRP.Simple.
 
 For the MITM attack, the idea is that, posing as the server, Mallory has
 control over the parameters 'salt', 'b', 'B', and 'u', but doesn't know
 anything to do with 'x', and so has to guess at that.
 
 If Mallory supplies salt = mempty, B = g mod n, and u = 1, then the
 client will compute:
 
     S = g ^ (a + x) mod n
 
 and forward him MAC = HMAC-SHA256(SHA256(S), mempty). Duly supplied with
 the client's public key ('A') and MAC, and using a trivial b = 1 as a
 secret key, Mallory can guess x = SHA256(password) to compute:
 
     S' = (A v) mod n
        = (A g ^ x) mod n
 
 and then check if HMAC-SHA256(SHA256(S'), mempty) = MAC. If it verifies,
 then he knows the password.
 
 To not make this too annoying, I'll draw the password to be cracked from
 /usr/share/dict/words. Once Mallory provides the public key and MAC
 from the client, we'll generate our dictionary and check if the MAC is
 present in the keyspace using a compiled, optimized binary.
 
 Here's a run of the MITM protocol (`mallory "3000" mitm` and `client
 "3000" srpsimple auth`):
 
     (cryptopals) mallory: LiSteNiNG..
     (cryptopals) client: session established
     (cryptopals) client: sending authentication request
     (cryptopals) mallory: rECeIvEd aUTheNtICaTioN ReQUesT fOr l33th4x0r@hotmail.com
     (cryptopals) mallory: wiTh PuBLiC kEy 4992116105881074929461308645820763003777270799868975573291
     (cryptopals) mallory: aCKiNg AuTheNTicAtIon ReQueST FOr l33th4x0r@hotmail.com
     (cryptopals) client: received authentication request ack
     (cryptopals) client: sending MAC f20ac41224b4054d2f89a7c319ed5bf3f8bb68cf4169f620f45e49acb4dd179c
     (cryptopals) mallory: rECeIvEd MAC f20ac41224b4054d2f89a7c319ed5bf3f8bb68cf4169f620f45e49acb4dd179c
     (cryptopals) mallory: USiNg PaRaMeTeRs 4992116105881074929461308645820763003777270799868975573291 aNd f20ac41224b4054d2f89a7c319ed5bf3f8bb68cf4169f620f45e49acb4dd179c
     (cryptopals) mallory: GoINg ofFLinE..
 
 Now taking those parameters to the `offline-dictionary-attack` binary we get
 the result pretty quickly:
 
     $ PK="4992116105881074929461308645820763003777270799868975573291"
     $ MAC="f20ac41224b4054d2f89a7c319ed5bf3f8bb68cf4169f620f45e49acb4dd179c"
     $ offline-dictionary-attack "$PK" "$MAC"
     (cryptopals) success
     (cryptopals) password: omniana
 
 #### 5.39
 
 A note on primegen for RSA: I didn't bother with it, as recommended, but
 looked at how it should be done. It seems straightforward; one generates
 a sufficiently large random number, then tests that it isn't divisible
 by the first several hundred primes, then performs a probabilistic
 primality test sufficiently many times that the error probability is
 very small. A reference suggested that the error probability should be
 less than 1 / 2^128.
 
 I used cryptonite's Crypto.Number.Prime module, which implements the
 above procedure.
 
 In any case, RSA: one finds two k-bit primes, 'p' and 'q', and uses
 their product to construct a public modulus n = pq and value
 `t = (p - 1) (q - 1)`. The public key is (n, e) for 'e' a number
 relatively prime to 't', and the private key is (n, d), for d such that
 `ed = 1 mod t` (i.e., 'd' is congruent mod 't' to the inverse of 'e').
 "Relatively prime" or "coprime" means, for two numbers 'a' and 'b', that
 they have a greatest common denominator of 1.
 
 Encryption and decryption are then just modular exponentiation
 operations using the keys. To go from Natural to ByteString and back,
 I used some old functions -- roll and unroll -- that I wrote for
 [urbit-hob](http://git.jtobin.io/urbit-hob) a few years back (though
 actually I think I cribbed them from the Data.Binary internals):
 
     data Key = Key Natural Natural
       deriving (Eq, Show)
 
     data Keypair = Keypair {
         sec :: Key
       , pub :: Key
       } deriving (Eq, Show)
 
     keygen :: Int -> IO Keypair
     keygen siz = loop where
       loop = do
         p <- fromIntegral <$> P.generatePrime siz
         q <- fromIntegral <$> P.generatePrime siz
         let n   = p * q
             et  = pred p * pred q
             e   = 3
             md  = modinv e et
         case md of
           Nothing -> loop
           Just d  -> pure $ Keypair (Key d n) (Key e n)
 
     encrypt :: Key -> BS.ByteString -> BS.ByteString
     encrypt (Key e n) m = unroll (DH.modexp (roll m) e n)
 
     decrypt :: Key -> BS.ByteString -> BS.ByteString
     decrypt = encrypt
 
 Works fine:
 
     > Keypair sec pub <- keygen 1024
     > let cip = encrypt pub "secret!"
     > TIO.putStrLn $ T.take 32 $ B64.encodeBase64 cip
     zZFjaw7BR6rP0EaNsTFRnCInwsghANrE
     > let msg = decrypt sec cip
     > msg
     "secret!"
 
 The Cryptopals.RSA module exports the keygen, encrypt, and decrypt
 functions, as well as modinv and roll & unroll.
 
 #### 5.40
 
 The problem behind the Chinese Remainder Theorem, as formulated by one
 孫子 (not *that* 孫子) and passed on to me via Wikipedia, is:
 
 > There are certain things whose number is unknown. If we count them by
 > threes, we have two left over; by fives, we have three left over; and
 > by sevens, two are left over. How many things are there?
 
 I.e. what is x, if x is congruent to 2 mod 3, 3 mod 5, and 2 mod 7?
 
 In Sunzi's case the answer is congruent to 23 mod 105, and the Chinese
 Remainder Theorem states that such a solution always exists given
 certain conditions (notably that the moduli are pairwise coprime).
 
 In our case, for plaintext 'm' and ciphertexts c0, c1, and c2, we have
 that m ^ 3 is congruent to c0 mod n0, c1 mod n1, and c2 mod n2. The
 Chinese Remainder Theorem asserts that there exists some 'c' that is
 congruent to m ^ 3 modulo `n0 * n1 * n2`. The trick here (this is known
 as Håstad's attack, apparently) is that since m is smaller than every n,
 we have that m ^ 3 is smaller than `n0 * n1 * n2`, and so that 'c' is
 precisely equal to m ^ 3, rather than congruent to it.
 
 So, following the CRT construction:
 
     > let msg = "attack at 10pm"
     >
     > Keypair _ p0@(Key e0 n0) <- keygen 1024
     > Keypair _ p1@(Key e1 n1) <- keygen 1024
     > Keypair _ p2@(Key e2 n2) <- keygen 1024
     >
     > let c0 = encrypt p0 msg
     > let c1 = encrypt p1 msg
     > let c2 = encrypt p2 msg
     >
     > let ms0 = n1 * n2
     > let ms1 = n0 * n2
     > let ms2 = n0 * n1
     >
     > :{
     > let res = (roll c0 * ms0 * modinv' ms0 n0
     >          + roll c1 * ms1 * modinv' ms1 n1
     >          + roll c2 * ms2 * modinv' ms2 n2)
     >       `mod`
     >           (n0 * n1 * n2)
     > :}
 
 The 'integer-roots' package provides a helpful cube root function:
 
     > unroll $ R.integerCubeRoot res
     "attack at 10pm"