【摘要】：信息技術(shù)尤其是互聯(lián)網(wǎng)的蓬勃發(fā)展,使得個體間的聯(lián)系愈加密切,信息安全問題同時日益凸顯,而密碼學(xué)是信息安全的基石。密碼算法可分為對稱密碼算法和非對稱密碼算法。對稱密碼算法包括分組密碼、流密碼、Hash函數(shù)、消息鑒別碼(MAC)、認(rèn)證加密算法等。SPONGE結(jié)構(gòu)具有固定大小的內(nèi)部狀態(tài),但可以處理任意長度的輸入,生成任意給定長度的輸出,近年來被廣泛應(yīng)用于Hash函數(shù)、MAC和認(rèn)證加密算法等的設(shè)計。立方攻擊由Dinur和Shamir在2009年歐密會上提出,將對稱加密算法看作多項式系統(tǒng),根據(jù)某些公開變量的乘積項(稱為極大項),提取秘密變量(密鑰)信息。黃森洋等在2017年歐密會上提出了條件立方攻擊的方法,在第一輪中為公開變量添加關(guān)于密鑰比特的控制條件,利用極大項的存在性恢復(fù)密鑰信息。本文對幾種典型的SPONGE類密碼算法展開研究,分別給出了新型條件立方攻擊。在對CAESAR認(rèn)證加密競賽獲勝算法ASCON的研究中,建立了更為一般化的條件立方攻擊模型。對代數(shù)表達(dá)式提取部分公因子,并根據(jù)每個公因子構(gòu)造比特控制方程,加入功能性立方變量的調(diào)控,進而得到立方攻擊區(qū)分器,給出了縮減為5輪、6輪、7輪ASCON初始化階段的密鑰恢復(fù)攻擊,時間復(fù)雜度分別為224、240、2103.92。目前,本文提出的7輪理論攻擊和6輪實際攻擊是ASCON初始化階段的最優(yōu)分析結(jié)果。在對KECCAK相關(guān)算法的研究中,引入了混合整數(shù)線性規(guī)劃(MILP)方法,豐富了KECCAK相關(guān)算法的自動化分析工具;提出了控制變量擴散的新模式,對變量的控制從第一輪延伸到了第二輪,擴展了分析輪數(shù),大幅降低了KEECCAK相關(guān)算法的分析難度。系列分析結(jié)果包括美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)標(biāo)準(zhǔn)KMAC256、KECCAK-MAC-384/-512和CAESAR認(rèn)證加密競賽第三輪候選算法KETJE等縮減版本的(新型)條件立方攻擊�！たs減輪數(shù)Ascon的密鑰分割與條件立方攻擊認(rèn)證加密算法AsCON是CAESAR認(rèn)證加密競賽獲勝算法之一。Dinur等在2015年歐密會上首次提出了類立方的密碼分析方法,要求立方變量在第一輪中兩兩不乘,并應(yīng)用于帶密鑰模式、狀態(tài)大小為1600比特的KECCAK算法。在2015年CT-RSA會議上,Dobraunig等將類立方的密碼分析方法用于5輪、6輪ASCON算法。在原有的密鑰恢復(fù)攻擊工作中,對ASCON算法進行密鑰恢復(fù)攻擊的最高輪數(shù)是6輪,而對于帶密鑰模式、狀態(tài)大小為1600比特的KECCAK算法(包括KECCAK-MAC、KEYAK),其密鑰恢復(fù)攻擊的最高輪數(shù)大于等于7輪。究其原因,ASCON算法狀態(tài)大小為320比特,遠(yuǎn)遠(yuǎn)小于1600比特,且具有更為復(fù)雜的非線性層設(shè)計,所以攻擊者很難找到足夠數(shù)量的在第一輪兩兩不乘的立方變量,因此其密鑰恢復(fù)攻擊的輪數(shù)較KECCAK算法更短。針對條件立方攻擊,本文提出了更為一般化的模型。在對5輪、6輪ASCON的分析中,找到了新的立方變量集合,而其所依賴的條件只與密鑰比特有關(guān),在原有的工作中,對6輪ASCON進行密鑰恢復(fù)攻擊的時間復(fù)雜度為266,為理論分析結(jié)果,本文給出了時間復(fù)雜度為240的6輪實際攻擊。此外,提出了7輪ASCON的密鑰恢復(fù)攻擊:引入基于密鑰分割的條件立方攻擊方法,基于不同的密鑰條件,將整個密鑰空間分為多個子空間;對于每個密鑰子空間,建立不同的立方區(qū)分器,確定當(dāng)前密鑰是否屬于此密鑰子空間;以此類推,檢測完成所有密鑰子空間,從而可以完全恢復(fù)整個密鑰空間。7輪ASCON密鑰恢復(fù)攻擊的時間復(fù)雜度大約為2103.9,特別地,對于一個大小為2117的弱密鑰集,可以實施更為高效的攻擊,時間復(fù)雜度為277。將ASCON初始化階段的密鑰恢復(fù)攻擊延長了一輪。·縮減輪數(shù)Keccak(密鑰模式)的新型條件立方攻擊及MILP模型KECCAK算法是一族SPONGE函數(shù),具有狀態(tài)大小不同的7種置換部件。美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)發(fā)布的最新Hash函數(shù)標(biāo)準(zhǔn)SHA-3即基于KECCAK算法。在2017年歐密會上,針對帶密鑰模式的KECCAK算法,黃森洋等提出了一種高效的密鑰恢復(fù)攻擊方法,即條件立方攻擊。通過設(shè)置比特條件,有效控制了條件立方變量的擴散;然后通過一種貪婪算法,逐一添加普通立方變量,最終找到滿足如下要求的足夠數(shù)量的普通立方變量:首先所有立方變量在第一輪中兩兩不乘,其次普通立方變量在第二輪中與條件立方變量不乘。利用立方變量的乘積項(極大項)的存在性恢復(fù)密鑰信息:若輸出中存在極大項,則密鑰比特條件不成立;若輸出中不存在極大項,則判斷密鑰比特條件成立。其中,找到足夠數(shù)量的普通立方變量是條件立方攻擊成功的關(guān)鍵。事實上,在逐一添加普通立方變量的過程中,新添加的普通立方變量有可能與很多待選比特在第一輪中相乘,所以添加這一個變量有可能導(dǎo)致很多變量無法被選,這無疑是一種損失。本文引入一種新的混合整數(shù)線性規(guī)劃(MILP)模型,用于搜索足夠數(shù)量的普通立方變量。將普通立方變量的擴散控制納入規(guī)劃模型,統(tǒng)籌處理立方變量的選取。同時將普通立方變量第一輪中兩兩不乘,第二輪中與條件立方變量不乘的性質(zhì)納入規(guī)劃模型。事實上,模型中使用一系列線性不等式,準(zhǔn)確刻畫選取普通立方變量的要求。設(shè)置目標(biāo)為求解普通立方變量的最大數(shù)目,求解MILP問題給出的最優(yōu)結(jié)果優(yōu)于原有結(jié)果。新的MILP模型利用統(tǒng)籌優(yōu)化的方法,將之前對于KECCAK-MAC-384和KECCAK-MAC-512的密鑰恢復(fù)攻擊結(jié)果都延長了一輪,達(dá)到了7輪KEECCAK-MAC-384和6輪KECCAK-MAC-512的密鑰恢復(fù)攻擊,復(fù)雜度分別為275和258.3。對于認(rèn)證加密算法KETJE MAJOR,其狀態(tài)大小為1600比特,如果初始狀態(tài)中的自由消息長度不小于704比特,那么可以達(dá)到7輪的攻擊。對于認(rèn)證加密算法KETJE MINOR,其狀態(tài)大小為800比特,使用6-6-6擴散模式的條件立方變量,可以實施7輪密鑰恢復(fù)攻擊。2018年亞密會上,宋凌等提出了改進的MILP模型,降低了6輪KECCAK-MAC-512密鑰恢復(fù)攻擊的復(fù)雜度。事實上,在帶密鑰模式KECCAK相關(guān)算法當(dāng)中,有一些自由度非常低的算法實例。對于這些算法,攻擊者即使利用MILP模型也無法找到足夠數(shù)量的普通立方變量,從而無法實施條件立方攻擊。本文提出了一種新型條件立方攻擊。首先,去除立方變量在第一輪中相互不乘的限制,于是,第一輪的輸出中存在一些二次項。其次,引入一些新的比特條件,使得在第二輪中所有二次項不與其他立方變量相乘,因此第二輪的輸出中不存在三次項。此外,引入“核心二次項”的概念,構(gòu)建新的擴散模式,即“6-2-2模式”,這些顯著地控制了二次項的擴散,對于核心二次項來說,甚至將第二輪的θ運算限制成為恒等變換。綜上,與之前的條件立方變量相比,核心二次項的分布更加稀疏,因此普通立方變量的選取有了更高的自由度,此外,第二輪中消除三次項所使用的比特條件數(shù)目顯著減少。繼續(xù)使用MILP方法搜索立方變量,對自由度非常低的帶密鑰模式KECCAK相關(guān)算法,也成功實施了新型條件立方攻擊。通過新型條件立方攻擊的研究,將7輪KECCAK-MAC-512和7輪KETJE SR v2密鑰恢復(fù)攻擊的時間復(fù)雜度分別由2111和299降低到了272和277。此外,9輪KMAC256和7輪KETJE SR v1密鑰恢復(fù)攻擊的時間復(fù)雜度也得到不同程度的降低。將KEECCAK-MAC-512和KETJE SR v2的條件立方攻擊延長了一輪。在試驗驗證中,給出了6輪KEETJE Sr v1和v2密鑰恢復(fù)的實際攻擊。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2019
【分類號】：TN918.1
【圖文】：

Ｋｅｔｊｅ采用的是基于ＭｏｎｋｅｙＤｕｐｌｅｘ［２１的ＭｏｎｋｅｙＷｒａｐ認(rèn)證加密模逡逑式，包含四部分：初始化，相關(guān)數(shù)據(jù)處理，明文處理和終結(jié)部分。忽略終逡逑結(jié)部分的Ｋｅｔｊｅ邋ｖ２算法如圖２．６所示，其置換函數(shù)是由Ｋｅｃｃａｋ－ｐ調(diào)整得逡逑來的邋ＫＥＣＣＡＫ－ｐ＊，ＫＥＣＣＡＫ－ｐ＊［６］＝７ｒ0ＫＥＣＣＡＫ－ｐ［６］0７ｒ＿１，目的是高效地重排逡逑狀態(tài)比特。如圖２．７所示，７Ｔ的逆為７Ｔ－１邋：邐＋邋３|幔唬蒎澹藉甕跡玻噸�，辶x希

本文編號：2753293