All About Crypto - CTF競賽密碼學方向指南

本文最初寫于2019年，旨在幫助希望在一些相對較難的CTF國際賽上解出密碼學題目的同學構建一個知識框架和學習路線，近日整理了部分內容，發表在看雪論壇上，以下是本文內容（也可訪問這里以PDF格式查看，排版更為清晰）。

密碼學不僅是CTF競賽中的一個重要的獨立考察方向，也經常作為考點出現在其他方向的題目當中。本文從個人作為一名CTF密碼學方向選手的視角入手，對需要掌握的相關內容進行整理與分析，以期幫助選手更好的學習密碼學，更好的進行密碼學方向題目的訓練，取得更好的比賽成績。

扎實的數學功底

密碼分析的各個環節都離不開數學分析，對于選手求解一道CTF中的密碼學方向題目來講也是如此。在CTF中，主要考察密碼學選手數論和抽象代數兩個方向的數學知識。

1.1 數論

在數論方向，選手應能較為熟練的了解和掌握包括：

整除理論（了解素數、合數、因數、倍數、整除等基本概念，掌握唯一分解定理、裴蜀定理、擴展歐幾里得定理、算數基本定理等基本定理）

同余理論（了解同余、原根、底數、指數、平方剩余、同余式、同余方程等基本概念，掌握歐拉定理、費馬小定理、中國剩余定理、二次互反律、威爾遜定理等基本定理）

連分數理論（了解連分數、無窮級數等基本概念，熟悉最佳有理數逼近、循環連分數展開、佩爾方程求解等運算過程）

不定方程（了解低次代數曲線所對應的不定方程的基本模型，熟悉二元一次不定方程、多元一次不定方程、掌握通過代數恒等變化、不等式估算、同余法、構造法、無窮遞降法等常用的不定方程求解方法）

數論函數（了解歐拉函數、莫比烏斯函數、單位函數、恒等函數、除數函數等常用函數，掌握莫比烏斯反演、狄利克雷卷積等常用方法）

1.2 抽象代數

在抽象代數方向，選手應能較為熟練的了解和掌握包括：

群論（熟悉群代數結構，掌握群相關性質及其運算律）

環論（熟悉群代數結構，掌握環相關性質及其運算律）

域論（熟悉群代數結構，掌握域相關性質及其運算律）

格論（熟悉格代數結構，掌握格相關性質及其運算律）

線性代數（熟悉向量空間代數結構，掌握向量相關性質及其運算律）

除此之外，諸如邏輯學、幾何學、拓撲學、泛函分析、概率論、數理統計等其他數學分支，雖然在CTF競賽中密碼學方向題目直接考察較少，但選手應至少對其相關基本知識有一個大致了解。

密碼學技能樹

2.1 古典密碼學

古典密碼學作為早期CTF競賽中密碼學方向的一種常見考察形式，目前已經逐漸退出國際賽的歷史舞臺了。

CTF中的古典密碼主要以代替（substitution）密碼和置換（permutatuion）密碼兩種形式出現，在題目當中，出題人通常不會顯式的告訴你題目所采用的加密算法，而是僅僅給出密文，預期選手通過特征檢索（如密文字符集中存在標志性的特殊字符）、題目暗示（如題目名稱、題目描述中出現了對加密算法的隱喻）等方式猜測出題目中可能使用的加密算法，或使用數理統計（針對密鑰空間較大的代換密碼，如仿射、維吉尼亞等）、爆破（針對密鑰空間較小的代換或置換密碼，如柵欄、移位等）等方式恢復出密鑰，最后解密密文拿到FLAG。

這類題目的難點通常不在于分析而在于猜測，因此往往難度較低，但是由于代替和置換是密碼學算法中的兩個最基本的操作，很多現代密碼學算法中的運算都可以看作是這兩種運算的復合運算，因此古典密碼學題目也可作為初接觸CTF競賽密碼學方向的選手的練習題目，有助于培養選手對基本運算操作的理解。

