分組密碼CLEFIA與基于四圈AES的消息認證碼的安全性分析.pdf

1、分組密碼屬于對稱密碼算法，用同一密鑰進行加密和解密運算。本質(zhì)上，分組密碼是一種有效的帶密鑰的置換，將固定長度的明文轉(zhuǎn)換為相同長度的密文。分組密碼廣泛應(yīng)用于各類密碼算法，消息認證碼將密鑰和任意長度的消息作為輸入，輸出一個固定長度的標簽。消息認證碼主要用于保證消息完整性和進行消息源認證。分組密碼和消息認證碼的安全性分析是密碼學研究領(lǐng)域的熱點問題。 新的設(shè)計理念使算法運行效率有了較大提高。鑒于其廣闊的應(yīng)用前景，新的設(shè)計理念對算法安全性

2、的影響值得我們深入探討。我們對分組密碼算法CLEFIA和消息認證碼算法PELICAN、MT-MAC-AES和PC-MAC-AES的安全性進行分析，并有如下結(jié)果。 （1）縮減輪數(shù)的CLEFIA算法的飽和度分析 索尼公司在CLEFIA的安全和性能評估報告中宣稱，CLEFIA足以抵抗所有現(xiàn)已提出的攻擊方法。對于飽和度分析，評估報告中給出了兩個8圈飽和特征，并用于分析約減到10圈的無白化密鑰的CLEFIA算法[48]。

3、我們指出評估報告中的8圈區(qū)分器的錯誤，并給出新的8圈區(qū)分器。將白化密鑰和子密鑰等價為一個子密鑰，并發(fā)現(xiàn)具有飽和特性的變量為32比特的方程可成功分割為4個變量為8比特的子方程，從而可利用分別征服策略，對每個子方程分別求解，減少需要猜測的密鑰個數(shù)。而且，采用“部分和”技術(shù)進一步降低攻擊的時間復雜度，將評估報告中對10圈CLEFIA的飽和度攻擊擴展到11圈的CLEFIA-128/192/256、12圈的CLEFIA-192/256和13圈的C

4、lEFIA-256，并將白化密鑰考慮在內(nèi)。該結(jié)果是目前對CLEFIA算法進行飽和度分析的最好結(jié)果。 結(jié)合CLEFIA算法的結(jié)構(gòu)，方程（）可以按字節(jié)分割為四個子方程，從而可以利用分別征服攻擊，分別對每個變量為8比特的子方程求解。而且，我們發(fā)現(xiàn)128比特的白化密鑰和128比特的子密鑰的異或值相當于一個128比特的子密鑰。因此，可以大大降低求解一個方程需要猜測的子密鑰的個數(shù)，進而降低攻擊的復雜度。以約減到10圈的CLEFIA算法為例，

5、第一個子方程如下： 其中，Y0可由密文直接獲得?？梢姡挥?0比特子密鑰（RK'17.0，RK18）和該子方程相關(guān)，而文獻[28]卻是64比特子密鑰（RK17，RK18）。在具體求解過程中，通過采用部分和技術(shù)[18]，可進一步降低攻擊的時間復雜度。 密鑰猜測環(huán)節(jié)的時間復雜度為246.2次加密運算，而此前的結(jié)果為2124次加密運算。通過窮舉第11圈的64比特子密鑰，我們將10圈的分析應(yīng)用于11圈，復雜度為2111.4次加密

6、運算和299.8個選擇明文。同理，可將該攻擊應(yīng)用于12圈的CLEFIA-192/256和13圈的CLEFIA-256。 （2）縮減輪數(shù)的CLEFIA算法的不可能差分分析 索尼公司在評估報告中給出了兩個9圈不可能差分特征，并用于分析10圈的CLEFIA-128/192/256，11圈的CLEFIA-192/256和12圈的CLEFIA-256，其中，對12圈的分析也沒有考慮白化密鑰[48]。 我們的分析基于評估報告

7、中的不可能差分特征，但是采用了新的路線擴展方式，減少需要猜測的子密鑰個數(shù)。結(jié)合對CLEFIA算法輪函數(shù)的新發(fā)現(xiàn)，及白化密鑰可與子密鑰結(jié)合的特性，更加有效地過濾錯誤密鑰，使攻擊效率顯著提高。在預(yù)計算處理方面，根據(jù)所需明文對的特殊差分形式，提煉代數(shù)特征，提出新的生日篩法，降低攻擊的時間復雜度。對于CLEFIA-128/192/256，將評估報告中10圈的分析擴展到12圈，并且，對于13圈的CLEFIA-192/256和14圈的CLEFIA-

8、256，該攻擊同樣適用。此外，指出并改正Tsunoo等對12圈CLEFIA的攻擊中時間復雜度方面的問題。同時，分析表明，該算法中采用的白化密鑰并不能增強抗不可能差分分析的強度。 在不可能差分分析過程中，首先，要在不可能差分特征的兩端分別添加適當?shù)娜?shù)，得到所需的輸入輸出差分。通過預(yù)計算，構(gòu)造滿足特殊輸入差分的明文集合，并篩選出滿足特殊輸出差分的明文對。因為2n個明文一共可產(chǎn)生22n-1個明文對，所以需要更有效的算法來篩選明文對。

