/Cryptopals-challenges

Challenge accepted!

Primary LanguagePython

CRYPTOPALS WRITE-UP

SET 1

1.1. Convert hex to base64

  • Step 1: Convert hex to ascii using decode('hex')
  • Step 2: Convert ascii to base64 using b64decode

1.2. Fixed XOR

  • 2 methods:
    • 1st method: Loop through each bit and assign 1 if corresponding bit is different, 0 otherwise
    • 2nd method: Loop through each bit, and use ^ operator (xor)

1.3. Single-byte XOR cipher (Substitution cipher)

  • Description: ciphertext = key XOR plaintext. key contains a single-byte and its duplication until the key has the same length as plaintext. e.g:

  • How to break: What do we have? ciphertext. How to get plaintext? plaintext = ciphertext XOR key => So we need key => Bruteforce single-byte key (maybe from 0-9,A-Z,a-z). With every key, after doing XOR operation to get plaintext, calculate how "english" the plaintext is, based on letters-frequency table. The key with highest score would be the true key!

1.4. Detect single-character XOR

  • This challenge asks us to find which of the 60-character strings in the file has been encrypted by single-character XOR.
  • Use break_single_byte_xor in challenge 3, iterate through all the strings, to find the possible single-character xor key and word score of each line
  • Result: Now that the party is jumping\n

1.5. Implement repeating-key XOR

  • Step 1: Duplicate key "ICE" to the same length as message
  • Step 2: XOR them to get ciphertext!

1.6. Repeating-key XOR cipher (Vigener's cipher)

  • Description: ciphertext = key XOR plaintext. key contains multiple-bytes and its duplication until the key has the same length as plaintext. e.g:

  • How to break:
    • Step 1: Get keysize
      • Break ciphertext into chunks with length keysize (brute-force). For each keysize, calculate Hamming distance between every 2 chunks of ciphertext -> Derive average Hamming distance of the whole ciphertext for that keysize
      • The keysize with lowest average Hamming distance is the correct one
    • Step 2: Get key
      • Break ciphertext into chunks with length of correct keysize. Create a block of every first-byte of every chunk (that block would be encrypted with single-byte key XOR) -> Decrypt that block using above breaking single-byte xor cipher to get the key letter
      • Do the same with next blocks of second-byte, third-byte,...,keysize-byte to get the FULL key!
    • Step 3: Get plaintext
      • Duplicate key to get key string with length of ciphertext
      • plaintext = ciphertext XOR key_string
      • Enjoy! :)

1.7. AES in ECB mode

  • Use Crypto module in python to implement ECB mode: from Crypto.Cipher import AES

1.8. Detect AES in ECB mode

  • ECB's problem: the same block of plaintext will encrypt to the same ciphertext
  • So loop through each line of ciphertext, check which one has duplicated block of ciphertext, it will be the one encrypted using ECB mode

SET 2

2.9. Implement PKCS#7 padding

  • E.g: For a block of 8 bytes
  • For a block size of X bytes, the missing bytes will be padded with the total number of missing bytes

2.10. Implement CBC mode

  • In CBC mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. We need an IV for the first block of plaintext.
  • The encrypt() function will split the plaintext into blocks (usually size 16), and then do the encryption
  • The decrypt() function will split each block of ciphertext, decrypts it, and XORs with the previous block of ciphertext to recover the plaintext

2.11. An ECB/CBC detection oracle

  • This challenge asks us to detect whether we’ve encrypted a text with ECB or CBC, chosen at random.
  • Recall the properties of ECB vs CBC — ECB will take two identical plaintext blocks and produce two identical ciphertext blocks.
  • So just detect ECB using the function in challenge 8. If it's ECB, return ECB. If not, return CBC

2.12. Byte-at-a-time ECB decryption (Simple)

  • WHAT WE HAVE? an oracle that produces AES-128-ECB(your-string || unknown-string, random-key)
  • GOAL: find unknown-string with this oracle.
  • STEPS:
    • Step 1: find the block size of the cipher
      • feed in incrementing offsets to the oracle, until the ciphertext length increases.
      • The size of the increase will be block_size, because of the padding.
    • Step 2: find the flag byte-by-byte
      • How? Since I control my-string, I can ensure each time that the oracle encrypts 15 bytes that I know + one unknown byte. I can then create a table of all possible ciphertexts of the 15 known bytes + 1 unknown byte, and compare the ciphertext the oracle returns to the ciphertexts in my table.

