后量子時代區塊鏈中哈希函數比較研究

劉 昂 文 津 許盛偉 陳 穎 秦曉宏 藍浩書

1(北京電子科技學院網絡信息化管理處 北京 100070)

2(北京郵電大學網絡空間安全學院 北京 100876)

3(北京電子科技學院網絡空間安全系 北京 100070)

4(北京電子科技學院信息安全研究所 北京 100070)

5(北京電子科技學院密碼科學與技術系 北京 100070)

2008年,Nakamoto[1](中本聰)首次引出了區塊鏈的概念.此后,區塊鏈技術得到全世界學者的深入研究,并在各行各業得到廣泛應用.

我國非常重視區塊鏈的發展,2016年,國務院首次將區塊鏈技術作為戰略性前沿技術列入《“十三五”國家信息化規劃》[2];2019年10月24日,十九屆中共中央政治局就區塊鏈技術發展現狀和趨勢進行第十八次集體學習,強調“把區塊鏈作為核心技術自主創新重要突破口,加快推動區塊鏈技術和產業創新發展”[3],區塊鏈已被提升到國家戰略高度;2021年兩會后,區塊鏈作為數字經濟7個重點領域被寫入十四五規劃綱要[4],表明2021—2025年區塊鏈已被列入政府重點工作內容.

區塊鏈是一種鏈式數據結構[5],以區塊(block)的形式存儲數據,區塊按照生成時間順序組成1條鏈,1個區塊中存在多筆交易信息,多個區塊通過哈希值前后連接,形成一個“區塊鏈”.

區塊鏈從本質上講是一個共享信息數據庫[6],存儲于其中的數據或信息具有“不可偽造”“不可篡改”“全程留痕”“可以追溯”“公開透明”“集體維護”等特征.基于這些特征,區塊鏈技術奠定了堅實的“信任”基礎,創造了可靠的“合作”機制,具有廣闊的應用前景.

區塊鏈在網絡安全中扮演著至關重要的角色[7],可以降低可能導致整個網絡故障的網絡攻擊風險.然而量子計算機以其強大的并行計算能力,可以輕松破解經典計算機難以破解的數學困難問題[8],從而對現代密碼技術尤其是公鑰密碼構成安全威脅.量子計算對傳統密碼學的影響極大程度地威脅了區塊鏈系統的安全穩定發展.Grover量子算法在搜索上較經典搜索算法能提供2次加速,從而能加速對哈希函數的前像碰撞攻擊[9].量子計算機的大規模應用將對哈希函數的安全性造成巨大影響[10],進而給網絡安全帶來巨大隱患[11-12],所以研究具有抗量子性的哈希函數意義重大.

本文將首先研究量子計算機對區塊鏈中的哈希函數的攻擊形式,然后開展區塊鏈中哈希函數的抗量子安全性研究,對當前區塊鏈中的哈希函數的設計進行歸納和總結,最后對后量子時代區塊鏈中的哈希函數的設計提出有益建議并對前景進行了展望.

1 哈希函數及其面臨的量子計算攻擊威脅

1.1 哈希函數定義及其性質

作為區塊鏈的起源性技術,哈希函數在區塊鏈的數據完整性保護上發揮著不可替代的作用,哈希函數的抗第二原像性(弱抗碰撞性)直接決定了區塊鏈的不可篡改性[13].

哈希函數又稱散列函數,是密碼學上一類將任意長度的消息映射到某一固定長度的哈希值的單向函數,它滿足以下3個基本性質[14]:

1) 抗原像性.對任意給定的哈希值h,尋找1個消息x,使得H(x)=h在計算上不可行.

2) 弱抗碰撞性.給定消息x,其哈希值h=H(x),尋找1個不同于消息x的消息x′,滿足h=H(x′)在計算上不可行.

3) 強抗碰撞性.尋找2個不同的消息x和x′,使得H(x)=H(x′)在計算上不可行.