2.2 現代密碼學

現代密碼學作為目前CTF競賽中密碼學方向的主要考察形式，從總體上可以分為對稱密碼學、非對稱密碼學、哈希函數和數字簽名四大類題目，其中每類題目在知識點層面雖互有交集，但由于考察形式各有側重，因此本文對這四類題目類型分別進行論述。

2.2.1 對稱密碼學

2.2.1.1 序列密碼（流密碼）

流密碼通常以字節或比特為基本單位來處理信息，其密鑰通常派生自一個較短的種子密鑰，而派生算法一般為一個偽隨機數生成算法，流密碼的安全性取決于密鑰流的安全性，因此CTF中的流密碼類題目也主要以偽隨機數生成器部分為主，當然除此之外，題目有時也會考察選手對某一具體的流密碼算法的理解和分析能力，如A5/1、RC4等。

對于偽隨機數生成器來講，常見的考察模型主要可以分為兩類：

一類為線性同余生成器（LCG），題目要求選手通過對生成器源碼審計，找出設計缺陷（針對生成器參數隨機化的場景）或進行數學推導恢復未知參數（針對參數恒定不變但缺失部分參數的場景），繼而連續預測出接下來產生的若干個隨機數，從而達到服務器要求拿到FLAG。

另一類為反饋移位寄存器，其中又可分為線性反饋移位寄存器（LFSR）和非線性反饋移位寄存器（NFSR）兩類主要考察模型，出題人通常會根據某一初始狀態采用某種生成方法生成一份輸出結果，然后將生成方法和輸出結果提供給選手，預期選手還原出初始狀態從而作為FLAG。

2.2.1.2 分組密碼（塊密碼）

塊密碼使用某一基本塊為基本單位來處理信息，在加密時需要將明文數據分成若干基本塊，再針對每一塊進行加密，如果最后一塊的長度小于基本塊的長度，還需要進行padding。

目前CTF中針對塊密碼主要從三個角度考察：

第一類是從塊密碼當中的ARX（A-有限域上的模加，R-循環移位，X-異或）三種基本操作入手，考察選手對組合運算的熟練程度和理解能力。

第二類是從具體算法角度入手，考察AES、DES等經典加密算法（或該加密算法的自定義修改版本）的線性攻擊、差分攻擊、積分攻擊等攻擊手法和選手做密碼分析的能力。

第三類是從分組模式入手，考察算法在padding時（如針對PKCS5 Padding的Padding Oracle攻擊）或加密模式上（如CBC字節翻轉攻擊、CFB重放攻擊）可能會出現的問題。

2.2.2 非對稱密碼學

CTF競賽中的非對稱密碼學主要考察三大類問題，即大整數分解問題、離散對數求解問題（包括橢圓曲線上的離散對數求解問題）和基于格（Lattice）的計算問題：

2.2.2.1 大整數分解問題

CTF中大整數分解問題主要以RSA算法為模型進行考察，RSA在目前CTF競賽中考察頻率可以說所有考點第一位，幾乎任何一場比賽都會有一道密碼學題目考察RSA，根據題目中給定的RSA算法的不同場景，其攻擊手法五花八門，需要選手具備很強的數論功底。

但也正是由于RSA知識點考察過于熱門，導致網上相關資料和現成的攻擊腳本較為成熟，對于一些簡單的RSA類題目，選手往往只需判斷出該題涉及到的RSA的哪一類場景，然后根據特征去檢索攻擊手法即可，但對于一些國際賽上的高質量RSA類題目，仍然需要選手具備極強的分析和推導能力。目前針對RSA的常見攻擊大致包括以下幾類：

針對模數的攻擊：如Pollard’s p -1算法（p-1光滑）、Williams’s p + 1（p+1光滑）、試除法（|p-q|過大）、費馬分解（|p-q|過小）、共模攻擊、模不互素攻擊等。

針對公鑰的攻擊：如小公鑰指數攻擊、低加密指數廣播攻擊等。

