基于隨機性測試的分組密碼體制識別方案*

趙志誠,趙亞群,劉鳳梅

1.信息工程大學數學工程與先進計算國家重點實驗室,鄭州 450001

2.信息保障技術重點實驗室,北京 100072

1 引言

密碼分析作為一種被動攻擊方法,是指在不知道解密密鑰及通信者所采用的加密體制的細節的條件下,試圖獲得機密信息.根據所研究的對象,密碼分析研究的對象主要包括兩個部分:密碼算法和密文.根據著名的Kerchoffs 原理[1]提出加密算法的公開不應該影響明文和密鑰的安全,當前大多數密碼分析方法也是在假設密碼體制已知的前提下,展開對各種密碼算法的分析.然而在現實中,被動攻擊的一方通常僅能獲取敵手的密文,這種情況下密碼分析者只能開展唯密文攻擊.因此識別密文的密碼體制(以下簡稱密碼體制識別)就成為了開展密碼分析的一個前提條件.

近年來,AES 征集和評選、NESSIE 計劃和Estream 計劃等一系列公開的加密標準征集活動極大地帶動了密碼體制設計的發展[2,3].與此同時,針對當前各類密碼體制的密碼分析正持續成為研究熱點.密碼體制識別技術是密碼分析的一個重要組成部分,主要研究在不同密碼體制加密的密文中識別出具體的密碼體制.許多具體的密碼分析技術是專為某種密碼體制設計的,或假設已知產生密文的密碼體制.而在現實中,密碼分析者得到的只是未知編制的密文,因此對于密碼體制的識別是開展具體密碼分析的前提條件.此外,密碼體制抵抗識別的能力也可以衡量密碼體制安全性,對于密碼體制的設計與安全性評估具有積極的參考意義.因此開展密碼體制識別相關研究,對于推動密碼學的應用與發展有著雙重的促進作用.

目前,密碼體制識別方案的設計思路主要來源于統計學方法和機器學習技術[4].研究者認為,某一特定密碼體制產生的密文與其他密碼體制產生的密文在空間分布上存在一定的差異,從而嘗試提取出能夠刻畫相應差異的特征,作為識別密碼體制的依據.早期基于統計學的密碼體制識別方法通過提取密文的各類統計指標進行比較,并給出識別結果.隨著密碼學的發展,各類密碼體制混淆擴散能力不斷提升,給密碼體制識別帶來巨大挑戰.為此機器學習方法被引入密碼體制識別任務中.基于機器學習技術的密碼體制識別方案將特征視為一組屬性、將識別任務等同于分類任務,在包含特征和算法標簽的訓練數據集上訓練分類器模型,再用訓練好的分類器對測試集數據(僅包含從密文中提取的特征)進行識別[4–7].基于機器學習技術的密碼體制識別方案設計簡單、表現穩定,且能處理數據之間的復雜關系,已經成為密碼體制識別領域的研究熱點.

密碼體制識別最初的研究對象是古典密碼體制.2001年,Pooja[8]設計了一種基于字母使用頻率的古典密碼體制識別方案,分析了包括置換密碼、代換密碼和維吉尼亞密碼在內的主要的古典密碼.隨著現代密碼技術的飛速發展,傳統的基于統計學方法的密碼體制識別技術逐漸失效.此時針對復雜且安全系數高的現代密碼,國外研究者結合模式識別領域相關技術,設計了一系列基于機器學習方法的密碼體制識別方案.2006年,文獻[5]借鑒文檔分類技術,提出了基于支持向量機的分組密碼識別方案,考慮了對包含AES、DES、3DES、Blowfish、RC5 在內的五種密碼體制的識別.2008年,Negireddy 等人[9]利用模式識別技術,對AES、DES、TDES、Blowfish、RC5 等密碼體制在ECB 與CBC 模式下的加密密文做了區分實驗.