1953年,IBM公司提出,為提高對數據庫文件的檢索效率,為每個文件生成1個電子指紋,搜索文件時直接搜索其電子指紋就能將文件搜索出來,簡單高效.1981年,為提升數字簽名RSA的安全性,避免偽造攻擊,防止數據被篡改,Davis和Price提出密碼哈希函數的概念[15].數據被篡改后電子指紋發生變化,從而發現篡改行為,進而保證數字簽名的安全性.對文件進行數字簽名時,僅對其摘要值而非原文件進行簽名即可,提升數字簽名效率.摘要值長度從128b,160b,192b,256b,384b,…,512b不等,高效便捷.當前主流的基于公鑰的數字簽名,即運用哈希函數對文件生成定長的摘要值后進行數字簽名.

1.2 針對哈希函數的量子計算攻擊

哈希函數在區塊鏈系統中應用廣泛,以比特幣平臺為例,在交易中使用哈希函數對每一筆交易生成摘要值后作數字簽名;在鏈上數據的完整性保護上,使用哈希函數及基于哈希函數的Merkle樹結構作完整性校驗,并使用哈希值完成前后區塊的連接;在工作量證明(proof of work, PoW)共識機制中使用尋找哈希函數特定輸出對應的輸入作為數學難題來為礦工分配新區塊的記賬權.

以Grover算法為代表的量子算法能有效實施針對經典哈希函數的量子計算攻擊,攻擊形式主要是原像攻擊和第二原像攻擊.

1.2.1 挖礦攻擊

原像攻擊:在密碼學中,哈希函數上的原像攻擊用于尋找有著特定哈希值的消息,1個哈希函數應該抵御對其原像的攻擊.即給定y,找到1個原像x,使得H(x)=y.在比特幣中,礦工們通過尋找滿足哈希值為特定值的NONCE來獲得新區塊記賬權和挖礦獎勵(新比特幣的產生).比特幣挖礦就是發現新區塊、驗證待確認交易并將其添加到比特幣區塊鏈的過程.量子攻擊者使用Grover算法加速搜索,能很快找到原像,從而在挖礦游戲中取得壓倒性優勢,甚至壟斷記賬權,從而大大破壞比特幣系統的去中心化程度,這就是針對PoW共識機制的挖礦攻擊.該攻擊將導致51%攻擊,即擁有量子計算機的礦工能憑借壓倒性的算力優勢將壟斷新區塊的生成,破壞區塊鏈的去中心化[16].

為提高對原像攻擊的抗性,雙重哈希是一種可以抵御在某種情況下攻擊者已經破解了首個哈希的好策略.比特幣系統使用雙重哈希SHA-256,這是一種2000年代減緩哈希破解的常見手段[17].然而量子攻擊者使用的是暴力破解手段,雙重哈希結構并未改變像(輸出)的空間大小,因而不能有效抵抗量子敵手的原像攻擊.

1.2.2 偽造攻擊

第二原像攻擊:攻擊者在哈希值維持不變的前提條件下找到假消息m′替換合法消息m,即尋找m′使得H(m′)=H(m).在比特幣為代表的區塊鏈系統中,攻擊者通過尋找哈希沖突,對區塊鏈上的數據實施第二原像攻擊,使用非法數據篡改合法交易數據,并且由于哈希值維持不變,也不會被校驗發現.這就是針對鏈上數據的偽造(篡改)攻擊.

哈希函數是把任意長度的輸入(又叫作預映射(pre-image))通過哈希算法變換成固定長度的哈希值輸出,因此這種轉換是一種壓縮映射,即哈希值的空間通常遠小于輸入的空間,不同的輸入可能會哈希成相同的輸出,因而從映射角度看,哈希函數顯然是多對1映射,因此理論上必然存在碰撞,這也正是量子敵手成功實施第二原像攻擊的基礎,但是并非所有的消息都有第二原像.

近年來,大量研究量子計算機的機構和學者利用量子力學現象解決常規計算機難以解決的數學困難性問題.2019年,Google團隊就在1臺53b的量子計算機上僅用200s便完成了在超級計算機上需要1萬年的計算[18],顯示了量子計算超強的運算速度與處理能力,也透露出量子技術對區塊鏈的潛在威脅.有研究顯示,Bitcoin,Ethereum,Dash,Litecoin,Zcash,Monero,Ripple,NXT,Byteball,Bytecoin,IOTA等區塊鏈均已受到量子威脅影響[19].而哈希函數在區塊鏈中扮演重要角色,被王小云院士視為區塊鏈的起源性技術.哈希函數在區塊鏈中具有加密數據、驗證數據、身份認證等重要功能,區塊鏈數據的不可篡改等特性就是哈希函數的抗碰撞性確保的.如果大型量子計算機被完全研發出來,它們將對當前的經典密碼算法尤其公鑰密碼造成毀滅性的災難,許多協議、算法將不再是安全的[20].

