Robin算法改進(jìn)的6輪不可能差分攻擊

沈 璇，王欣玫，何 俊，孫志遠(yuǎn)

國防科技大學(xué) 信息通信學(xué)院，武漢430010

分組密碼算法是對稱密碼算法中非常重要的一大類。它的安全性分析方法可以分為直接分析和間接分析兩種，其中直接分析指的是利用數(shù)學(xué)、計(jì)算機(jī)等工具直接對密碼算法本身的安全性進(jìn)行分析[1-3]，而間接分析指的是利用密碼算法在密碼設(shè)備中運(yùn)行時(shí)泄露的信息進(jìn)行分析[4-6]，間接分析又稱為側(cè)信道分析。很多密碼學(xué)者在設(shè)計(jì)分組密碼算法時(shí)，會考慮密碼算法對側(cè)信道攻擊的抵抗能力。

為了有效抵抗側(cè)信道攻擊，2014年，Grosso等人[7]在“快速軟件加密”會議上設(shè)計(jì)了一類新的分組密碼算法族——基于LS設(shè)計(jì)的算法族。該算法族采用比特切片設(shè)計(jì)，設(shè)計(jì)者根據(jù)該設(shè)計(jì)思想給出了兩個(gè)具體的分組密碼算法，一個(gè)是非對合的分組密碼算法Fantomas，另外一個(gè)是對合的分組密碼算法Robin。Robin算法采用SP結(jié)構(gòu)，其線性組件和非線性組件均是對合的。

不可能差分攻擊是目前針對分組密碼算法最有效的攻擊方法之一，它對包括AES、SMS4、Camellia、ARIA、SIMON、SKINNY、Piccolo等[8-14]在內(nèi)的許多分組密碼算法的安全性分析效果顯著。該攻擊方法由Knudsen[15]和Biham等人[16]獨(dú)立提出，它由不可能差分構(gòu)造和密鑰恢復(fù)兩個(gè)階段組成，其中前者需要構(gòu)造盡可能長的不可能差分區(qū)分器，后者利用已構(gòu)造的區(qū)分器進(jìn)行密鑰恢復(fù)得到正確密鑰。此外，不可能差分構(gòu)造階段得到的區(qū)分器除了長度外，區(qū)分器的形式同樣能夠影響最后的攻擊效果。

目前，Robin算法的不可能差分攻擊結(jié)果主要有：2014年，Grosso等人在設(shè)計(jì)文檔中，基于算法的比特模式，利用中間相錯(cuò)技術(shù)構(gòu)造了3輪的不可能差分區(qū)分器。該區(qū)分器主要是利用中間差分某一比特構(gòu)造矛盾，該構(gòu)造方法并未充分利用線性層的信息。為了解決這一問題，充分挖掘線性層的信息構(gòu)造更長輪數(shù)的區(qū)分器，2018年，Shen等人[17]將Robin算法的比特模式等價(jià)轉(zhuǎn)換為字節(jié)模式，并利用UID方法[18]搜索到4輪不可能差分區(qū)分器，達(dá)到了不考慮非線性層細(xì)節(jié)情況下的最優(yōu)長度，該區(qū)分器的構(gòu)造已充分利用了線性層的信息，進(jìn)一步作者利用該區(qū)分器攻擊了6輪的算法，攻擊的數(shù)據(jù)復(fù)雜度為2119個(gè)選擇明文，時(shí)間復(fù)雜度為2101.81次6輪算法加密。與此同時(shí)，需要指出的是，作者在進(jìn)行不可能差分攻擊時(shí)，沒有充分利用輪密鑰之間的信息，只是將涉及到的輪密鑰看成獨(dú)立密鑰分別進(jìn)行猜測。若在攻擊的過程中能夠充分挖掘輪密鑰的信息，則能夠降低輪密鑰的猜測量，進(jìn)而降低攻擊所需的時(shí)間復(fù)雜度。

為了解決上述線性層和輪密鑰信息的利用問題，進(jìn)一步改進(jìn)Robin算法不可能差分攻擊的結(jié)果。