2011年,Manjula 等人[4]提出了一種基于決策樹分類器的密碼體制識別方案,對包含2 種古典密碼、1 種序列密碼、6 種分組密碼、2 種公鑰密碼的11 種密碼體制進行了識別.2012年,Chou 等人[10]利用支持向量機技術分別對CBC 和ECB 兩種工作模式下的加密密文進行區分,對ECB 模式下的密文進行了成功區分,對于CBC 模式下的密文則不能區分.2013年,De Souza 等人設計了一種基于神經網絡的識別方案,研究了AES 最終輪候選密碼算法的識別[5].2015年,吳楊等人[11]基于隨機性測試采集了3 種密文特征,并在對AES、Camellia、DES、3DES、SMS4 五種分組密碼體制的識別過程中使用了K-均值聚類算法.Sharif 等人[6,12]在其設計的分組密碼體制識別方案中,比較了使用8 種不同的分類器模型的識別效果,其結果顯示,組合分類器模型Rotation Forest 效果最佳.2017年,黃良韜等人[13]結合已有的密碼體制識別研究成果,從密碼體制識別方案設計和特征提取兩大問題著手,提出一種基于隨機森林算法的密碼體制分層識別方案,其識別研究對象涵蓋古典、分組、序列和公鑰等現有主要的密碼體制.該文給出一個較完整的密碼體制識別問題的定義系統,并將密碼體制的單層識別和分層識別統一于該系統下.

密碼體制識別方案主要關注兩個方面:密文特征的選取與挖掘、機器學習算法的選擇.隨著機器學習算法包括深度神經學習網絡的發展,在算法選擇方面,目前多數機器學習算法均有相應的程序包(例如R語言),研究者可以較為簡易的對各類算法的分類性能進行比較.在密碼體制識別任務中,特征提取對密碼體制識別的成功率具有重要影響.由于分類算法直接對所提取特征進行處理,而密文數據自身通常具備較強的隨機性質,因此提取出能有效地刻畫密文信息的特征,成為識別任務中的關鍵環節.目前公開研究中的密文特征可以大致分為五類:

(1)計算字符、特定長度字節或比特等的熵[13];

(2)統計字符、特定長度字節、比特的概率[13];

(3)對密文開展隨機性測試獲得足夠的返回值作為密文特征,如文獻[11]基于碼元頻數檢測、塊內頻數檢測及游程檢測設計了3 類表現比較優異的特征;

(4)將密文看成可變長的文檔向量[5];

(5)將以上某幾類特征組合成新的特征[10,13].

表1 部分文獻中出現的密文特征Table 1 Typical features in some papers

觀察表1,可以看到上述特征維數均在100 以上,個別特征維數已經超過10 萬維.在機器學習領域,特征維數的提高通常會增加數據分析的存儲開銷與運行時間消耗.在機器學習領域,特征工程[14]的一個重要內容就是篩選信息量更多、靈活性更強的特征,從而能夠在簡單模型訓練中也能得到優秀的結果.基于機器學習的密碼體制識別任務,同樣需要關注密文特征提取方式的改進以提高復雜數據環境下的識別效率.然而由于密數據通常具有較高的隨機性,如何提取有效的密文特征、密文特征構建方法的創新,國內外關于該方面的公開研究較少,密文特征提取方式較為簡單,因此特征所包含的密文信息有限.

分組密碼算法以其易于標準化及運算速度快等特點得到廣泛應用,其安全性也一直備受關注.目前關于分組密碼算法攻擊的分析集中于差分密碼分析、線性密碼分析和強力攻擊[3].對分組密碼體制識別的研究,可以為現實中的密碼分析提供支持,同時也有助于密碼安全性評估.本文主要關注AES、Blowfish和Camellia 等多種安全性較高且被廣泛使用的分組密碼體制的識別任務.基于隨機性測試提出的一類新密文特征,并在由隨機森林算法構成的分類器中開展分類訓練和測試.

本文主要內容如下:第1 節介紹密碼體制識別的相關概念和領域近年來的研究脈絡與成果,對于已有的主要工作及其方法作簡要分析;第2 節簡略介紹了本文所提方案的主要構成部分;第3 節主要介紹基于隨機性測試的密文特征提取方法;第4 節給出完整的密碼體制識別方案;在第5 節展示實驗結果并作分析;最后第6 節總結全文并展望后續工作.

2 密碼體制識別基本原理

密碼體制識別問題首先涉及到待識別密碼體制集合即識別對象.當識別對象確定后,即可對具體的識別問題進行研究,給出相應的識別方案.而對方案效果的評價一般通過識別準確率給出.文獻[13]將這些密碼體制識別問題中的基本要素進行整合,給出密碼體制識別及其識別方案的定義如下:

定義1(密碼體制識別)考慮密碼體制集合M={m1,m2,···,mN},其中N為密碼體制數量.對于由任意密碼體制m∈M加密生成的密文文件F,密碼體制識別是指在可獲取文件內容,但不知曉其密碼體制m的情形下,通過某一識別方案J,以一定的準確率hJ識別出其密碼體制m的過程,它由三元組Γ =(M,J,hJ)完全刻畫.識別準確率在模式識別語意下有明確的意義,這里準確率hJ是評價密碼體制識別方案的一種自然的度量.

