潘向榮

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

0 引 言

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

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

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

1 Lattice算法介紹

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

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

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

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

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

2 滑動攻擊的基本原理

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

用 Fr○Fr-1○Fr-2○…○F1表 示 一 個 輪 數(shù) 為 r的迭代分組密碼?；瑒庸舻幕舅枷隱5]是將一個加密過程相對于另一個加密過程“滑動”一輪。如果明密文對(P,C)和(P*,C*)滿足條件F1(P)=P*和Fr*(C)=C*，則稱該密文對為一個滑動對（Slide pair），如圖4所示?；瑒訉嶋H上為分析者提供兩組一輪的密碼變換的輸入和輸出。

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

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

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

3 Lattice的滑動攻擊

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

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

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

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

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

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

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

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

4 對Lattice算法的滑動攻擊算法性能分析

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

5 結(jié) 語

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