2.13. ECB cut-and-paste

  • WHAT WE HAVE? "login" page (profile_for(email) function) with input for email + ciphertext (or cookie) for user profile AFTER inputting email + decrypting function (with unknown key - set key as global) to see user profile
  • GOAL: Change our email so that the ciphertext from "email=XX..XX&uid=10&role=user" => "email=XX..XX&uid=10&role=admin" (XX..XX is our email input)
  • WHAT WE KNOW? This challenge uses AES128 => each block has 16 bytes 2 things in ciphertext NEED to be changed - "XX..XX" and "user"->"admin" => So we need at least 2 blocks (16 bytes each block - but in practice, we don't know which cipher it uses, we need a function to find the block size) to hold each one. Why need separate blocks to hold for each text we want to change? 1 byte is changed -> whole block is changed
  • WHAT TO DO?
    • GOAL: Find EVIL ciphertext of "email=XX..XX&uid=10&role=admin"
    • 3 main steps to do:
      • STEP 1: Get ciphertext1 of 1st block "email=XX..XX&uid=10&role="
        • STEP 1.1: Determine how many "X" to input based on the block size
        • STEP 1.2: Input email = "XX..XX" ("XX..XX" can be any character - "AA..AA")
        • STEP 1.3: Get ciphertext of profile_for(email) (only get padded block of "email=XX..XX&uid=10&role=")
      • STEP 2: Get ciphertext2 of 2nd block "adminPPPPPPPPPPP" (P - padding byte)
        • STEP 2.1: Determine how many "X" to input to push "admin" to 2nd block
        • STEP 2.2: Input email = "XX..XX" || "admin" || padding PKCS7
        • STEP 2.3: Get ciphertext of profile_for(email) (only get 2nd block of 16 bytes)
      • STEP 3: EVIL ciphertext = ciphertext1 || ciphertext2
    • Thanks to ECB's vulnerability (same plaintext '+' same key = same ciphertext), if we have ciphertext of "email=XX..XX&uid=10&role=admin", we ALWAYS have plaintext as "email=XX..XX&uid=10&role=admin" under the same key in session

2.14. Byte-at-a-time ECB decryption (Harder)

  • GOAL: Decrypt unknown string byte-by-byte
  • WHAT WE HAVE? Ciphertext AES_128_ECB(random_prefix || user's input || unknown_string)
  • WHAT WE KNOW? We can decrypt unknown_string byte-by-byte by repeatedly calling AES_128_ECB with specific input
  • WHAT TO DO? Same as challenge 12 + determine "random_prefix" size so that we can pad the input with missing bytes of "random_prefix" to get block-aligned.
    • How to determine "random_prefix" size?
      • 1.Create a buffer of block size length
      • 2.Concatenate your buffer with itself N times (where N is a large positive integer) and use this as your input to the encryption oracle. For example, if N = 2 and your buffer is "YELLOW SUBMARINE", your input would be "YELLOW SUBMARINEYELLOW SUBMARINE".
      • 3.Pass your input to the encryption oracle to obtain a ciphertext. Search the ciphertext for N consecutive identical blocks. The index of the first byte of the N blocks is the beginning of your input and also the length of the random_prefix!
      • 4.If you can't find N consecutive identical blocks in the ciphertext, it's probably because the random_prefix is not block aligned. Prepend 1 byte to your input and go back to step 3.
      • 5.Note: To get the true size of the random_prefix, you must subtract the number of prepended padding bytes
      • 6.If you have prepended block_size - 1 bytes to the input and you still cannot find N consecutive identical blocks, the ciphertext wasn't encrypted in ECB mode and we're out of luck.

2.15. PKCS7 padding validation

2.16. CBC bitflipping attacks

  • WHAT WE HAVE?

    • ciphertext = generate( AES_128_CBC_ENC("comment1=cooking%20MCs;userdata=" || payload || ";comment2=%20like%20a%20pound%20of%20bacon") )
    • output = AES_128_CBC_DEC(ciphertext)
    • Only input in payload ";","=" will be removed from input by generate() function

  • GOAL: Output contains ";admin=true;"

  • WHAT TO DO?

    • Modify ciphertext -> Break CBC mode cipher
    • How to modify ciphertext? ()
      • Theory: In CBC mode, since we XOR each decrypted block with previous ciphertext block, we can change a byte in plaintext by changing CORRESPONDING byte in previous ciphertext (though this completely corrupts previous plaintext - but we can create a JUNK block to be corrupted) => use this to produce the unescaped characters ";" and "=" in the plaintext!
      • Practice:
        • junk_block = "A" * 16
        • admin_block = "AadminAtrueA"
        • => Change 3 "A" bytes in admin_block with ";","=",";" respectively. How? change ciphertext of each corresponding "A" byte in junk_block, so that after XOR function, we get ";","=",";". Change with what? Here's intersting part. (1) x XOR y = 'A' || x: ciphertext byte in junk_block, y: decrypted byte (2) z XOR y = ';' || z: ciphertext byte we need to find (1) XOR (2) => z = x XOR ('A' XOR ';') replace x with z ... same steps with "=" ... after changing 3 bytes in ciphertext, we get the EVIL ciphertext = "....z1...z2...z3...."! decrypt it and enjoy!

SET 3

3.17. The CBC padding oracle

  • WHAT WE HAVE?

    • A ciphertext
    • A paddding oracle (a service that receives ciphertext -> decrypts it -> check valid PKCS7 padding -> return True | False)

  • GOAL? Decrypt ciphertext by calling padding oracle repeatedly (brute-force)

  • How?

    • Suppose we have 2 ciphertext blocks: C = C1 || C2, and plaintext of C2 is P2
    • Let the last byte in ciphertext block 1 be C1_15, last one in decrypted block 2 be D1_15, last one in plaintext block 2 be P2_15
    • Goal: guess P2_15 correctly
    • How?
      • Change C1_15 = C1_15 XOR guess XOR '0x01' -> We have new C'
      • Brute-force guess ( 0 <= guess <= 256), for each guess, padding_oracle(C') to get P2_15' = C1_15' XOR D1_15 = C1_15 XOR guess XOR '0x01' XOR D1_15 = P2_15 XOR guess XOR '0x01'
      • If guess == P2_15 => Save guess
    • Repeat with second to last byte, third to last byte, ... with padding byte "0x02","0x03",... => Decrypted block C2
    • Repeat the same process to decrypt block C3 by modifying ciphertext block C2, C4 by C3, C5 by C4, ...
    • NOTE: Decrypt block C1 why modifying ciphertext IV

3.18. Implement CTR, the stream cipher mode

  • CTR encryption:
  • CTR decryption:
  • CTR parameters:
    • key= YELLOW SUBMARINE
    • nonce = 0
    • format = 64 bit unsigned little endian nonce, 64 bit little endian block count (byte count / 16)

3.19. Break fixed-nonce CTR mode using substitutions

  • THEORY: Because the CTR nonce wasn't randomized for each encryption, each ciphertext has been encrypted against the same keystream.

  • WHAT TO DO?

    • Function 1: (multiple encryption) take a list of base64 text and encrypt each one then return list of encrypted text
    • Function 2: (multiple decryption) take a list of ciphertexts and find the keystream

  • HOW TO FIND?

    • ciphertext XOR plaintext = keystream
    • ciphertext XOR keystream = plaintext
    • Take the longest ciphertext, brute-force first corresponding plaintext byte then XOR with first ciphertext byte to get corresponding keystream byte X.
    • XOR that keystream byte with the rest corresponding bytes in other ciphertexts to produce corresponding plaintext bytes.
    • Check how "english" those plaintext bytes are -> save score.
    • Brute-force next plaintext byte -> repeat. The keystream byte X with the highest score would be the CORRECT keystream byte.
    • Repeat same process with next bytes
    • Finally, we get the full keystream -> XOR it with each ciphertext to get plaintext

3.20. Break fixed-nonce CTR statistically

  • WHAT TO DO? Same as 19
  • HOW TO DECRYPT:
    • Concatenate all padded-to-longest-length ciphertexts into 1 string
    • Since each ciphertext is encrypted using the same key -> the whole string is encrypted with repeated-key-xor
    • Use break-repeating-key-xor function in challenge 6 to get the keystream
    • XOR that keystream with each ciphertext to get plaintext

3.21. Implement the MT19937 Mersenne Twister RNG

3.22. Crack an MT19937 seed

  • Just brute-force the seed (timestamp) backward in time (seed_trial -= 1) until it has the same PRNG with the original seed

3.23. Clone an MT19937 RNG from its output

  • To clone an MT19937 RNG, we need to find its 624-value internal state by reverse-engineering MT19937
  • STEPS:
    • get 624 RNG outputs
    • untemper each one (more details in my code)
    • Create a new generator and set it to have the same state
  • QUESTION! What if we don't have all 624 outputs? can we still predict next output with clone?

3.24. Create the MT19937 stream cipher and break it

  • What we have?
    • Task 1:
      • create a MT19937Cipher with a given key as seed to encrypt / decrypt a plaintext / ciphertext
      • with only ciphertext, find the MT19937Cipher key using a known plaintext
    • Task 2:
      • create a token using MT19937RNG seeded with current time
      • write a function that checks whether a token is generated using MT19937RNG seeded with timestamp
  • What to do?
    • Task 1:
      • create a MT19937Cipher class with encrypt / decrypt functions. encrypt() generates a keystream using MT19937RNG seeded with 16-bit key (repeatedly until keystream has the same length with plaintext)
      • Brute-force key from 0 - 2^16 until the decrypted plaintext contains the known-plaintext
    • Task 2:
      • same as 22

SET 4

4.25. Break "random access read/write" AES CTR

  • GOAL: Recover the original plaintext after encrypt it under CTR and edit ciphertext by edit(ciphertext, key, offset, newtext).
  • HOW?
    • Because we can seek into the ciphertext and edit arbitrary characters, we we can simply guess each plaintext character.
    • For each byte in the ciphertext, I can try all 256 characters by replacing the ciphertext byte with my encrypted guess using the provided edit() function. If the new ciphertext exactly matches the original ciphertext, then I know my guess for the plaintext character is correct, since it encrypted to the same byte.

4.26. CTR bitflipping

  • WHAT WE HAVE?
    • An oracle - a service that encrypt a text = prefix || our input || postfix using AES in CTR mode, then return ciphertext
    • That oracle will clean ";", "=" from our input
    • That oracle also provide decrypt() to decrypt ciphertext
  • GOAL?
    • Make output of oracle's decrypt() produce a text include ";admin=true"
  • HOW?
    • Step 1: get ciphertext prefix size => append ADMIN ciphertext (C2) after that
      • Encrypt two different ciphertexts
      • Since the stream ciphers encrypts bit by bit, the prefix length will be equal to
      • the number of bytes that are equal in the two ciphertext.
    • Step 2: create ADMIN ciphertext
      • We can get ciphertext C1: C1 XOR keystream = "?admin?true" (1)
      • We want to get ciphertext C2: C2 XOR keystream = ";admin=true" (2)
      • (1) XOR (2) => C1 XOR C2 = "?admin?true" XOR ";admin=true" (3)
      • C1 XOR (3) => C2 = C1 XOR "?admin?true" XOR ";admin=true"
      • EVIL ciphertext = ciphertext(prefix) + C2 + ciphertext(postfix)
      • => Now decrypt EVIL ciphertext to get ADMIN privilege!!

4.27. Recover the key from CBC with IV=Key

  • WHAT WE HAVE?
    • An insecure oracle provides
      • a service that encrypts prefix || messages || postfix in CBC mode with IV = key
      • a service to decrypt ciphertext + check ADMIN privilege + check if all characters in a plaintext are ASCII compliant (in ASCII table - printable), if not, will show exception and return the corrupted text
  • GOAL?
    • Get the hidden key from oracle
  • HOW?
    • Basically, send 3 blocks ( block_size = 16 (AES) ) of ciphertext to oracle's service - check admin:
      • CT = C1 || "\x00" * block_size || C1
      • oracle decrypts plaintext: PT = iv XOR dec(C1) || ........ || "\x00 * block_size" XOR dec(C1)
      • oracle returns corrupted PT from exception to attacker
      • Attacker computes: P1 XOR P3 = iv XOR "\x00 * block_size" = iv = key

4.28. Implement a SHA-1 keyed MAC

4.29. Break a SHA-1 keyed MAC using length extension

  • WHAT WE HAVE?
    • An oracle - a service using SHA1-MAC to:
      • Generate a SHA1 MAC digest for a message using a secret key
      • Check the given digest matches the SHA1 MAC of a message
  • GOAL?
    • Modify a message in-flight provided with its digest -> forge a new message containing extra payload (e.g: 'admin=true')
  • HOW?
    • To break SHA1 MAC, we need to get its padding state (pre-processing state), after forged the new message, and the internal state (h0,h1,h2,h3,h4)
    • Brute-force key-length until forged digest is the same as digest of forged message:
      • Get the forged message (original-message || glue-padding || new-message)
      • glue-padding? Pads the given message the same way the pre-processing of the SHA1 algorithm does.
      • Get the SHA1 internal state (h1, h2, h3, h4, h5) by reversing the last step of the hash
      • Get SHA1 hash of the extra payload, by setting the state of the SHA1 function to the cloned one that we deduced from the original digest.
      • If the forged digest is valid, return it together with the forged message.
      • Else, keep brute-forcing

4.30. Break an MD4 keyed MAC using length extension

  • Same as 29 with MD4 implementation

4.31. Implement and break HMAC-SHA1 with an artificial timing leak

  • WHAT WE HAVE?
    • A server:
    • A client:
      • Recover the digest byte-by-byte with timing attack
  • GOAL?
    • Recover the digest byte-by-byte with timing attack
  • HOW?
    • Iterate through all possible bytes (0 - 15 <=> 0 - F), making a request with my known bytes + byte_guess + padding.
    • Take the maximum delay each time, which would occur when I've guessed the byte correctly, causing another sleep of 50ms, for an added delay of 100ms.
    • The byte with maximum delay each time is the correct byte for a position in digest
    • Append that byte to known bytes (found bytes) and brute-force next byte
  • NOTE:
    • Run challenge_31_server.py before attack
    • Then run challenge_31_client.py

4.32. Break HMAC-SHA1 with a slightly less artificial timing leak

  • Same as 31 but add normalization method for more accuracy
  • NOTE: Run challenge_31_server.py before attack

SET 5

5.33. Implement Diffie-Hellman

  • Diffie-Helman (basic key exchange):
  • Alice & Bob wants to exchange secret key in an open channel
  • => Alice sends A to Bob, Bob sends B to A
  • Alice has secret a, Bob has secret b such that, A = (g ^ a) mod p, B = (g ^ b) mod p (g, p are constants)
  • => Secret key of Alice & Bob is kAB = A^b = B^a = (g ^ ab) mod p

5.34. Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection

  • kAB = (p^a) mod p = (p^b) mod p = 0
  • -> Secret key of Alice & Bob becomes 0!
  • -> Hacker uses the key to decrypt messages

5.35. Implement DH with negotiated groups, and break with malicious "g" parameters

  • Same as challenge_34
  • NOTE:
    • When g = 1, all powers of g are 1 as well => secret key is always 1
    • When g = p, as in challenge 34, powers are all divisible by p => secret key is always 0
    • When g = p-1 is raised to a power, then mod p will be either 1 or -1

5.36. Implement Secure Remote Password (SRP)

  • Secure Remote Password (SRP)
  • A form of authentication in which the client does not need to reveal password
  • Server:
    • stores a verifier for a client that wants to authenticate, v = g ^ x, x = H(salt, password)
    • A salt is a random value used to safeguard the password hash from being easily identifiable in a hash lookup rainbow table
    • Generate a session key K with verifier
  • Client:
    • After exchaing some parameters with server, generate a session key K with password
    • => The server checks client's K == server's K => If true, successfully authenticates the client

5.37. Break SRP with a zero key

  • NOTE!!! RUN challenge_36_server first
  • Break SRP with a zero key:
    • Server produces K by:
      • S = (A * v ^ u) ^ b mod N
      • K_server = H(S)
    • => A = 0 or A = N or A = N^2 => S = 0
    • => we can authenticate simply by sending K_client = H(0) without knowing the password!

5.38. Offline dictionary attack on simplified SRP

  • NOTE!!!!
    • Use Python 3 for challenge_38_server.py and challenge_38_client.py
    • Due to issues of sha256 in python 2 (e.g: "utf-8" encoding issue: UnicodeDecodeError: 'ascii' codec can't decode byte...)
    • Python3 doesn't have web.py yet so I had to use "flask" for server-client protocols
  • Explain:
    • Same as challenges 36,37 but now Server "leaks" some parameters like b, B, u, salt
    • From those params, MITM hacker can compute session key K and brute-force K until get common dictionary word for password

5.39. Implement RSA

  • RSA
    • Basic of RSA is about to find 3 prime numbers e, d, n (n - very large prime) such that for all m (0 < m <n)
    •   (m ^ e) ^ d = m (mod n)
    • NOTE: even knowing e and n or even m it can be extremely difficult to find d
  • RSA algorithm involves 4 steps:
    • Key generation: + compute p, q, n = pq, phi(n) = (p-1)(q-1) such that lcm(n, phi(n)) != 1 + e = 3 (for this challenge) + d = invMod(e, n)
    • Key distribution
      • Suppose that Bob wants to send information to Alice. If they decide to use RSA,
      • Bob must know Alice's public key (n, e) to encrypt the message and Alice must use her private key (n, d)
      • to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key to Bob
      • via a reliable, but not necessarily secret, route. Alice's private key is never distributed.
    • Encryption
      • ciphertext_int = message_int ^ e (mod n)
    • Decryption
      • message_int = ciphertext_int ^ d (mod n)

5.40. Implement an E=3 RSA Broadcast attack

  • Attack RSA based on CRT (Chinese Remainder Theorem):
    • Let p, q be coprime. Then the system of equations:
      • x = a (mod p)
      • x = b (mod q)
    • have a unique solution x modulo (p * q)
  • For RSA:
    • Attacker got CT1, CT2, CT3 with corresponding public keys N1, N2, N3:
      • C1 = M^3 mod N1
      • C2 = M^3 mod N2
      • C3 = M^3 mod N3
    • => We need to find M (unique)
    • => Follow the steps in the challenge to find M

SET 6

6.41. Implement unpadded message recovery oracle

  • The Oracle (server) provides service to encrypt user's message and decrypt ciphertexts (NOT in database)
  • The attacker can ask for the encryption and decryption of anything he/she wants - except user's ciphertexts which are in database
  • => GOAL: Attacker recover user's message from its ciphertext using decryption service of server
  • HOW?
    • In Unpadded RSA, if operations like multiplication and addition are carried out on ciphertext, it is as if the same operation were applied to the plaintext
    • => The attacker can't ask for the decryption of user's ciphertext, but attacker can ask for the decryption of ciphertext_2 and attacker knows that the result will be plaintext_2.
    • => Just divide out the scaling factor, and attacker has the plaintext.

6.42. Bleichenbacher's e=3 RSA Attack

  • When signing a message using RSA:
    • User generates signature using (n, d): sig = m ^ d mod n
    • Server verifies signature using (n, e): (sig ^ e mod n) == m
  • In this challenge, instead of signing message, m, we sign the PKCS1.5 encoding of message's hash:
    • 00 01 FF FF ... FF 00 ASN.1 HASH
  • How to exploit?
    • A faulty PKCS1.5 verifier might not check all "FF" bytes in middle exist
    • We can generate "corrupted" PKCS1.5 padding message: forged_m = 00 01 FF 00 ASN.1 HASH_M GARBAGE
    • => Forged signature (forged_sig) will be the cube root of that (in power of 1/e with e=3)
  • Verifying process:
    • Oracle checks:
      • (forged_sig ^ e) mod n contains "00 01 FF 00" ? True because = forged_m ^ ((1/e) * e) mod n = forged_m
      • HASH_M == H(message) ?

6.43. DSA key recovery from nonce

  • NOTE: USE PYTHON3 !! python2 doesn't give correct result, I'll look into it when I have time.

  • DSA (Digital Signature Algorithm) involves 3 main parts:

    • Key generation:
      • Generate a 1024-bit prime p
      • Find a 160-bit prime divisor q of p-1
      • Find an element g which generates the subgroup of p with q elements
      • Choose a random private key x (0 < x < q)
      • Compute y = g ^ x mod p
      • => The keys are now:
        • public = (p, q, g, y)
        • private = (x)
    • Signing:
      • Choose a random key 0 < k < q
      • Compute r = g ^ k mod q
      • Compute s = (SHA(message) + x*r) * inv_mod(k, q) mod q
    • Verifying:
      • Compute w = inv_mod(s, q)
      • Compute u1 = w * SHA(message) mod q
      • Compute u2 = w * r mod q
      • Compute v = (g^u1 * y^u2 mod p) mod q
      • Verify v == r mod q

  • How to recover private key from signature's nonce?

    • Attacker has: H(message), r, s, y (public key)
    • Given k, private key can be calculated: x = (s * k) - H(message) * inv_mod(r,q) mod q
    • Attacker brute-forces k until get_public_key_from_private_key(x) == y
    • if True, return x - the private key

6.44. DSA nonce recovery from repeated nonce

  • NOTE: USE PYTHON3 for this challenge!! python2 doesn't give correct result, I'll look into it when I have time.

  • When messages are signed using DSA with repeated nonce (r, k), given a pair of messages, attacker can find k using the formula:

  • Proof! (mathematically)

    • private key formula:
      • x = (s1 * k) - m1 * inv_mod(r1,q) mod q
      • x = (s2 * k) - H(messa * inv_mod(r2,q) mod q
      • if r1 == r2:
      • => k = (m1 - m2) / (s1 - s2) mod q
    • We have k => We have x! (same as challenge 43)

6.45. DSA parameter tampering

  • If g = p + 1 or g = 0 => r = (g ^ k) mod p = 1 for ALL k => same signature can be verified for different messages

6.46. RSA parity oracle

  • plaintext P is within the bounds [0, N] - LB(lower bound) = 0, UB(uppder bound) = N iterate this algorithm log2(N) times to find P from original ciphertext C
    • C' = ((2^e mod N) * C) mod N
    • if (oracle.check_parity(C') == ODD):
      • LB = (LB + UB) / 2
    • else:
      • UB = (LB + UB) / 2
  • => The final upper bound is the plaintext we need to find

6.47. Bleichenbacher's PKCS 1.5 Padding Oracle (Simple Case)

  • Oracle (server):

    • Implement RSA to encrypt, decrypt messages
    • Check PKCS1.5 valid padding of ciphertext

  • Attacker:

    • Intercept a ciphertext
    • Use server's checking PKCS1.5 padding to crack the plaintext from ciphertext

  • PKCS1.5:

    • 00 || 02 || padding_string || 00 || data_block

  • HOW? (this challenge is basically full of math instructions so I just follow the steps (more detailed write-up of math when I have time) more details below or follow this link:http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf)

    • Step 1: Blinding.
    • Step 2: Searching for PKCS conforming messages
      • 2.a: Start the search
      • 2.b: Searching with more than one interval left
      • 2.c: Searching with one interval left
    • Step 3: Narrowing the set of solutions

6.48. Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case)

  • SAME AS 47
  • Difference: Key bit length = 768 => takes a bit more time to run

SET 7

7.49. CBC-MAC Message Forgery

  • Server: verify request with valid MAC to continue transaction (shared key with user)
  • Part 1: Client can send IV as a parameter in request (Default IV: good_iv = "\x00" * 16 in CBC_MAC)
    • Hacker controls 1's account to get valid MAC for request: normal_msg = "_from=1&to=0&amount=10000"
    • Generates an evil request: evil_msg = "_from=2&to=0&amount=10000"
    • creates forged_iv = evil_msg XOR (normal_msg XOR good_iv)
    • Send normal request (normal_msg) along with forged_iv to get valid MAC for evil request
      • HOW: In server when CBC_MAC encryption happens,
        • 1st step: forged_iv XOR evil_msg[16] = normal_msg XOR good_iv
        • .............
      • => We receive orginal valid MAC for new evil request!
  • PART 2: the attacker uses length extension to append an evil string ";0:10000" to a recipients list in a victim's transaction.
    • The attacker first generates a MAC for a valid message that names him as a recipient.
    • He then intercepts a normal message like "from=2&tx_list=3:5000;4:7000" (hacker doesn't control 2,3,4),
    • and xors in his own message at the end, causing the resultant MAC to become his own MAC.

7.50. Hashing with CBC-MAC

  • Forged msg = evil_msg + (cbc_mac(evil_msg) XOR normal_msg[:16]) + normal_msg[16:]
  • CBC-MAC encrypting 1st block: evil_msg + cbc_mac(normal_msg[:16]) XOR normal_msg[:16] + normal_msg[16:]
  • CBC-MAC encrypting n-th block: Forged_mac = normal_mac

7.51. Compression Ratio Side-Channel Attacks

  • The server has services:
    • Format request (along with default, hidden session id)
    • Compress formatted request using "zlib"
    • Encrypt compressed data using CTR or CBC mode => then return the final length
  • Attacker will:
    • Send any request (any content)
    • Recover hidden session id (knowing only the length of encrypted, compressed, formatted request)
  • How?
    • Just know this: the more repeated strings in data, the better (return smaller length) zlib compresses data
    • Using that fact, brute-force session-id byte-by-byte with alphabet characters (the correct byte will reduce the most length of data)
      • In CTR mode, just like that.
      • In CBC mode, using the same fact to brute-force padding bytes with these characters '!@#$%^&*()-~[]{}'`, and at the same time also brute-force session id

7.52. Iterated Hash Function Multicollisions

  • Good reference: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf

  • WHAT TO DO?

    • Step 1: build merkle_damgard() hash function
    • Step 2: generate collisions
    • Step 3:
      • Take f, g are 2 different hash functions
        • f(x) is hashing function with "cheap" state "\x00\x00"
        • g(x) is hashing function with "expensive" state "\x00\x00\x00\x00"
      • Build h such that h(x) = f(x) || g(x)
      • Find collision between 2 hash functions f & g

  • NOTE: About generating collisions

    • Consider h(x) - a hash function (I use ECB for this challenge) that we can find 2 "colliding" messages from each hash
    • Here's how calling h(x) i times can generate 2^i colliding messages
      • E.g: i = 2

7.53. Kelsey and Schneier's Expandable Messages

  • GOAL: find x' such that H(x') = H(x) = y

  • GOOD reference (part 4.2 - long-Message Attacks with Expandable Messages): https://www.schneier.com/academic/paperfiles/paper-preimages.pdf

  • Steps:

    • Step 1: Generate an expandable message of length (k, k + 2^k - 1)
      • Step 1.1: Starting from the hash function's initial state, find a collision between a single-block message and a message of 2^(k-1)+1 blocks. + DO NOT hash the entire long message each time. Choose 2^(k-1) dummy blocks, hash those, then focus on the last block.
      • Step 1.2: Take the output state from the first step. Use this as your new initial state + and find another collision between a single-block message and a message of 2^(k-2)+1 blocks.
      • Step 1.3: Repeat this process k total times. Your last collision should be between a single-block message and a message of 2^0+1 = 2 blocks.
    • Step 2: Hash M and generate a map of intermediate hash states to the block indices that they correspond to
    • Step 3: Find a single-block "bridge" to intermediate state in map
    • Step 4: Generate a prefix of the right length such that len(prefix || bridge || M[i..]) = len(M)

7.54. Kelsey and Kohno's Nostradamus Attack

  • GOOD reference: https://eprint.iacr.org/2005/281.pdf
  • GOAL: make a prediction about some event that hashes to some output H and after the event has passed, create a correct "prediction" that also hashes to H, thus convincing people that we knew the results of the event beforehand
  • STEPS:
    • Step 1: Generate a large number of initial hash states. Say, 2^k with k = 8 (I use urandom(2) - 2 bytes for each state)
    • Step 2: Using "diamond structure", get your prediction from initial 2^k states (Get colliding messages with each 2 pair of states -> generate an intermediate hash value)
    • Step 3: You need to commit to some length to encode in the padding. Make sure it's long enough to accommodate your actual message, this suffix, and a little bit of glue to join them up. Hash this padding block using the state from step 2

7.55. MD4 Collisions

  • GOOD reference: https://fortenf.org/e/crypto/2017/09/10/md4-collisions.html

  • GOAL: Given a message block M (I use urandom), find a message block M', differing only in a few bits, that will collide with it in hash value generated by MD4. Just so long as a short set of conditions holds true for M.

    • Conditions?

  • WHAT TO DO? (main steps)

    • Enforce those conditions for 3 rounds of MD4 compression function
    • In each round, iterate over each word in the message block sequentially and mix it into the state. (careful not to stomp on any of the previous round's conditions)
    • Once you've adequately massaged M, you can simply generate M' by flipping a few bits and test for a collision

7.56. RC4 Single-Byte Biases

  • GOOD reference: http://www.isg.rhul.ac.uk/tls/RC4biases.pdf#figure.2

  • WHAT WE HAVE?

    • An oracle: - Receive request (P) - Append request (P) with "secret cookie" - Return ciphertext P + cookie encrypted with RC4 using different keys every request

  • GOAL: Decode this secret cookie: "QkUgU1VSRSBUTyBEUklOSyBZT1VSIE9WQUxUSU5F" by spawning arbitrary requests and analyse the ciphertext

  • Single-byte biases theorems:

      1. The probability that Z2, the second byte of keystream output by RC4, is equal to 0x00 is approximately 1/128
      1. For 3 <= r <= 255, the probability that Zr, the r-th byte of keystream output by RC4, is equal to 0x00 is: Pr(Zr = 0x00) = 1/256 + Cr/256^2
    • => Since Cr = Pr XOR Zr, Zr -> 0x00 => Cr -> Pr (corresonding ciphertext byte has bias toward plaintext byte Pr)
    • ** IMPORTANT!! **
    • Thus, obtaining many ciphertext samples Cr for a fixed plaintext Pr allows interference of Pr by a majority vote:
    • => Pr is equal to the value of Cr that occurs most often

  • Single-byte bias attack algorithm:

    • Check Algorithm 4 here:

  • MAIN STEPS:

    • Step 1: Gain exhaustive knowledge of the keystream biases.
    • Step 2: Encrypt the unknown plaintext 2^30+ times under different keys.
    • Step 3: Compare the ciphertext biases against the keystream biases.

  • NOTE: control the position of the cookie by requesting "/", "/A", "/AA", and so on (to guess next byte in plaintext)