典型密碼結(jié)構(gòu)的不可能差分區(qū)分器研究*

劉 健，畢鑫杰，李艷俊，，金 達(dá)

(1.中國(guó)電子科技集團(tuán)公司第十五研究所 信息產(chǎn)業(yè)信息安全測(cè)評(píng)中心，北京 100083；2.北京電子科技學(xué)院 密碼科學(xué)與技術(shù)系，北京 100070)

0 引言

1949年Shannon發(fā)表了經(jīng)典論文“Communication Theory of Secrecy System”[1]，該文從抵抗攻擊的角度出發(fā)，提出了加密算法的“混淆”和“擴(kuò)散”準(zhǔn)則?；煜蛿U(kuò)散成功地實(shí)現(xiàn)分組密碼明文、密鑰和密文之間呈現(xiàn)多種偽隨機(jī)性質(zhì)，因而成為現(xiàn)代分組密碼設(shè)計(jì)的重要原則之一。進(jìn)一步，Shannon還在文章中介紹了代替(Substitution)-置換(Permutation)網(wǎng)絡(luò)(簡(jiǎn)稱(chēng)SPN)，其主要是基于代替S盒和P置換兩種最基本組件的密碼運(yùn)算，又叫做混合變換(mixing transformations)。不同的混合變換組合成了不同的整體結(jié)構(gòu)，以實(shí)現(xiàn)“混淆”和“擴(kuò)散”的目標(biāo)。目前分組密碼中比較主流的整體結(jié)構(gòu)有Feistel結(jié)構(gòu)、SP結(jié)構(gòu)、廣義Feistel結(jié)構(gòu)、MISTY結(jié)構(gòu)等。

隨著分組密碼設(shè)計(jì)與分析的發(fā)展，一方面算法結(jié)構(gòu)方面的研究越來(lái)越細(xì)化，比如Feistel-SP組合結(jié)構(gòu)、ARX結(jié)構(gòu)、基于邏輯單元設(shè)計(jì)的整體結(jié)構(gòu)等[2-4]；同時(shí)，以往主要用于分組密碼的整體結(jié)構(gòu)越來(lái)越廣泛地應(yīng)用于網(wǎng)絡(luò)空間安全領(lǐng)域的數(shù)據(jù)快速加密認(rèn)證體制中，如序列密碼設(shè)計(jì)、Hash函數(shù)設(shè)計(jì)以及認(rèn)證加密算法設(shè)計(jì)等，最具代表性的是2018年NIST發(fā)起的輕量級(jí)認(rèn)證算法征集活動(dòng)，第一輪候選算法廣泛采用了這些整體結(jié)構(gòu)。另一方面對(duì)結(jié)構(gòu)的安全性分析和證明也有了豐富的成果[5-9]。與差分分析、線性分析相比，不可能差分區(qū)分器基于截?cái)嗖罘謽?gòu)建，對(duì)于差分性能較好的算法攻擊效果更好，如對(duì)CLEFIA的攻擊可以達(dá)到13輪[10]，對(duì)Camellia的攻擊最長(zhǎng)可以達(dá)到14輪[11]；然而，密碼學(xué)者們更多地關(guān)注具體密碼算法的不可能差分安全性，對(duì)于一般的結(jié)構(gòu)安全性分析證明較少，以至于新的密碼算法設(shè)計(jì)會(huì)出現(xiàn)結(jié)構(gòu)方面的安全隱患，比如2019年全國(guó)密碼設(shè)計(jì)競(jìng)賽中候選算法TASS1[12]，基于廣義Feistel結(jié)構(gòu)設(shè)計(jì)，并且采用了隨機(jī)密鑰池保證安全性，但是由于未對(duì)整體結(jié)構(gòu)進(jìn)行評(píng)估，導(dǎo)致了存在全輪不可能差分區(qū)分器[13]。因此，隨著信息安全技術(shù)及其應(yīng)用的快速發(fā)展，不管是現(xiàn)在還是將來(lái)，密碼結(jié)構(gòu)安全始終是密碼算法安全的首要保障。

本文對(duì)Feistel結(jié)構(gòu)、SP結(jié)構(gòu)、廣義Feistel結(jié)構(gòu)、MISTY結(jié)構(gòu)四種主要整體結(jié)構(gòu)進(jìn)行了介紹和研究，重點(diǎn)對(duì)廣義Feistel結(jié)構(gòu)的TYPE-I型、TYPE-II型和TYPE-III型進(jìn)行了詳細(xì)分析，基于這些結(jié)構(gòu)的特點(diǎn)構(gòu)建了不可能差分區(qū)分器，進(jìn)一步給出了詳細(xì)證明過(guò)程。本文研究希望能夠?yàn)榫W(wǎng)絡(luò)空間安全領(lǐng)域分組密碼、序列密碼、Hash函數(shù)、認(rèn)證加密等對(duì)稱(chēng)密碼結(jié)構(gòu)的設(shè)計(jì)與分析提供參考。

