<!-- 注意上面三行 --> # 現代密碼學 序章 ### by AlanHacker ---  ### [前測](https://forms.gle/x9yDKSaJpv9fgAYL6) ---  ## [Slido #5400 108](https://app.sli.do/event/nEvRRwkowafmzDYM2BKoY9) --- ## [練習題平台](https://ctf.hackersir.org/challenges) --- ## Before Start ---- ### 環境建置(1) * 創建資料夾 * 開啟 VScode * 開啟資料夾->(選到創建的資料夾) * (Ctrl + ~) 開啟命令列 ---- ### 環境建置(2) ```= pip install pwntools pip install pycryptodome ``` ---- ### 環境建置(3) * 沒報錯代表安裝成功 ``` > python >>>import Crypto >>>from pwn import * ``` --- ## Outline * 基本知識 * 雜湊函數 * 對稱式加密 * Block Cipher * Stream Cipher --- # 基本知識 ---- ### ASCII 編碼轉換 ---- * 大小 1 byte、使用 7 bits 編碼 * 用於表示英文字母與常見字符  ---- ### ASCII in Python ```python= chr() # 將數字轉成字元 ord() # 將字元轉成數字 ``` ---- ### 小練習 ``` # 請嘗試解碼 secret secret = [99, 114, 121, 112, 116, 111, 123, 105, 95, 67, 52, 78, 95, 99, 111, 78, 118, 51, 114, 116, 95, 64, 115, 99, 105, 105, 95, 33, 78, 95, 112, 121, 84, 72, 79, 78, 125] ``` ---- <font size=6>加密後可能會有非 ascii 可顯示字元出現 如：0 ~ 31、128 ~ 255 就是如此</font>  ---- 所以需要將密文編碼為較友善、較易傳輸的形式 Crypto CTF 中較常見的有： * Hex String * base64 ---- ### Hex String * 16 進制字串 * 字串 => (10) 數字 => (16) 數字 => 字串 * e.g. `"ABC"` => `65 66 67` => `41 42 43` => `"414243"` * 反過來做就是解碼 ---- ### 進位轉換 ```python= [1-7|3|4-5] number = 123 h = hex(number) # '0x7b' # 使用 int() 時，有如 0b、0x、0 這種前綴沒關係 int(h, 16) # 123 ``` ---- ### Hex String 轉換(1) ```python= [1-14|1-8|10-14] my_string = "Attack on Titan" hex_string = "" for c in my_string: hex_string += hex(ord(c))[2:] print(hex_string) # 41747461636b206f6e20546974616e original_string = "" for i in range(0, len(hex_string), 2): original_string += chr(int(hex_string[i : i + 2], 16)) print(original_string) # Attack on Titan ``` ---- ### Hex String 轉換 (2) ```python= [1-14|1-6|7-10|12-14] """ Python 中的字串型別有兩種：str(Unicode 字串)、bytes(二進制字串) 它們之間轉換必須透過 encode()、decode() str.encode() -> bytes bytes.decode() -> str """ my_string = "Attack on Titan" hex_string = my_string.encode().hex() print(hex_string) # 41747461636b206f6e20546974616e # fromhex 接收 str original_string = bytes.fromhex(hex_string) print(original_string.decode()) # Attack on Titan ``` ---- ### 小練習 ```python= # 小提醒: str、bytes 轉換要做什麼? # 請嘗試解碼 secret secret = "63727970746f7b6845783f68656b3f4b65583f4b454b3f5730575f755f525f615f4865584572217d" ``` ---- ### Base64 * 以 64 個字元編碼 * 因 $2^6=64$ ，所以 6 bits => 一個字元 * ~~16 進位是一種 base16~~ * 常用於網路傳輸、如圖片等二進位資料 ---- ```python= [1-8|4-5|6-8] from base64 import b64encode, b64decode my_data = "[粛聖!!ロリ神レクイエム☆](https://www.youtube.com/watch?v=Ci_zad39Uhw)" # 因為是處理二進制資料的編碼 # 所以必須用 bytes 操作 b64_string = b64encode(my_data.encode()) print(b64_string) # b'W+eym+iBliEh44Ot44Oq56We44Os44Kv44Kk44Ko44Og4piGXShodHRwczovL3d3dy55b3V0dWJlLmNvbS93YXRjaD92PUNpX3phZDM5VWh3KQ==' print(b64decode(b64_string).decode()) # [粛聖!!ロリ神レクイエム☆](https://www.youtube.com/watch?v=Ci_zad39Uhw) ``` ---- ### 小練習 ```python= # 小提醒: str、bytes 轉換要做什麼? # 請嘗試解碼 secret secret = "Y3J5cHRveyFTX0I0c0U2NF9BX251TWIzcl9zWXNURW19" ``` ---- ### Python 檔案讀寫(1) ```py= # filename 為你的檔案名稱、mode 為對檔案做的操作 with open(filename, mode) as f: f.read() f.write() ``` ---- ### Python 檔案讀寫(2) ```python= [1-13|3-6|8-13] # 寫檔範例 # 假設把字串 "abc" 寫入一個叫 myfile2.txt　的檔案 with open("myfile2.txt", "w") as f: f.write("abc") # myfile2.txt 內容："abc" # 假設把二進位資料 b'\x01\x02\x03\x04\x05' # 寫入一個叫 myfile2.txt　的檔案 with open("myfile2", "wb") as f: f.write(b'\x01\x02\x03\x04\x05') # myfile2.txt 內容：b'\x01\x02\x03\x04\x05' # 因為是二進位資料，所以會是亂碼 ``` ---- ### Python 檔案讀寫(3) ```python= [1-10|3-5|7-10] # 讀檔範例 # 假設有一個 myfile.txt 的文字檔案，裡面的內容是 "abc" with open("myfile.txt", "r") as f: print(f.read()) # 'abc' # 假設有一個 myfile 的二進位檔案 # 裡面的內容用十六進位看是 01 02 03 04 05 with open("myfile", "rb") as f: print(f.read()) # b'\x01\x02\x03\x04\x05' ``` ---- ## [Lab: Image Decode](https://ctf.hackersir.org/challenges#Image%20Decode-63) ---- * 我們加密的對象已經不一樣了 * 純文字資料 => 二進制資料 * 像[上次社課](https://hackmd.io/@ClubSlide/H1bkHKPZa#/14/2)用加法加密對人類來說好算 * 但對電腦不太好算！ * 因此要找一個讓電腦好算的方式！ ---- ### 異或 Exclusive or * a.k.a XOR, [互斥或](https://zh.wikipedia.org/zh-tw/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96) * 電腦運算速度很快 * 二進位運算 * 有很多類似加法的性質 * 可以當作「加法」的替代 ---- $\oplus$ 代表 XOR * $0 \oplus 0=0$ * $0 \oplus 1=1$ * $1 \oplus 0=1$ * $1 \oplus 1=0$ ---- ### bitwise XOR * 對於字串或二進位資料 * 在二進位下逐位元分開進行 XOR ---- * `"a"` XOR `"b"` => `97` XOR `98` => `01100001` XOR `01100010` | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | |---|---|---|---|---|---|---|---| | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | => `00000011` ---- ### XOR in Python(1) ```python= # 大多數程式語言都用 ^ 代表 XOR，Python 也不例外 print(97 ^ 98) # 3 ``` ---- ### XOR in Python(2) ```python= # 對字串 XOR 有兩種做法 plain = "wink" key = 11 # 方法一 result = "" for c in plain: result += chr(ord(c) ^ 11) print(result) # {ebg ``` ---- ### XOR in Python(3) ```python= # 對字串 XOR 有兩種做法 plain = "wink" key = 11 # 方法二 # 對 bytes 進行 XOR # 這個方法較通用 from pwn import xor print(xor(plain.encode(), 11)) # b'{ebg' ``` ---- ### XOR 的美好性質 <font size = 5>前三個跟加法很像</font> * 交換律 $a\oplus b=b\oplus a$ * 結合律 $(a\oplus b)\oplus c=a\oplus (b\oplus c)$ * 單位元素 $a\oplus 0=a$ * 自反性 $a\oplus a=0$ ---- 所以可以知道三個重點： 1. 運算順序什麼的不重要 2. 括號可以隨便括 3. 同一個數字算兩次會被"取消"掉 * $a\oplus b\oplus b=a\oplus0=a$ 4. 可以移項 * $a\oplus b=c\Rightarrow a\oplus b\oplus b=c\oplus b$ $\Rightarrow a=c\oplus b$ ---- ## [Lab: XOR property](https://ctf.hackersir.org/challenges#XOR%20property-64) ---- ## [Lab: XOR Decryption](https://ctf.hackersir.org/challenges#XOR%20decryption-65) --- # 雜湊函數 ---- ### 雜湊函數 * 又稱哈希函數 * 如同[上次社課](https://hackmd.io/@ClubSlide/H1bkHKPZa#/8/8)所提到的幾個性質 * 不可逆函數 * 一對一函數 * 單向函數 * 資訊摘要 * 被拿來簽章、驗證 * 不定長度輸入、固定長度輸出 ---- * 多對一出現代表內容有被偽造的風險 * 這種狀況叫做「碰撞」  ---- ### MD5 * 輸出長度：128 bits * 已被找出碰撞 ---- ### SHA 家族 * Secure Hash Algorithm，縮寫為 SHA * 美國國家安全局（NSA）設計 * 美國國家標準與技術研究院（NIST）發佈 ---- ### SHA1 * 輸出長度：160 bits * 已被找出碰撞 ---- ### SHA2 * 輸出長度：224、256、384、512 bits * 尚未被找出碰撞 ---- ### SHA3 * 輸出長度：224、256、384、512 bits * 尚未被找出碰撞 * 因為 SHA1 被破解，因而設計上與 SHA1、SHA2 截然不同 ----  <small>[source: wikipedia](https://zh.wikipedia.org/zh-tw/SHA%E5%AE%B6%E6%97%8F#SHA%E5%87%BD%E6%95%B0%E5%AF%B9%E6%AF%94)</small> ---- ### Hash in Python ```py= from hashlib import md5 from hashlib import sha1 from hashlib import sha224, sha256, sha384 from hashlib import sha3_224, sha3_256, sha3_384 print(md5(b"jojo").digest()) # b'u\x10\xd4\x98\xf2?X\x15\xd37n\xa7\xba\xd6N)' print(md5(b"jojo").hexdigest()) # "7510d498f23f5815d3376ea7bad64e29" ``` ---- ## [Lab: Hash Cipher](https://ctf.hackersir.org/challenges#Hash%20Cipher-66) --- # 對稱式加密 ---- ### 對稱式加密 * 加解密使用同一把 key * ~~所以理論上古典加密都是對稱式加密~~  --- ## Block Cipher ---- ### Block Cipher * 區塊加密法 * 將明文分成多個等長的區塊（block） * 對每區塊分別加密解密 ----  ---- ### AES * 進階加密標準(Advanced Encryption Standard) * Block Cipher * 16 bytes 一個區塊 * 不足 16 bytes 遵照 [PKCS#7](https://stackoverflow.com/questions/34865313/bouncy-castle-pkcs7-padding) Padding 填充 * 已知攻擊方法只有社交工程和旁道攻擊 ---- ### PKCS#7 Padding * 區塊長度 $\neq$ 16 的倍數 -> 補到變 16 倍數 * 區塊長度 $=$ 16 的倍數 -> 額外再補 16 bytes ```py= from Crypto.Util.Padding import pad pad(b"0123456789", 16) # b'0123456789\x06\x06\x06\x06\x06\x06' pad(b"0123" * 4, 16) # b'0123012301230123\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10' ``` ---- ### Mode of operation * 區塊加密法工作模式 * 定義 key 如何為多個區塊進行加密 * 常見的工作模式有 * ECB * CBC * CTR * OFB * CFB ---- ### ECB Mode * 電子密碼本(Electronic codebook)  ---- ### 缺點 * 因為各區塊單獨加密 * 所以相同區塊加密結果相同 ----  ---- ### AES-ECB in Python ```python= from Crypto.Cipher import AES from Crypto.Util.Padding import pad key = pad(b'key', 16) aes = AES.new(key = key, mode = AES.MODE_ECB) print(aes.encrypt(pad(b"test", 16)).hex()) # 8e0d95a9f720c6eaa1cab10e44ce50e8 ``` ---- ### 常見弱點 * Cut-Paste Attack ---- ### Cut-Paste Attack * 研究表明：漢字的序順並不定一能影響閱讀 * ECB 也是一樣 * 因此可以用拼接已知區塊的方式竄改內容 ---- ### 範例 ```py= [1-15|1-6|8-15] plain = b"username=Sandra&deposit=1000000;username=Daniel&deposit=0000000;" block_1 = "username=Sandra&"; block_2 = "deposit=1000000;"; block_3 = "username=Daniel&"; block_4 = "deposit=0000000;"; # after AES-ECB encryption cipher_1 = "aaaaaaaaaaaaaaaa"; cipher_2 = "bbbbbbbbbbbbbbbb"; cipher_3 = "cccccccccccccccc"; cipher_4 = "dddddddddddddddd"; cipher = "aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbccccccccccccccccdddddddddddddddd"; ``` ---- ### Daniel 很窮，他要怎麼財富自由？ ---- ### 和 Sandra 交換存款！ ---- ```py= [1-15|1-6|8-15] hacked_cipher = "aaaaaaaaaaaaaaaaddddddddddddddddccccccccccccccccbbbbbbbbbbbbbbbb"; hacked_cipher_1 = "aaaaaaaaaaaaaaaa"; hacked_cipher_2 = "dddddddddddddddd"; hacked_cipher_3 = "cccccccccccccccc"; hacked_cipher_4 = "bbbbbbbbbbbbbbbb"; # After AES-ECB decryption hacked_block_1 = "username=Sandra&"; hacked_block_2 = "deposit=0000000;"; hacked_block_3 = "username=Daniel&"; hacked_block_4 = "deposit=1000000;"; hacked_plain = "username=Sandra&deposit=0000000;username=Daniel&deposit=1000000;" ``` ---- ### demo in Python ```python= from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad from os import urandom key = urandom(16) # 16 bytes aes = AES.new(key = key, mode = AES.MODE_ECB) plain = b"username=Sandra&deposit=1000000;username=Daniel&deposit=0000000;" cipher = aes.encrypt(pad(plain, 16)) block_1, block_2, block_3, block_4, padding = cipher[:16], cipher[16:32], cipher[32:48], cipher[48:64], cipher[64:80] hacked_cipher = block_1 + block_4 + block_3 + block_2 + padding hacked_plain = unpad(aes.decrypt(hacked_cipher), 16) print(hacked_plain) ``` ---- ## [Lab: ECB](https://ctf.hackersir.org/challenges#ECB-68) --- ## Stream Cipher ---- ### Stream Cipher * 串流加密法 * 使用**某種方式**無限產生 key stream * 明文與對應位置的 key stream 加密 ---- ### OTP * 一次性密碼本(One Time Pad) * 理論中絕對安全，牢不可破 * 但條件太嚴苛，難以實現 ---- ### 加密方法 1. key 與明文等長 2. key 為完全隨機的序列 3. key 用完即丟，且只有通訊雙方能知道 4. 加密的方式可以用傳統的加法；也可用 XOR ---- ### 範例 <font size=5>使用 XOR</font> * $\text{明文} = [1, 2, 3]$ * $\text{key} \,\, = [5, 2, 1]$ * $\text{密文} = [4, 0, 2]$ ---- ### 困難 * key 與明文等長，難以傳遞 ---- ### 常見弱點 * key 重複使用(變 Many Time Pad) * key 洩漏 ---- ## [Lab: Many Time Pad](https://ctf.hackersir.org/challenges#Many%20Time%20Pad-67) ---  ### [後測](https://forms.gle/ZdUYxvTx2oWDuuaU7)