本文首先利用中間相錯(cuò)技術(shù)構(gòu)造了一條新的4輪不可能差分區(qū)分器，該區(qū)分器長度同樣達(dá)到了不考慮非線性層細(xì)節(jié)情況下的最優(yōu)長度。該區(qū)分器的構(gòu)造充分挖掘了線性層的信息，解決了線性層信息利用問題。進(jìn)一步，該區(qū)分器的形式與文獻(xiàn)[17]不同，這使得它在密鑰恢復(fù)階段涉及到的輪密鑰也不一樣。利用新構(gòu)造的區(qū)分器，在進(jìn)行密鑰恢復(fù)時(shí)，涉及到的輪密鑰之間存在線性關(guān)系，解決了輪密鑰信息利用問題。具體來說，本文利用輪密鑰之間的線性關(guān)系，在進(jìn)行密鑰猜測時(shí)，能夠少猜測1個(gè)字節(jié)的輪密鑰量，進(jìn)而能夠降低約28的時(shí)間復(fù)雜度。

1 Robin算法簡介

Robin算法的分組長度為128 bit，密鑰長度也為128 bit，總輪數(shù)為16輪。該算法采用比特切片設(shè)計(jì)，在該算法的設(shè)計(jì)文檔中，它是基于比特的形式進(jìn)行描述?？紤]到其作用到每列上的線性層均相同，因此在文獻(xiàn)[17]中，作者將該算法的比特描述等價(jià)轉(zhuǎn)換為字節(jié)描述，這樣更有利于區(qū)分器的構(gòu)造。本文也采用基于字節(jié)的描述方式。

Robin算法的整體加密流程，如圖1所示。

圖1 Robin算法的加密流程

明文先與種子密鑰進(jìn)行異或，然后經(jīng)過16輪輪函數(shù)迭代后得到密文。Robin算法的輪函數(shù)由三部分組成：S層、L層和KC層。

S層：16個(gè)8 bit的S盒并置加密。在本文中，S盒只需要視為雙射即可，故S盒的具體細(xì)節(jié)不給出，可參見文獻(xiàn)[7]。

L層：在S層之后，利用一個(gè)分支數(shù)為8的16×16的二元矩陣作用在128 bit的狀態(tài)上。若L層的輸入為X=(x0,x1,…,x15)，輸出為Y=(y0,y1,…,y15)，這里xi、yi(i=0,1,2,…,15)均為8 bit的字節(jié)，則線性層L對應(yīng)的加密變換為：

在Robin算法中，L層是對合的，即L層和L-1層加密變換完全相同。

KC層：種子密鑰K和輪常數(shù)Con(i)進(jìn)行異或，再與中間狀態(tài)異或。這里Con(i)表示第i輪的輪常數(shù)，具體取值參見文獻(xiàn)[7]。

在本文中，Robin算法的任一128 bit狀態(tài)X=(x0,x1,…,x15)，這里xi均為8 bit的字節(jié)，均按照圖2的4×4矩陣形式進(jìn)行排列。

圖2 128 bit狀態(tài)按照矩陣形式排列

2 Robin算法4輪不可能差分區(qū)分器構(gòu)造

本章利用中間相錯(cuò)技術(shù)構(gòu)造了Robin算法的一條新的4輪不可能差分區(qū)分器。注意該區(qū)分器的長度達(dá)到了不考慮S盒細(xì)節(jié)情形下的區(qū)分器最長輪數(shù)。

下面給出Robin算法的新4輪不可能差分區(qū)分器：

這里b、h均是非零字節(jié)差分。

證明 如圖3所示，該命題的證明思路主要是從加密方向看，輸入差分經(jīng)過兩輪正向差分傳播后，中間差分在第8、9字節(jié)處相等；從解密方向看，輸出差分經(jīng)過兩輪反向差分傳播后，中間差分在對應(yīng)的第8、9字節(jié)處不等，故得矛盾。

圖3 Robin算法4輪不可能差分

注意到KC層和KC-1層是通過異或的方式參與加解密的，在差分傳播的過程中，它們可以視為常數(shù)，不改變差分的值。下面分別從加密方向和解密方向進(jìn)行詳細(xì)說明：

（1）加密方向。第2輪的輸入差分為：

經(jīng)過S層后這里b和c均是非零字節(jié)差分。再經(jīng)過L層和KC層后第3輪的輸入差分和第2輪的輸出差分相同，經(jīng)過S層后，接著經(jīng)過L層和KC層后得到的輸出差分為：

并且有e8=e9=d0⊕d6⊕d14⊕d15。