1 Feistel結(jié)構(gòu)

20世紀(jì)60年代Horst Feistel設(shè)計(jì)出基于SP結(jié)構(gòu)的LUCIFER體制，在該體制中沒(méi)有給出具體S盒，而且加解密不同，需要消耗更多的硬件電路。后來(lái)Horst Feistel由“流水線”工作模式想到每次只加密一半的明文數(shù)據(jù)，進(jìn)而設(shè)計(jì)了加解密相似的結(jié)構(gòu)，并以Feistel命名。1967年公開(kāi)發(fā)表的幾篇技術(shù)報(bào)告為Feistel密碼結(jié)構(gòu)的安全性研究奠定了基礎(chǔ)。加解密相似是Feistel型密碼的一個(gè)實(shí)現(xiàn)優(yōu)點(diǎn)，但其每輪只對(duì)一部分?jǐn)?shù)據(jù)進(jìn)行處理，需要兩輪甚至多輪才能改變輸入的每一個(gè)比特。基于Feistel結(jié)構(gòu)的代表算法有數(shù)據(jù)加密標(biāo)準(zhǔn)DES、日本分組密碼標(biāo)準(zhǔn)Camellia等。

1.1 Feistel結(jié)構(gòu)描述

定義1Feistel結(jié)構(gòu)是一種典型的迭代結(jié)構(gòu)，它能夠?qū)崿F(xiàn)擴(kuò)散與混亂，構(gòu)成安全強(qiáng)度高的密碼算法。假設(shè)圈函數(shù)為QK，輸入為X0，X1，一輪加密可以表示為：

Feistel結(jié)構(gòu)如圖1所示。函數(shù)F不一定可逆，可由一些非線性組件和線性組件構(gòu)成，起到擴(kuò)散和混淆的效果。

圖1 Feistel結(jié)構(gòu)

圈變換QK可以被分解為t?π，這 里π由π(X0，X1)=(X0⊕FK(X1)，X1)定義。容易驗(yàn)證π是恒等變換，即π是它自身的逆，也稱(chēng)為對(duì)合函數(shù)；t是交換函數(shù)，也是對(duì)合的。容易得到圈函數(shù)QK逆π?t。

將Feistel結(jié)構(gòu)迭代r輪，當(dāng)最后一輪去掉交換時(shí)解密過(guò)程與加密過(guò)程一樣，這是因?yàn)镋K=πr?t…?π2?t?π1，=π1?t…?πr-1?t?πr。所以解密時(shí)只需將密文作為輸入，輪子密鑰的次序與加密過(guò)程相反。

1.2 不可能差分區(qū)分器

性質(zhì)1假設(shè)函數(shù)F為隨機(jī)置換，則Feistel結(jié)構(gòu)存在5輪不可能差分區(qū)分器[14]。

如圖2所示，對(duì)于一個(gè)5輪Feistel結(jié)構(gòu)，假設(shè)α為非零差分，那么當(dāng)輸入差分為(0，α)時(shí)，輸出差分為(0，α)的概率為0。證明過(guò)程主要利用了F為置換的特點(diǎn)，詳細(xì)過(guò)程見(jiàn)文獻(xiàn)[14]。

圖2 Feistel的5輪不可能差分區(qū)分器

2 SP結(jié)構(gòu)

根據(jù)混淆-擴(kuò)散原則，SP結(jié)構(gòu)設(shè)計(jì)得非常清晰，由S盒層和P擴(kuò)散層組合生成。S盒層一般被稱(chēng)為混淆層，主要起混淆作用；P置換一般組成擴(kuò)散層，主要起擴(kuò)散作用。在明確S盒和P置換的某些密碼指標(biāo)后，設(shè)計(jì)者能估計(jì)SP結(jié)構(gòu)密碼抵抗差分分析和線性分析的能力。SP結(jié)構(gòu)與Feistel結(jié)構(gòu)相比，可以得到更快速的擴(kuò)散，但是SP密碼的加/解密通常不相似，若要相似需采用逆等函數(shù)作為組件。SP結(jié)構(gòu)代表算法有國(guó)際加密標(biāo)準(zhǔn)AES、韓國(guó)標(biāo)準(zhǔn)ARIA、2019競(jìng)選勝出算法uBlock[15]等。