定義2(密碼體制識別方案)在密碼體制識別問題 Γ 中,密碼體制識別方案由三元組J=(oper,fea,alg)刻畫,其中oper 表示方案進行密碼體制識別的工作流程,fea 表示方案對密文數據所提取的特征或特征集,alg 表示方案采取的識別算法.

定義3(識別場景)在密碼體制識別方案J中,任意待識別密碼體制集合M即對應一種識別場景,記作qM.

根據識別場景和分類需求的不同,密碼體制識別可以細分為簇分和單分.簇分是為了判斷密文所屬的密碼體制在較大層次下的類別,如:判斷密文是分組密碼加密的還是公鑰密碼加密的,是分組密碼中的CBC 模式還是ECB 模式等.單分則是確定密碼體制的具體類別,如ECB 模式下128 bits 密鑰長度下AES 與Camellia 所加密密文的識別.

在上述定義下,密碼體制識別問題可記為Γ =(M,J,hJ),其中,密碼體制識別方案由三元組J=(oper,feaM,CA)刻畫,其中oper 表示方案進行密碼體制識別的工作流程、feaM表示方案對密文數據所提取的特征(與待識別密碼體制集合M相關),CA 為方案采取的分類算法,在本文中即為后續提到的隨機森林算法.工作流程oper 由訓練階段和測試階段的一系列步驟組成,以過程形式敘述如下:

過程oper.

訓練階段

步驟1.采集已知密碼體制的一組密文文件F1,F2,···,Fn,其中n為文件個數;

步驟2.對文件內容數據進行特征提取,得一組特征集FeaM={,,···,},其中,i=1,2,···,n是維數為d的向量,稱d為特征維數;

步驟3.記n個文件的密碼體制標簽(已知)形成一個n維向量Lab={lab1,lab2,···,labn},稱二元組(FeaM,Lab)為帶標簽的數據;

步驟4.將帶標簽的數據(FeaM,Lab)提交分類算法CA,進行分類模型的訓練.

測試階段

步驟1.對一個待識別密文文件F的內容數據進行特征提取,得到d維特征fea;

步驟2.將特征fea 輸入到在訓練階段訓練好的分類模型中,后者給出密碼體制識別結果,即密碼體制標簽lab.

上述示例展示了形式化定義的基于機器學習的密碼體制識別方案,給定三元組J=(oper,fea,alg),即決定了一種密碼體制識別方案.圖1 是識別方案的訓練與測試流程圖.

3 特征提取

在機器學習領域,模型的質量通常由所選取的特征直接決定,特征對機器學習應用的效果有重要影響[15].本文引言已經介紹了密碼體制識別任務中常見的密文特征提取方式,現有的密文特征存在識別成功率較低、維數較高的缺點.在文獻[11]中,研究者運用隨機性測試返回值構建的密文特征向量,對部分分組密碼體制取得了較好的區分結果.文獻[13]也選擇了NIST 標準中的5 種隨機性測試特征作為密文特征,并完成了多項密碼體制識別任務.分析已有的研究結果可以發現部分隨機性測試返回值確實可以反映密文中存在的差異,并以此完成密碼體制識別任務.下面本文將從隨機性測試的數學基礎出發,介紹基于隨機性測試的密文特征提取方法.

圖1 密碼體制識別方案流程圖Figure 1 Flowchart of cryptosystems recognition scheme

3.1 隨機性測試的數學基礎

目前眾多的隨機性檢測項目和方法,主要用于檢測密碼算法輸出序列的統計特性,其中影響較為廣泛的是美國商務部國家標準技術協會(NIST)于2001年5月公布的NIST FIPS140-2 標準[16]中定義的用于密碼系統安全性度量的諸多隨機性檢測方案.測試一個序列的隨機性,實質上是檢驗其是否是真隨機的或與真隨機序列之間的差距,而假設檢驗[17]是隨機性測試的理論基礎.在檢驗時,首先提出一個待檢驗的原假設,記作H0.相應地,與原假設相反的假設稱備擇假設,記作H1.例如,在隨機性測試中一般設置原假設H0為:序列是隨機的;備擇假設H1:序列是非隨機的.對于每個檢驗來說,若檢驗結果接受原假設即表明待檢數據是隨機的,否則認為待檢數據是非隨機的.檢驗的具體步驟如下:

步驟1.確定原假設H0和備擇假設H1;

步驟2.根據H0的內容選取合適的統計量X,并確定其分布;

步驟3.按給定的顯著性水平α,查統計量X所對應分布的分位數表,找出臨界值,確定拒絕域;

步驟4.將由樣本計算出的統計量X的值與查得的臨界值進行比較,從而作出判斷,即:若統計量X的值落入了拒絕域中,則拒絕H0,否則接受H0.

此外,假設檢驗會產生二類錯誤類型,如表2 所示.

表2 假設檢驗錯誤類型Table 2 Types of hypothesis testing errors

在實際應用中,衡量隨機性的方法通常有2 種:門限值法和P-value 值法.這里以測試統計量X服從χ2分布為例來說明.

(1)門限值法.先做出分布的概率密度曲線如圖2,根據給定的顯著性水平α與相應的α分位點,再對統計量X與進行比較,確定是拒絕還是接受原假設.

(2)P-value 值法.同樣作出χ2分布的概率密度曲線,先求出統計量X,然后計算從X到無窮的積分,將積分結果(即P-value 值,圖中的陰影部分面積)與α進行比較,確定接受原假設與否.本文中討論的隨機性測試正是通過選取的測試統計量來計算P-value 值,將P-value 值作為接受原假設的強度,其含義是:真隨機數的隨機性比待測序列弱的概率.如果其值為1 則是完全真隨機的,值為0 則是完全非隨機的.對于顯著性水平α,如果P-valueα,那么原假設被接受,序列是隨機的,反之被拒絕,序列是非隨機的.參數α也即是表2 中錯誤類型1 的概率,通常α的取值范圍是[0.001,0.01],如圖3 所示.

圖2 卡方分布的概率密度曲線及其α 分位點Figure 2 Probability density curve of Chi-square distribution and its quantile of α

圖3 卡方分布的概率密度曲線及其P-value 分位點Figure 3 Probability density curve of Chi-square distribution and its quantile of P-value

3.2 密文特征提取方法

同時在3.1 節中對隨機性測試的介紹中也可以了解到,NIST 隨機性測試對于序列隨機性的檢測具有較廣泛的覆蓋面,對于序列的全局或部分的隨機性均有針對性的測試.本文在保證隨機性測試返回值有意義的前提下,對密文進行分塊或改變部分測試中的參數,再分別運行15 種NIST 隨機性測試,分別得到了密數據集數量不等的測試返回值也就是第2 節中提到的P-value 值,這些返回值就作為密數據的特征數據.

采集密文特征數據過程中,為保證隨機性測試返回值的有效性,在對密文分塊時,對于測試的每個密文塊均做到符合各隨機性測試對序列長度的要求.設置密文分塊個數有兩個依據:(1)分塊后的密文塊大小必須符合隨機性測試所需的序列長度要求(一些測試對于檢測序列的長度要求較大,本文一般對密文不再分塊,或者只分較少塊);(2)在保證條件一的基礎上,由于文件大小為512 kb,為了方便測試,所以選擇的分塊數都是512 的因子,這樣在分塊后,可以減少密文數據的損失.考慮到本文試圖選取一些性能優良的低維特征,為此對于密文分塊或特征維數均采取一定控制,一般不超過256 維.根據特征提取的方式和維數不同,上述特征可分為15 類共計48 種特征,其具體提取方式如下(設待檢測序列長度為n):

(1)累積和測試(cumulative sums test).檢測序列中的部分和是否太大或太小,太大或太小均被認為是非隨機的,該測試返回2 個值.該測試要求待檢測序列n100.分別將密文分為8、16、32、64和128 塊,執行該測試提取得到的特征有:16 維、32 維、64 維、128 維和256 維共計5 種,分別簡記為:Cus16、Cus32、Cus64、Cus128、Cus256.

(2)線性復雜度測試(linear complexity test).采用Berlekamp-Massey 算法[18,19]計算每個子序列的線性復雜度,并與真隨機序列的復雜度作比較,以確定待測序列的隨機性,該測試返回1 個值,要求待檢測序列長度n106,且子序列長度M滿足500M5000,因此最多只能將密文分為4 塊.執行該測試得到的特征有:4 維共計1 種,簡記為:Lc4.

(3)最長1 游程測試(longest run of ones test).檢測序列中最長1 游程的長度與真隨機序列中最長1 游程的長度是否近似一致,該測試返回1 個值,要求待檢測序列長度n128.分別將密文分為32、64、128 塊,執行該測試得到的特征有:32 維、64 維和128 維共計3 種,分別簡記為:Lro32、Lro64 和Lro128.