9、發(fā)現(xiàn)輸入輸出差分之間的代數(shù)特征，利用生日攻擊[67]，提出生日篩法，將對2n個明文進行篩選的時間復雜度控制在2n次異或運算。例如，輸入差分△P=（0，0，a，*），而要篩選出的明文對滿足輸出差分△C=（*，*，0，a），其中，a為固定的32比特非零值，*表示任意的32比特非零值。根據(jù)△P的第二、三字節(jié)和△C的三、四字節(jié)相等的特性，轉(zhuǎn)換為篩選滿足△C=（*，*，0，0）的明文對，其中，C=（P>>>32）（）C，而這可以通過生日攻擊來實現(xiàn)

10、。 然后，對每個篩選出的明文對，猜測相關(guān)的子密鑰，進行加密或解密，使得加解密后的結(jié)果和不可能差分特征吻合的密鑰為錯誤密鑰，將其從子密鑰空間刪除。分析足夠多的明文對，直到子密鑰空間中只剩下一個元素，就是正確的子密鑰。在過濾正確子密鑰的過程中，我們發(fā)現(xiàn)利用以下性質(zhì)，對32比特子密鑰的求解可通過時間-存儲平衡，在一次F運算內(nèi)完成。 ·對F函數(shù)（F0或F1），若已知兩個32比特的輸入（In，In'）及相應(yīng)的輸出差分△Out，則求

11、解F函數(shù)的子密鑰RK只需一次F-運算。 而且，結(jié)合CLEFIA算法的特殊結(jié)構(gòu)，推導出含有兩個子密鑰的線性表達式如下，從而將兩個子密鑰合為一個，減少猜測密鑰的個數(shù)。 利用上述特性，對11圈CLEFIA的攻擊只需2103.1次加密運算和2103.1個選擇明文，比設(shè)計者給出的2188次加密運算和2103.5個選擇明文有較大改善。而且，結(jié)合一種特殊的選擇明文方式，該攻擊可以擴展到12圈的CLEFIA-128/192/256，復雜

12、度為2119.1次加密運算和2119.1個選擇明文。同理，可分析13圈的CLEFIA-192/256和14圈的CLEFIA-256。 Fsunoo等也獨立發(fā)現(xiàn)了類似的性質(zhì)，并公布了新的9圈不可能差分路線，將不可能差分分析擴展到12圈的CLEFIA-128/192/256，13圈的CLEFIA-192/256和14圈的CLEFIA-256[53]。然而，他們對12圈CLEFIA的分析忽略了預(yù)計算的時間復雜度，從而導致實際攻擊的時

13、間復雜度為2125.8次加密運算，而不是文獻中的2118.9。我們指出，其預(yù)計算的時間復雜度可以用本論文中提出的生日篩法來降低，使得分析12圈CLEFIA的的時間復雜度仍為2118.9次加密運算。目前，這些分析結(jié)果已被Tsujihara等改進[52]。 （3）基于四圈AES的消息認證碼的不可能差分分析 基于四圈AES的消息認證碼PELICAN，MT-MAC-AES和PC-MAC-AES都屬于迭代MAC算法。Preneel

14、等指出，可利用生日攻擊對這類算法進行存在性偽造，復雜度為2n+1/2個消息和2n+1/2次詢問，其中，n為MAC值的長度[38]。此外，在密鑰或中間狀態(tài)已知的情況下，可對PELICAN進行第二原像攻擊[22]。還存在一種側(cè)信道碰撞攻擊可以恢復PELICAN的中間狀態(tài)，從而進行選擇性偽造[8]。 最近，王小云教授等提出了利用生日攻擊識別滿足特殊差分的內(nèi)部幾乎碰撞的新技術(shù)[59，62]。通過識別具有特殊差分的內(nèi)部幾乎碰撞，而非簡單的

15、碰撞，可以提煉出更多的信息。根據(jù)生日攻擊，收集足夠多的消息及其認證碼（一般為2n/2左右），可以保證具有特殊差分的內(nèi)部幾乎碰撞的存在性。然后，通過附加具有特殊差分形式的消息對，能以接近于1的概率將這個內(nèi)部幾乎碰撞識別出來。文獻[23，66]的一系列工作將這個識別內(nèi)部幾乎碰撞的新思想分別應(yīng)用于CBC類MAC的第二原像攻擊和ALPHA-MAC的等價子密鑰恢復攻擊。 結(jié)合上述工作，在王小云教授的建議下，我們首次將不可能差分分析用于MA

16、C算法。對分組密碼來說，不可能差分分析[4]是一種有效的分析方法，可以分析7圈的AES-128（一共10圈）[1.29]。但是，由于MAC算法的中間狀態(tài)及其差分被最后的加密運算或復雜的帶密鑰的迭代過程所掩蓋，鮮有用不可能差分分析MAC算法的文章。利用生日攻擊，解決MAC算法中間狀態(tài)的差分難識別的問題。由于PELICAN、MT-MAC-AES和PC-MAC-AES以AES和4圈AES為組件，可根據(jù)新發(fā)現(xiàn)的3圈AES不可能差分特征，恢復PE

17、LICAN的中間狀態(tài)，復雜度為285.5個選擇消息和285.5次詢問。靈活選擇消息的差分，可對PELICAN進行選擇性偽造。該恢復中間狀態(tài)的攻擊可轉(zhuǎn)換為對MT-MAC-AES的子密鑰恢復攻擊，復雜度保持不變。對PC-MAC-AES，一旦恢復了中間狀態(tài)，可以分別恢復兩個128比特的主密鑰，復雜度為285.5個選擇消息和2128次詢問。 大致思路為：首先，構(gòu)造兩個各含2n/2個消息的集合，保證每個消息對滿足特殊差分。然后，利用生日攻