2.1 SP結(jié)構(gòu)描述

定義2假設(shè)SP結(jié)構(gòu)每輪的圈函數(shù)包含三層變換：先是將mn比特明文數(shù)據(jù)分為n個(gè)子塊，每塊含m比特，即S層為n個(gè)S盒并置；然后置換層P為線性變換。S盒是m比特隨機(jī)置換：，設(shè)S盒輸入為Xi⊕Ki，輸出為Yi；P是線性變換：；最后輸出的Zi與輪密鑰Ki運(yùn)算：Zi⊕Ki，1≤i≤n。圈函數(shù)用公式描述為：

S盒層變換：Yi=S(Xi⊕Ki)，1≤i≤n；P層變換：[Z1，Z2，…，Zn]T=P[Y1，Y2，…，Yn]T。

圖3所示為SP結(jié)構(gòu)示意圖。

圖3 SP結(jié)構(gòu)

SP結(jié)構(gòu)中，由于最后一輪的線性變換沒(méi)有加強(qiáng)密碼性能，同時(shí)為了減小加解密變換的差異，因此在設(shè)計(jì)迭代結(jié)構(gòu)時(shí)通常將最后一輪的線性變換省略掉。這種SP結(jié)構(gòu)既可以用來(lái)構(gòu)建分組密碼算法的整體結(jié)構(gòu)，例如AES、uBlock；也可以作為Feistel整體結(jié)構(gòu)中圈函數(shù)的部件，例如SM4、CLEFIA、Camellia等算法。

2.2 不可能差分區(qū)分器

性質(zhì)2對(duì)于SP結(jié)構(gòu)密碼算法，若S盒為隨機(jī)置換，那么無(wú)論P(yáng)取哪一種線性變換，必存在2輪不可能差分區(qū)分器[16]。

性質(zhì)3若擴(kuò)散層P對(duì)應(yīng)系數(shù)矩陣中的元素含0，則基于字節(jié)(半字節(jié))設(shè)計(jì)的SP結(jié)構(gòu)存在3輪不可能差分區(qū)分器[16]。

采用二元域上矩陣作為擴(kuò)散層P，則矩陣中必有零元素出現(xiàn)。根據(jù)這個(gè)性質(zhì)容易推出3輪不可能差分區(qū)分器，如圖4所示。

圖4 SP結(jié)構(gòu)3輪不可能差分路徑

在實(shí)際使用的分組密碼算法中，擴(kuò)散層P通常由多級(jí)擴(kuò)散構(gòu)成，結(jié)合S盒差分分布表，通常存在更多輪數(shù)的區(qū)分器，如AES、ARIA、uBlock都存在4輪不可能差分區(qū)分器[16]。

3 廣 義Feistel結(jié)構(gòu)

廣 義Feistel結(jié) 構(gòu)(Generalized Feistel Structure，GFS)[17]是Feistel結(jié)構(gòu)的推廣，特點(diǎn)是對(duì)分組再進(jìn)行小分塊處理，使同時(shí)處理的分塊長(zhǎng)度較小。目前出現(xiàn)的主要有TYPE-I、TYPE-II、TYPE-III三種結(jié)構(gòu)。2010年FSE會(huì)議上Suzaki等人基于圖論的知識(shí)對(duì)TYPE-II型進(jìn)行了改進(jìn)，減小了全擴(kuò)散的輪數(shù)[18]。

3.1 廣義Feistel結(jié)構(gòu)描述

基于TYPE-I結(jié)構(gòu)設(shè)計(jì)的分組密碼有CAST[19]、SMS4等；基于TYPE-II結(jié)構(gòu)設(shè)計(jì)的分組密碼有CLEFIA等；基于TYPE-III結(jié)構(gòu)設(shè)計(jì)的分組密碼有MARS[20]、輕量級(jí)LEA[21]等；基于改進(jìn)TYPE-II結(jié)構(gòu)設(shè)計(jì)的分組密碼有輕量級(jí)LBlock、TWINE[22]等。下面對(duì)TYPE-I、TYPE-II和TYPE-III型結(jié)構(gòu)依次進(jìn)行介紹和不可能差分區(qū)分器證明。

定義3假設(shè)輸入一組明文分成n個(gè)子塊，即X0，X1，…，Xn-1，定義一個(gè)函數(shù)FK(不要求可逆)，則圈函數(shù)可以表示成：