針對私鑰的攻擊：如Wiener’s attack（基于連分數）、私鑰低位泄露攻擊等。

Coppersmith & LLL相關攻擊：如已知m高位攻擊、已知p高位攻擊、Coppersmith’s short-pad attack、Boneh and Durfee attack等。

結合Oracle的攻擊：有時題目當中除了提供給選手參數之外還會提供一個加密/解密Oracle，結合Oracle可以衍生出更多種攻擊形式，如針對加密Oracle的公鑰泄露攻擊（選擇明文），針對解密Oracle的RSA LSB parity Oracle攻擊（選擇密文）。

2.2.2.2 離散對數求解問題

CTF中考察DLP類問題主要以Diffie–Hellman 密鑰交換協議和ElGamal算法為主，要求選手能夠通過審計代碼找出問題關鍵點，并使用攻擊算法求解DLP問題，常用的DLP攻擊算法包括：

小步大步法（Baby-step giant-step，中間相遇攻擊的思想）

Pollard’s Rho algorithm（基于Miller-Rabin算法，遞歸求解）

Pollard’s Kangaroo algorithm（基于隨機步）

Pohlig-Hellman algorithm（針對階n是光滑且僅有小素因子）

CTF中考察ECDLP類問題主要以橢圓曲線加密（ECC）為主，其曲線有限域通常為以素數為模的域 GF(p)或特征為2的域 GF(2^m)，ECDLP類題目的考察方式除了包括上面提到的DLP的一些常見模型和攻擊手法的橢圓曲線版以外，也包括一些針對曲線上存在的問題的攻擊形式，如：

針對E(Fp)=p（Frobenius軌跡t=p+1?E(Fp)=1）的上非正規橢圓曲線的Smart’s attack。

針對p|q+1?E(Fq)（Frobenius軌跡t是p的倍數）的超奇異橢圓曲線的MOV攻擊（借助Tate pairing或者Weil pairing）。

2.2.2.3 基于格的計算問題

CTF中考察格中的計算困難問題主要包括最近向量問題（CVP）和最短向量問題（SVP）問題，其考察形式主要分為兩類：

一類是利用格理論去分析已知的經典密碼算法，如使用格基規約算法（LLL）來分析DSA簽名系統（如DSA nonce biases）、RSA加密系統（如RSA的小私鑰攻擊、Coppersmith相關的攻擊）、背包加密系統（如Merkle–Hellman背包公鑰加密算法）等。

另一類是分析基于格中困難問題設而設計新的后量子密碼體制，如NTRU密碼系統、GGH密碼系統、Gentry算法的全同態加密系統、基于LWE問題的密碼系統、Ajtai–Dwork概率公鑰密碼系統等。

基于格的計算問題類題目在目前CTF競賽中頻繁出現，一度成為國際賽當中的主流考點，尤其是對LLL算法的理解和使用，成為解出許多高分值題目的關鍵。很多時候格相關攻擊較為復雜，需要選手結合論文來進行推導，關于CTF競賽中的論文問題會在后面的章節具體闡述。

2.2.3 數字簽名

數字簽名主要用于對數字消息進行簽名，主要用于防止消息被冒名偽造、篡改，以及通信雙方的身份鑒別。由于數字簽名主要依賴于非對稱密碼算法，因此CTF當中考察數字簽名類題目也主要依托非對稱密碼體系來進行設計，常見的包括RSA簽名、ElGamal簽名、DSA簽名、針對某一特定橢圓曲線的ECC簽名等，題目模型通常為要求我們提供某一特定字符串的簽名，如果能正確通過驗證則提供給選手FLAG，針對數字簽名類題目的攻擊我們一般從三個角度來切入：

設法直接計算私鑰，比如參數值過小或曲線選擇不合適，導致私鑰可以被直接計算出來（如2019 ASIS CTF Quals-Halloween Party題目，給定y坐標求x坐標，計算2在模P.order()上的逆并將結果乘2*P直接得到P）。

