Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[Crypto in CTF] Block Cipher Mode

oalieno
October 31, 2020

[Crypto in CTF] Block Cipher Mode

oalieno

October 31, 2020
Tweet

More Decks by oalieno

Other Decks in Technology

Transcript

  1. ⽬錄 • ECB Mode • ECB Mode / Cut &

    Paste • ECB Mode / Prepend Oracle Attack • CBC Mode • CBC Mode / Bit-Flipping Attack • CBC Mode / Padding Oracle Attack • CTR Mode
  2. Block Cipher 加密 16 bytes 明⽂ 16 bytes 密⽂ 密鑰

    • 輸入輸出長度固定 • 以 AES 為例 • 輸入明⽂ 16 bytes • 輸出密⽂ 16 bytes • 密鑰長度有 16, 24, 32 bytes 三種 最常⾒
  3. 加密 16 bytes 明⽂ 16 bytes 密⽂ 密鑰 加密 14

    bytes 明⽂ + 2 bytes 填充 ( padding ) 16 bytes 密⽂ 密鑰 30 bytes 明⽂ Block Cipher
  4. ECB Mode / Cut & Paste Encrypt user:hi;money:10 A Key

    Encrypt ;id=015647659901 B Key Encrypt 5874573959304852 C Key
  5. ECB Mode / Cut & Paste Decrypt A user:hi;money:10 Key

    Decrypt C 5874573959304852 Key Decrypt C 5874573959304852 Key 錢錢變多了xD
  6. The Oracle • 使⽤ AES ECB Mode • 伺服器將我們的明⽂ prepend

    在 fl ag 前⾯作加密 def oracle(plain): aes = AES.new(KEY, AES.MODE_ECB) return aes.encrypt(plain + flag)
  7. 找 fl ag[0] Encrypt AAAAAAAAAAAAAAAC Ciphertext Key Encrypt TF{FLAG}… Ciphertext

    Key 先塞 15 個垃圾 讓 fl ag 的第⼀個字元掉進來
  8. 塞 15 個⼀樣的垃圾 + 爆搜最後⼀個 byte 找 fl ag[0] Encrypt

    AAAAAAAAAAAAAAA\00 Ciphertext Key Encrypt CTF{FLAG}… Ciphertext Key
  9. 找 fl ag[0] Encrypt AAAAAAAAAAAAAAA\01 Ciphertext Key Encrypt CTF{FLAG}… Ciphertext

    Key 塞 15 個⼀樣的垃圾 + 爆搜最後⼀個 byte
  10. 找 fl ag[1] Encrypt AAAAAAAAAAAAAACT Ciphertext Key Encrypt F{FLAG}… Ciphertext

    Key 先塞 14 個垃圾 讓 fl ag 的前兩個字元掉進來
  11. 找 fl ag[1] Encrypt AAAAAAAAAAAAAAC\00 Ciphertext Key Encrypt CTF{FLAG}… Ciphertext

    Key 塞 14 個⼀樣的垃圾 + 已知的 fl ag 第⼀個 byte + 爆搜最後⼀個 byte
  12. 找 fl ag[1] Encrypt AAAAAAAAAAAAAAC\01 Ciphertext Key Encrypt CTF{FLAG}… Ciphertext

    Key 塞 14 個⼀樣的垃圾 + 已知的 fl ag 第⼀個 byte + 爆搜最後⼀個 byte
  13. CBC Mode / Bit-Flipping Attack Decrypt Ciphertext …b5 Key …49

    ⊕ Decrypt Ciphertext Plaintext Key ⊕ ⊕ 1 ⊕ 1
  14. CBC Mode / Bit-Flipping Attack Decrypt …04 …91 Key IV

    ⊕ Decrypt Ciphertext …e3 Key ⊕ ⊕ 1 ⊕ 1
  15. CBC Mode / Bit-Flipping Attack Decrypt …03 …f3 Key IV

    ⊕ Decrypt Ciphertext …e2 Key ⊕
  16. CBC Mode / Bit-Flipping Attack Decrypt …04 …91 Key IV

    ⊕ Decrypt Ciphertext …e3 Key ⊕ ⊕ e3 ⊕ 66 ⊕ e3 ⊕ 66
  17. CBC Mode / Bit-Flipping Attack Decrypt …81 …1c Key IV

    ⊕ Decrypt Ciphertext …66 Key ⊕ 將解密的明⽂改成我們指定的 0x66
  18. CBC Mode / Bit-Flipping Attack • 透過修改 IV 和 Ciphertext

    來控制 Plaintext • 其他 CFB, OFB, CTR 也存在相同的攻擊⽅式
  19. The Oracle • 使⽤ AES CBC Mode 配上 PKCS#7 Padding

    Scheme • 伺服器能幫我們解密訊息 • 如果解密出來的訊息 Padding 錯誤會噴錯 def unpad(data): if not all([x == data[-1] for x in data[-data[-1]:]]): raise ValueError return data[:-data[-1]] def oracle(cipher): aes = AES.new(KEY, AES.MODE_CBC) try: plain = unpad(aes.decrypt(cipher)) except ValueError: return False return True
  20. PKCS#7 : Cryptographic Message Syntax https://tools.ietf.org/html/rfc2315 後⾯要填充 6 個 bytes

    34 83 E6 2F 20 0A 33 AC 49 41 06 06 06 06 06 06 明⽂ • 這個標準裡⾯定義了⼀種 Padding 的格式 • 要填充 5 個 bytes 就填充 5 個 0x05 • 要填充 2 個 bytes 就填充 2 個 0x02
  21. Padding 錯誤 • 怎麼樣會 Padding 錯誤? • 抓最後⼀個 byte 就可以知道

    Padding 長度 都要等於最後⼀個 byte 34 83 E6 2F 20 0A 33 AC 49 41 06 ab 06 06 06 06
  22. Python Implementation def pad(data): p = 16 - len(data) %

    16 return data + bytes([p]) * p def unpad(data): if not all([x == data[-1] for x in data[-data[-1]:]]): raise ValueError return data[:-data[-1]]
  23. Padding Oracle Attack …00 Decrypt Ciphertext …2e Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試最後⼀個 byte
  24. Padding Oracle Attack …01 Decrypt Ciphertext …2f Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試最後⼀個 byte
  25. Padding Oracle Attack …02 Decrypt Ciphertext …2c Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試最後⼀個 byte
  26. Padding Oracle Attack …2f Decrypt Ciphertext …01 Key ⊕ 推論

    ( 很⼤機率 ) Padding 正確 暴⼒嘗試最後⼀個 byte 2f 47 ⊕ ⊕ 69 = 明⽂ 原本的密⽂
  27. Padding Oracle Attack …002c Decrypt Ciphertext …1502 Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試倒數第⼆個 byte 47 69 02 ⊕ ⊕ 2c = 設定明⽂最後⼀個 byte 為 02
  28. Padding Oracle Attack …012c Decrypt Ciphertext …1402 Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試倒數第⼆個 byte
  29. Padding Oracle Attack …022c Decrypt Ciphertext …1702 Key ⊕ 不知道

    只知道 Padding 錯誤 暴⼒嘗試倒數第⼆個 byte
  30. Padding Oracle Attack …172c Decrypt Ciphertext …0202 Key ⊕ 推論

    Padding 正確 17 7d ⊕ ⊕ 68 = 明⽂ 原本的密⽂ 暴⼒嘗試倒數第⼆個 byte
  31. Summary • 總共有三層迴圈 • 猜 0 - 255 直到猜出⼀個 byte

    • ⼀次解出⼀個 byte 直到解完⼀個 block • ⼀次解出⼀個 block 直到解完所有 blocks • 解出⼀個 block 最多需要 4096 次嘗試
  32. CTF Challenges 原汁原味 padding oracle attack : • CSAW CTF

    2016 Quals - Neo • HITCON CTF 2016 Quals - Hackpad • BAMBOOFOX CTF 2018 - mini-padding padding 相關攻擊技巧 : • HITCON CTF 2017 Quals - Secret Server • HITCON CTF 2017 Quals - Secret Server Revenge • BAMBOOFOX CTF 2018 - baby-lea-revenge • BAMBOOFOX CTF 2018 - baby-lea-impossible
  33. CTR Mode Encryption ⊕ Encrypt a59c…0000 Ciphertext Key Plaintext ⊕

    Encrypt a59c…0001 Ciphertext Key Plaintext Counter
  34. CTR Mode Decryption ⊕ Encrypt a59c…0000 Plaintext Key Ciphertext ⊕

    Encrypt a59c…0001 Plaintext Key Ciphertext Counter
  35. CTR Mode • 利⽤ AES 去產⽣ xor key 然後做 xor

    cipher • 加密和解密都是⽤ AES Encryption,因為要產⽣相同的 xor key • Counter 會初始⼀個隨機數字,每次加⼀ • Block 之間沒有互相依賴,可平⾏運算
  36. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag =
  37. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag = CTR Mode
  38. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag = Authentication
  39. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag = • len 是 bitlen • [10]64 → 000000000000000a 不是 16 bytes 的倍數會在後⾯補 \x00
  40. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag = Ek 0 H H = Ek(0)
  41. GCM Mode Encryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf • MultH 是在 GF(2128) 下乘上 H

    • GF(2128) 的 reduction modulus 是 x128 + x7 + x2 + x + 1 • 從 bytes 轉成 GF(2128) 下的元素 • u is the variable of the polynomial • x0x1…x127 → x0 + x1u + … + x127u127 • '\x00…\x00\x01\x02' → x119+x126 MultH
  42. Galois Field • Galois Field ( GF ) 或叫 Finite

    Field • GF(2128) 裡⾯的元素可以表⽰成⼀個 degree = 127 的多項式 • 加法和乘法就是做多項式的加法和除法 modulo ⼀個 degree = 128 的 irreducible polynomial • GCM Mode ⽤的 GF(2128) 是 modulo x128 + x7 + x2 + x + 1
  43. GCM Mode Decryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag =
  44. GCM Mode Decryption https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf a59c…0002 a59c…0001 a59c…0003 J0 inc32 inc32

    IV Ek ⊕ Plaintext Ciphertext ⊕ MultH Ek Ek ⊕ Ciphertext Plaintext MultH ⊕ MultH [len(A)]64 || [len(C)]64 MultH ⊕ Associated Data ⊕ Auth Tag = 這邊和加密時顛倒 其他都⼀樣
  45. GCM Mode / Forbidden Attack • ⼜叫 Nonce Repeating Attack

    • 也就是當 IV 重複⽤的情況 • 假設可以拿到任意明⽂加密的結果 • 這個攻擊可以做到偽造簽章
  46. GCM Mode / Forbidden Attack • T = AH4 +

    C1H3 + C2H2 + LH + Ek(J0) Tag Associated Data Ciphertext [len(A)]64 || [len(C)]64 • 在 Authentication 中做的 xor 就是 GF(2128) 中的加法 • Tag 可以表⽰成在 GF(2128) 中的式⼦如下 未知的只有藍⾊的部分
  47. GCM Mode / Forbidden Attack • T1 = A1H4 +

    C11H3 + C12H2 + L1H + Ek(J0) • T2 = A2H4 + C21H3 + C22H2 + L2H + Ek(J0) • T1 - T2 = (A1 - A2)H4 + (C11 - C21)H3 + (C12 - C22)H2 + (L1 - L2)H • 做兩次加密拿到兩個 Tag • 兩個相減後只剩 H 未知,解⽅程式求根可得 H • 有 H 帶回原式可得 Ek(J0) 就可以偽造 Tag 了
  48. POODLE ATTACK CVE-2014-3566 • 發⽣在 SSL 3.0 • Padding Oracle

    Attack ㄏ • Server 透露了加密資料在解密後的 padding 格式是否是正確的 • Mutate 被加密的資料,然後透過 server 的反應來還原明⽂