分組密碼算法Lattice的滑動(dòng)攻擊*

潘向榮

（中國(guó)西南電子技術(shù)研究所，四川 成都 610036）

0 引 言

短波通信由于其設(shè)備質(zhì)量輕、機(jī)動(dòng)靈活和抗毀性強(qiáng)等優(yōu)點(diǎn)，在軍事通信領(lǐng)域占有極其重要的地位。自動(dòng)鏈路建立（Automatic Link Establishment，ALE）[1]是一種無(wú)需用戶操作即可使短波臺(tái)站尋找一個(gè)合適的頻率并建立鏈路的自動(dòng)化技術(shù)，是短波通信系統(tǒng)中的重要組成部分。自20世紀(jì)70年代末至今，自動(dòng)鏈路建立協(xié)議已經(jīng)發(fā)展至第三代，即3G-ALE。與第二代ALE技術(shù)相比，3G-ALE技術(shù)提高了鏈路建立速度、信道利用率、數(shù)據(jù)吞吐率，能夠在更低信噪比下實(shí)現(xiàn)連接，并支持Internet協(xié)議及應(yīng)用等。全球許多政府和非政府組織均在使用利用ALE技術(shù)的無(wú)線電通信技術(shù)。

SoDark族算法[2]是面向ALE應(yīng)用的分組密碼算法，實(shí)現(xiàn)對(duì)ALE標(biāo)準(zhǔn)中協(xié)議數(shù)據(jù)單元（Protocol Data Unit，PDU）中敏感數(shù)據(jù)的機(jī)密性。SoDark族算法包括Lattice算法、SoDark-3算法和SoDark-6算法。Lattice算法應(yīng)用于第二代ALE（2G ALE），分組長(zhǎng)度為24 bit，密鑰長(zhǎng)度為56 bit，迭代輪數(shù)8輪。3G ALE標(biāo)準(zhǔn)中使用了稱為SoDard-3的版本對(duì)26位協(xié)議數(shù)據(jù)單元（PDU）中的24位數(shù)據(jù)進(jìn)行加密。SoDark-3的迭代輪數(shù)為16輪，其輪函數(shù)與Lattice算法相同。由于3G ALE還使用48位的PDU，因此SoDark-3已擴(kuò)展為具有48位大小的版本，稱為SoDark-6。

Lattice算法是SoDark族算法中的基本算法。對(duì)Lattice算法的分析成果將極大地促進(jìn)對(duì)SoDark族算法的成功分析，進(jìn)而實(shí)現(xiàn)對(duì)短波通信情報(bào)信息的破譯，對(duì)獲取其語(yǔ)義內(nèi)容具有重要意義。本文簡(jiǎn)述了Lattice算法、SoDark族算法在短波通信系統(tǒng)中所起的作用及破譯SoDark族算法的意義。第1部分簡(jiǎn)要描述Lattice算法；第2部分介紹滑動(dòng)攻擊的基本原理；第3部分詳細(xì)介紹滑動(dòng)攻擊對(duì)Lattice算法的攻擊；第4部分對(duì)滑動(dòng)攻擊算法性能進(jìn)行分析；第5部分總結(jié)全文。

1 Lattice算法介紹

Lattice算法[3]是SoDark族算法中的基本算法，分組長(zhǎng)度為24 bit，密鑰長(zhǎng)度為56 bit，迭代輪數(shù)8輪。Lattice加密算法的輸入包括密鑰（Key）、種子（S eed）和待加密數(shù)據(jù)3組數(shù)據(jù)。算法以每24 bit明文數(shù)據(jù)為單位分別進(jìn)行加密計(jì)算。完整加密過(guò)程共包含8次迭代運(yùn)算，每次迭代運(yùn)算中的操作數(shù)據(jù)包括1 Byte密鑰、1 Byte種子和1 Byte源數(shù)據(jù)。每個(gè)步驟運(yùn)算結(jié)果從256×8 bit的加密運(yùn)算表中查詢相應(yīng)行列，得到本次計(jì)算的8 bit結(jié)果。加密算法流程如圖1所示。