由這種方式獲得的函數(shù)被稱(chēng)為T(mén)YPE-I型結(jié)構(gòu)，其結(jié)構(gòu)如圖5所示。

圖5 TYPE-I型結(jié)構(gòu)

TYPE-I型結(jié)構(gòu)迭代r輪后，加密變換EK=π1，r??π1，1，解密變換?…?π1，r-1??π1，r，不僅要變換輪密鑰順序，還需改變循環(huán)移位的方向。

定義4假設(shè)輸入一組明文分成n個(gè)子塊，即X0，X1，…，Xn-1，定義一個(gè)函數(shù)FK(一般情況下是雙射)，則TYPE-II圈函數(shù)可以表示成：

圖6 TYPE-II型結(jié)構(gòu)

TYPE-II型結(jié)構(gòu)迭代r輪后，加密變換EK=π2，r?，解密變換?…，不僅要變換輪密鑰順序，還需改變循環(huán)移位的方向。

定義5假設(shè)輸入一組明文分成n個(gè)子塊，即X0，X1，…，Xn-1，定義一個(gè)函數(shù)FK(一般情況下是雙射)，則圈函數(shù)可以表示成：

其中t=n-2，稱(chēng)由這種方式獲得的函數(shù)為T(mén)YPE-III結(jié)構(gòu)。

基于TYPE-III設(shè)計(jì)的分組密碼相對(duì)較少，MARS和LEA算法基于這種結(jié)構(gòu)設(shè)計(jì)。

圖7 TYPE-III型結(jié)構(gòu)

TYPE-III型結(jié)構(gòu)迭代r輪后，加密變換EK=π3，r?，解密變換?…?，不僅要變換輪密鑰順序，還需改變循環(huán)移位的方向。

3.2 不可能差分區(qū)分器

性質(zhì)4設(shè)函數(shù)F是隨機(jī)置換，則n輪全擴(kuò)散的TYPE-I型分組密碼必有n2+n-1輪不可能差分區(qū)分器。

證明：TYPE-I型分組密碼擴(kuò)散較慢，所以以表的形式給出各輪輸入差分模式。如表1所示，對(duì)于n分塊的TYPE-I型結(jié)構(gòu)輸入差分為[0，0，0，…，0，0，a]，經(jīng)過(guò)n輪加密之后為[ΔF(a)，0，0，…，0，0，a]，ΔF(a)為非零值；再經(jīng)過(guò)n-1輪，即在第2n-1輪輸入處差分為，，因?yàn)楱抋=?，差分值 不 確定，而為非零，所以記作[?，*，*，…，*]；在加密方向繼續(xù)推導(dǎo)，在第2n+1輪輸出處差分模式為[?，*，*，…，⊕a，?]。其中“*”表示非零子塊。

表1 TYPE-I型結(jié)構(gòu)加密方向差分模式

如表2所示，假設(shè)若干輪加密后輸出差分模式為[a，0，0，…，0，0，0]，解密方向經(jīng)過(guò)1輪輸出[0，a，0，…，0，0，0]，容易推導(dǎo)出n2-n-2輪后輸出為[?，?，?，…，?，a，?]，共解密n2-n-2輪。與加密方向第2n+1輪輸出處差分模式[?，*，*，…，⊕a，?]發(fā)生矛盾，所以共有n2-n-2+2n+1=n2+n-1輪不可能差分區(qū)分器，如圖8所示。

圖8 TYPE-I型不可能差分區(qū)分器

表2 TYPE-I型結(jié)構(gòu)解密方向差分模式

例如，當(dāng)分塊為3時(shí)，容易推導(dǎo)不可能差分區(qū)分器輪數(shù)為8；當(dāng)分塊為4時(shí)，如MARS-256算法，容易驗(yàn)證其區(qū)分器輪數(shù)大于15。

性質(zhì)5設(shè)函數(shù)F是隨機(jī)置換，則n輪全擴(kuò)散的TYPE-II型分組密碼必有2n+1輪不可能差分區(qū)分器。

證明：n輪全擴(kuò)散的TYPE-II型結(jié)構(gòu)分塊為n，下面從加密方向和解密方向進(jìn)行推導(dǎo)。

在加密方向，假設(shè)n個(gè)子塊X0，X1，…，Xn-1的輸入差分模式為[0，0，…，0，a]，即Xn-1處差分非零，其余子塊差分全為0，經(jīng)過(guò)n輪變換之后輸出差分模式為[*，*，…，*，a]。