量子敵手可以使用Grover算法通過搜索哈希沖突,在不改變哈希值的條件下篡改某一筆交易而不被發現.Grover的搜索算法[22]允許在計算逆哈希函數時實現2次加速效果,這種攻擊將允許攻擊者篡改鏈上的合法交易,破壞區塊鏈上的數據完整性.例如,文獻[23]使用Grover算法查找哈希函數中的沖突,得出哈希函數必須輸出3n位才能提供n位安全級別的結論.這樣的結論意味著許多當前的哈希函數在后量子時代將無效,而其他像SHA-2或SHA-3這樣的函數將不得不增加其輸出大小.

以使用Merkle樹的比特幣為例,量子敵手可以通過使用Grover算法構造數據,使得構造出的數據與真實數據通過同一個哈希函數計算出的值相同,以達到篡改數據并維持哈希值不變從而不被發現的目的.例如在圖1的Merkle樹中,敵手構造的數據Tx′與原始數據Tx通過同一哈希函數計算出的哈希值相同,即H(Tx)=H(Tx′),從而用Tx′替換原始數據Tx,其哈希值及Merkle根將維持不變,以實現前像碰撞攻擊.

圖1 前像碰撞攻擊

2 哈希函數對比分析

本文對5種哈希算法進行了對比分析,其輸入、輸出、優點與缺點如表1所示:

表1 哈希算法總結

2.1 傳統經典哈希算法

自1953年Hans Peter Luhn提出哈希函數[24]以來,1970年哈希函數蓬勃發展,2001年美國國家標準與技術研究院(National Institute of Standards and Technology, NIST)發布SHA-256算法[25],2008年中本聰[1]將哈希函數應用到區塊鏈中,并成為區塊鏈技術不可撼動的基石.

SHA-256算法屬于SHA-2系列,在2008年被公認為最安全最先進的算法之一,中本聰提出的比特幣除了生成地址中有一個環節使用了REPID-160算法,其他需要作哈希運算的地方均使用SHA-256,SHA-256是最早運用于區塊鏈中的哈希函數之一.其他的傳統經典哈希算法Ethash,Scrypt,RIPEMD160等,下面具體介紹SHA-256.

SHA-256[26]是一個Merkle-Damgard結構的迭代哈希函數,如圖2所示,計算流程是一個迭代計算的過程,當最后一個消息塊處理完畢以后,最終的輸出值就是所輸入的原始消息的SHA-256值.

圖2 SHA-256算法流程

SHA-256通過將不定長的消息和文件等數據轉換為固定長度為256b且難以區分的字符串來保護數據不被截取或篡改.相同的輸入依據SHA-256計算的值是唯一的,但當輸入有修改時,即使是很微小的修改得到的哈希結果也會完全不同.SHA-256算法的特點是易于檢查,較難偽造,具有很強的抗強碰撞的能力.以現在的計算機破解需要消耗極大的資源,因此無法獲得利益.但隨著量子計算機的發展,SHA-256的安全性也將受到影響.據文獻[19]顯示,SHA-256的前量子安全級別為256b,預估后量子安全級別為128b.

其他傳統經典哈希算法同樣受到量子計算機不同程度的影響,具體如表2所示:

表2 傳統經典哈希算法受量子計算機的影響情況

2.2 基于量子密鑰的Toeplitz哈希算法

2018年,Kiktenko等人[27]使用Toeplitz哈希計算認證標簽值,Toeplitz哈希計算簡單,且在信息理論上是安全的.

Toeplitz哈希是一類特殊的通用哈希函數[28],基于Toeplitz矩陣進行哈希值的計算[29].維數為n×m的Toeplitz矩陣通過向量矩陣乘法可以將長度為m的原始消息計算為長度為n的哈希結果.Toeplitz矩陣是在左右對角線上具有常數值的矩陣.這種特定結構減少了構造隨機矩陣時所需的隨機比特數.例如,當構造m×n對角常數矩陣時,所需的隨機比特數將從mn減少到m+n-1.