(4)重疊塊測試(overlapping template matchings test).統計待測序列中,特定長度的連續“1”的數目,并計算與真隨機序列的情況偏離,如果偏離較大則認為序列是非隨機的,該測試返回1 個值,要求待檢測序列長度n106,考慮到測試對于序列的長度要求較大,對于該測試的密文序列未作分塊.更改測試中參數的取值,得到特征有:4 維(根據參數不同設置分為2 種),分別簡記為:Otm4-1 和Otm4-2.

(5)隨機游走測試(random excursions test).檢測序列中某個特定狀態出現的次數是否遠遠超過真隨機序列中的情況,如果超出較多,則認為序列是非隨機的,該測試返回8 個值,要求待檢測序列長度n106.將密文快分為1、2、3、4 塊,執行該測試得到的特征有:8 維、16 維、24 維和32 維共計4 種,分別簡記為:Re8、Re16、Re24 和Re32.

(6)隨機游走測試變量(random excursions variant test).檢測序列中某一特定狀態在一個隨機游程中出現的次數與真隨機序列的偏離程度,如果偏離程度較大,則序列是非隨機的,該測試返回18 個值,要求待檢測序列長度n106.將密文平均分割為1、2、3 和4 塊,執行該測試得到的特征有:18 維、36 維、54 維、72 維共計4 種,分別簡記為:Rev18、Rev36、Rev54 和Rev72.

(7)近似熵測試(approximate entropy test).比較序列中長度分別為m-bit 與(m?1)-bit 串出現的頻次,再與正態分布下的序列對比,從而確定序列隨機性,該測試返回1 個值,要求待檢測序列長度m

(8)全局通用測試(universal statistical test).檢測序列是否能在信息不丟失的情況下被明顯壓縮,通常一個不可被明顯壓縮的序列是隨機的,該測試返回1 個值,要求待檢測序列n387840.因此將密文平均分割為2、4 和8 塊,執行測試得到的特征有:2 維、4 維和8 維共計3 種,分別簡記為:Us2、Us4 和Us8.

(9)離散傅里葉測試(discrete Fourier transform test).檢測序列中的周期性質,并與真隨機序列的周期性質比較,通過二者之間的偏離程度來確定待測序列隨機性,該測試返回1 個值,要求待檢測序列n1000.將密文平均分割為32、64、128 和256 塊,執行該測試得到的特征有:32 維、64 維、128維和256 維共計4 種,分別簡記為:Dft32、Dft64、Dft128 和Dft256.

(10)連續塊測試(serial test).檢測序列中所有m-bit 組合子串出現的次數是否與真隨機序列中的情況近似相同,如果是則序列符合隨機性要求,該測試返回1 個值,要求待檢測序列長度m

(11)二元矩陣秩測試(rank test).將序列構造成若干矩陣,檢測序列中固定長度子序列的線性相關性.如果線性相關性較小,則認為序列是隨機的,該測試返回1 個值,要求待檢測序列長度n>M×N,其中M和N分別為矩陣的行列數(NIST 默認M=N=32).將密文平均分割為32、64 和96 塊,執行該測試得到的特征有:32 維、64 維和96 維共計3 種,分別簡記為:Rt32、Rt64 和Rt96.

(12)非重疊塊測試(non-overlapping template matchings test).統計序列中,某特定模式出現的次數,并計算與真隨機序列中的偏離,如果偏離較大則認為序列是不隨機的.當重疊模塊長度為5 時,該測試返回12 個值;當重疊模塊長度為6 時,該測試返回20 個值;當重疊模塊長度為7 時,該測試返回40 個值;當重疊模塊長度為8 時,該測試返回74 個值;當重疊模塊長度為9 時,該測試返回148 個值,該測試對待測序列未給明確規定,但是在測試樣例中,序列長度為220.由于該測試不分塊即可返回數十個返回值,故在本測試中不再對密文做分塊.分別選擇測試參數即重疊模塊長度為:m=5,6,7,8,9,執行該測試得到的特征有:12 維、20 維、40 維、74 維和148 維共計5 種,分別簡記為:Nt12、Nt20、Nt40、Nt74和Nt148.