在解密方向，假設(shè)第2n+1輪輸出的n個(gè)子塊[X0，X1，…，Xn-1]差分模式為[0，0，…，a，0]，即Xn-2處差分非零，其余子塊差分全為0，經(jīng)過(guò)n輪解密變換之后得到第n+1輪輸出差分模式為[*，*，…，a，*]。

由于第n+1輪輸入Xn-2的差分非0，F(xiàn)k是置換，因此此處出現(xiàn)矛盾，即不可能出現(xiàn)Fk(Xn-2)⊕a=a。圖9為2n+1輪不可能差分區(qū)分器。

圖9 TYPE-II型不可能差分區(qū)分器

性質(zhì)6設(shè)函數(shù)Fi是由密鑰控制的隨機(jī)置換，則n個(gè)子塊的TYPE-III型分組密碼必有n+2輪不可能差分區(qū)分器。

證明：如圖10所示，假設(shè)輸入差分模式為[0，0，…，0，a]，經(jīng)過(guò)2輪加密變換為[0，0，…，a，ΔFn(a)，0]，由于ΔFn(a)為非零，可以記為“*”，n輪加密之后第n+1輪輸入為[?，?，…，?，*，a]；假設(shè)第n+2輪輸出為[0，…，0，a，0，0]，解密1輪并經(jīng)過(guò)循環(huán)移塊之后得到[*，0，…，0，0，a]，由于Fn為隨機(jī)置換，因此非零差分“*”輸入，輸出差分必定非零，即Fn(*)⊕a≠a，此處矛盾。

圖10 TYPE-III型不可能差分區(qū)分器

因此，n個(gè)子塊的TYPE-III型分組密碼必有n+2輪不可能差分區(qū)分器。

4 MISTY結(jié)構(gòu)

MISTY結(jié)構(gòu)[23]由日本著名密碼學(xué)家Mitsuru Matsui等人于1995年提出，基于此結(jié)構(gòu)系列算法被設(shè)計(jì)出，包含MISTY1、MISTY2和KASUMI，其中KASUMI算法是基于MISTY1算法的改進(jìn)版本，是第三代移動(dòng)通信技術(shù)中的一種核心加密算法。

4.1 MISTY結(jié)構(gòu)描述

定義6假設(shè)輸入明文P為X0，X1，密鑰為K，輸入函數(shù)為F，則MISTY圈函數(shù)可以表示為：

如圖11所示，MISTY結(jié)構(gòu)類(lèi)似于Feistel，函數(shù)F只對(duì)輸入的一半數(shù)據(jù)加密。

圖11 MISTY結(jié)構(gòu)

4.2 不可能差分區(qū)分器

性質(zhì)7當(dāng)Fi函數(shù)(1≤i≤4)為隨機(jī)置換時(shí)，MISTY至少存在4輪不可能差分區(qū)分器[23]。

如圖12所示，假設(shè)輸入差分[x0，y0]=[α，0]，經(jīng)過(guò)兩輪變換之后在y1處必為非零；再假設(shè)4輪加密之后輸出差分為[x2，y2]=[β，β]，經(jīng)過(guò)兩輪解密之后在y1處必為零。由此構(gòu)成矛盾，所以[α，0]→[β，β]為4輪不可能差分區(qū)分器。

圖12 MISTY的4輪不可能差分區(qū)分器

5 結(jié)論

本文對(duì)四種主要密碼整體結(jié)構(gòu)進(jìn)行了不可能差分區(qū)分器介紹和研究，重點(diǎn)給出了TYPE-I、TYPE-II和TYPE-III型結(jié)構(gòu)的不可能差分區(qū)分器證明過(guò)程。雖然這些密碼整體結(jié)構(gòu)有一定長(zhǎng)度的區(qū)分器，但是當(dāng)設(shè)計(jì)具體密碼算法時(shí)，由于無(wú)法使圈變換中F函數(shù)完全隨機(jī)，因此基于這類(lèi)結(jié)構(gòu)設(shè)計(jì)的對(duì)稱(chēng)密碼算法往往有更長(zhǎng)的不可能差分區(qū)分器，如基于SP結(jié)構(gòu)設(shè)計(jì)的AES、ARIA都存在4輪不可能差分區(qū)分器，基于TYPE-II設(shè)計(jì)的CLEFIA存在9輪不可能差分區(qū)分器。因此關(guān)于對(duì)稱(chēng)密碼整體結(jié)構(gòu)在不同計(jì)算模型下的細(xì)化研究和分析是本文下一步的研究重點(diǎn)。