設法恢復私鑰，即通過若干特殊明文簽名對，采用建立方程等方式重構出密鑰（如2019 DEFCON CTF Quals-Tania題目，通過LLL算法和Babai最近平面算法恢復出密鑰）。

設法偽造簽名，即在不知道私鑰的情況下，直接構造出特定字符串的簽名來拿到FLAG（如2019 RealWorld CTF-bank題目，通過rogue-key attack偽造Schnorr比特幣簽名算法的銀行提款簽名）。

2.2.4 哈希函數

CTF中考察哈希函數類問題主要以兩類場景進行展開：

一類是哈希碰撞類場景，常見的攻擊類型包括：

同謀碰撞攻擊：生成任意兩個不同的消息和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)

在考察形式上，題目通常會直接要求選手向服務器提交A、B兩個輸入，如果滿足AB但HASH(A)=HASH(B)，則判斷碰撞成功。HASH碰撞類題目雖然場景簡單，但通常題目難度較大，而且很多時候都是出題人魔改之后的哈希算法，因此要求選手具備較強的分析能力，在攻擊上多以考察代數攻擊為主，如：

利用small capacity parameter誤用問題構造SHA3 Keccak海綿結構碰撞（2019 0CTF/TCTF Quals-babysponge）

利用Petit-Lauter攻擊構造超奇異同構圖上Charles-Goren-Lauter哈希函數的弱實例碰撞（2017 HXP CTF-categorical）

另一類則是哈希偽造場景，雖然很多時候偽造哈希也可以通過尋找碰撞的方式來實現，但是它和碰撞場景下的考察側重點通常不同，一種典型的攻擊手法即哈希長度擴展攻擊，即在已知的值和的長度的情況下（這里的值未知，即代表哈希時的salt），要求選手對于任意一個的值。對于哈希偽造的場景，我們的重點一般直接從攻擊手法入手，而不需要對源碼進行審計（絕大多數情況下，這類場景也不會給出哈希算法細節，而是直接調用現成的MD5、SHA1庫函數）。

讀paper的能力

自2018年起，大量論文題開始登上CTF歷史舞臺，然而一場標準的CTF國際賽通常為48小時，留給選手的分析時間是有限的，因此對于很多國際賽上的密碼分析類題目來講，選手是很難在短時間內提出一種可行的攻擊手段的。這個時候，就需要快速提煉出題目當中的模型、場景等關鍵內容，然后去檢索并閱讀與之對應的會議、期刊論文，從中尋找攻擊思想或手段。因此，選手的論文閱讀理解能力（尤其是英文文獻的閱讀能力）對于密碼學方向來講就顯得尤為重要。近年來國際賽當中CTF題目與學術界論文或研究成果聯系緊密，如：

2018 PlaidCTF-braid題目，考察選手通過閱讀論文[1]，解決一個辮子群（Braid Group）下的 Conjugacy Search 問題。

2018 Hack.lu CTF- Escape the grid題目，考察選手通過閱讀論文[2]，攻破一個使用了非安全函數產生仿射變換的 rasta 密碼系統。

2019 0CTF/TCTF Quals-zer0lfsr題目，考察選手通過通過閱讀論文[3]，利用Fast Correlation Attack恢復出一個Meier-Staffelbach模型下0.75相關性的3個LFSR的初始狀態（雖然這道題在當時比賽時被z3非預期了）。

2019 PwnThyBytes CTF-Wrong Ring題目，考察選手通過閱讀論文[4]，通過將環上帶誤差學習（RLWE）樣本轉化為多項式帶誤差學習(PLWE)樣本，攻擊一個（non-dual）RLWE的實例來求私鑰。

還有很多題目直接以某一論文或研究成果為背景進行設計，如：

2017 ASIS CTF Final-Marijuana

2017年5月，Divesh Aggarwal等學者提出了一種基于梅森素數的公鑰密碼體系[5]，2個月后，該密碼系統被Marc Beunardeau等學者攻破，相關成果以論文形式發表[6]，同年9月，該事件以CTF形式出現在當年的ASIS CTF競賽當中，預期選手通過閱讀論文使用隨機劃分和LLL攻擊攻破密碼系統。