加密使用56 bit密鑰和64 bit種子，其中種子由TOD、頻率、Word等構(gòu)成，結(jié)構(gòu)如圖2所示。64 bit種子包含頻率、當(dāng)前時(shí)間、日期以及wordnumber，其中TOD時(shí)間要求是非遞減的。月域由4 bit構(gòu)成，1代表1月，12代表12月；日期域由5 bit構(gòu)成，代表從1號(hào)～31號(hào)；粗時(shí)間域采用11 bit，代表從午夜開始的分鐘數(shù)，午夜粗時(shí)間域和精時(shí)間域都清0；精時(shí)間域采用6 bit，表示更精確的秒級(jí)時(shí)間，當(dāng)時(shí)間精度大于分鐘時(shí)，精時(shí)間域默認(rèn)為全1（時(shí)間質(zhì)量為6或7）。采用時(shí)間同步協(xié)議獲取精確時(shí)間后，精時(shí)間域更新為獲取的精確時(shí)間。頻率域每4 bit代表一個(gè)十進(jìn)制數(shù)。

Lattice加密算法流程如下。Lattice算法中使用的S盒是一個(gè)從域GF(28)到GF(28)的映射，不妨表示為f:GF(28)→GF(28)，如圖3所示。

不妨采用矢量V表示密鑰變量字節(jié)，s表示TOD或頻率種子字節(jié)。每次加密算法循環(huán)從矢量V和s中依次選取1 Byte進(jìn)行計(jì)算，共包括8次循環(huán),完成對(duì)24 bit源數(shù)據(jù)的加密。

假設(shè)A為每次加密循環(huán)共3個(gè)字節(jié)中的第1個(gè)字節(jié)，B為第2個(gè)字節(jié)，C為第3個(gè)字節(jié)，A′、B′和C′是本輪運(yùn)算的輸出，則每一輪中，計(jì)算方法如下：

2 滑動(dòng)攻擊的基本原理

滑動(dòng)攻擊由David Wagner和Alex Biryukov于1999年提出[4]，適用于算法的迭代過(guò)程具有一定的自相似性的密碼算法。在多數(shù)情況下，滑動(dòng)攻擊與迭代輪函數(shù)的具體性質(zhì)和執(zhí)行輪數(shù)無(wú)關(guān)。，任何可以被分解為執(zhí)行若干次輪函數(shù)F的密碼算法都可以嘗試采用滑動(dòng)攻擊來(lái)分析。換句話說(shuō)，滑動(dòng)攻擊的特點(diǎn)是不依賴于密碼算法的輪數(shù)，即如果采用滑動(dòng)攻擊能對(duì)某密碼算法進(jìn)行有效攻擊，則將該密碼算法的迭代輪數(shù)增加任意輪后所得到的新算法仍然不能抵抗滑動(dòng)攻擊。由于SoDark算法的輪函數(shù)與Lattice算法的輪函數(shù)相同，只是迭代輪數(shù)是Lattice算法的2倍，因此采用滑動(dòng)攻擊對(duì)Lattice算法的分析成果能極大地促進(jìn)對(duì)SoDark算法的成功破譯。

用 Fr○Fr-1○Fr-2○…○F1表 示 一 個(gè) 輪 數(shù) 為 r的迭代分組密碼?；瑒?dòng)攻擊的基本思想[5]是將一個(gè)加密過(guò)程相對(duì)于另一個(gè)加密過(guò)程“滑動(dòng)”一輪。如果明密文對(duì)(P,C)和(P*,C*)滿足條件F1(P)=P*和Fr*(C)=C*，則稱該密文對(duì)為一個(gè)滑動(dòng)對(duì)（Slide pair），如圖4所示?；瑒?dòng)對(duì)實(shí)際上為分析者提供兩組一輪的密碼變換的輸入和輸出。

老師在鼓勵(lì)學(xué)生閱讀的同時(shí)不妨創(chuàng)設(shè)情境，讓幾個(gè)學(xué)生結(jié)為一個(gè)閱讀小組布置一篇有趣的文章。例如在人教版小學(xué)語(yǔ)文二年級(jí)上冊(cè)的課本中就有《曹沖稱象》、《狐假虎威》等我國(guó)有名的短故事，但是很少有涉及到外國(guó)寓言童話的小文章，所以老師們不妨給學(xué)生布置一些《伊索寓言》、《格林童話》等，每周選擇一個(gè)閱讀小組讓小組自行選擇一篇最近閱讀過(guò)的小故事進(jìn)行小組課堂表演，利用表演的方式激發(fā)起學(xué)生的閱讀興趣。

根據(jù)滑動(dòng)對(duì)的定義，滑動(dòng)攻擊將按以下步驟對(duì)密碼算法進(jìn)行攻擊。假設(shè)密碼算法輸入為N個(gè)比特，由于輪函數(shù)Fi與其使用的輪密鑰相關(guān)，若能選擇輪密鑰對(duì)(K,K*)使得Fi*=Fi+1，則根據(jù)生日攻擊原理，需要2N/2個(gè)明文-密文對(duì)就能找到滿足上述條件的滑動(dòng)對(duì)。