文獻[27]采用的方案中,如果通信雙方Alice和Bob共享一個其他人不知道的秘密私鑰Kaut,則可以對接收到的對方消息進行身份驗證.秘密私鑰生成的前提是雙方在會話開始時就有少量“種子”密鑰來認證對方的身份.一旦建立了私鑰,身份驗證過程則是:Alice向Bob發送1條消息,其中包含使用該密鑰生成的哈希標簽.在收到消息后,Bob計算其哈希標記.如果哈希標記一致,Bob可以確定該消息是從Alice發送的.哈希標簽的具體計算公式如下:

h(Mi)=TSMi⊕ri,

(1)

其中TS是由長度為lh+lM-1的字符串S生成的lh×lMToeplitz矩陣,ri是長度為lh的位串,⊕是按位異或,S和ri都是私有的,并且取自公共私鑰Kaut.那么竊聽者正確猜測已被修改消息的哈希標簽的概率不超過2-lh.如果傳輸了一系列消息,則可以在不影響安全性的情況下再次使用字符串S,而每次都必須重新生成字符串ri.私鑰以每條消息lh(單位為b)的速率被消耗.其中lh=40,lM=222.

如果一個裝有量子計算機的惡意方離線偽造數據庫.它將過去的一個交易記錄更改為自己的利益,并對同一塊中的其他交易的變體進行Grover搜索,以使其哈希保持不變,從而使偽造版本看起來合法.一旦搜索成功,它就會入侵所有或部分網絡節點,并用偽造的版本替換合法數據庫.然而,這種攻擊造成重大損害的可能性似乎很低,因為攻擊者需要同時攻擊至少1/3的節點才能改變共識.此外,由于與經典搜索算法相比,Grover算法只提供了2次加速,因此可以通過將塊哈希長度的約定增加到其安全非量子值的2倍來防止這種情況.

該哈希函數采用一次一密的加密方式,在信息理論上絕對安全[27],可以有效抵御量子攻擊,為實現可擴展的量子安全區塊鏈平臺開辟了可能性.私鑰生成前的“種子”密鑰認證了通信雙方的身份,為算法提供了更高的安全性,但是成本太高,無法大規模應用于實踐.通信只在兩方之間進行,第三方無法驗證,存在通信一方作惡的可能性,竊聽者也可以冒充2個授權用戶(Alice和Bob)中的任何一個,以獲得對機密數據和資源的未經授權的訪問.

2.3 基于QIQW的量子哈希算法

2021年,Abd El-Latif等人[7]提出了使用基于QIQW(quantum-inspired quantum walks)的量子哈希函數鏈接區塊鏈的塊.量子漫步可以描述為希爾伯特空間元素到概率分布集合的非線性映射.這種性質加上量子漫步對初始條件變化的高度敏感性,使離散量子漫步可以被視為離散時間和離散值混沌系統.離散量子漫步的基本組成部分是硬幣粒子、漫步空間、進化算子和1組可觀察量.在這種情況下,如果量子漫步在有N個頂點的圓上運行,步行者是一個運行在基數為#(H)=N的希爾伯特空間H中的量子系統.受控交替量子漫步(controlled alternating quantum walks, CAQW)是由二進制串m控制的2維單步量子漫步.文獻[7]中正是基于CAQW的混沌行為構建了量子哈希函數.

基于CAQW構建量子哈希函數(quantum hash functions, QHF)的步驟為:

2) 通過使用等式h=fix(Pi×108) mod 2g將概率矩陣P轉換為比特串,獲得二進制消息m的哈希值,其中哈希值的長度為N2×g(單位為b).

假設使用標準量子通信信道在發送方和接收方之間交換主密鑰參數(N,α,β,θ0,θ1,θ2).交換的密鑰參數在消息加密、解密和身份驗證過程都是需要的.

Alice和Bob通過防篡改的量子安全信道交換初始參數(N,α,β,θ0,θ1,θ2).數字設備的計算精度為10-16,用于構造哈希值和密鑰流的密鑰空間允許為1096,這提供了額外的通信安全層.因此,基于QIQW的量子哈希函數可以防止消息攻擊.