2017 HXP CTF-notsosmart

2017年2月，馬薩里克大學的Matus Nemec和Marek Sys等學者發現英飛凌科技提供的RSALib庫中的密鑰生成算法存在漏洞，并據此提出了一種可行的RSA ROCA攻擊。同年11月，相關攻擊細節以論文形式披露[7]（該攻擊同步影響了TPM 1.2, 4.3.5版本前的YubiKey 4等產品，CVE編號：CVE-2017-15361），兩周后，該事件以CTF形式出現在當年的HXP CTF競賽當中，預期選手通過閱讀論文使用ROCA攻擊攻破一個RSA密鑰生成算法。

扎實的編程功底

對于絕大多數情況下，當選手通過審計源碼或者閱讀論文整理出一種攻擊手段之后，接下來都需要通過編程的方式寫一個solver或exp來計算出你所需要的數據或實現你的攻擊方式，這個時候就需要選手具備良好的編程功底，因為很多時候將復雜的數學模型轉化成可行的腳本并不是一件容易的事。

這里所提到的編程主要可以看成兩個部分：

一類是使用python、C/C++等這類語言進行編程，它是我們主要使用的編程語言，我們通過代碼來描述我們的攻擊過程，繼而實現攻擊。

第二類是針對某一工具的編程，常用的包括SageMath、MatLab、Mathematica編程等，這一類的編程往往起到的不是描述而是計算或輔助繪圖的作用，幫助我們更好的完成解題過程。其中尤其以SageMath最為常用，如針對群、環、域等代數結構的計算，在SageMath中都可以很方便的進行操作，而不需要進行代數結構的二次描述，另外很多常用算法都以內置函數的形式在SageMath當中集成，可以很方便的供選手使用。

值得關注的CTF

由于CTF競賽中專職密碼學方向的選手通常較少，因此一場比賽是否有較高質量的密碼學題目其實往往取決于辦比賽的戰隊中有沒有一個優秀的密碼學選手，目前有一些比賽的密碼學題目質量是要遠高于其他競賽的，值得參賽選手去重點關注（另外有一些戰隊雖然擁有很強的密碼學選手，但是戰隊辦比賽較少，可以關注其每次比賽賽后發布的writeup來了解其做題時的一些思路和解法）：

Teaser Dragon CTF（波蘭Google安全團隊Dragon Sector戰隊主辦）

0CTF/TCTF （中國騰訊安全A0E戰隊主辦）

HXP CTF （德國慕尼黑工業大學HXP戰隊主辦）

ASIS CTF & Crypto CTF （伊朗謝里夫理工大學ASIS戰隊主辦）

CODE BLUE CTF （日本聯合戰隊binja主辦）

PlaidCTF （美國卡耐基梅隆大學PPP戰隊主辦）

Midnight Sun CTF （瑞典HackingForSoju戰隊主辦）

SpamAndFlags Teaser CTF （匈牙利布達佩斯技術與經濟大學!SpamAndHex戰隊主辦）

PwnThyBytes CTF （羅馬尼亞PwnThyBytes戰隊主辦）

不只是CTF

對于一名密碼學方向的CTF選手來講，除了通過活躍于各大CTF比賽和在平時保持足夠的CTF題目訓練強度來提升自己的水平之外，實際上還有一些其他的密碼學相關競賽可以用來作為訓練，每年諸如NSU CRYPTO、WhibOx Contest等解題類密碼學競賽，也可以參加或做賽后練習用，以此來鍛煉密碼分析能力。

對密碼學的熱情

興趣因素放在本文最后一個環節進行論述，但是實際上這是學習密碼學的第一步，也是最重要的一步，擁有對探索密碼學領域的無限熱情，會使你比任何人都更有可能成為一名優秀的CTF密碼學選手。