(13)組內頻率測試(block frequency test).功能是檢測待測序列中,所有非重疊的M-bit 塊內的0 和1 的數量是否表現為隨機分布,該測試返回1 個值,要求待檢測序列n100 .將密文平均分割為32、64、128 和256 塊,執行該測試得到的特征有:32 維、64 維、128 維和256 維共計4 種,分別簡記為:Bf32、Bf64、Bf128 和Bf256.

(14)頻率測試(frequency test).功能是檢測二進制序列中,0 和1 的比例是否均衡,該測試返回1個值,要求待檢測序列n100.將密文平均分割為32、64、128 和256 塊,執行該測試得到的特征有:32維、64 維、128 維和256 維共計4 種,分別簡記為:Fre32、Fre64、Fre128 和Fre256.

(15)游程測試(run test).功能是檢測二進制序列中,游程分布情況是否符合隨機序列的要求,該測試返回1 個值,要求待檢測序列n100.將密文平均分割為32、64、128 和256 塊,執行該測試得到的特征有:32 維、64 維、128 維和256 維共計4 種,分別簡記為:Run32、Run64、Run128 和Run256.

作為上述特征性能的對比,本文選擇了6 種在公開文獻[4,7,12,13]中所使用的密文特征參與密碼體制識別.下面是這些特征的具體提取方法:

(16)將密文分別按分組長度為56 bits、128 bits、256 bits 分塊,計算所有塊中某一固定比特位的熵,形成維數與分塊長度相同的特征,3 種特征分別記為:F_56b、F_128b、F_256b;

(17)將密文分別按分組長度為9 bits、10 bits、11 bits 分塊,計算不同組合形式的比特串出現頻率,形成維數分別為256、512 和1024 的特征,3 種特征分別記為:F_256、F_512、F_1024.

4 識別方案

本文首先基于上述特征開展密文分類、分組密碼工作模式分類任務,以驗證基于隨機性特征在密數據分類任務中的有效性.在此基礎上選擇AES、DES、3DES、IDEA、Blowfish 和Camellia 等6 種分組密碼作為密碼體制識別研究對象.在方法構成層面,可分為兩個主要部分:密文特征提取和密碼體制識別分類器的構造.利用NIST 隨機性測試程序包中的15 種隨機性測試作為密文特征提取的方法基礎,提取了45 種密文特征,同時也提取了部分已有的文獻中提到的密文特征作為新密文特征的參照對象.本文采用隨機森林算法構造密碼體制識別分類器,并以提取到的各類密文特征數據作為分類器的輸入,經過數據的訓練與測試階段,最終完成對密碼體制的識別任務.

隨機森林算法由Tin Kam Ho[20]提出,隨后經由Leo Breiman 等人[21]對該算法做了擴展.隨機森林是一個包含多個決策樹的分類器,其輸出類別是由個別樹輸出類別的眾數而定(即所謂的投票方法).該算法對數據集的適應能力強,對于高維度的、離散和連續數據均能很好的處理,具有很好的抗噪聲能力,而且算法本身簡單且易于并行化.在分類實踐中得到廣泛應用.本文基于機器學習中的隨機森林(random forest)算法構造分類器,所提識別方案分為兩個部分:訓練部分和測試部分.其具體算法流程展示如下:

基于隨機森林的密碼體制識別分類器

輸入:密碼體制數目k、每種密碼體制加密密文數量S,維數為Dim 的密文特征fea=(x1,···,xDim)組成的樣本集T=(C1,C2,···,Ck),其中Ci=(feai,1,feai,2,···,feai,S),Ci包含的是所有密碼體制i加密的密文的特征集.

輸出:分類結果密碼體制A1,A2,···,Ak.

訓練階段

步驟1.輸入密文特征集T,包含kS個樣本,每個樣本表示一個密文特征,每個特征有Dim 個屬性,記為f1,f2,···,fDim;設定整數n

步驟2.采用有放回取樣,隨機在T中抽取M個樣本,形成Bootstrap 樣本集T?,作為決策樹根節點處的樣本.

步驟3.隨機從Dim 個屬性中選擇n個屬性作為單棵樹的候選屬性,符合條件n?Dim.再從這n個屬性中采用某種策略(如信息增益)來選擇1 個屬性作為該節點的分裂屬性.

步驟4.決策樹形成過程中每個節點都要按照步驟2 來分裂,至不能夠再分裂為止.

步驟5.重復步驟2–3 建立t棵決策樹構成隨機森林.

測試階段

步驟1.對任一個輸入的特征向量feai,j,記錄其在每一棵樹上輸出分類結果.

步驟2.統計投票結果,票數最高的類別就是feai,j的類別標簽.