（2）解密方向。第5輪的輸出差分為：

經(jīng)過KC-1層和L-1層后：

這里h為非零字節(jié)差分。再經(jīng)過S-1層后：

這里g1、g7、g9、g12均為非零字節(jié)差分。第4輪的輸出差分和第5輪的輸入差分相同，經(jīng)過KC-1層和L-1層后：

這里f8=0,f9=g12≠0。接著經(jīng)過S-1層后得到的輸入差分為：

綜上所述，輸入差分從加密方向傳播2輪得到的中間差分和輸出差分從解密方向傳播2輪得到的中間差分在第8、9字節(jié)處相矛盾，因此該差分為一條4輪不可能差分。

3 Robin算法6輪不可能差分攻擊

考慮到6輪Robin算法的最后一輪存在線性層，本節(jié)首先利用等價(jià)密鑰技術(shù)[19]，將Robin算法等價(jià)為一個(gè)新的算法，這樣能夠降低不可能差分攻擊時(shí)最后一輪的密鑰猜測量，進(jìn)而降低攻擊的復(fù)雜度。接著利用構(gòu)造的新的4輪不可能差分區(qū)分器，在區(qū)分器前后各加一輪，攻擊6輪的Robin算法。

設(shè)6輪Robin算法的明文為P，密文為C，根據(jù)Robin算法加密流程知：

圖4 6輪Robin算法最后一輪等價(jià)變換

此外，根據(jù)K′=L-1(K)，考慮K′的第1、7、9、12字節(jié)，有如下式子成立：

下面利用上章構(gòu)造的4輪不可能差分區(qū)分器，并結(jié)合等價(jià)密鑰技術(shù)，給出6輪Robin算法的不可能差分攻擊，如圖5所示。

圖5 Robin算法的6輪不可能差分攻擊

整個(gè)攻擊的步驟如下：

步驟1選擇一個(gè)明文結(jié)構(gòu)，該明文結(jié)構(gòu)中的數(shù)據(jù)滿足如下形式：

這里xi(i=0,1,2,…,6)是一個(gè)任意可變的字節(jié)，ci(i=0,1,2,…,8)是一個(gè)固定的字節(jié)。則在該明文結(jié)構(gòu)中任取兩個(gè)明文P0、P*0，它們的異或差分值滿足：

這里ai(i=0,6,7,10,11,14,15)表示一個(gè)非零的字節(jié)差分。該明文結(jié)構(gòu)能夠提供28×7=256個(gè)明文，能夠提供256×256/2=2111組明文對。

步驟2選取2n個(gè)上述明文結(jié)構(gòu)，則它們能夠提供2n+56個(gè)明文，2n+111組明文對，選擇使得密文差分滿足如下形式的明文對：

這里it(t=1,7,9,12)表示一個(gè)非零的字節(jié)差分，上述差分形式中有12個(gè)字節(jié)差分為零，它成立的概率為2-8×12=2-96。此時(shí)，經(jīng)過步驟2后剩下的明密對數(shù)量約為2n+111×2-96=2n+15。

步驟3對于上述剩余明密對，猜測最后一輪等價(jià)密鑰K′的第1、7、9、12字節(jié)，即K′1、K′7、K′9、K′12共計(jì)32 bit的密鑰，計(jì)算：

選擇使得該差分在第1、7、9、12字節(jié)處相等的明密對，上述事件成立的概率為2-8×3=2-24，則經(jīng)過步驟3后剩下的明密對數(shù)量約為2n+15×2-24=2n-9。

步驟4對于上述剩余明密對，猜測種子密鑰K的第0、6、7、10、11、14字節(jié)，即K0、K6、K7、K10、K11、K14共計(jì)48 bit的密鑰。

根據(jù)K′和K之間的關(guān)系，如式（1）中的第一個(gè)等式：

故有：

注意到在步驟3中K′1已猜測，當(dāng)猜測K0、K6、K7、K10、K11、K14后，K15即可得到。進(jìn)一步，計(jì)算：

選擇使得該差分在第0、6、7、10、11、14、15字節(jié)處相等的明密對，上述事件成立的概率為2-8×6=2-48。若該事件成立，則篩除K′的32 bit和K的48 bit共計(jì)80 bit的候選密鑰。