假定分組密碼算法的分組長(zhǎng)度為N，如果采用滑動(dòng)攻擊能成功破譯該算法，滑動(dòng)攻擊的復(fù)雜度通常接近于O(2N/2)。以色列學(xué)者Achiya Bar-On等人[6]針對(duì)采用代換-置換網(wǎng)絡(luò)（Substitution Permutation Network，SPN）和Feistel結(jié)構(gòu)的密碼算法、GOST及其變體算法，提出了改進(jìn)的滑動(dòng)攻擊方法。改進(jìn)后的滑動(dòng)攻擊極大地降低了攻擊的時(shí)間復(fù)雜度。

3 Lattice的滑動(dòng)攻擊

Lattice算法循環(huán)使用7 Byte密鑰V與8 Byte種子s，輪函數(shù)Fn+1如下：

若選擇另一個(gè)密鑰V*和種子S*，滿足：

則Fi*=Fi+1,1≤i≤7，恰好滿足對(duì)其實(shí)施滑動(dòng)攻擊的條件?；谏鲜鲇懻?，本文分析采用滑動(dòng)攻擊能有效破譯Lattice算法的可行性。下面對(duì)Lattice算法實(shí)施滑動(dòng)攻擊的過(guò)程如圖5所示。

注意到輪函數(shù)F1：

使用密鑰V[0]、V[1]、V[2]，輪函數(shù)F9為：

使用密鑰 V[3]、V[4]、V[5]，若兩組明文 - 密文 對(duì) (P,C)和 (P*,C*)滿 足 F1(P)=P*， 由 于 Fi*=Fi+1，1≤i≤7，則一定有F8*(C)=C*，也就是已知輪函數(shù)F1、F9的輸入與輸出。在已知種子s的前提下，可以計(jì)算出 V[0]、V[1]、V[2]、V[3]、V[4]、V[5]，具體計(jì)算表達(dá)式如下：

計(jì)算出的6 Byte密鑰不一定是正確的密鑰，窮舉V[6]，可得到完整的7 Byte密鑰。通過(guò)兩個(gè)明文-密文對(duì)，可驗(yàn)證分析得到的密鑰是否正確。不妨假設(shè)N是明文-密文對(duì)的個(gè)數(shù)，攻擊算法的偽代碼如下：

攻擊算法成功的關(guān)鍵在于存在兩組明文-密文對(duì)(P,C)和(P*,C*)滿足F1(P)=P*。在明文隨機(jī)選取的前提下，它的概率Pr為：

4 對(duì)Lattice算法的滑動(dòng)攻擊算法性能分析

本文通過(guò)計(jì)算機(jī)仿真實(shí)現(xiàn)了對(duì)Lattice算法的滑動(dòng)攻擊實(shí)例。本文設(shè)置Lattice算法的56 bit密鑰為C2 28 4A 1C E7 BE 2F，種子為543bd88000017550。通過(guò)使用上述滑動(dòng)攻擊方法和對(duì)應(yīng)的攻擊算法，分析得到Lattice密碼算法的密鑰與預(yù)置的密鑰完全一致，如圖6所示，表明本文成功地利用了滑動(dòng)攻擊方法對(duì)Lattice密碼算法實(shí)施了完全破譯。

5 結(jié) 語(yǔ)

SoDark族分組密碼算法用于實(shí)現(xiàn)第二代和第三代自動(dòng)鏈路建立（Automatic Link Establishment，ALE）系統(tǒng)所發(fā)送消息的機(jī)密性。Lattice算法是SoDark家族算法中的基本算法。本文基于滑動(dòng)攻擊原理，設(shè)計(jì)了采用滑動(dòng)攻擊分析Lattice算法的攻擊算法，并通過(guò)計(jì)算機(jī)仿真給出了對(duì)Lattice算法采用滑動(dòng)攻擊進(jìn)行密鑰恢復(fù)的實(shí)例。仿真結(jié)果表明，本文采用滑動(dòng)攻擊方法對(duì)Lattice算法實(shí)施攻擊的正確性和有效性。本文的分析成果對(duì)分析具有更高輪數(shù)的SoDark-3和SoDark-6密碼算法提供了堅(jiān)實(shí)基礎(chǔ)。在后續(xù)的研究工作中，將進(jìn)一步采用滑動(dòng)攻擊方法開展對(duì)SoDark-3和SoDark-6兩個(gè)密碼算法的分析。