5 實驗結果與分析

5.1 實驗對象及相關設置

本文中實驗選擇以由OpenSSL 密碼庫提供的AES、DES、3DES、IDEA、Blowfish 和Camellia 等6 種密碼體制,其基本設置如表3.基于隨機性測試的密文特征提取方法由C 程序實現,通過Rstudio 平臺上的隨機森林算法完成各類文本的分類.實驗所用到的明文來自圖片庫[22]隨機選擇的圖片拼接而成,隨后被平均分割成1000 份,每份大小均為512 kb.對于不同的分組密碼算法,凡未注明密鑰設置的均使用固定密鑰加密.實驗過程中,待分析的密文樣本量均為1000 份,每份大小均為512 kb.對實驗數據(即對密文文件提取特征所得到的數據)進行重復隨機子抽樣驗證(repeat random sub-sampling validation),每次抽樣對每一密碼體制生成的密文文件提取得到的特征樣本,隨機抽樣75% 作為訓練集,其余25% 作為測試集.以十折重復隨機子抽樣驗證測試集識別的平均準確率作為識別效果的度量.對6 種密碼體制的一一識別共計15 種識別場景進行了分類實驗.

表3 7 種分組密碼體制的具體參數列表Table 3 Parameter setting of 7 block ciphers

5.2 實驗結果與分析

5.2.1 明密文與分組密碼工作模式識別

在開展密碼體制識別前,本文首先測試基于隨機性測試密文特征在明密文識別和ECB 和CBC 兩種分組密碼工作模式識別任務中的有效性.其中,明密文識別實驗是對ECB 模式下AES 加密密文與明文進行分類,分組密碼工作模式識別則是對分別由ECB 和CBC 模式下的AES 加密密文的分類.為簡化數據采集,該部分實驗只選擇基于上述15 種隨機性測試的代表性密文特征作為分類時采集的特征數據.

表4 明文與AES 加密密文的識別結果Table 4 Recognition results of plaintext and ciphertext encrypted by AES

由表4 和表5 可以看出,多數基于隨機性測試特征均能夠以超過94% 的成功率實現對明密文的識別,以不低于82% 的成功率區分密文所使用的工作模式.考慮到明密文之間在統計上通常存在比較明顯的差異且密碼體制的工作模式對于密文隨機性也具有較大的影響,上述實驗初步驗證了這些特征在密數據分析中的有效性.

5.2.2 分組密碼體制識別

為進一步驗證基于隨機性測試特征在密碼體制識別中的作用,采集54 種基于隨機性測試的密文特征基礎上,對6 種分組密碼體質進行了一對一的分類實驗,表6 展示各類特征在15 種識別場景下的平均識別成功率和識別成功率的標準差,其中平均識別率表示密文特征其密碼體制識別性能的集中趨勢,標準差則反映其識別性能的穩定性.圖4 則以箱式圖的形式展示基于隨機性測試特征在不同識別情境下識別準確率的波動范圍與中位數的分布.

表5 ECB 模式與CBC 模式下AES 加密密文的識別結果Table 5 Recognition results of ciphertext encrypted by AES ECB and AES CBC

表6 基于隨機性測試的54 種密文特征的識別結果Table 6 Recognition performance of 54 features based on random tests

圖4 54 種基于隨機性測試特征在各識別場景下識別準確率的箱式圖Figure 4 Boxplot of 54 features’ recognition accuracies

結合表6 和圖4,可以發現,上述54 種密文特征的識別結果雖然存在較大差異,但總體上,多數特征能以高于隨機(圖3中的黑色水平線)的識別成功率區分6 種分組密碼體制中的任意2 種密碼體制,且部分特征具有較高的識別準確率.隨著維數增大,Aet 系列特征的識別準確率波動幅度也在增大,Bf 系列、Cus系列、Fre 系列、Run 系列、Us 系列、Rev 系列和Re 系列特征的識別準確率隨著維數增大而提高,Dft系列、Nt 系列特征識別準確率與維數的關系不明顯,Rt 系列特征的識別準確率隨著維數增大呈現出下降趨勢.從實驗數據來看,基于隨機性測試的密文特征維數與其識別準確率并沒有必然的關系.不同密碼體制加密的密文其隨機性存在差異,那么如果隨機性測試可以反映出這種差異,其對應密文特征的識別準確率就會高.而提取密文特征時密文分塊數、密文數據量顯然對于隨機性測試返回值的準確性(即反映密文隨機性水平的能力)有一定影響,這種影響既可能是正向的也可能是反向的,其具體的作用機理有待進一步驗證.

