陳懷鳳
(中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所,北京 100083)
分組密碼算法是對(duì)稱(chēng)密碼算法中一種,主要用于對(duì)信息進(jìn)行機(jī)密性保護(hù),例如當(dāng)前最為世人所熟知的高級(jí)加密標(biāo)準(zhǔn)AES[1]。最近幾年,隨著物聯(lián)網(wǎng)的快速發(fā)展,無(wú)線(xiàn)射頻技術(shù)(RFID)和傳感器網(wǎng)絡(luò)(WSNs)等應(yīng)用場(chǎng)景大幅增加,適于在此類(lèi)資源受限環(huán)境中進(jìn)行信息加密保護(hù)的輕量級(jí)密碼算法吸引了廣大密碼學(xué)者的注意力,許多輕量級(jí)的分組密碼算法也被設(shè)計(jì)出來(lái),例如PRESENT、LED、LBlock、Piccolo、Simon、Speck等。目前,關(guān)于“輕量”沒(méi)有嚴(yán)格明確的定義,一般情況下是指算法的實(shí)現(xiàn)很“小”,也就是占有很小的面積。除了面積外,設(shè)計(jì)人員也會(huì)考慮一些其他的準(zhǔn)則,例如算法的吞吐量、各種平臺(tái)的普適性、功率、能耗、延時(shí)等等。
本文從最近幾年提出的輕量級(jí)分組密碼算法出發(fā),分析當(dāng)前階段輕量級(jí)分組密碼算法的設(shè)計(jì)準(zhǔn)則與方法,為新的輕量級(jí)分組密碼算法的設(shè)計(jì)提供參考。
替換-置換結(jié)構(gòu)(SPN)和Feistel結(jié)構(gòu)是設(shè)計(jì)分組密碼算法的兩種主要結(jié)構(gòu),輕量級(jí)分組密碼算法方面同樣如此,在具體設(shè)計(jì)時(shí),算法的某些組件也可能是利用SPN或者Feistel結(jié)構(gòu)進(jìn)行設(shè)計(jì),形成嵌套結(jié)構(gòu)。
(1)PRESENT
PRESENT算法[2]在CHES’07上被提出,是與AES差異較大的SPN結(jié)構(gòu)算法,其線(xiàn)性變換是面向比特進(jìn)行操作的,而非以往常用的面向字節(jié)的變換,非線(xiàn)性層采用4比特S盒。該算法已被國(guó)際標(biāo)準(zhǔn)化組織(ISO)標(biāo)準(zhǔn)化[3]。
(2)LED
LED算法[4]在CHES’11上被提出,是基于AES的框架設(shè)計(jì)的64比特分組長(zhǎng)度的輕量級(jí)分組密碼算法,每一輪包括常數(shù)加、S盒替換、行移位、列混合,每四輪組成一步,進(jìn)行一次密鑰加??烧J(rèn)為其不存在密鑰擴(kuò)展算法,128比特密鑰分為兩個(gè)64比特長(zhǎng)度的子密鑰輪流與每一步的狀態(tài)進(jìn)行異或。
(3)PRINCE
PRINCE算法[5]在ASIACRYPT’12上被提出,前5輪與后5輪的輪常數(shù)具有簡(jiǎn)單的代數(shù)關(guān)系,除此之外是互逆的操作。該算法無(wú)密鑰擴(kuò)展算法,一部分用作白化密鑰,另一部分作為子密鑰直接與輪常數(shù)和輪狀態(tài)進(jìn)行異或,具有α-反射性,即以密鑰k的加密運(yùn)算等價(jià)于以k⊕α的解密運(yùn)算。
(4)ZORRO
ZORRO算法[6]在CHES’13上被提出,是借鑒了AES和LED的設(shè)計(jì)思路,每一輪包括S盒替換(只對(duì)其中4個(gè)nibble進(jìn)行)、常數(shù)加、行移位、列混合、密鑰加,該算法像LED一樣沒(méi)有密鑰擴(kuò)展算法,主密鑰分為64比特長(zhǎng)的子密鑰按輪進(jìn)行異或。
(5)Fantomas/Robin
Fantomas/Robin算法[7]在FSE’14上被提出,這兩個(gè)算法是屬于“LS設(shè)計(jì)”,狀態(tài)表示為s×l的矩陣,非線(xiàn)性層對(duì)每一列進(jìn)行s比特的S盒替換,線(xiàn)性層則對(duì)每一行進(jìn)行l(wèi)比特的線(xiàn)性變換,利用bit-slice技術(shù)進(jìn)行S盒快速實(shí)現(xiàn)。
(6)PRIDE
PRIDE算法[8]在CRYPTO’14上被提出,主要針對(duì)SPN結(jié)構(gòu)的線(xiàn)性層進(jìn)行優(yōu)化,在8比特微處理器上用盡可能少的指令實(shí)現(xiàn)算法,采用對(duì)合的S盒來(lái)降低加密和解密的差異性,也可利用bit-slice技術(shù)快速實(shí)現(xiàn)。密鑰分成白化密鑰和子密鑰,子密鑰只在部分字節(jié)上異或常數(shù),然后與每一輪狀態(tài)進(jìn)行異或。
(7)Midori
Midori算法[9]在ASIACRYPT’15上被提出,包括64比特和128比特兩種分組長(zhǎng)度版本,其基本結(jié)構(gòu)與AES類(lèi)似,也是包括S盒替換、行移位、列混合,密鑰擴(kuò)展算法極為簡(jiǎn)單,以128比特版本為例,密鑰與輪常數(shù)異或形成各輪的子密鑰,與每一輪狀態(tài)進(jìn)行異或。
(8)Rectangle
Rectangle[10]也是基于bit-slice技術(shù)設(shè)計(jì)的SPN結(jié)構(gòu)的輕量級(jí)分組密碼算法,狀態(tài)表示成4×16的矩陣。非線(xiàn)性操作為對(duì)每一列進(jìn)行4比特S盒替換,線(xiàn)性層則是對(duì)每一行進(jìn)行行循環(huán)移位,各行移位常數(shù)不同,其密鑰擴(kuò)展算法采用廣義Feistel結(jié)構(gòu)。
(9)SKINNY/MANTIS
SKINNY算法族[11]在CRYPTO’16上被提出,是一族可調(diào)的輕量級(jí)分組密碼算法,每一輪包括S盒替換、常數(shù)加、密鑰加、行移位、列混合,該算法使用TWEAKEY結(jié)構(gòu),輸入包括明文分組、tweak和密鑰,該算法利用MILP(混合整數(shù)線(xiàn)性編程)技術(shù)給出了差分路徑下活性S盒個(gè)數(shù)的界。MANTIS是SKINNY的低延時(shí)變種算法。
(10)SPARX
SPARX算法[12]在ASIACRYPT’16上被提出,整體采用SPN結(jié)構(gòu),但是其非線(xiàn)性層是采用模加、循環(huán)移位和異或操作構(gòu)造的ARX結(jié)構(gòu)算法,具體為三輪或四輪SPECK輪函數(shù)。其密鑰引入時(shí)覆蓋整個(gè)狀態(tài),而不是一半。該算法第一次對(duì)基于ARX結(jié)構(gòu)的分組密碼算法給出了針對(duì)差分特征和線(xiàn)性特征的可證明安全界。
(1)HIGHT
HIGHT算法[13]在CHES’06上被提出,是采用廣義Feistel結(jié)構(gòu)的ARX類(lèi)算法,具有8個(gè)分支,非線(xiàn)性操作通過(guò)模加運(yùn)算引入,線(xiàn)性變換有兩個(gè),都是將一個(gè)輸入的3個(gè)循環(huán)移位進(jìn)行異或求和。通過(guò)密鑰擴(kuò)展算法生成白化密鑰和輪密鑰,各種密鑰通過(guò)模加運(yùn)算和異或運(yùn)算引入。
(2)LBlock
LBlock算法[14]在ACNS’16上被提出,分組長(zhǎng)度為64比特,采用平衡Feistel結(jié)構(gòu),在其中一個(gè)分支上進(jìn)行循環(huán)移位操作,F(xiàn)函數(shù)則采用SPN結(jié)構(gòu)。F函數(shù)中采用4比特S盒,按nibble進(jìn)行位置變換完成線(xiàn)性操作。其密鑰擴(kuò)展算法引入了兩個(gè)新的4比特S盒。
(3)Piccolo
Piccolo算法[15]在CHES’11上被提出,分組長(zhǎng)度為64比特,采用廣義Feistel結(jié)構(gòu),具有4個(gè)分支。與其他廣義Feistel結(jié)構(gòu)算法不同,該算法的幾個(gè)分支之間具有較復(fù)雜的線(xiàn)性變換。其F函數(shù)采用SPN結(jié)構(gòu),其4比特S盒在具有合適的非線(xiàn)性度盒差分分布的密碼學(xué)特性的基礎(chǔ)上,硬件占用特別低。
(4)TWINE
TWINE算法[16]在2011年被提出,分組長(zhǎng)度為64比特,采用廣義Feistel結(jié)構(gòu),具有16個(gè)分支。其F函數(shù)是4比特狀態(tài)異或密鑰后過(guò)一個(gè)4比特S盒替換,線(xiàn)性變換主要是16個(gè)分支較為復(fù)雜的位置置換。
(5)LEA
LEA算法[17]在WISA’13上被提出,分組長(zhǎng)度為128比特,是采用廣義Feistel結(jié)構(gòu)的ARX類(lèi)算法,具有4個(gè)分支。所有的模加、循環(huán)移位和異或都是面向32比特字進(jìn)行的,密鑰擴(kuò)展算法也同樣采用ARX結(jié)構(gòu)。
(6)SIMON/SPECK
SIMON/SPECK算法[18]在2013年由美國(guó)國(guó)家安全局(NSA)提出,SIMON算法是面向硬件實(shí)現(xiàn)的輕量級(jí)分組密碼算法族,具有10個(gè)版本,采用平衡Feistel結(jié)構(gòu)。其輪函數(shù)特特別簡(jiǎn)單,只使用與、循環(huán)移位和異或操作。SPECK算法是面向軟件實(shí)現(xiàn)的輕量級(jí)分組密碼算法族,采用ARX結(jié)構(gòu),其輪函數(shù)只采用模加、循環(huán)移位和異或操作。設(shè)計(jì)人員并未對(duì)這兩個(gè)算法進(jìn)行安全性說(shuō)明,而是留給廣大密碼學(xué)者進(jìn)行分析。
(7)RoadRunneR
RoadRunneR算法[19]在LightSec’15上被提出,分組長(zhǎng)度為64比特,采用平衡Feistel結(jié)構(gòu)。與LBlock類(lèi)似,其F函數(shù)采用SPN結(jié)構(gòu),類(lèi)似于Fantomas/Robin算法的LS設(shè)計(jì),使用bit-slice技術(shù)實(shí)現(xiàn)S盒,其線(xiàn)性層則類(lèi)似于HIGHT算法,也是幾個(gè)循環(huán)移位的異或和。
(8)SIMECK
SIMECK算法[20]在CHES’15上被提出,是受SIMON算法族啟發(fā)而設(shè)計(jì)的算法族,其輪函數(shù)與SIMON相比,只在循環(huán)移位的位數(shù)上有所不同,以獲得更小的硬件面積。
輕量級(jí)分組密碼算法在設(shè)計(jì)時(shí)主要考慮的是“輕量化”,但除此之外,不同的密碼學(xué)者還有不同的考慮,在本節(jié)將根據(jù)上一節(jié)簡(jiǎn)單介紹的密碼算法,總結(jié)輕量級(jí)分組密碼算法的設(shè)計(jì)考慮的關(guān)鍵點(diǎn)。
本小節(jié)主要介紹密碼學(xué)界對(duì)密碼算法設(shè)計(jì)中“重量”的理解,在文獻(xiàn)[21]中對(duì)此有所介紹。
算法的“重量”一般是指運(yùn)行算法所需要的時(shí)間和空間的資源占用量,可以在兩種不同的環(huán)境中進(jìn)行測(cè)量:硬件環(huán)境和軟件環(huán)境。但是要注意,硬件環(huán)境中的輕量級(jí)算法并不意味著軟件環(huán)境中的輕量級(jí),反之亦然。
2.1.1硬件環(huán)境中的重量
存儲(chǔ)方面主要考慮實(shí)現(xiàn)算法需要的邏輯門(mén)數(shù)量,該量一般使用GE(Gate Equivalence,1GE等價(jià)于一個(gè)與非門(mén))作為單位。時(shí)間效率方面使用吞吐量(Throughput)來(lái)表示,也就是在給定時(shí)鐘頻率下,算法每秒鐘處理的數(shù)據(jù)比特?cái)?shù);包括密鑰擴(kuò)展操作在內(nèi)的延時(shí)也是考慮點(diǎn)之一。對(duì)上述量的評(píng)估比較復(fù)雜,由于各種硬件環(huán)境較多且不同密碼研究人員不同的評(píng)估環(huán)境和方式,很難對(duì)不同密碼研究人員的實(shí)現(xiàn)結(jié)果進(jìn)行合適的比較。
2.1.2軟件環(huán)境中的重量
軟件環(huán)境中的重量包括算法運(yùn)行的時(shí)間復(fù)雜度和存儲(chǔ)復(fù)雜度。時(shí)間復(fù)雜度的一種評(píng)估方式是加密算法(或解密算法)處理1字節(jié)數(shù)據(jù)需要的時(shí)鐘周期數(shù),但是某些特定的應(yīng)用場(chǎng)景中,密鑰擴(kuò)展等間接開(kāi)銷(xiāo)也較大,這種計(jì)算方式不太準(zhǔn)確;另外一種就是考慮算法整體的延時(shí),也就是將所有間接開(kāi)銷(xiāo)都計(jì)算在內(nèi)考慮需要的時(shí)鐘周期數(shù)。存儲(chǔ)復(fù)雜度主要是考慮算法正常運(yùn)行時(shí)占用的RAM空間量,另外,也要考慮算法存儲(chǔ)(例如Flash)占用的空間量。
2.1.3耗電功率
耗電量是軟硬件實(shí)現(xiàn)都要考慮的一個(gè)指標(biāo)。RFID中存在功率限制,或者說(shuō)某些嵌入式設(shè)備是采用電池供電的,在設(shè)計(jì)算法時(shí)應(yīng)當(dāng)要考慮算法運(yùn)行時(shí)的平均耗電量以及相應(yīng)的功率峰值。
在2012年,SAARINEN M J O和ENGELS D W從RFID或輕量化傳感器網(wǎng)絡(luò)的工業(yè)使用方面提出了輕量級(jí)密碼算法應(yīng)該符合的限制和目標(biāo)[22],主要包括以下幾點(diǎn):
(1)算法可在不經(jīng)過(guò)明顯改動(dòng)的條件下,實(shí)現(xiàn)單向可調(diào)的認(rèn)證加密算法、解密算法以及安全的哈希函數(shù)。
(2)各種輸入(包括初始化向量IV、認(rèn)證關(guān)聯(lián)數(shù)據(jù)等)的填充以及操作規(guī)則需明確定義,輸入數(shù)據(jù)比率應(yīng)當(dāng)盡可能小以避免消息的擴(kuò)展操作。
(3)初始化向量IV可以不是nonce(nonce在重用選擇IV攻擊中也是安全的),在各種可能的攻擊模型中,安全強(qiáng)度與密鑰以及狀態(tài)的長(zhǎng)度一致。
(4)硬件實(shí)現(xiàn)應(yīng)當(dāng)?shù)陀? 000門(mén)(GE),該實(shí)現(xiàn)包含加密、解密算法以及相應(yīng)的狀態(tài)存儲(chǔ);在MCU或CPU平臺(tái)上的軟件實(shí)現(xiàn)速度以及大小也應(yīng)在設(shè)計(jì)時(shí)作為指標(biāo)進(jìn)行考慮。
(5)算法應(yīng)當(dāng)有不低于50個(gè)周期的延時(shí),且加密或解密的吞吐量滿(mǎn)足每周期至少輸出1比特。
(6)功率應(yīng)當(dāng)?shù)陀?~10 μW/MHz,相應(yīng)的峰值應(yīng)分別低于3 μW和30 μW,也就是說(shuō)在2 MHz頻率下,峰值應(yīng)當(dāng)?shù)陀?.5~15 μW/MHz。
根據(jù)設(shè)計(jì)準(zhǔn)則,將第1節(jié)中的輕量級(jí)分組密碼算法進(jìn)行簡(jiǎn)單的分類(lèi),主要包括面向軟件輕量化、面向硬件輕量化這兩個(gè)方向進(jìn)行設(shè)計(jì)的算法,部分算法在設(shè)計(jì)者精心選擇密碼組件的前提下,能夠適應(yīng)多種平臺(tái)或者滿(mǎn)足多種目標(biāo),例如低延時(shí)或低功耗。
面向硬件輕量化設(shè)計(jì)的分組密碼算法如下:
(1)PRESENT:非線(xiàn)性層采用4比特S盒,線(xiàn)性層使用簡(jiǎn)單的比特拉線(xiàn)。
(2)LED:采用4比特S盒(PRESENT的S盒),線(xiàn)性變換是特別簡(jiǎn)單的矩陣乘重復(fù)四次。
(3)PRINCE:采用4比特S盒,采用4個(gè)簡(jiǎn)單的小矩陣構(gòu)造大的線(xiàn)性層矩陣。
(4)Midori:Midori64采用4比特S盒,線(xiàn)性層采用的矩陣只有1和0元素,比較簡(jiǎn)單。
(5)Rectangle:采用4比特S盒,使用bit-slice技術(shù)快速實(shí)現(xiàn),線(xiàn)性層由循環(huán)移位和異或組成,利于軟硬件實(shí)現(xiàn)。
(6)SKINNY/MANTIS:SKINNY64采用4比特S盒,線(xiàn)性變換只有循環(huán)移位操作以及簡(jiǎn)單的異或構(gòu)成,該算法的軟件實(shí)現(xiàn)也很有優(yōu)勢(shì)。
(7)HIGHT:面向硬件實(shí)現(xiàn)設(shè)計(jì)的ARX類(lèi)算法,所有運(yùn)算都是以8比特為單位進(jìn)行的,所以也適合8比特軟件平臺(tái)實(shí)現(xiàn)。
(8)LBlock:采用4比特S盒,線(xiàn)性操作包括32比特字的循環(huán)左移8位以及按4比特nibble的置換。
(9)Piccolo:采用廣義Feistel結(jié)構(gòu),4比特S盒,F(xiàn)函數(shù)中的線(xiàn)性操作只有按nibble的拉線(xiàn),分支間使用簡(jiǎn)單的矩陣乘。
(10)TWINE:采用具有16個(gè)分支的廣義Feistel結(jié)構(gòu),4比特S盒,線(xiàn)性變換就是按nibble的拉線(xiàn)操作。
(11)SIMON、SIMECK:只有循環(huán)移位、與和異或操作,硬件占用極低。
面向軟件輕量化設(shè)計(jì)的分組密碼算法如下:
(1)ZORRO:采用的8比特S盒是利用更小的S盒組合構(gòu)造而成的。
(2)Fantomas/Robin:采用8比特S盒(利用小S盒構(gòu)造),利用bit-slice技術(shù)快速實(shí)現(xiàn),設(shè)計(jì)者認(rèn)為該算法硬件實(shí)現(xiàn)也較有優(yōu)勢(shì)。
(3)PRIDE:面向8比特位寬單片機(jī)的軟件實(shí)現(xiàn)設(shè)計(jì),bit-slice技術(shù)實(shí)現(xiàn)16個(gè)并行的4比特S盒,并選擇使用極少指令數(shù)的線(xiàn)性變換操作。
(4)SPARX:面向軟件輕量化實(shí)現(xiàn)設(shè)計(jì),采用ARX結(jié)構(gòu)。
(5)LEA:面向軟件快速實(shí)現(xiàn)設(shè)計(jì),采用ARX結(jié)構(gòu),以32比特為單位進(jìn)行各種運(yùn)算。
(6)SPECK:面向軟件快速實(shí)現(xiàn)設(shè)計(jì),采用ARX結(jié)構(gòu)。
(7)RoadRunneR:面向8比特處理器的軟件輕量化實(shí)現(xiàn)設(shè)計(jì),具有較低的代碼量,同時(shí)吞吐量較高。采用可bit-slice快速實(shí)現(xiàn)的4比特S盒以及具有較少代碼量的線(xiàn)性操作。
3.3.1硬件輕量化的分組算法特點(diǎn)與設(shè)計(jì)思路
通過(guò)總結(jié)以上可以發(fā)現(xiàn),面向硬件的輕量級(jí)分組密碼算法具有以下特點(diǎn):
(1)非線(xiàn)性運(yùn)算多使用4比特S盒或者不使用S盒。這主要是4比特S盒的代數(shù)表示形式比較簡(jiǎn)單,占用的門(mén)數(shù)較少,例如LBlock選取的S盒全都可以只使用22個(gè)GE實(shí)現(xiàn)。
(2)存在多個(gè)S盒時(shí),使用相同的S盒,利于算法的多種實(shí)現(xiàn)方式,比如并行以提高加密速率,或著串行重用S盒以降低資源占用。
(3)線(xiàn)性層比較簡(jiǎn)單,多使用按nibble的位置置換或是由簡(jiǎn)單矩陣構(gòu)成的復(fù)雜矩陣進(jìn)行矩陣乘運(yùn)算。位置置換在硬件中幾乎不占用資源,復(fù)雜矩陣在硬件中可以通過(guò)簡(jiǎn)單矩陣的重用來(lái)實(shí)現(xiàn),資源占用低。
(4)使用SPN結(jié)構(gòu)的輕量級(jí)分組密碼算法其加密與解密的操作一般是不同的,這會(huì)在實(shí)現(xiàn)解密運(yùn)算時(shí),增加許多額外的資源,但考慮到各種工作模式的存在以及實(shí)際使用中加密和解密在設(shè)備中使用的不對(duì)稱(chēng)性(只進(jìn)行加密或解密),這一問(wèn)題可以通過(guò)相應(yīng)的協(xié)議來(lái)解決。不然的話(huà),就需要非常細(xì)心地選擇各種密碼組件,例如對(duì)合的S盒或像PRINCE的α-反射結(jié)構(gòu)。
(5)Feistel結(jié)構(gòu)的加密和解密運(yùn)算結(jié)構(gòu)相同,在實(shí)現(xiàn)時(shí)不會(huì)增加太多額外資源。
(6)密鑰擴(kuò)展算法要簡(jiǎn)單,可以重用密碼算法輪函數(shù)中的組件,有些算法甚至無(wú)密鑰擴(kuò)展的過(guò)程,直接與輪常數(shù)異或后再作用到中間狀態(tài)上,例如LED、PRINCE等。
3.3.2軟件輕量化的分組算法特點(diǎn)與設(shè)計(jì)思路
通過(guò)總結(jié)以上可以發(fā)現(xiàn),面向軟件的輕量級(jí)分組密碼算法具有以下特點(diǎn):
(1)使用4比特S盒的密碼算法多利用bit-slice技術(shù)提升加密效率,這需要在選擇S盒時(shí)注意S盒代數(shù)實(shí)現(xiàn)時(shí)的指令個(gè)數(shù)。
(2)ARX類(lèi)的算法適合軟件快速實(shí)現(xiàn),加法、異或、循環(huán)移位操作適合在CPU或MCU中通過(guò)一條(或很少的)指令實(shí)現(xiàn)。
(3)循環(huán)移位常數(shù)選擇8或者8的倍數(shù),適合在8比特及其以8倍數(shù)為位寬的處理器上快速執(zhí)行。
(4)SPN結(jié)構(gòu)或者Feistel結(jié)構(gòu)在硬件實(shí)現(xiàn)中的優(yōu)缺點(diǎn)在軟件方面也有類(lèi)似的問(wèn)題,主要體現(xiàn)在代碼量以及執(zhí)行效率方面。
(5)密鑰擴(kuò)展算法要簡(jiǎn)單,可以重用密碼算法輪函數(shù)中的組件以降低代碼量。
本文簡(jiǎn)單介紹了當(dāng)前階段輕量級(jí)分組密碼算法的設(shè)計(jì)特點(diǎn),在給出密碼算法“重量”理解的基礎(chǔ)上,分析了輕量級(jí)密碼算法非線(xiàn)性組件與線(xiàn)性組件的特點(diǎn),并從結(jié)構(gòu)以及組件等方面給出了設(shè)計(jì)面向硬件輕量化或軟件輕量化分組密碼算法的設(shè)計(jì)思路,為新輕量級(jí)分組密碼算法的設(shè)計(jì)提供參考。