<!-- 注意上面三行 --> # 現代密碼學 序章 ### by AlanHacker --- ### [前測](https://forms.gle/8m4HZ89h7nMAfyri7) --- # [Slido](https://app.sli.do/event/bm8UQKJavLmjSPnsXjjejC) --- ## Before Start ---- ### Google Colab 教學 * 進入雲端硬碟 * 左上角[新增]->[更多]->[Google Colaboratory] ----  ---- ### 套件安裝 ```= # 在 Command Line pip install pwntools pip install pycryptodome pip install requests # 在 google colab !pip install pwntools !pip install pycryptodome !pip install requests ``` --- ## Outline * 基本知識 * 雜湊函數 * 對稱式加密 * Block Cipher * Stream Cipher --- # 基本知識 ---- ### ASCII 編碼轉換 ---- * 大小 1 byte、使用 7 bits 編碼 * 用於表示英文字母與常見字符 ---- ```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>  <small>圖片來源: [wikimedia](https://commons.wikimedia.org/wiki/File:ASCII-Table-wide.svg)</small> ---- 所以需要將密文編碼為較友善、較易傳輸的形式 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 轉換 ```python= [1-29|3-9|11-15|17-25|27-29] 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 # 方法二 """ Python 中的字串型別有兩種：str(Unicode 字串)、bytes(二進制字串) 它們之間轉換必須透過 encode()、decode() str.encode() -> bytes bytes.decode() -> str """ 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 檔案讀寫 ```py= [1-29|1-4|8-10|12-15|19-22|24-29] # filename 為你的檔案名稱、mode 為對檔案做的操作 with open(filename, mode) as f: f.read() f.write() # 讀檔範例 # 假設有一個 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' # 寫檔範例 # 假設把字串 "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= import requests def fetch_gist_content(gist_url): try: response = requests.get(gist_url) response.raise_for_status() return response.text except requests.RequestException as e: print(f"Error fetch: {e}") return None url = "https://gist.githubusercontent.com/AW-AlanWu/885565449ef2cb73dc30ad564bb99d28/raw/541b1d895966c2f5bb2320e765f39fce9f0711be/secret.txt" # secret 內為某張 png 圖片的 base64 編碼結果 # 請嘗試解碼並恢復圖片 secret = fetch_gist_content(url) ``` ---- * 我們加密的對象已經不一樣了 * 純文字資料 => 二進制資料 * 像[上次社課](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) * 二進位上的加法 * 可以想成位元間的 $\neq$ 符號 ---- 二進位只有 0 和 1，如果超過必須 mod 2 * $0 + 0=0$ * $0 + 1=1$ * $1 + 0=1$ * $1 + 1=0$ ---- 位元間的比較 * $0\neq0\Rightarrow \text{False}$ * $0\neq1\Rightarrow \text{True}$ * $1\neq0\Rightarrow \text{True}$ * $1\neq1\Rightarrow \text{False}$ ---- ### 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 ```python= # 大多數程式語言都用 ^ 代表 xor，python 也不例外 print(97 ^ 98) # 3 # bitwise xor 有兩種做法 plain = "wink" key = 11 # 方法一 result = "" for c in plain: result += chr(ord(c) ^ 12) print(result) # {ebg # 方法二 # 這個方法通用性較好 from pwn import xor print(xor(plain.encode(), 12)) # b'{ebg' ``` ---- ### 小練習 ``` # secret 被 bitwise xor 27 了！ # 請嘗試解密 secret secret = "xibkot`X[uDND,~*WDv(DStlD,TDC+IDRUDkBOSTu$f" ``` ---- ### Xor 的美好性質 * [上次社課](https://hackmd.io/@ClubSlide/H1bkHKPZa#/14/2)中我們用加法加密，那怎麼解密? * 用減法 * 在二進位中，我們用 xor 加密，那怎麼解密? * xor 代表位元的加法 * 所以得用位元的減法 ---- 二進位只有 0 和 1，如果小於 0 必須 mod 2 * $0 - 0=0$ * $0 - 1=1$ * $1 - 0=1$ * $1 - 1=0$ 阿不就還是 XOR? ---- ### 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$ ---- ### 小練習 1 ``` # 提示1：想想美好的性質 # 提示2：有工具就不需要自己動手 # 以下均為 hex string 表示，解密時需要轉回 bytes # 請嘗試解出 flag a ^ c = "144d696775452d35783c65220c276a714105560d6c152c3c11383c1078417272100705535d1631620456" b ^ c = "2249762906546d5807071b360d78557b60053c000500533a44415a187d1a4c0e4867437d52091b59270c" a ^ b ^ flag = "5576663e077e3b3a3742216c6e0d6059115f0f391a4c204f182642476a0479131704196f5b4072545127" ``` ---- ### 小練習 2 ```py= # secret 被一個 byte 加密了，請嘗試解密 # secret 為 hex string 表示，解密時需轉回 bytes secret = "e2f3f8f1f5eefaa0b4def5c9e8f2dee0deb6d8d1b2deb1e7dee2e0e4d2e0d3dec2e8f1c9b2f3fc" ``` --- # 雜湊函數 ---- ### 雜湊函數 * 又稱哈希函數 * 如同[上次社課](https://hackmd.io/@ClubSlide/H1bkHKPZa#/8/8)所提到的幾個性質 * 不可逆函數 * 一對一函數 * 單向函數 * 資訊摘要 * 被拿來簽章、驗證 * 不定長度輸入、固定長度輸出 ---- * 多對一出現代表內容有被偽造的風險 * 這種狀況叫做「碰撞」  ---- ### MD5 * 輸出長度：128 bit * 已被找出碰撞 ---- ### SHA 家族 * Secure Hash Algorithm，縮寫為 SHA * 美國國家安全局（NSA）設計 * 美國國家標準與技術研究院（NIST）發佈 ---- ### SHA1 * 輸出長度：160 bit * 已被找出碰撞 ---- ### SHA2 * 輸出長度：224、256、384、512 bit * 尚未被找出碰撞 ---- ### SHA3 * 輸出長度：224、256、384、512 bit * 尚未被找出碰撞 * 因為 SHA1 被破解，因而設計上與 SHA1、SHA2 截然不同 ----  ---- ### 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" ``` ---- ### 小練習 ```py= # base64 都可以加密了，為什麼雜湊不能拿來加密? # 所以我用下面的程式加密了 flag ，請嘗試解密 secret 吧! from hashlib import sha3_256 with open("flag.txt", "r") as f: flag = f.read() secret = "" for c in flag: secret += sha3_256(c.encode()).hexdigest()[:5] print(secret) # "263abf695d9d0f314c688897212c6dfdce6c837f1b42fb72b7cdc5612c6df695df695d9d0f3b72b7c837fb72b7263ab800848ee93b72b712c6d8ee933e5e39d0f3b72b7889724253880084263ab5a082b72b7cdc56d7e94263ab5a082b72b7b039180084cdc56bf872263abb72b7cdc5688972d7e94a0b37a0b375bf60" ``` --- # 對稱式加密 ---- ### 對稱式加密 * 加解密使用同一把 key * ~~所以理論上古典加密都是對稱式加密~~  ---- 今天將主要介紹以下兩種對稱加密演算法 * OTP * AES --- ## 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 * 多出來的長度 < 16 -> 補到 16 * 多出來的長度 == 0 -> 多補 16  ---- ### Mode of operation * 區塊加密法工作模式 * 定義 Key 如何為多個區塊進行加密 * 常見的工作模式有 * ECB * CBC * CTR * OFB * CFB ---- ### ECB Mode * 電子密碼本(Electronic codebook)  ---- ### 缺點 * 因為各區塊單獨加密 * 所以相同區塊加密結果相同 ----  ---- ### 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 也是一樣 * 因此可以用拼接已知區塊的方式竄改內容 ---- ### 範例 ```= [1-30|1-12|14-16|18-30] plain = "username=rebecca;deposit=1000000username=charlie;deposit=0000000"; block_1 = "username=rebecca"; block_2 = ";deposit=1000000"; block_3 = "username=charlie"; block_4 = ";deposit=0000000"; cipher1 = "aaaaaaaaaaaaaaaa"; cipher2 = "bbbbbbbbbbbbbbbb"; cipher3 = "cccccccccccccccc"; cipher4 = "dddddddddddddddd"; cipher = "aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbccccccccccccccccdddddddddddddddd"; /* 你是 Charlie，要怎麼竄改自己的存款? */ /* 將代表存款的 cipher 2 與 cipher 4 交換 */ hacked_cipher = "aaaaaaaaaaaaaaaaddddddddddddddddccccccccccccccccbbbbbbbbbbbbbbbb"; cipher1 = "aaaaaaaaaaaaaaaa"; cipher2 = "dddddddddddddddd"; cipher3 = "cccccccccccccccc"; cipher4 = "bbbbbbbbbbbbbbbb"; block_1 = "username=rebecca"; block_2 = ";deposit=0000000"; block_3 = "username=charlie"; block_4 = ";deposit=1000000"; plain="username=rebecca;deposit=0000000username=charlie;deposit=1000000" ``` ---- ### demo in python ```python= [1-19|9-10|12-16|15-19] from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad from random import randbytes key = pad(randbytes(16), 16) aes = AES.new(key = key, mode = AES.MODE_ECB) record1 = b"username=rebecca;deposit=1000000" record2 = b"username=charlie;deposit=0000000" cipher1 = aes.encrypt(pad(record1, 16)) cipher2 = aes.encrypt(pad(record2, 16)) block1, block2, pad1 = cipher1[:16], cipher1[16:32], cipher1[32:] block3, block4, pad2 = cipher2[:16], cipher2[16:32], cipher2[32:] print(unpad(aes.decrypt(block1 + block4 + pad1), 16)) print(unpad(aes.decrypt(block3 + block2 + pad2), 16)) ``` --- ## 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> * 明文 = `1 2 3` * key = `5 2 1` * 密文 = `4 0 2` ---- ### 難點 * 世界上不存在真正的隨機 * key 太大，難以傳遞 ---- ### 常見弱點 * key 重複使用(變 Many Time Pad) * key 洩漏 ---- ### 小練習 ```py= # 給你被加密過後的 flag，請嘗試解出原本的 flag from random import randbytes from pwn import xor with open("flag.txt", "r") as f: flag = f.read().encode() assert(len(flag) % 6 == 0) key = randbytes(6) print(xor(flag, key).hex()) # 2afa05ac198932c111ac018324ed12a804882ed733b208b91de111b932b628ec23b503b93bed1db0049230d715af32973ce108b9328521e910b008882ee112bb4c9b ``` --- ### [後測](https://forms.gle/8m4HZ89h7nMAfyri7)