假設Bob收到交易信息后,Bob根據與Alice交換的初始密鑰參數(N,α,β,θ0,θ1,θ2)從S提取哈希碼hashA,從接收到的加密文本中提取哈希碼hashB.接下來,將hashA與hashB一起比對.若發現加密文本并非Alice所發,該筆交易被丟棄.因此,基于QIQW的量子哈希函數可以防止無消息攻擊.

當Eve冒充Alice并試圖與Bob通信時,Eve無法訪問初始參數(N,α,β,θ0,θ1,θ2)以操作QHF并向Bob發送未經授權的事務.Bob將通過身份驗證過程檢測到Eve的存在并丟棄此事務.同時,如果Eve冒充Bob并試圖與Alice通信,Eve無法訪問有關關鍵參數(調用QHF所需的參數)的信息違反交易數據的可能性.如前所述,QHF的巨大密鑰空間使得違反事務數據變得不切實際.此外,如果Eve成功獲得密碼文本及其嵌入的哈希值(即Eve成功猜測了N),Eve無法獲得受量子信道保護的完整密鑰參數,就無法訪問交易數據.因此,基于QIQW的量子哈希函數可以防止模擬攻擊.

基于QIQW的量子哈希函數可以抵御來自數字和量子計算機的可能攻擊[7],從而確保后量子時代物聯網設備之間的數據安全傳輸.為基于量子啟發模型設計區塊鏈技術打開大門,是本文目前較為推薦的哈希方案.

2.4 基于Hilbert變換的量子哈希算法

2021年,Wen等人[30]提出了一種基于Hilbert變換的量子哈希算法,并與量子SWAP測試和量子隱形傳態一起構造了一種具有后量子安全性的量子區塊鏈系統.其中的量子哈希算法具體構造如下:

給定一個經典量子函數ψ,它將1個n位0/1字符串映射到1個具有n個量子位的量子態.

ψ:{0,1}n→(H2)?s,

(2)

其中

(H2)?s=H2?…?H2=H2s

(3)

是由s個量子位的單個量子位狀態空間組成的2s維Hilbert空間中的單位向量.函數ψ也可以用狄拉克符號表示為ψ:ω→|ψ(ω)〉.

如果ψ滿足以下2點則為量子單向函數:

1) 容易進行正向計算.即存在1個量子算法可以滿足在多項式時間內計算任何輸入ω的輸出|ψ(ω)〉.

2) 根據給定的|ψ(ω)〉值無法計算出ω.即根據量子信息理論,無法從|ψ(ω)〉得到ω.

|ψ(ω)〉的性質:如果n?s,那么就不可能從給定的|ψ(ω)〉中獲得ω的值.

對于任意1對輸入ω和ω′,ω≠ω′,如果函數ψ的映射是ω→|ψ(ω)〉,則|ψ(ω)〉和|ψ(ω′)〉是δ-正交,即|〈ψ(ω)〉|ψ(ω′)〉|<δ,該函數稱為δ-resistance函數.

如果函數ψ:{0,1}n→(H2)?s同時是一個量子單向函數和δ-resistance函數,那么這個函數被稱為(n,s,δ)量子哈希函數.

根據輸入情況不同,將判定結果中測量結果、測量結果概率、判定結果、是否判定正確的統計如表3所示:

表3 不同輸入情況的判定結果統計

2.5 基于數學困難問題的哈希算法

1900年,德國數學家Hilbert[31]在巴黎第2屆國際數學家大會上作的題為《數學問題》的著名講演中,提出23個問題作為對未來數學家的挑戰,整系數多項式是否存在整數解的難題正是其中的第10個.1970年蘇聯數學家馬蒂塞維奇最終證明:在一般情況下,答案是否定的.

求解整數多項式方程組的問題就是找到一個可行的辦法,通過有限次的運算確定含有任意多個未知數的整系數不定方程fi=(x1,x2,…,xn)=0,i=1,2,…,m的解.該問題在算法上無法解決,此外,如果多項式的次數≥3且n>m,那么這個問題在算法上是整數不可解的.

2018年,Krendelev等人[32]提出了一種哈希函數構建方法,該方法基于求解整數多項式方程組的問題,并使用1組參數增強哈希函數持久性,其中方程的數量小于未知參數的數量.