因?yàn)橹虚g的4輪差分是不可能差分，所以滿足該不可能差分輸入和輸出形式的候選密鑰是錯(cuò)誤的密鑰。當(dāng)分析完2n-9個(gè)密文對后，錯(cuò)誤密鑰仍然能夠保留下來的數(shù)目為：

當(dāng)n=62.8時(shí)，

則所有可能的錯(cuò)誤密鑰被篩除，剩下的密鑰即為正確密鑰。

復(fù)雜度分析。數(shù)據(jù)復(fù)雜度為2n+56=2118.8個(gè)選擇明文；時(shí)間復(fù)雜度主要由步驟3和步驟4組成，注意到在步驟3中主要涉及4個(gè)S盒解密，而1輪解密涉及16個(gè)S盒，結(jié)合早夭技術(shù)[20]知，步驟3需要：

在步驟4中涉及7個(gè)S盒加密，而1輪加密涉及16個(gè)S盒，則步驟4需要：

注意到在復(fù)雜度計(jì)算時(shí)，Robin的1輪算法加密和1輪算法解密的時(shí)間相當(dāng)，因此恢復(fù)80 bit密鑰信息需要的時(shí)間復(fù)雜度為：

它約為296.55/6≈293.97次6輪算法加密。此外，種子密鑰信息是128 bit，上述攻擊能夠恢復(fù)其中80 bit信息，剩下的48 bit密鑰信息可通過窮盡搜索得到。故總的時(shí)間復(fù)雜度為293.97+248≈293.97次6輪算法加密。

4 結(jié)果對比

本文通過構(gòu)造Robin算法新的4輪不可能差分區(qū)分器，利用輪密鑰之間的關(guān)系，攻擊了6輪Robin算法，攻擊的數(shù)據(jù)復(fù)雜度為2118.8個(gè)選擇明文，時(shí)間復(fù)雜度為293.97次6輪算法加密。該結(jié)果與已有不可能差分攻擊結(jié)果的比較如表1所示，表中“—”表示無。從表1可以看出，在區(qū)分器構(gòu)造方面，與文獻(xiàn)[17]相同，本文構(gòu)造的區(qū)分器同樣達(dá)到了4輪，解決了區(qū)分器構(gòu)造中的線性層信息利用問題。但是本文構(gòu)造的區(qū)分器形式與文獻(xiàn)[17]不同，這意味著在密鑰恢復(fù)階段對應(yīng)的輪密鑰不同；在算法攻擊方面，與文獻(xiàn)[17]相比，本文同樣達(dá)到了6輪的攻擊輪數(shù)，但是本文通過充分挖掘輪密鑰之間的關(guān)系，解決了文獻(xiàn)[17]中輪密鑰信息利用不充分的問題。通過建立輪密鑰之間的線性關(guān)系，使得在攻擊的過程中，猜測的輪密鑰量減少，攻擊所需的復(fù)雜度降低。具體來說，本文攻擊所需的數(shù)據(jù)復(fù)雜度略低，時(shí)間復(fù)雜度約為文獻(xiàn)[17]的1/256，較大程度地降低了不可能差分攻擊所需的時(shí)間復(fù)雜度。

表1 Robin算法不可能差分攻擊總結(jié)

5 結(jié)束語

本文主要研究了Robin算法的不可能差分性質(zhì)。通過中間相錯(cuò)技術(shù)構(gòu)造了一條新的4輪不可能差分區(qū)分器，該區(qū)分器涉及到的輪密鑰之間存在線性關(guān)系，利用該線性關(guān)系，在密鑰恢復(fù)階段，相比文獻(xiàn)[17]能夠少猜測1個(gè)字節(jié)的輪密鑰。本文的攻擊結(jié)果相比已有最好結(jié)果，主要改進(jìn)了其時(shí)間復(fù)雜度，使得它約為已有最好結(jié)果的2?8。

目前關(guān)于Robin算法的不可能差分構(gòu)造還沒有利用到非線性組件S盒的具體細(xì)節(jié)。下一步通過研究非線性組件的信息，希望構(gòu)造更長輪數(shù)的區(qū)分器，進(jìn)而改進(jìn)其不可能差分攻擊結(jié)果。此外，Robin算法與韓國標(biāo)準(zhǔn)算法ARIA相似，希望通過對Robin算法的研究，能夠進(jìn)一步提高對ARIA算法的安全性分析結(jié)果。