鄭明輝,喬譯萱,朱小強,陳 珩
(1.湖北民族大學 智能科學與工程學院,湖北 恩施 445000;2.四川大學 網(wǎng)絡空間安全學院,四川 成都 610065)
在實際的通信過程中,數(shù)據(jù)保密性和數(shù)據(jù)完整性是傳輸數(shù)據(jù)的基本安全需求。密碼雜湊算法作為基礎的密碼算法之一,主要功能是提供數(shù)據(jù)的完整性檢驗,即數(shù)據(jù)經(jīng)過信道傳輸和存儲過程未被未授權(quán)方修改。密碼雜湊算法的實質(zhì)是將任意長度的消息序列映射成固定長度的輸出值(也稱為雜湊值)。并且無法從雜湊值反推出原本的消息序列,稱為雜湊函數(shù)的單向性?;谠撎匦?,雜湊值可以構(gòu)造“數(shù)據(jù)指紋”來進行數(shù)據(jù)的完整性檢驗,應用于身份認證、密鑰推導、消息認證碼、區(qū)塊鏈等場景。典型的密碼雜湊算法包括MD5、SHA1、SHA2、SM3等。其中,SM3算法[1]是由國家商用密碼管理辦公室于2010年公布的商用密碼標準,2012年成為行業(yè)標準,并于2016年成為國家標準,2018年正式成為ISO/IEC國際標準[2]。北京大學密碼學研究組開發(fā)維護的密碼算法工具包OpenSSL分支GmSSL支持SM3算法[3],并在之后的正式版本中添加了SM3算法的實現(xiàn)[4]。
Merkle-Damgard(記作MD)結(jié)構(gòu)[5-6]是密碼雜湊算法的經(jīng)典迭代結(jié)構(gòu),基于該結(jié)構(gòu)所構(gòu)造的雜湊函數(shù),如果壓縮函數(shù)具有抗碰撞性,則該函數(shù)也具有抗碰撞性。SM3算法作為MD結(jié)構(gòu)的典型代表,將任意長度的數(shù)據(jù)輸入壓縮成256 bit的輸出,能夠有效抵御窮舉攻擊,同時采用消息雙字介入、P置換等方法構(gòu)造具有更高復雜性的輪函數(shù),使得對SM3算法構(gòu)造原像攻擊是比較困難的[7]。安全性方面,目前針對MD5、SHA-1、RIPEMD、HAVAL等雜湊函數(shù)已找到快速碰撞的方法[8],同時在碰撞攻擊、區(qū)分器攻擊、原像攻擊方式下,對SM3 算法的攻擊難度相比其他傳統(tǒng)算法更高[9],能夠在具有高安全性需求的應用場景下進行數(shù)據(jù)傳遞。
然而,由于MD結(jié)構(gòu)是串行結(jié)構(gòu),在效率上很難突破,同時易遭受消息擴展攻擊及二次碰撞攻擊[10],所以研究人員開始將目光投向雜湊算法的迭代結(jié)構(gòu)。徐勁松等[11]提出基于并行擴展算法的雜湊函數(shù),提升了算法安全強度,但不適合短消息的處理。Yang等[12]針對雜湊函數(shù)并行迭代結(jié)構(gòu)的局部碰撞問題提出基于混沌映射的壓縮函數(shù),增強了算法的抗碰撞能力和運算效率,但由于基于格的并行迭代結(jié)構(gòu),導致運算開銷沒有顯著降低。Halder等[13]利用2D-CA技術(shù)構(gòu)建雜湊函數(shù)的迭代結(jié)構(gòu),使算法的隨機性和擴散性有所提升,但算法的輪函數(shù)定義為35輪,運算復雜性不高。Liu等[14]構(gòu)造具有更高隨機性的3D-ECM來充當海綿函數(shù),同時輸出指定長度的雜湊值,減輕了側(cè)信道攻擊的威脅,但由于構(gòu)造過程中增加字符轉(zhuǎn)換操作,無法保證運算效率的提升。Todorova等[15]提出基于Zaslavsky混沌映射的雜湊算法,該算法具有更強的抗碰撞性,但由于迭代過程中使用較多異或操作,導致算法復雜性不高。王鎮(zhèn)道等[16]將MD5算法迭代過程的64步運算設計為32級的流水線,在保持串行運算的前提下提高了算法的運算速度,但未曾考慮算法安全性。巫光福等[17]以MD5算法為例構(gòu)造基于線性分組碼的密碼雜湊算法,提高了密碼雜湊算法輸出值的隨機性,但產(chǎn)生的雜湊值為128 bit,抗窮舉攻擊能力較弱。
綜上所述,目前針對密碼雜湊算法迭代結(jié)構(gòu)的研究方法主要包含并行計算和混沌映射。其中:并行計算達到了提高數(shù)據(jù)運算效率,但與串行結(jié)構(gòu)相比增大了計算復雜度;混沌映射則是通過提升初值敏感度來增強雜湊算法的抗碰撞性,但未考慮優(yōu)化雜湊值的比特混亂度,雜湊值混亂度的提升也是算法安全性的重要評估條件之一。針對構(gòu)建具有更高隨機性的密碼雜湊算法,本文提出基于糾錯碼的SM3改進算法的設計方案,選用糾錯能力更強的線性分組碼并計算對應的生成矩陣;在生成的有效碼字中選擇8個最優(yōu)碼字串聯(lián)賦值給初始寄存器,同時與每個512 bit消息分組進行迭代壓縮運算,所產(chǎn)生的雜湊值為256 bit,若采用蠻力攻擊,則需要執(zhí)行2256數(shù)量級的操作,保證算法的安全性。實驗結(jié)果表明,本文算法滿足雪崩效應,并在運算效率相近的情況下,產(chǎn)生的雜湊值隨機性更高,同時算法內(nèi)存消耗更少。
在數(shù)字通信過程中不可避免發(fā)生差錯,對于接收到的數(shù)據(jù)序列,糾錯碼的主要作用是在存儲設備及通信中進行糾錯和檢錯,被廣泛用于密碼學和通信系統(tǒng)中。糾錯碼主要分為分組碼和卷積碼。下面重點介紹分組碼[18]及其相關(guān)知識[19-21]。
定義1(線性分組碼)有限域GFq上 的一個(n,k)線性分組碼C是GFqn上的k維線性子空間,其中,n為分組碼的碼長,碼C中向量稱作碼字,k為信息碼元長度,k/n為 碼的信息率,n-k為 碼C的校驗位或者監(jiān)督位。
定義2(漢明距離)兩個不同碼字之間的漢明距離定義為兩個序列之間對應不同的位數(shù),記作d。
式中,⊕為異或運算。
碼字間的距離表示碼字之間差異程度的大小。當存在干擾時,距離越大,一個碼字變成另一個碼字的可能性越小。
定義3(最小漢明距離)碼C的最小漢明距離dmin定義為所有任意兩個碼字漢明距離的最小值。對于線性分組碼,記為(n,k,dmin)。
定義4(生成矩陣)對于(n,k,d)線性分組碼,有下列關(guān)系式:
式中:m為k維矢量;k×n的矩陣G稱為線性分組碼C的生成矩陣,G的行向量構(gòu)成碼C的一組基。
對于給定信息碼元長度k、碼長n的 線性分組碼C,其生成矩陣不唯一,并且可以通過初等行變換相互進行轉(zhuǎn)換。其中,無論生成矩陣如何初等變換,碼字都是唯一確定的,任意生成矩陣可產(chǎn)生相同的 2k個碼字。
SM3算法是基于分組迭代的國際密碼雜湊算法,該算法比其他國際雜湊算法標準設計更復雜,具體表現(xiàn)在Merkle Damgard迭代結(jié)構(gòu)中每一輪壓縮都使用2個消息字,以及消息拓展過程中每一輪都使用5個消息字,并且將不同群運算結(jié)合,使明文消息非線性迅速擴散。下面給出基于糾錯碼的SM3改進算法具體構(gòu)造過程。
單個消息分組處理過程主要利用糾錯碼構(gòu)建初始常量并將其嵌入到初始緩存器中,再進行64步迭代操作。具體分為初始常量構(gòu)造、消息預處理、消息擴展、迭代壓縮、雜湊值輸出5個步驟。其中,輸入是最大長度為264-1 bit的消息,輸出是長度為256 bit的消息雜湊值,處理單元是512 bit消息分組。
在構(gòu)造基于糾錯碼的SM3算法過程中,需要選擇合適的線性分組碼C,一個最優(yōu) (n,k,dmin)分 組碼C必須滿足以下條件。
1)確定n和k,使dmin盡量最大化,則構(gòu)造出的碼C可以提高糾錯能力。
2)確定n和dmin,使k盡量最大化,則構(gòu)造出的碼C可以提高傳輸速率。
3)確定k和dmin,使n盡 量最小化,則構(gòu)造出的碼C可以提高傳輸速率。
綜上所述,構(gòu)造性能良好的糾錯碼,需要考慮信息k、碼長n、最小漢明距離dmin這3個參數(shù)的相互制約問題,達到傳輸效率及糾錯能力的平衡。
根據(jù)可變擬陣搜索算法和擬陣聯(lián)接度的定義[22],可以構(gòu)建一類最優(yōu)的二進制線性 (n,k,dmin)碼及它的生成矩陣Ga×b[23]。因為本文所構(gòu)建的加法常數(shù)表需8個32 bit串聯(lián)而成,所以選擇構(gòu)建SM3的線性分組碼為(32,6,16),并求得該線性分組碼的生成矩陣G6×32。為了使加法常數(shù)能達到隨機化和無規(guī)律性最大化的效果,需要有效降低比特之間的規(guī)律性,經(jīng)過測試,選擇將生成矩陣G6×32進行循環(huán)左移6位,最終產(chǎn)生的雜湊值的熵值達到預期設計要求,即雜湊算法的隨機性更高。生成碼字集合U={u1,u2,···,u2k},k=6。
基于SM3算法的初始常量及迭代過程的特征,應選擇8個碼字串聯(lián)來構(gòu)建本文算法的初始常量,其中初始常量集合B0以下列方式選?。?/p>
重新構(gòu)造的初始常量應滿足兩個要求:
1)初始常量二進制表示中,1、0的數(shù)量比趨近于1。
2)初始常量二進制表示中,最長1游程小于10,最長0游程小于8。
假設輸入消息m的 長度為lbit,首先,在消息的末尾先添加比特“1”;再在后面添加k個“0”,k滿足l+1+k≡488 mod 512;再添加64 bit的比特串來表示輸入消息的長度l,得到填充后的消息m′,長度為512×nbit;最后,將消息m′按512 bit進行分組:
式中,n=(l+k+65)/512。
1)將m′i分為16個32 bit的比特串W0,W1,···,W15。
2)W16,W17,···,W67以下列規(guī)則進行擴展:
式中,Wj為 消息擴展的第j個字,< <<k表示循環(huán)左移k比特運算,固定公式P1(·)定義為:
3)W16,W17,···,W67以下列規(guī)則進行擴展:
式中,W′j為消息擴展的第j+69個字。
將初始常量集合B0中8個碼字分別賦值于寄存器A、B、C、D、E、F、G、H中,對第i個消息分組m′i以下列方式迭代:
式中,CF壓縮函數(shù)由64步迭代運算組成,Bi為第i次迭代輸入的集合。將Bi賦值于A、B、C、D、E、F、G、H作為初始寄存器,同時添加中間變量S S1、S S2、TT1、TT2進行左向賦值操作,具體過程描述如式(9)~(12):
式中,←表示左向賦值運算符,Tj為 32 bit常量,F(xiàn)Fj(·)、GGj(·)為 定義好的布爾函數(shù)[1],0 ≤j≤63。
將更新后的中間變量TT1、TT2 與寄存器A、B、C、D、E、F、G、H進行狀態(tài)更新,過程描述如下:
1)將初始寄存器A、C、E、G分別賦值于寄存器B、D、F、H,然后將中間變量TT1賦 值于寄存器A。
2)對中間變量TT2 進行公式運算后賦值于E,具體運算過程如下:
式中,固定公式P0(·)定義為:
3)將更新后的寄存器B、F進行循環(huán)左移操作后賦值于寄存器C、G,描述如下:
每輪迭代的輸入都是上一輪迭代的輸出再與512 bit的分組消息進行運算的結(jié)果。
最終所有消息分組處理完畢之后,最后一個512 bit的輸出即為算法雜湊值。
密碼雜湊算法的安全水平是由它的輸出長度決定的[24],本文所構(gòu)造的雜湊函數(shù)輸出長度為512 bit,與128 bit的輸出相比更能抵抗原像攻擊、第二原像攻擊和碰撞攻擊。
第2節(jié)所構(gòu)造的密碼雜湊函數(shù)是針對SM3算法的改進算法,下面從雪崩效應、信息熵方面進行本文算法的安全性分析,同時通過仿真實驗進行算法運算效率和內(nèi)存損耗性能分析與討論。
3.1.1 雪崩效應分析
密碼學中約定密碼雜湊算法應滿足雪崩效應,即輸入消息微小的改變會引起雜湊值至少一半以上的位數(shù)發(fā)生變化,以達到更好的混淆效果,利用式(17)~(19)對本文改進算法的雪崩效應進行穩(wěn)定性評估。
式(17)~(19)中,Bi為第i次測試的雜湊值改變的比特數(shù),P為平均雪崩系數(shù),N為測試的總次數(shù),n為雜湊值比特數(shù),B為平均變化比特數(shù)。理想狀態(tài)下P為50%,表明密碼雜湊算法具有良好的雪崩效應,均方差 ΔP數(shù)值越小,則密碼雜湊算法的穩(wěn)定性越好[25]。
為了進一步驗證改進算法性能,選擇傳統(tǒng)SHA-256算法和SM3算法,以及改進的MD5算法[17](記為Wu-MD5算法)進行雪崩效應測試。隨機選擇明文消息并計算生成的雜湊值,任意改變消息中的1 bit,同時計算新生成的雜湊值。由于雜湊值長度不同,所以僅針對雪崩系數(shù)P及均方差 ΔP進行數(shù)值比較,結(jié)果如表1所示。值得說明的是,雪崩效應僅是雜湊算法擴散效應的指標之一,其結(jié)果無法直觀地進行4種算法混淆性的優(yōu)劣比較,僅能夠進行雪崩效應的穩(wěn)定性評估。
表1 不同測試次數(shù)下4種算法的雪崩特性統(tǒng)計Tab.1 Avalanche characteristics statistics of four algorithms under different test times
表1結(jié)果表明:在測試總次數(shù)N分別為1 000、5 000、10 000和50 000的情況下,本文算法與其他3種算法的雪崩系數(shù)P均接近50%,達到了雜湊函數(shù)雪崩效應的理想狀態(tài),說明本文算法擁有良好的混淆和擴散性;同時,本文算法的均方差 ΔP的數(shù)值偏小,充分說明本文算法具有穩(wěn)定的雪崩效應。
3.1.2 信息熵分析
熵反映了信息源的平均不確定性,在密碼學領域內(nèi),信息熵也是用于衡量信息序列隨機性的一項重要指標。信息序列的隨機性越大,熵值越大;信息序列的隨機性越小,熵值越小[26]。一般熵值的大小也與攻擊者分析雜湊算法的規(guī)律性所需要的時間成正比。利用熵值的大小來度量糾錯碼構(gòu)建的改進密碼雜湊算法的安全性。熵的計算公式為:
式中,H(x)為 消息x的 信息熵,p(xi)為 消息中xi出現(xiàn)的概率。
針對第2節(jié)中生成矩陣G6×32分別進行循環(huán)左移5、6、7位操作,輸入長度為20~500 byte的樣本數(shù)據(jù),計算在輸入數(shù)據(jù)相同時的雜湊值信息熵,如圖1所示。由圖1可以看出,循環(huán)左移6位時信息熵數(shù)值更高,相對于循環(huán)左移5、7位穩(wěn)定性更好,而循環(huán)左移操作的目的是增大比特之間的無規(guī)律性,說明構(gòu)造的加法常數(shù)值符合算法設計最初指標,即達到隨機性和無規(guī)律性最大化,提升了雜湊值隨機性。
圖1 本文算法中不同循環(huán)左移位數(shù)的信息熵比較Fig.1 Information entropy comparison of different cyclic left shift numbers in the proposed algorithm
為了評估本文算法的雜湊值隨機性,在明文樣本相同的情況下,選擇典型的密碼雜湊算法進行雜湊值的信息熵對比實驗,具體標準為:1)本文算法是基于SM3算法的改進雜湊算法,所以選擇SM3算法進行對比;2)在雜湊值長度都為256 bit的情況下,選擇SHA-256算法進行對比。不同算法的雜湊值信息熵對比實驗結(jié)果如表2所示。
表2 本文算法、SM3算法及SHA-256算法的雜湊值信息熵比較Tab.2 Comparison of information entropy between the proposed algorithm, SM3 algorithm and SHA-256 algorithm
表2表明:在迭代結(jié)構(gòu)相似的情況下,本文算法因為選擇糾錯更強的最優(yōu)碼 (n,k,dmin)來構(gòu)建加法常數(shù)表,雜湊值的熵值相對于 SM3算法有所增加;在雜湊值長度相同的情況下,由于本文算法迭代結(jié)構(gòu)包含消息雙字介入等方法,使得輪函數(shù)復雜性提升,消息能夠快速擴散,從而導致最終生成雜湊值的信息熵值更高,隨機性更強。以上結(jié)果表明,本文所構(gòu)造的SM3改進算法利用糾錯碼技術(shù)有效平衡了雜湊值長度和迭代結(jié)構(gòu)兩個方面,使得算法雜湊值隨機性有所提升,能夠更好地隱藏明文消息和雜湊值之間的關(guān)聯(lián)性。
一般來說,密碼雜湊算法的運算效率及內(nèi)存損耗是需要研究人員考慮的重要方面,在配置為Intel Core i5-9400 2.90 GHz、16 GB RAM的計算機上,進行改進算法與傳統(tǒng)SM3算法的時間效率及內(nèi)存損耗的對比實驗,并進行分析。
3.2.1 運算效率分析
利用 Java 1.8.0_291進行算法運算效率測試。針對不同明文消息長度的輸入,分別選擇本文算法與SM3算法進行效率分析,如圖2所示。
圖2 本文算法與SM3算法時間復雜度比較Fig.2 Comparison of time complexity between the proposed algorithm and SM3 algorithm
由于迭代結(jié)構(gòu)的串行特性,明文消息長度和運行時間成正比,圖2結(jié)果表明,本文算法可以支持算法快速運算,在輸入明文消息長度為40~1 080 byte的條件下,1 s內(nèi)可以進行450~2 000次運算,與SM3算法的運算效率基本一致。
3.2.2 內(nèi)存消耗分析
JProfiler作為商業(yè)授權(quán)的Java性能剖析工具,具有對被分析對象影響較小、針對內(nèi)存(memory)分析功能強大等特點,專用于分析Java SE、Java EE應用程序。利用JProfiler分析工具,針對不同長度的明文輸入,選用30個明文樣本集,對本文改進算法及SM3算法分別進行相同明文輸入的內(nèi)存損耗測試對比,結(jié)果如圖3所示。
圖3 本文算法與SM3算法內(nèi)存損耗比較Fig.3 Comparison of memory loss between the proposed algorithm and SM3 algorithm
由圖3可知:本文算法的內(nèi)存損耗并不高,在明文輸入長度為100~3 000 byte的條件下,隨著消息長度的增加,計算量增大,導致內(nèi)存損耗呈線性增長趨勢;同時,由于本文利用糾錯碼來構(gòu)造加法常數(shù)表,導致在消息長度相同的情況下,本文算法相比于SM3算法內(nèi)存損耗降低0.01~0.07 MB,實現(xiàn)了性能優(yōu)化。
基于糾錯碼的SM3算法是在傳統(tǒng)SM3算法的基礎上進行的改進。改進后的SM3算法不僅具有較強的雪崩效應,且具有更強的隨機性,使攻擊者更難找到其中規(guī)律。上述算法效率及內(nèi)存損耗實驗表明,本文改進算法在效率相同的情況下內(nèi)存損耗有所下降,為高效率、低內(nèi)存需求的應用場景提供技術(shù)參考。
為了提高雜湊值的隨機性,本文利用糾錯碼可以在數(shù)字通信過程中提高可靠度的特性,提出一種對SM3算法的改進方案。該方案選擇擬陣理論構(gòu)建的線性分組碼(32,6,16),通過生成矩陣G6×32計算有效碼字,同時利用周期性原則選擇8個碼字構(gòu)建初始常量值,并嵌入到迭代結(jié)構(gòu)中進行64輪運算;從信息熵值和雪崩效應兩個角度進行雜湊值穩(wěn)定性和隨機性評估,同時測試本文算法在運算效率和內(nèi)存損耗的全局性能并進行分析。實驗結(jié)果表明,本文算法具有理想雪崩效應的特性,生成的雜湊值相比其他密碼雜湊算法混亂度有明顯提高,使攻擊者更難逆推出明文消息,具備更高的算法安全性。另外,本文算法在保留傳統(tǒng)密碼雜湊算法的串行迭代結(jié)構(gòu)的前提下,能夠在1 s內(nèi)進行450~2 000次高速運算,且內(nèi)存損耗與SM3算法相比降低0.01~0.07 MB,為信息安全領域的應用開發(fā)提供理論參考。在未來的研究工作中,將重點研究密碼雜湊算法的迭代結(jié)構(gòu),嘗試采用并行結(jié)構(gòu)進行數(shù)據(jù)運算效率的優(yōu)化,并且在區(qū)塊鏈技術(shù)的底層架構(gòu)來驗證優(yōu)化后算法的適用性。