該方法在構建時需要首先確認參數,在基礎版本中,需要確認的參數有:模塊p,維度大小m×n,開始系數集合α1,α2,…,αn,塊的大小b,形成被加數h1(x),h2(x),…,hm(x)的規則.為了獲得更好的結果,作者還制定了參數要求.所有計算都將在模塊p上進行.模塊應該是足夠大的素數.根據從參數α1,α2,…,αn,αi∈導出的特殊規則生成一些向量集,其中n是任意整數,代表這些向量的維數為n.假設某個哈希文檔由1組數字描述為x=(x1,x2,…),一定數量的比特組合形成1個數字,一定數量的數字組合形成1個條件塊.塊的位數可以是8,10,12等.該哈希算法的具體計算過程如下:

1) 數據準備.

根據輸入文件準備1個十進制整數字符串x=(x1,x2,…,xm).

然后根據開始系數集合α1,α2,…,αn生成一個矩陣A=(a1,a2,…,am),其中ai根據公式ai=α1a1+α2a2+…+αnan構造為遞歸序列.

2) 構造哈希函數.

H(x)=[a1h1(x)+a2h2(x)+…+
amhm(x)] mod (p).

(4)

根據上述公式構建的向量即是哈希,其中函數h1(x),h1(x),…,hm(x)可以自己選擇任何規則構建,也可以按照公式計算:

H(x)=[a1x1x2+a2x2x3+…+
amxmx1] mod (p),

(5)

哈希函數的輸出字符串的大小為n×m.

3) 修改.

在大文件中,某些項為0的概率是很大的.其主要原因是當某些項的0累加時,形成一個遞歸序列的規則.為了在算法的基礎版本中避免這種情況,作者使用循環移位的方法.或者直接將0分量替換為固定數,固定數也可以是一個參數.

該哈希算法對量子計算機具有抵抗力,并基于算法上無法解決的問題——尋找整數多項式方程組的解實現.所開發的算法是參數化的,因此哈希函數的結果取決于幾個參數,只要參數有一點變化,函數的值就會發生很大變化(雪崩效應),大大增加了決策時間.按位比較,雪崩效應約為47%～50%,它能夠抵抗沖突.碰撞在理論上是可能的.然而,為該哈希算法找到沖突是沒有意義的,因為如果方程組中存在次數大于3的多項式,則問題在算法上是無法解決的,因此碰撞是不可能的[32].但是同基于概率分布矩陣的量子哈希函數,秘密參數的知悉范圍非常關鍵,若范圍太大則很容易遭受敵人攻擊,范圍太小則不易于第三方進行消息驗證,秘密參數知悉范圍的選取建議根據實際問題進行具體判定.

3 哈希函數設計建議

區塊鏈對未來數據存儲至關重要,而區塊鏈中哈希函數的安全性更是時刻影響著區塊鏈的總體安全性,因此研究具有抗量子性的哈希函數為區塊鏈在后量子時代的穩健運行提供有力基礎具有十分重要的意義.本文在以上提出的5種哈希方案中,目前最推薦2.2節中基于QIQW的量子哈希函數,可以抵御來自數字和量子計算機的可能攻擊.2.3節中的方案由于存在誤差,所以目前不推薦,未來消除誤差后,將其應用到區塊鏈中也是一個不錯的選擇.

除此以外,經過分析與總結,本文建議在未來區塊鏈的設計中遵循以下3個原則:

3) 帶有秘密參數的哈希函數.若存在量子攻擊的可能性,推薦使用帶有秘密參數的哈希函數.使用量子加密通信等可信信道來傳輸秘密參數,利用量子物理特性來保證秘密參數的機密性,從而抵御經典或量子計算機可能的攻擊.

4 結 語

本文對哈希函數的量子計算攻擊及其對區塊鏈的影響進行了分析,對當前的5類抗量子攻擊的區塊鏈中的哈希函數進行了分析、對比和總結,最后對區塊鏈中的哈希函數的設計給出了幾點建議,本文的工作將為后量子時代區塊鏈中的哈希函數的設計提供有益參考,下一步將針對量子時代的區塊鏈的特性和不足,提出新的抗量子設計方案,在輕量化、抗碰撞性、安全性上等取得更好的發展.