在對各密文特征在具體識別場景中的識別性能時,也發現部分特征的識別成功率與所識別的密碼體制存在明顯的相關性關系.如表7,Bf 系列特征(表中選取Bf128)對于3DES、IDEA 的區分,Us 系列特征(表中選取Us8)對于Camellia 的區分,Fre 系列特征(表中選取Fre256)對于3DES 的區分均要優于它們在其它識別場景中的表現.這幾類特征對于某幾類密碼具有較高的識別率,表明部分密碼體制加密密文確實存在一定的隨機性差異,也說明了開展密碼體制識別研究的可行性.

表7 部分密文特征的具體識別結果Table 7 Recognition results of part features in different situations(%)

5.2.3 與現有結果對比

為驗證基于隨機性測試的密文特征有效性,本文選擇了6 種公開文獻中提出的密文特征,并在相同實驗條件下開展了密碼體制識別實驗.對比實驗選擇的特征分為兩類:(1)基于比特熵的特征;(2)基于比特串概率的特征.

由于本文所提出的54 種基于隨機性測試的密文特征識別性能差異較大,受篇幅所限,在表6 中識別性能相對較低的密文特征就不再與公開文獻中的特征做對比.在表8 中,我們只選取基于隨機性測試的6 種密文特征與其它已有的6 種密文特征做對比.可以發現,基于隨機性測試的6 種特征雖然在識別準確率并不占優勢,但是其特征維數通常較低.例如Nt20 特征的識別準確率與F_1024 的識別準確率相差5% 左右,但是Nt20 特征的維數僅為后者的1/50,這也顯示出Nt20 特征具有數據存儲量小的優勢,對于提高大批量密數據的快速識別能力有一定的現實意義.

表8 部分基于隨機性測試的密文特征與其它密文特征識別結果對比Table 8 NT series features and other features’ recognition results

5.2.4 實驗結果的假設檢驗

在上述基于機器學習的密碼體制識別方案中,分類實驗將在同等條件下運行分類算法十次所得結果的平均值作為分類的最終結果.為驗證分類方法的準確性,本文采用均值檢驗法獨立兩樣本T-檢驗[23]對各實驗結果進行檢驗.即:兩組不同特征的識別準確率數據,檢驗一組總體均值是否大于對照組總體均值,這里假定兩個總體獨立地服從正態分布.相應的假設檢驗問題為:H0:μ1=μ2?H1:μ1>μ2.

將上述實驗中十折的每一折數據記錄下來并作為一組數據,同時生成一組以為均值的隨機數數據.設置顯著性水平為0.01,檢測兩組數據的均值是否相等,驗證實驗數據的真實性.經檢驗,在顯著性水平為0.01 的情況下,本文實驗中涉及的所有數據的假設檢驗結果均符合要求.

6 總結與展望

本文在已知密文條件下,以AES、DES、3DES、IDEA、Blowfish 和Camellia 等六類典型分組密碼為識別分析對象,通過改變隨機性測試算法的提取方式與參數設置,提出了一系列分組密碼算法識別的新特征.以上述所提取的特征為分類依據,并在OpenSLL 密碼庫、VS2012 以及R 語言環境下進行了實驗仿真.實驗表明,基于隨機性測試的密文特征能夠以較高的識別準確率完成明密文識別和密碼體制工作模式的識別.對于難度較高的分組密碼體制識別,本文提出的54 種特征絕大多數也具有一定的識別性能,部分特征的識別性能接近或達到了目前已有的密文特征的水平.與現有的多數密文特征比較,基于隨機性測試的密文特征具有更低的維數.此外,通過比較實驗數據,發現一些密文特征在不同識別場景下的識別準確率與密碼體制存在一定的相關性,即對于某幾類密碼體制具有較高的識別準確率.基于隨機性測試的密文特征,在密碼體制識別中具有一定的有效性,因此作為改進密文特征提取的一個新思路值得進一步研究探索.

本文的實驗對象包含的密碼體制種類有限,基于隨機性測試的密文特征在密碼體制識別中的適用性及其識別效果也需要結合密碼學中的相關理論做出嚴謹的解釋.同時對于隨機化密鑰設置和CBC 模式下的分組密碼體制識別也需要進一步的研究探索.后續工作中,將針對更多識別情形下,基于隨機性測試的密文特征的提取方法,進一步改進識別分類器的算法以提高密碼體制識別效率.