All About Crypto - CTF競賽密碼學(xué)方向指南
?本文旨在幫助希望在一些相對較難的CTF國際賽上解出密碼學(xué)題目的同學(xué)構(gòu)建一個知識框架和學(xué)習(xí)路線，近日整理了部分內(nèi)容，以下是本文內(nèi)容
All About Crypto - CTF競賽密碼學(xué)方向指南
0 前言
??密碼學(xué)不僅是CTF競賽中的一個重要的獨立考察方向，也經(jīng)常作為考點出現(xiàn)在其他方向的題目當(dāng)中。本文從個人作為一名CTF密碼學(xué)方向選手的視角入手，對需要掌握的相關(guān)內(nèi)容進行整理與分析，以期幫助選手更好的學(xué)習(xí)密碼學(xué)，更好的進行密碼學(xué)方向題目的訓(xùn)練，取得更好的比賽成績。
【CTF環(huán)境搭建&學(xué)習(xí)資料】
1 扎實的數(shù)學(xué)功底
??密碼分析的各個環(huán)節(jié)都離不開數(shù)學(xué)分析，對于選手求解一道CTF中的密碼學(xué)方向題目來講也是如此。在CTF中，主要考察密碼學(xué)選手?jǐn)?shù)論和抽象代數(shù)兩個方向的數(shù)學(xué)知識。
1.1 數(shù)論
??在數(shù)論方向，選手應(yīng)能較為熟練的了解和掌握包括：
整除理論（了解素數(shù)、合數(shù)、因數(shù)、倍數(shù)、整除等基本概念，掌握唯一分解定理、裴蜀定理、擴展歐幾里得定理、算數(shù)基本定理等基本定理）
同余理論（了解同余、原根、底數(shù)、指數(shù)、平方剩余、同余式、同余方程等基本概念，掌握歐拉定理、費馬小定理、中國剩余定理、二次互反律、威爾遜定理等基本定理）
連分?jǐn)?shù)理論（了解連分?jǐn)?shù)、無窮級數(shù)等基本概念，熟悉最佳有理數(shù)逼近、循環(huán)連分?jǐn)?shù)展開、佩爾方程求解等運算過程）
不定方程（了解低次代數(shù)曲線所對應(yīng)的不定方程的基本模型，熟悉二元一次不定方程、多元一次不定方程、掌握通過代數(shù)恒等變化、不等式估算、同余法、構(gòu)造法、無窮遞降法等常用的不定方程求解方法）
數(shù)論函數(shù)（了解歐拉函數(shù)、莫比烏斯函數(shù)、單位函數(shù)、恒等函數(shù)、除數(shù)函數(shù)等常用函數(shù)，掌握莫比烏斯反演、狄利克雷卷積等常用方法）
1.2 抽象代數(shù)
??在抽象代數(shù)方向，選手應(yīng)能較為熟練的了解和掌握包括：
群論（熟悉群代數(shù)結(jié)構(gòu)，掌握群相關(guān)性質(zhì)及其運算律）
環(huán)論（熟悉群代數(shù)結(jié)構(gòu)，掌握環(huán)相關(guān)性質(zhì)及其運算律）
域論（熟悉群代數(shù)結(jié)構(gòu)，掌握域相關(guān)性質(zhì)及其運算律）
格論（熟悉格代數(shù)結(jié)構(gòu)，掌握格相關(guān)性質(zhì)及其運算律）
線性代數(shù)（熟悉向量空間代數(shù)結(jié)構(gòu)，掌握向量相關(guān)性質(zhì)及其運算律）
??除此之外，諸如邏輯學(xué)、幾何學(xué)、拓撲學(xué)、泛函分析、概率論、數(shù)理統(tǒng)計等其他數(shù)學(xué)分支，雖然在CTF競賽中密碼學(xué)方向題目直接考察較少，但選手應(yīng)至少對其相關(guān)基本知識有一個大致了解。
2 密碼學(xué)技能樹
2.1 古典密碼學(xué)
??古典密碼學(xué)作為早期CTF競賽中密碼學(xué)方向的一種常見考察形式，目前已經(jīng)逐漸退出國際賽的歷史舞臺了。 ??CTF中的古典密碼主要以代替（substitution）密碼和置換（permutatuion）密碼兩種形式出現(xiàn)，在題目當(dāng)中，出題人通常不會顯式的告訴你題目所采用的加密算法，而是僅僅給出密文，預(yù)期選手通過特征檢索（如密文字符集中存在標(biāo)志性的特殊字符）、題目暗示（如題目名稱、題目描述中出現(xiàn)了對加密算法的隱喻）等方式猜測出題目中可能使用的加密算法，或使用數(shù)理統(tǒng)計（針對密鑰空間較大的代換密碼，如仿射、維吉尼亞等）、爆破（針對密鑰空間較小的代換或置換密碼，如柵欄、移位等）等方式恢復(fù)出密鑰，最后解密密文拿到FLAG。 ??這類題目的難點通常不在于分析而在于猜測，因此往往難度較低，但是由于代替和置換是密碼學(xué)算法中的兩個最基本的操作，很多現(xiàn)代密碼學(xué)算法中的運算都可以看作是這兩種運算的復(fù)合運算，因此古典密碼學(xué)題目也可作為初接觸CTF競賽密碼學(xué)方向的選手的練習(xí)題目，有助于培養(yǎng)選手對基本運算操作的理解。
2.2 現(xiàn)代密碼學(xué)
??現(xiàn)代密碼學(xué)作為目前CTF競賽中密碼學(xué)方向的主要考察形式，從總體上可以分為對稱密碼學(xué)、非對稱密碼學(xué)、哈希函數(shù)和數(shù)字簽名四大類題目，其中每類題目在知識點層面雖互有交集，但由于考察形式各有側(cè)重，因此本文對這四類題目類型分別進行論述。
2.2.1 對稱密碼學(xué)
2.2.1.1 序列密碼（流密碼）
??流密碼通常以字節(jié)或比特為基本單位來處理信息，其密鑰通常派生自一個較短的種子密鑰，而派生算法一般為一個偽隨機數(shù)生成算法，流密碼的安全性取決于密鑰流的安全性，因此CTF中的流密碼類題目也主要以偽隨機數(shù)生成器部分為主，當(dāng)然除此之外，題目有時也會考察選手對某一具體的流密碼算法的理解和分析能力，如A5/1、RC4等。 ??對于偽隨機數(shù)生成器來講，常見的考察模型主要可以分為兩類： ??一類為線性同余生成器（LCG），題目要求選手通過對生成器源碼審計，找出設(shè)計缺陷（針對生成器參數(shù)隨機化的場景）或進行數(shù)學(xué)推導(dǎo)恢復(fù)未知參數(shù)（針對參數(shù)恒定不變但缺失部分參數(shù)的場景），繼而連續(xù)預(yù)測出接下來產(chǎn)生的若干個隨機數(shù)，從而達到服務(wù)器要求拿到FLAG。 ??另一類為反饋移位寄存器，其中又可分為線性反饋移位寄存器（LFSR）和非線性反饋移位寄存器（NFSR）兩類主要考察模型，出題人通常會根據(jù)某一初始狀態(tài)采用某種生成方法生成一份輸出結(jié)果，然后將生成方法和輸出結(jié)果提供給選手，預(yù)期選手還原出初始狀態(tài)從而作為FLAG。
2.2.1.2 分組密碼（塊密碼）
??塊密碼使用某一基本塊為基本單位來處理信息，在加密時需要將明文數(shù)據(jù)分成若干基本塊，再針對每一塊進行加密，如果最后一塊的長度小于基本塊的長度，還需要進行padding。 ??目前CTF中針對塊密碼主要從三個角度考察： ??第一類是從塊密碼當(dāng)中的ARX（A-有限域上的模加，R-循環(huán)移位，X-異或）三種基本操作入手，考察選手對組合運算的熟練程度和理解能力。 ??第二類是從具體算法角度入手，考察AES、DES等經(jīng)典加密算法（或該加密算法的自定義修改版本）的線性攻擊、差分攻擊、積分攻擊等攻擊手法和選手做密碼分析的能力。 ??第三類是從分組模式入手，考察算法在padding時（如針對PKCS5 Padding的Padding Oracle攻擊）或加密模式上（如CBC字節(jié)翻轉(zhuǎn)攻擊、CFB重放攻擊）可能會出現(xiàn)的問題。
2.2.2 非對稱密碼學(xué)
??CTF競賽中的非對稱密碼學(xué)主要考察三大類問題，即大整數(shù)分解問題、離散對數(shù)求解問題（包括橢圓曲線上的離散對數(shù)求解問題）和基于格（Lattice）的計算問題：
2.2.2.1 大整數(shù)分解問題
??CTF中大整數(shù)分解問題主要以RSA算法為模型進行考察，RSA在目前CTF競賽中考察頻率可以說所有考點第一位，幾乎任何一場比賽都會有一道密碼學(xué)題目考察RSA，根據(jù)題目中給定的RSA算法的不同場景，其攻擊手法五花八門，需要選手具備很強的數(shù)論功底。 ??但也正是由于RSA知識點考察過于熱門，導(dǎo)致網(wǎng)上相關(guān)資料和現(xiàn)成的攻擊腳本較為成熟，對于一些簡單的RSA類題目，選手往往只需判斷出該題涉及到的RSA的哪一類場景，然后根據(jù)特征去檢索攻擊手法即可，但對于一些國際賽上的高質(zhì)量RSA類題目，仍然需要選手具備極強的分析和推導(dǎo)能力。目前針對RSA的常見攻擊大致包括以下幾類：
針對模數(shù)的攻擊：如Pollard’s p -1算法（p-1光滑）、Williams’s p + 1（p+1光滑）、試除法（|p-q|過大）、費馬分解（|p-q|過?。?、共模攻擊、模不互素攻擊等。
針對公鑰的攻擊：如小公鑰指數(shù)攻擊、低加密指數(shù)廣播攻擊等。
針對私鑰的攻擊：如Wiener’s attack（基于連分?jǐn)?shù)）、私鑰低位泄露攻擊等。
Coppersmith & LLL相關(guān)攻擊：如已知m高位攻擊、已知p高位攻擊、Coppersmith’s short-pad attack、Boneh and Durfee attack等。
結(jié)合Oracle的攻擊：有時題目當(dāng)中除了提供給選手參數(shù)之外還會提供一個加密/解密Oracle，結(jié)合Oracle可以衍生出更多種攻擊形式，如針對加密Oracle的公鑰泄露攻擊（選擇明文），針對解密Oracle的RSA LSB parity Oracle攻擊（選擇密文）。
2.2.2.2 離散對數(shù)求解問題
??CTF中考察DLP類問題主要以Diffie–Hellman 密鑰交換協(xié)議和ElGamal算法為主，要求選手能夠通過審計代碼找出問題關(guān)鍵點，并使用攻擊算法求解DLP問題，常用的DLP攻擊算法包括：
小步大步法（Baby-step giant-step，中間相遇攻擊的思想）
Pollard’s Rho algorithm（基于Miller-Rabin算法，遞歸求解）
Pollard’s Kangaroo algorithm（基于隨機步）
Pohlig-Hellman algorithm（針對階n是光滑且僅有小素因子）
??CTF中考察ECDLP類問題主要以橢圓曲線加密（ECC）為主，其曲線有限域通常為以素數(shù)為模的域 GF(p)或特征為2的域 GF(2^m)，ECDLP類題目的考察方式除了包括上面提到的DLP的一些常見模型和攻擊手法的橢圓曲線版以外，也包括一些針對曲線上存在的問題的攻擊形式，如：
針對E(Fp)=p（Frobenius軌跡t=p+1?E(Fp)=1）的上非正規(guī)橢圓曲線的Smart’s attack。
針對p|q+1?E(Fq)（Frobenius軌跡t是p的倍數(shù)）的超奇異橢圓曲線的MOV攻擊（借助Tate pairing或者Weil pairing）。
2.2.2.3 基于格的計算問題
??CTF中考察格中的計算困難問題主要包括最近向量問題（CVP）和最短向量問題（SVP）問題，其考察形式主要分為兩類： ??一類是利用格理論去分析已知的經(jīng)典密碼算法，如使用格基規(guī)約算法（LLL）來分析DSA簽名系統(tǒng)（如DSA nonce biases）、RSA加密系統(tǒng)（如RSA的小私鑰攻擊、Coppersmith相關(guān)的攻擊）、背包加密系統(tǒng)（如Merkle–Hellman背包公鑰加密算法）等。 ??另一類是分析基于格中困難問題設(shè)而設(shè)計新的后量子密碼體制，如NTRU密碼系統(tǒng)、GGH密碼系統(tǒng)、Gentry算法的全同態(tài)加密系統(tǒng)、基于LWE問題的密碼系統(tǒng)、Ajtai–Dwork概率公鑰密碼系統(tǒng)等。 ??基于格的計算問題類題目在目前CTF競賽中頻繁出現(xiàn)，一度成為國際賽當(dāng)中的主流考點，尤其是對LLL算法的理解和使用，成為解出許多高分值題目的關(guān)鍵。很多時候格相關(guān)攻擊較為復(fù)雜，需要選手結(jié)合論文來進行推導(dǎo)，關(guān)于CTF競賽中的論文問題會在后面的章節(jié)具體闡述。
2.2.3 數(shù)字簽名
??數(shù)字簽名主要用于對數(shù)字消息進行簽名，主要用于防止消息被冒名偽造、篡改，以及通信雙方的身份鑒別。由于數(shù)字簽名主要依賴于非對稱密碼算法，因此CTF當(dāng)中考察數(shù)字簽名類題目也主要依托非對稱密碼體系來進行設(shè)計，常見的包括RSA簽名、ElGamal簽名、DSA簽名、針對某一特定橢圓曲線的ECC簽名等，題目模型通常為要求我們提供某一特定字符串的簽名，如果能正確通過驗證則提供給選手FLAG，針對數(shù)字簽名類題目的攻擊我們一般從三個角度來切入：
設(shè)法直接計算私鑰，比如參數(shù)值過小或曲線選擇不合適，導(dǎo)致私鑰可以被直接計算出來（如2019 ASIS CTF Quals-Halloween Party題目，給定y坐標(biāo)求x坐標(biāo)，計算2在模P.order()上的逆并將結(jié)果乘2*P直接得到P）
設(shè)法恢復(fù)私鑰，即通過若干特殊明文簽名對，采用建立方程等方式重構(gòu)出密鑰（如2019 DEFCON CTF Quals-Tania題目，通過LLL算法和Babai最近平面算法恢復(fù)出密鑰）
設(shè)法偽造簽名，即在不知道私鑰的情況下，直接構(gòu)造出特定字符串的簽名來拿到FLAG（如2019 RealWorld CTF-bank題目，通過rogue-key attack偽造Schnorr比特幣簽名算法的銀行提款簽名）。
2.2.4 哈希函數(shù)
??CTF中考察哈希函數(shù)類問題主要以兩類場景進行展開： ??一類是哈希碰撞類場景，常見的攻擊類型包括：
同謀碰撞攻擊：生成任意兩個不同的消息和x和y，使得哈希值f(x)=f(y)
第二原像攻擊：給定任意一個x及其哈希值f(x)，可以生成一個與之不同的y使得哈希值f(x)=f(y)
相同前綴攻擊：給定任意一個前綴p，可以生成兩個不同的后綴和x和y，使得哈希值f(p+x)=f(p+y)
選擇前綴攻擊：給定任意兩個不同的前綴p和q，可以生成兩個不同的后綴x和y，使得哈希值f(p+x)=f(q+y)
??在考察形式上，題目通常會直接要求選手向服務(wù)器提交A、B兩個輸入，如果滿足AB但HASH(A)=HASH(B)，則判斷碰撞成功。HASH碰撞類題目雖然場景簡單，但通常題目難度較大，而且很多時候都是出題人魔改之后的哈希算法，因此要求選手具備較強的分析能力，在攻擊上多以考察代數(shù)攻擊為主，如：
利用small capacity parameter誤用問題構(gòu)造SHA3 Keccak海綿結(jié)構(gòu)碰撞（2019 0CTF/TCTF Quals-babysponge）
利用Petit-Lauter攻擊構(gòu)造超奇異同構(gòu)圖上Charles-Goren-Lauter哈希函數(shù)的弱實例碰撞（2017 HXP CTF-categorical）
??另一類則是哈希偽造場景，雖然很多時候偽造哈希也可以通過尋找碰撞的方式來實現(xiàn)，但是它和碰撞場景下的考察側(cè)重點通常不同，一種典型的攻擊手法即哈希長度擴展攻擊，即在已知的值和的長度的情況下（這里的值未知，即代表哈希時的salt），要求選手對于任意一個的值。對于哈希偽造的場景，我們的重點一般直接從攻擊手法入手，而不需要對源碼進行審計（絕大多數(shù)情況下，這類場景也不會給出哈希算法細節(jié)，而是直接調(diào)用現(xiàn)成的MD5、SHA1庫函數(shù)）。
【CTF環(huán)境搭建&學(xué)習(xí)資料】
3 讀paper的能力
??自2018年起，大量論文題開始登上CTF歷史舞臺，然而一場標(biāo)準(zhǔn)的CTF國際賽通常為48小時，留給選手的分析時間是有限的，因此對于很多國際賽上的密碼分析類題目來講，選手是很難在短時間內(nèi)提出一種可行的攻擊手段的。這個時候，就需要快速提煉出題目當(dāng)中的模型、場景等關(guān)鍵內(nèi)容，然后去檢索并閱讀與之對應(yīng)的會議、期刊論文，從中尋找攻擊思想或手段。因此，選手的論文閱讀理解能力（尤其是英文文獻的閱讀能力）對于密碼學(xué)方向來講就顯得尤為重要。近年來國際賽當(dāng)中CTF題目與學(xué)術(shù)界論文或研究成果聯(lián)系緊密，如：
2018 PlaidCTF-braid題目，考察選手通過閱讀論文[1]，解決一個辮子群（Braid Group）下的 Conjugacy Search 問題。
2018 Hack.lu CTF- Escape the grid題目，考察選手通過閱讀論文[2]，攻破一個使用了非安全函數(shù)產(chǎn)生仿射變換的 rasta 密碼系統(tǒng)。
2019 0CTF/TCTF Quals-zer0lfsr題目，考察選手通過通過閱讀論文[3]，利用Fast Correlation Attack恢復(fù)出一個Meier-Staffelbach模型下0.75相關(guān)性的3個LFSR的初始狀態(tài)（雖然這道題在當(dāng)時比賽時被z3非預(yù)期了）。
2019 PwnThyBytes CTF-Wrong Ring題目，考察選手通過閱讀論文[4]，通過將環(huán)上帶誤差學(xué)習(xí)（RLWE）樣本轉(zhuǎn)化為多項式帶誤差學(xué)習(xí)(PLWE)樣本，攻擊一個（non-dual）RLWE的實例來求私鑰。
??還有很多題目直接以某一論文或研究成果為背景進行設(shè)計，如：
2017 ASIS CTF Final-Marijuana
??2017年5月，Divesh Aggarwal等學(xué)者提出了一種基于梅森素數(shù)的公鑰密碼體系[5]，2個月后，該密碼系統(tǒng)被Marc Beunardeau等學(xué)者攻破，相關(guān)成果以論文形式發(fā)表[6]，同年9月，該事件以CTF形式出現(xiàn)在當(dāng)年的ASIS CTF競賽當(dāng)中，預(yù)期選手通過閱讀論文使用隨機劃分和LLL攻擊攻破密碼系統(tǒng)。
2017 HXP CTF-notsosmart
??2017年2月，馬薩里克大學(xué)的Matus Nemec和Marek Sys等學(xué)者發(fā)現(xiàn)英飛凌科技提供的RSALib庫中的密鑰生成算法存在漏洞，并據(jù)此提出了一種可行的RSA ROCA攻擊。同年11月，相關(guān)攻擊細節(jié)以論文形式披露[7]（該攻擊同步影響了TPM 1.2, 4.3.5版本前的YubiKey 4等產(chǎn)品，CVE編號：CVE-2017-15361），兩周后，該事件以CTF形式出現(xiàn)在當(dāng)年的HXP CTF競賽當(dāng)中，預(yù)期選手通過閱讀論文使用ROCA攻擊攻破一個RSA密鑰生成算法。
4 扎實的編程功底
??對于絕大多數(shù)情況下，當(dāng)選手通過審計源碼或者閱讀論文整理出一種攻擊手段之后，接下來都需要通過編程的方式寫一個solver或exp來計算出你所需要的數(shù)據(jù)或?qū)崿F(xiàn)你的攻擊方式，這個時候就需要選手具備良好的編程功底，因為很多時候?qū)?fù)雜的數(shù)學(xué)模型轉(zhuǎn)化成可行的腳本并不是一件容易的事。 ??這里所提到的編程主要可以看成兩個部分： ??一類是使用python、C/C++等這類語言進行編程，它是我們主要使用的編程語言，我們通過代碼來描述我們的攻擊過程，繼而實現(xiàn)攻擊。 ??第二類是針對某一工具的編程，常用的包括SageMath、MatLab、Mathematica編程等，這一類的編程往往起到的不是描述而是計算或輔助繪圖的作用，幫助我們更好的完成解題過程。其中尤其以SageMath最為常用，如針對群、環(huán)、域等代數(shù)結(jié)構(gòu)的計算，在SageMath中都可以很方便的進行操作，而不需要進行代數(shù)結(jié)構(gòu)的二次描述，另外很多常用算法都以內(nèi)置函數(shù)的形式在SageMath當(dāng)中集成，可以很方便的供選手使用。
5 值得關(guān)注的CTF
??由于CTF競賽中專職密碼學(xué)方向的選手通常較少，因此一場比賽是否有較高質(zhì)量的密碼學(xué)題目其實往往取決于辦比賽的戰(zhàn)隊中有沒有一個優(yōu)秀的密碼學(xué)選手，目前有一些比賽的密碼學(xué)題目質(zhì)量是要遠高于其他競賽的，值得參賽選手去重點關(guān)注（另外有一些戰(zhàn)隊雖然擁有很強的密碼學(xué)選手，但是戰(zhàn)隊辦比賽較少，可以關(guān)注其每次比賽賽后發(fā)布的writeup來了解其做題時的一些思路和解法）：
Teaser Dragon CTF（波蘭Google安全團隊Dragon Sector戰(zhàn)隊主辦）
0CTF/TCTF （中國騰訊安全A0E戰(zhàn)隊主辦）
HXP CTF （德國慕尼黑工業(yè)大學(xué)HXP戰(zhàn)隊主辦）
ASIS CTF & Crypto CTF （伊朗謝里夫理工大學(xué)ASIS戰(zhàn)隊主辦）
CODE BLUE CTF （日本聯(lián)合戰(zhàn)隊binja主辦）
PlaidCTF （美國卡耐基梅隆大學(xué)PPP戰(zhàn)隊主辦）
Midnight Sun CTF （瑞典HackingForSoju戰(zhàn)隊主辦）
SpamAndFlags Teaser CTF （匈牙利布達佩斯技術(shù)與經(jīng)濟大學(xué)!SpamAndHex戰(zhàn)隊主辦）
PwnThyBytes CTF （羅馬尼亞PwnThyBytes戰(zhàn)隊主辦）
6 不只是CTF
??對于一名密碼學(xué)方向的CTF選手來講，除了通過活躍于各大CTF比賽和在平時保持足夠的CTF題目訓(xùn)練強度來提升自己的水平之外，實際上還有一些其他的密碼學(xué)相關(guān)競賽可以用來作為訓(xùn)練，每年諸如NSU CRYPTO、WhibOx Contest等解題類密碼學(xué)競賽，也可以參加或做賽后練習(xí)用，以此來鍛煉密碼分析能力。
7 對密碼學(xué)的熱情
??興趣因素放在本文最后一個環(huán)節(jié)進行論述，但是實際上這是學(xué)習(xí)密碼學(xué)的第一步，也是最重要的一步，擁有對探索密碼學(xué)領(lǐng)域的無限熱情，會使你比任何人都更有可能成為一名優(yōu)秀的CTF密碼學(xué)選手。
8 參考資料
【CTF環(huán)境搭建&學(xué)習(xí)資料】
