第7章流密碼7.1異或運算7.2一次一密及多次一密7.3流密碼7.4反饋移位寄存器7.5線性同余發(fā)生器7.6梅森旋轉(zhuǎn)算法7.7RC4流密碼算法7.8快速相關(guān)攻擊

7.1異或運算

7.1.1異或簡介

異或(ExclusiveOR,XOR)也稱為半加運算。異或的運算法則實際上就是不帶進(jìn)位的二進(jìn)制加法。在實際運算時,需要把數(shù)據(jù)轉(zhuǎn)換為二進(jìn)制然后逐個比特進(jìn)行異或運算,具體的按位異或運算法則如下:

圖7.1異或原理

圖7.2異或在流密碼中的應(yīng)用

7.1.3異或編程

編程語言都提供了實現(xiàn)異或運算的位運算符。Python語言用“∧”符號表示位異或運算。在Python語言中,異或只能處理int整型變量,不能處理str字符或者字符串等類型。

1.整數(shù)異或

Python在處理整數(shù)異或運算時,首先將整數(shù)轉(zhuǎn)換為二進(jìn)制表示,并讓其長度相同(短的前面補(bǔ)0),然后將兩個二進(jìn)制數(shù)按位異或,最后將結(jié)果轉(zhuǎn)換回十進(jìn)制數(shù)。

圖7.3Python異或

2.字符異或

兩個字符進(jìn)行異或,其本質(zhì)與按位異或是一樣的。兩個英文字符在異或時,首先把字符轉(zhuǎn)換為其ASCII碼對應(yīng)的整數(shù)值,然后轉(zhuǎn)換成8個比特的二進(jìn)制數(shù),之后進(jìn)行按位異或運算。示例如下:

上述代碼通過ord函數(shù)將str類型轉(zhuǎn)換成int類型,從而實現(xiàn)字符與字符的異或。

這里我們看到,字母“A”和字母“a”的ASCII碼值,正好相差32,也就是空格的ASCII碼值。轉(zhuǎn)換成二進(jìn)制以后可以看出,“A”和“a”的二進(jìn)制位只有第六位是不同的,其他的字母也有此特征,讀者可以自行驗證。而第六位正好對應(yīng)的就是26-1=25=32,因此大寫字母如果與空格進(jìn)行異或,可以得到小寫字母;同樣,小寫字母與空格異或也可以得到大寫字母。

7.1.4異或?qū)嵺`

根據(jù)異或運算,我們可以實現(xiàn)基于單個字符的異或密碼。例如,有明文字符串“Astreamcipherisamethodofencryptionwhereapseudorandomcipherdigitstreamis

combinedwithplaintextdigits.”,密鑰字符取“X”,那么對應(yīng)的加密代碼和結(jié)果如下:

針對單字符的異或加密密文,如果要破解其密鑰或者恢復(fù)其明文,本身沒有什么難度,因為單個字符組成的密鑰空間非常小。關(guān)鍵是在破解過程中涉及的一些知識點是需要讀者掌握的。在此以Cryptopals第4道挑戰(zhàn)題為例進(jìn)行說明,題目描述如圖7.4所示。

圖7.4Cryptopals-set1-challenge4

附件提供的文件內(nèi)容共有327行文本,每一行都是60個字符長度的字符串。根據(jù)題意,其中的某一行是由英文句子和某個字符異或得到的,題目要求找到這一行。文件的部分內(nèi)容如圖7.5所示。

圖7.5題目附件中的部分文本行

首先,觀察文件中的每一行,可以看到所有字符都在0~9和a~f的范圍內(nèi),可以推測密文是十六進(jìn)制表示。根據(jù)每行長度和每兩個十六進(jìn)制數(shù)表示一個字符,可知每一行有30個英文字符。

其次,加密密鑰是單個字符,其范圍在0x00~0xff之間,有256種可能,可以進(jìn)行暴力破解。

最后,對于暴力破解結(jié)果是否正確,需要根據(jù)英文的語言特點進(jìn)行自動化判定。這可以使用第2章中提到的頻率分析方法。根據(jù)常見字母的出現(xiàn)頻率對結(jié)果進(jìn)行打分,分?jǐn)?shù)越高越可能是有意義的英文句子。在此通過計算暴力破解出來的明文有多少是合法的字符(僅包含英文字母和數(shù)字以及空格)來實現(xiàn),合法字符數(shù)量越多,越有可能是我們想要的答案。

上述代碼的第3行給出的閾值是0.85,也就是說,只要異或后的字符串當(dāng)中有85%是我們認(rèn)為的合法字符,就輸出對應(yīng)的密文、密鑰以及明文。從輸出結(jié)果來看,共有8行達(dá)到了要求,可以明顯看出,圖7.6所示第二行是我們想要的結(jié)果。

圖7.6暴力破解打分結(jié)果

7.2一次一密及多次一密

一次一密(OneTimePad,OTP)顧名思義就是一次性的便簽本(Pad),如圖7.7所示。便簽本上記錄了五個數(shù)字一組的隨機(jī)數(shù)字序列。加密時隨機(jī)從里面選取一部分?jǐn)?shù)字作為密鑰對明文消息進(jìn)行加密。

圖7.7一次一密便簽本

加密過程可以分兩步實施:

(1)原始消息轉(zhuǎn)換為數(shù)字序列,例如按照ASCII碼值轉(zhuǎn)換;

(2)從Pad中選取一組數(shù)字序列和明文數(shù)字序列進(jìn)行某種簡單的數(shù)學(xué)運算。

在此以某國的OTP為例,了解OTP的工作原理。

首先,賦予每個大寫字母對應(yīng)的數(shù)字,如圖7.8(a)所示。

依據(jù)圖7.8(a),把明文消息的字母用對應(yīng)的數(shù)字替換,如圖7.8(b)所示。

從圖7.7中選擇一組數(shù)字(在此從第一行開始取數(shù)),然后分別同上述消息數(shù)字進(jìn)行相加運算,如果和超過100,則減去100,如圖7.8(c)所示。

然后把密文數(shù)字序列按照5個數(shù)字一組進(jìn)行發(fā)送(傳輸),如下所示:

要解密密文,接收端從Pad的相同頁選擇相同的數(shù)字序列,并做減法運算(如果小于0,需要加100),如圖7.8(d)所示。

圖7.8加密過程圖示

最后把數(shù)字再轉(zhuǎn)換為對應(yīng)的大寫字母,恢復(fù)出明文消息。

由上述實例,可以看出OTP的安全性主要依賴以下規(guī)則:

(1)OTP需要真正隨機(jī)的字符串作為密鑰(噪聲);

(2)OTP密鑰長度不短于明文消息長度;

(3)只有兩份OTP存在;

(4)OTP只使用一次;

(8)用后及時銷毀。

7.2.1真正隨機(jī)密鑰

事實上,隨機(jī)數(shù)對于密碼學(xué)來說至關(guān)重要,如密鑰、初始化向量、nonce等參數(shù)的產(chǎn)生都依賴隨機(jī)數(shù)發(fā)生器。但通過計算機(jī)系統(tǒng)來獲得真正的隨機(jī)數(shù)非常困難,后續(xù)章節(jié)(7.4~7.7)會給出實例說明。真正的隨機(jī)數(shù)通常由物理現(xiàn)象產(chǎn)生,如環(huán)境溫度、電子元件噪聲、核裂變和復(fù)雜的物理過程等,這些現(xiàn)象可以產(chǎn)生無規(guī)律的、無法預(yù)測的真隨機(jī)數(shù)?，F(xiàn)在流行的生成隨機(jī)數(shù)的方法都是通過傳入一個“比較隨機(jī)”的“種子”(例如時間)生成“偽隨機(jī)數(shù)”。在一次一密中,由于異或運算的特性,其安全性嚴(yán)重依賴于密鑰流,如果未使用真正的隨機(jī)數(shù)作為密鑰,則攻擊者可以預(yù)測出后續(xù)要使用的密鑰流,從而破解密文。

7.2.2多次一密

一次一密的另外一個安全隱患來自密鑰的復(fù)用。如果重復(fù)使用加密密鑰,那么一次一密就成了兩次一密或者多次一密,也就是說兩次或多次重復(fù)使用相同的密鑰進(jìn)行加密。以兩次一密為例,只要將兩次加密得到的密文進(jìn)行異或計算就得到了兩次明文的異或。

此時,只要已知一個明文當(dāng)中的部分信息,就可以恢復(fù)另外一個明文的部分信息。在此以兩張圖片作為明文來舉例說明,圖片如圖7.9、圖7.10所示。圖7.9明文圖片P1

圖7.10明文圖片P2

然后使用圖7.11所示隨機(jī)圖片作為加密密鑰,與上述兩幅圖片分別進(jìn)行異或運算。圖7.11密鑰圖片K

圖片之間的異或運算的Python實現(xiàn)代碼如下。代碼通過PythonPIL圖像處理庫讀入圖片內(nèi)容,然后把像素信息轉(zhuǎn)換成字節(jié)形式,再進(jìn)行異或加密,最后將加密結(jié)果保存為圖片形式即可。需要注意的是,明文圖片和密鑰圖片的大小相同。

最終兩張明文圖片異或加密后的結(jié)果分別如圖7.12、圖7.13所示。

圖7.12密文圖片C1

圖7.13密文圖片C2

從表面上看,這兩張圖片是隨機(jī)的,毫無意義,在不知道加密圖片K的情況下很難恢復(fù)出明文圖片。但是如果攻擊者知道這兩張圖片是使用同一個密鑰(圖片)加密的,那么只需將這兩張圖片異或(在代碼中更改第2行和第4行的文件名字即可),就能得到如圖7.14所示的結(jié)果。

下面以ALEXCTF2017-CR2題目“Manytimesecrets”為例,對Crib-dragging技術(shù)進(jìn)行講解,其中密文內(nèi)容如下:

從題目名字“Manytimesecrets”可知,考察的是多次一密的相關(guān)知識。密文文件的內(nèi)容有11行,那么可以大膽地猜測這11行密文都是通過與同一個密鑰加密得到的,也就是“十一次一密”,并且根據(jù)flag的格式,密鑰是以“ALEXCTF{”作為前綴的字符串。

7.3流密碼

一次一密系統(tǒng)是一種絕對安全的密碼系統(tǒng),但它在現(xiàn)實當(dāng)中是不可實現(xiàn)的。首先是密鑰的完全隨機(jī)難以實現(xiàn),特別是在密碼應(yīng)用中,大量的隨機(jī)數(shù)生成算法都是確定的,輸出的序列不是統(tǒng)計隨機(jī)的。其次是密鑰的分發(fā)問題,一次一密系統(tǒng)事先需要將和明文長度相同的密鑰通過安全信道傳輸給接收方。如果現(xiàn)實中存在這樣一條安全的通信信道,那么完全可以直接將明文傳輸給接收方。

一次一密作為流密碼的雛形,為流密碼的產(chǎn)生奠定了基礎(chǔ)。正如前述,一次一密無法實現(xiàn)的一個難題是無法找到真正隨機(jī)的密鑰,就算找到了這個與明文長度相等的密鑰也無法很好地保存。因此我們常常將一個較小的“種子”傳入一個黑盒中,讓這個黑盒為我們產(chǎn)生一系列近似隨機(jī)的比特串。我們稱這個黑盒為偽隨機(jī)數(shù)生成器(PseudoRandomNumberGenerator,PRNG)。通過PRNG,只需要傳入一個只有幾個字節(jié)大小的“種子”,就可以生成MB甚至GB級別的密鑰流。

流密碼實際上就是使用一個PRNG來生成密鑰流,然后對明文進(jìn)行異或加密的。接收端采用相同的PRNG生成相同的密鑰流,對密文進(jìn)行異或解密恢復(fù)明文。流密碼模型如圖7.15所示。

圖7.15流密碼模型

從圖7.15可知,流密碼實際的加解密過程非常簡單,就是異或運算。流密碼的安全重點在于隨機(jī)數(shù)生成器。在密碼學(xué)中,隨機(jī)數(shù)生成器主要有以下三種。

1.統(tǒng)計學(xué)偽隨機(jī)數(shù)生成器

在給定的數(shù)列中,每個數(shù)字出現(xiàn)的數(shù)量大致相等,分布均勻并獨立。

2.密碼學(xué)安全偽隨機(jī)數(shù)生成器(CSPRNG)

在身份認(rèn)證、會話密鑰和流密碼應(yīng)用中,單獨滿足統(tǒng)計隨機(jī)是不夠的,還需要隨機(jī)序列是不可預(yù)測的,這包括從數(shù)字序列不可預(yù)測出種子(后向不可預(yù)測)以及從數(shù)字序列預(yù)測出后續(xù)的數(shù)字序列(前向不可預(yù)測)。

3.真隨機(jī)數(shù)生成器(TRNG)

真隨機(jī)數(shù)生成器產(chǎn)生的隨機(jī)樣本不可重現(xiàn)。為了產(chǎn)生真隨機(jī)性,需要從大自然的物理環(huán)境來獲取隨機(jī)信息,如環(huán)境溫度、聲音、輻射變化等,這些源統(tǒng)稱為熵源。根據(jù)這些源或者源的組合生成的信息一般認(rèn)為不可重現(xiàn)。

7.4反饋移位寄存器

反饋移位寄存器(FeedbackShiftRegister,FSR)是一種常見的流密碼密鑰流產(chǎn)生裝置,其基本結(jié)構(gòu)如圖7.16所示。

圖7.16n級反饋移位寄存器

其中:

·a1,a2,…,an為n個寄存器的初始狀態(tài)。

·F(…)為反饋函數(shù)。如果F(…)為線性函數(shù),那么稱其為線性反饋移位寄存器(LinearFeedbackShiftRegister,LFSR),否則稱其為非線性反饋移位寄存器(Nonlinear

FeedbackShiftRegister,NFSR)。

·每次反饋移位寄存器移出一個比特位,即有an+1=F(a1,a2,…,an),更一般的表示是ai+n+1=F(ai+1,ai+2,…,ai+n)。

7.4.1線性反饋移位寄存器

線性反饋移位寄存器的模型如圖7.17所示。圖7.17線性反饋移位寄存器

LFSR有如下特性:

(1)初始狀態(tài)相同,輸出序列也相同。也就是說,初始狀態(tài)決定了輸出序列。

(2)輸出序列看似隨機(jī),但是由于狀態(tài)寄存器個數(shù)有限,所以在移位輸出到一定次數(shù)后會出現(xiàn)循環(huán)(周期性)。假如一個LFSR內(nèi)部有n個狀態(tài)寄存器,則可能的狀態(tài)共有2n種,根據(jù)第一個特性,必然會產(chǎn)生循環(huán)。

(3)除去全0狀態(tài),還剩下有2n-1種狀態(tài),因此LFSR可以產(chǎn)生不重復(fù)最長序列的長度為有2n-1,也可以說它的周期是有2n-1。周期達(dá)到有2n-1的線性反饋移位序列也稱為m序列。

m序列在通信領(lǐng)域有著廣泛的應(yīng)用,循環(huán)冗余校驗碼(CRC)就可以通過LFSR來產(chǎn)生校驗和。而CRC生成多項式的首位和最后一位必須為1,因此LFSR的系數(shù)cn和c0肯定是1。

LFSR能產(chǎn)生m序列的充要條件是:LFSR的特征多項式F(x)為本原多項式。其中F(x)=xn

+xn-1+xn-2+…+x1+x0,這里的xi

與系數(shù)ci(i=n,n-1,…,1,0)一一對應(yīng)。當(dāng)F(x)滿足下列三個條件時,F(x)為本原多項式。

(1)F(x)是不可約的,即不能再分解因式;

(2)F(x)可整除xp+1,其中p=2n-1;

(3)F(x)不能整除xq+1,其中q<p。

部分常見的本原多項式如表7.1所示。

【例7-2】當(dāng)n=5時,對應(yīng)的本原多項式八進(jìn)制形式為(45)8,將其轉(zhuǎn)換成二進(jìn)制形式為(100101)2,即x5+x2+1,可以得到

對應(yīng)的LFSR如圖7.18所示。

圖7.18特征多項式為(45)8的5級LFSR

假設(shè)初始狀態(tài)為(a1a2a3a4a5)=(11000),則根據(jù)式(7.1),寄存器的狀態(tài)依次是

根據(jù)上述寄存器的狀態(tài)值,(45)8的5-LFSR的序列周期為31,后續(xù)會循環(huán)出現(xiàn)上述狀態(tài)值。

對于n比較小的情況,其實手工就可以進(jìn)行破解,請看下例同樣是n=5的情況。假設(shè)Eve獲得了密文串101101011110010和對應(yīng)明文串011001111111001,將明文與密文異或可以得到密鑰流(ai,i=1,2,3,…)=110100100001011,如果此時Eve還知道密鑰流是使用5級LFSR產(chǎn)生的,那么可以構(gòu)建如下方程:

就可以得到生成密鑰流用的LFSR(這與圖7.18所示的LFSR是一樣的):

上述針對LFSR的手工移位操作也可以用程序來實現(xiàn)。以下Python代碼對應(yīng)的F(x)=x32+x30+x27+x20+x12+x8+x5+x3+1。下列代碼中輸入?yún)?shù)R為初始狀態(tài)(整型數(shù)),mask為特征多項式系數(shù)的二進(jìn)制表示。

上述代碼中的mask變量長度為32,表明是一個n=32的32級線性反饋移位寄存器(見圖7.19),并且c32、c30、c27、c20、c12、c8、c5、c3為1,也就是選擇了a1、a3、a6、a13、a21、a25、a28、a30作為反饋函數(shù)的輸入,新產(chǎn)生的比特位a33與以下8個比特有關(guān),關(guān)系式如下:

圖7.1932級線性反饋移位寄存器

【例7-3】根據(jù)上述LFSR的實現(xiàn)代碼,從密鑰流(key文件)暴力破解flag信息。

上述密鑰流生成代碼中:

·第5行的R保存的是flag字符串中花括號里面的內(nèi)容,是由十六進(jìn)制數(shù)組成的字符串。在此,flag作為LFSR的寄存器初始狀態(tài)。flag字符串長度為14,格式為“flag{xxxxxxxx}”,花括號中的8個十六進(jìn)制字符轉(zhuǎn)換成整型數(shù)R后和mask一起傳入lfsr函數(shù),生成連續(xù)的比特密鑰流,并保存寫入key文件中。

·代碼的第11行到13行完成lfsr函數(shù)調(diào)用,每次調(diào)用得到新的寄存器狀態(tài)和一個比特的輸出,每輸出8個比特即將其轉(zhuǎn)換為一個字節(jié)寫入key文件中,寫100次,共計100個字節(jié)。

當(dāng)LFSR的位數(shù)不超過30位且知道多項式mask的情況下,可以考慮采用暴力枚舉的方法暴力破解初始狀態(tài)(或者稱為種子seed或者key)。

·首先,確定flag的長度。根據(jù)分析已經(jīng)確定flag包含8個十六進(jìn)制字符,也就是有168=4294967296種可能。

·其次,確定暴力破解成功的判斷條件。將某個flag值傳入lfsr函數(shù),如果生成的密鑰流與key文件一致,則說明該flag正確

除了采用暴力破解的方法,還可以根據(jù)LFSR的線性特性,通過密鑰流反推flag的值。

因為flag是用于填充最初的LFSR寄存器初始狀態(tài)的,所以首先看一下flag的最后一位即將被移出寄存器之前的LFSR狀態(tài)和對應(yīng)的比特關(guān)系以及示意圖(見圖7.20)。

圖7.20時間定格在flag最后一個比特移出寄存器之前

此時LFSR已經(jīng)產(chǎn)生密鑰流key的前31個比特(圖中a33~a63),即將移位得到下一個密鑰流比特a64。實際上整個密鑰流key都是已知的,也就是后續(xù)的第32位(a64)也是已知的。根據(jù)前32個密鑰流比特和flag最后一個比特位(a32)的關(guān)系,可以計算出flag的最后一位a32。由于flag最后一位只有兩種情況(為0或者為1),在此先假設(shè)其為0,然后使用已知的mask和lfsr函數(shù)生成下一位(也就是key的第32位,實際是已知的)來破解,計算關(guān)系如圖7.21所示。

圖7.21最后一位破解示意

最終即可得到完整的flag。

使用LFSR的好處是簡單快捷,易于軟硬件高速實現(xiàn)。但由于寄存器狀態(tài)有限,并且由于其線性特性,LFSR任意時刻的輸出可以通過最初的內(nèi)部狀態(tài)線性推導(dǎo)表示出來,因此需要更加安全的NFSR。

7.4.2非線性反饋移位寄存器

鑒于應(yīng)用于流密碼中的移位寄存器對安全性的要求,實際中更多使用的是非線性反饋移位寄存器(NFSR),它的結(jié)構(gòu)和LFSR類似,但是其反饋函數(shù)不再是線性函數(shù),而采用的是非線性函數(shù)。NFSR通過非線性反饋函數(shù)將LFSR組合起來,使生成的密鑰序列更加復(fù)雜、周期更長、不可預(yù)測性更高。NFSR主要有以下幾種結(jié)構(gòu):

(1)非線性組合生成器。這種結(jié)構(gòu)通常對多個LFSR的輸出使用一個非線性組合函數(shù)來構(gòu)成(見圖7.22)。如果n個LFSR的長度分別為l1,l2,…,ln,那么密鑰流的線性復(fù)雜度變?yōu)閒(l1,l2,…,ln),可見這種設(shè)計方法可以大大增加線性復(fù)雜度。

圖7.22非線性組合生成器圖7.23非線性濾波生成器

(2)非線性濾波生成器。這種結(jié)構(gòu)只使用一個LFSR,密鑰流是通過一個非線性函數(shù)f作用于LFSR的某些狀態(tài)來直接產(chǎn)生的,其中f函數(shù)也稱為濾波函數(shù)。采用這類結(jié)構(gòu)(見圖7.23)設(shè)計的流密碼有ISO/IEC國際標(biāo)準(zhǔn)加密算法SNOW2.0,以及3GPPLTE國際加密算法標(biāo)準(zhǔn)算法SNOW3G和國密ZUC(祖沖之算法)等。

圖7.23非線性濾波生成器

(3)鐘控生成器。這類結(jié)構(gòu)使用至少一個LFSR的輸出來控制另一個(或多個)LFSR的輸出(見圖7.24)。采用鐘控生成器設(shè)計的流密碼要避免不規(guī)則鐘控帶來的輸出效率的降低,比較典型的幾個算法有用于全球移動通信系統(tǒng)(GSM)加密的A5/1算法、LILI-128和eSTREAM計劃中面向硬件設(shè)計的MICKEY2.0等。

圖7.24鐘控生成器

根據(jù)上述代碼給出的密鑰流生成算法,flag除了“flag{}”外還有18個十六進(jìn)制的符號(代碼第5行)。還有兩個函數(shù)——lfsr和single_round,分別完成LFSR和NFSR功能。

·lfsr:24位的LFSR。

·single_round:非線性組合函數(shù)。R1、R2、R3均為十六進(jìn)制表示的6個字符長度的字符串,15、16、17行代碼就是將它們和對應(yīng)的掩碼輸入lfsr生成新的R1、R2、R3,最后以return中的表達(dá)式實現(xiàn)核心的非線性變換:

上述非線性變換對應(yīng)的是NFSR當(dāng)中一類稱為Geffe

的序列生成器。該生成器由3個LFSR組成,其中LFSR2用于控制LFSR1和LFSR3兩者當(dāng)中哪一個起作用(見圖7.25)圖7.25Geffe序列生成器

最后的30行至44行代碼是利用上述兩個函數(shù)輸出密鑰流到文件中。最內(nèi)層循環(huán)(37至39行代碼)連續(xù)8次調(diào)用single_round()函數(shù)產(chǎn)生8個比特密鑰流;再向外兩層循環(huán)分別調(diào)用1024次完成1kB和1MB密鑰流的生成;最外層循環(huán)(30行~44行代碼)將生成的1MB字節(jié)密鑰流輸出到文件中,文件名從“0”開始一直到“1023”,一共1024個文件。整個密鑰流生成流程如圖7.26所示。

圖7.26密鑰流生成流程

這里由于代碼中flag的長度太長,不考慮暴力破解方法解密。

盡管在NFSR中,f函數(shù)是非線性運算,也就是最終的密鑰流是通過多個LFSR獨立生成后再通過f函數(shù)的某種數(shù)學(xué)運算組合在一起的,但是最終的密鑰流輸出(output)往往同某個LFSR存在概率統(tǒng)計相關(guān),因此可以采用相關(guān)攻擊(CorrelationAttack)完成LFSR的猜解。這種攻擊本質(zhì)上是一種分治的操作,也就是從密鑰流輸出恢復(fù)每個獨立的LFSR。

以下根據(jù)f函數(shù)的組合關(guān)系,也就是代碼中single_round函數(shù)最后的return返回前的計算公式:

來分析密鑰流輸出(output)和各個LFSR輸入之間的關(guān)系。根據(jù)式(7.5)有對應(yīng)的真值表,如表7.2所示。

由表7.2可以得到以下概率:

·P(x1=output)=3/4;

·P(x2=output)=1/2(等概率,和隨機(jī)選擇0或1一樣);

·P(x3=output)=3/4。

根據(jù)上述概率關(guān)系,特別是x1和x3與密鑰流輸出之間的強(qiáng)相關(guān)性(相等的概率為75%),可以單獨對R1和R3進(jìn)行暴力破解。如果R1或者R3單獨產(chǎn)生的密鑰流與前述NFSR生成的密鑰流輸出(結(jié)果保存在前面代碼所給出的1024個文件中)強(qiáng)相關(guān),那么有理由相信我們的猜解是正確的。

完整的猜解代碼如下所示。代碼中的guess函數(shù)用于單獨猜測x1(R1)和x3(R3),brute_force函數(shù)在已知x1和x3的基礎(chǔ)上暴力破解x2。由于單獨每個LFSR的長度相對較短(見題目代碼20至25行),因此單獨暴力破解每個LFSR在計算上成為可能。如果整體一起暴力破解,三個LFSR的長度達(dá)到了17+19+21=57位,57位的暴力破解空間太大,因此是不可行的。

最后將三部分拼接,得到完整的flag——“flag{01b9cb05979c16b2f3}”。顯然NFSR的分析比LFSR要復(fù)雜得多。雖然看似是簡單的三個LFSR的組合,但是要想直接暴力破解,計算量太大,因此其安全性相比LFSR要高很多。

7.5線性同余發(fā)生器

線性同余發(fā)生器(LinearCongruentialGenerator,LCG)是一種偽隨機(jī)序列生成算法,顧名思義就是采用線性運算以及模運算來產(chǎn)生偽隨機(jī)序列。LCG的理論相對容易理解,并且實現(xiàn)簡單。

LCG通常采用以下公式來產(chǎn)生線性同余序列Xi:

其中:

·m是模數(shù),要求m>0;

·a是乘數(shù),要求0<a<m;

·c是增量,要求0≤c<m;

·X0表示初始值,要求0≤X0<m。

以上參數(shù)均為正整數(shù)。模數(shù)m和乘數(shù)a是公式中最重要的參數(shù),能否合理地選擇這兩個參數(shù)將決定其產(chǎn)生的線性同余序列<X>=X1,X2,…,Xn,…的優(yōu)劣。

【例7-4】當(dāng)m=10,X0=a=c=7時,得到的序列如下:

7,6,9,0,7,6,9,0,7,6,9,0,…

顯然,上述序列的周期為4,這說明同余序列總是會進(jìn)入一個循環(huán),也就是說它最終必定在n個數(shù)之間無休止地重復(fù),這個性質(zhì)對于所有的LCG都適用。一個優(yōu)秀的LCG必須有足夠長的周期。

7.5.1參數(shù)選擇

要構(gòu)造一個滿足密碼安全的線性同余發(fā)生器,需要綜合考慮隨機(jī)序列的周期性、統(tǒng)計分布和計算效率。這些性質(zhì)都依賴于參數(shù)的選擇,尤其是模數(shù)m和乘數(shù)a的選取。

1.模數(shù)m的選擇

模數(shù)m應(yīng)盡可能大,以產(chǎn)生長周期隨機(jī)序列。如果計算機(jī)的字長為ω,一般推薦取m=2ω,也可以取m=2ω+1或m=2ω-1,或是取m小于2ω的最大素數(shù)。通常而言,如果取m=2ω,則其計算過程可以利用位運算實現(xiàn)高效計算,但是產(chǎn)生的隨機(jī)序列中各元素的低比特位的隨機(jī)性并不是很好。因為當(dāng)m=2ω時,對于一個s位的整數(shù)Z,Z模m的結(jié)果實際上就是Z的比特位中右邊的ω位的結(jié)果,而如果取m=2ω+1,結(jié)果會大不一樣,如圖7.27所示。

圖7.27Zmod2ω和Zmod(2ω+1)

定理:當(dāng)m=2ω時,LCG的周期將會是ω。

證明:

假設(shè)d是m的一個因子,q為某一整數(shù),令Yn滿足如下關(guān)系

再將

兩邊同時模d,可以消去qm:

不難發(fā)現(xiàn),式(7.9)實際上也是一個LCG,它產(chǎn)生的隨機(jī)序列也具有周期性,但是其周期小于d。這里的<Y>序列實際上對應(yīng)了原線性同余序列<X>的低位字節(jié),可以將序列<Y>

理解為是將<X>的低位單獨抽取出來組成的一個序列。

2.乘數(shù)a的選擇

可以立即排除a=1的情況,否則有以下線性同余式:

此時產(chǎn)生的隨機(jī)序列是一種有規(guī)律的序列,例如X0=3、c=1、m=8時,有如下序列:

可見以上序列不具有隨機(jī)特性,而a=0的情況甚至更糟糕,因此一般都假定:a≥2。

按照如下方式選定系數(shù)a可以產(chǎn)生最大周期為m的線性同余序列:

·c是正整數(shù);

·a、c、X0都比m小;

·c與m互素;

·m的所有質(zhì)因子的積能整除a-1;

·如果m是4的倍數(shù),則b=a-1也是4的倍數(shù)。

以上定理表明,當(dāng)c不等于0時(c與m互質(zhì),自然就不可能等于0),有可能產(chǎn)生周期為m的線性同余序列。

另一方面,當(dāng)c=0時,也即

時,是否有可能產(chǎn)生周期為m的線性同余序列?答案是否定的。用反證法:如果c=0時產(chǎn)生了周期為m的線性同余序列,那么0必然在這個序列中,但是如果0在序列中,必然會導(dǎo)致線性同余序列退化成全0的序列,因此原命題不成立

綜上所述,線性同余序列參數(shù)的選擇需要遵循以下幾點:

(1)模數(shù)m應(yīng)該盡可能大,通常至少應(yīng)大于230,考慮到計算效率,通常會結(jié)合計算機(jī)的字長選取m的值。

(2)如果m選取為2的冪,也即2ω,則選取的a通常應(yīng)該滿足amod8=5。

(3)當(dāng)參數(shù)m和a的選定比較合理時,對于c的選擇約束性不是很強(qiáng)烈,但要保證c與m互素。

(4)種子X0應(yīng)該是隨機(jī)選取的,可以將時間戳作為種子。

7.5.3針對LCG的攻擊方式

LCG在密碼安全性方面十分脆弱,接下來根據(jù)參數(shù)的已知情況分以下四種情形討論對LCG的攻擊。

·已知乘數(shù)a、增量c、模數(shù)m;

·已知乘數(shù)a、模數(shù)m,增量c未知;

·已知模數(shù)m,乘數(shù)a和增量c未知;

·乘數(shù)a、增量c、模數(shù)m均未知。

1.已知乘數(shù)a、增量c、模數(shù)m

這種情況下,就相當(dāng)于已知LCG的所有參數(shù)。現(xiàn)在已知某LCG系統(tǒng)產(chǎn)生了以下三組連續(xù)的值,并且知道上述三個參數(shù)。

在已知三個參數(shù)并且知道了產(chǎn)生的序列值后,可以很容易地根據(jù)LCG公式推算后續(xù)或者之前的某個序列值。讀者可自行驗證上述值和參數(shù)是否一致。

2.已知乘數(shù)a、模數(shù)m,增量c未知

3.已知模數(shù)m,乘數(shù)a和增量c未知

4.乘數(shù)a、增量c、模數(shù)m均未知

現(xiàn)在三個參數(shù)都未知,但是已知LCG產(chǎn)生的初值和隨后多個連續(xù)的序列值。

按照LCG的表達(dá)式以及上述已知的信息構(gòu)造線性方程組,發(fā)現(xiàn)由于模數(shù)未知和模算術(shù)折返特性,每次新建一個線性方程式的同時也會引入新的未知變量,如下面的k1、k2、k3。

7.6梅森旋轉(zhuǎn)算法

梅森旋轉(zhuǎn)(MersenneTwister)算法是利用線性反饋移位寄存器快速產(chǎn)生偽隨機(jī)數(shù)的方法,但它并不能用于安全要求高的應(yīng)用場景,因為它和線性同余算法一樣具有周期性,通過觀察周期,即可對之后生成的隨機(jī)數(shù)序列進(jìn)行預(yù)測。

7.6.1算法簡介

如果形如2n-1的數(shù)是一個素數(shù),則稱之為梅森素數(shù)。例如n=19937就是一個梅森素數(shù),這也是梅森旋轉(zhuǎn)算法名字MT19937的由來。常見的兩種梅森旋轉(zhuǎn)算法為基于32位的

MT19937-32和基于64位的MT19937-64。梅森旋轉(zhuǎn)算法的周期為219937-1,說明它是一個19937級的線性反饋移位寄存器。梅森旋轉(zhuǎn)算法是利用線性反饋寄存器一直進(jìn)行移位旋轉(zhuǎn),因此實際上MT19937-32只需要用32位就能做到。

整個算法主要分為三個步驟:

(1)獲得初始的梅森旋轉(zhuǎn)鏈;

(2)對梅森旋轉(zhuǎn)鏈?zhǔn)褂眯D(zhuǎn)算法;

(3)對旋轉(zhuǎn)算法所得的結(jié)果進(jìn)行處理。

上述Python代碼實現(xiàn)了MT19937RNG類,其中有三個核心函數(shù),分別為_init_()函數(shù)、generate_numbers()函數(shù)、extract_number()函數(shù)。

·_init_()函數(shù)是創(chuàng)建MT19937RNG對象時執(zhí)行的初始化函數(shù)。在_init_()函數(shù)中,定義一個數(shù)組MT用于存儲梅森旋轉(zhuǎn)鏈,數(shù)組MT有624個元素,根據(jù)種子seed初始化MT[0]的值,后續(xù)元素由以下遞推關(guān)系計算得到:

MT元素值也稱為梅森旋轉(zhuǎn)鏈。

·generate_numbers()函數(shù)的功能是更新MT數(shù)組,即對梅森旋轉(zhuǎn)鏈?zhǔn)褂妹飞D(zhuǎn)算法進(jìn)行更新,其具體實現(xiàn)就是將MT[i]、MT[(i+1)%624]和MT[(i+397)%624]的值,通過遞推關(guān)系

計算出新的MT[i]值。

·extract_number()函數(shù)對generate_numbers()函數(shù)生成的梅森旋轉(zhuǎn)鏈進(jìn)行處理,將處理結(jié)果作為隨機(jī)數(shù)輸出。設(shè)第i個隨機(jī)數(shù)為num,計算過程如下:

7.6.2安全性分析

通過代碼分析,MT19937RNG在初始化時建立了一個長度為624的數(shù)組MT,使用extract_number()函數(shù)來生成隨機(jī)數(shù)。

第一次生成隨機(jī)數(shù)時調(diào)用generate_numbers()函數(shù)更新MT數(shù)組的值,之后每連續(xù)生成624個隨機(jī)數(shù),都將使用generate_numbers()函數(shù)更新MT數(shù)組的值。

通過分析extract_number()函數(shù)的代碼,能夠發(fā)現(xiàn)該函數(shù)的計算過程是可逆的。假設(shè)生成的隨機(jī)數(shù)序列存儲在數(shù)組randomnum[]中,其中,randomnum[k]是第k個隨機(jī)數(shù),由于extract_number()函數(shù)可逆,則可根據(jù)randomnum[k]求解對應(yīng)的MT[k]的值,也可根據(jù)extract_number()計算MT[i]對應(yīng)的randomnum[i]的值,其中,MT[i]可通過generate_numbers()函數(shù)求解,新MT[i]的值是由MT[i]、MT[i+1]和MT[i+397]生成的。

因此,可以將前624個隨機(jī)數(shù)的值保存在數(shù)組randomnum[]中,通過extract_number()函數(shù)計算的逆過程得到每個randomnum[k]對應(yīng)的MT[k],即得到初始的梅森旋轉(zhuǎn)鏈。根據(jù)梅森旋轉(zhuǎn)算法生成隨機(jī)數(shù)的過程,使用generate_numbers()函數(shù)更新梅森旋轉(zhuǎn)鏈(數(shù)組MT[]),最后對新的MT[]數(shù)組使用extract_number()函數(shù)生成隨機(jī)數(shù),從而可以對624個隨機(jī)數(shù)之后的隨機(jī)數(shù)值進(jìn)行預(yù)測。

7.7RC4流密碼算法

7.7.1RC4工作原理RC4流密碼算法主要分兩步來實現(xiàn):第一步:密鑰調(diào)度算法(KeySchedulingAlgorithm,KSA),根據(jù)給定的密鑰初始化S盒;步:偽隨機(jī)數(shù)生成算法(PseudoRandom-GenerationAlgorithm,PRGA),生成密鑰流。上述兩個算法在流密碼系統(tǒng)中的組成結(jié)構(gòu)如圖7.28所示。

圖7.28RC4流密碼組成

1.KSA(密鑰調(diào)度算法)

密鑰調(diào)度算法首先初始化數(shù)組S和T,其中S數(shù)組包含256個元素,每個元素都是一個字節(jié)。數(shù)組S中的元素依次為0、1、2、3、…、254、255;數(shù)組T的元素值就是密鑰的重復(fù)循環(huán),如圖7.29所示。

圖7.29初始化數(shù)組S和T

接著在上述初始化后的S和T數(shù)組基礎(chǔ)上,對S數(shù)組的某兩個元素進(jìn)行置換操作。兩個元素由索引指針i和j來表示,i從0開始依次遞增,j每次遞增的量由S[i]和T[i]相加后對256取模得到,最后交換下標(biāo)i和下標(biāo)j分別指向的這兩個元素。置換代碼如下,示意圖如圖7.30所示。

圖7.30初始置換S

2.PRGA(偽隨機(jī)數(shù)生成算法)

PRGA生成加密所需的密鑰字節(jié)流,而不是比特流,每循環(huán)一次產(chǎn)生一個字節(jié),用于后續(xù)同明文異或加密。密鑰流實際上就是從數(shù)組S中隨機(jī)選取得到的,和數(shù)組T無關(guān)。每次循環(huán)當(dāng)中分別計算索引指針i和j,然后把上述兩個位置的元素置換,并把這兩個元素的值相加后作為新的索引位置,該位置的元素就是這一輪的密鑰流字節(jié)輸出。

PRGA代碼如下,示意圖如圖7.31所示。

圖7.31RC4PRGA生成密鑰流

7.7.2RC4安全性分析

根據(jù)前面RC4流密碼算法的介紹,其核心組件是KSA和PRGA,因此,對RC4安全性的分析也從這兩個算法組件展開。

1.密鑰調(diào)度算法安全分析

RC4密鑰調(diào)度算法的安全問題主要在于密鑰和密鑰流之間的相關(guān)性,也就是某些特定的密鑰可能導(dǎo)致產(chǎn)生的偽隨機(jī)密鑰流呈現(xiàn)某種規(guī)律,從而導(dǎo)致明文信息部分泄露或者恢復(fù)。

圖7.32RC4弱密鑰推導(dǎo)過程

圖7.32中只要密鑰滿足(K[0],K[1],…,K[255])=(0,0,255,254,…,3,2),

那么就可以使KSA算法的置換失效。圖中的計算是基于(mod256)完成的,根據(jù)模運算特性,還可以得到其他更多組弱密鑰,這里只是列舉了最簡單的一種。

除此之外,研究人員針對KSA算法還發(fā)現(xiàn)了一類稱為“不變性(Invariance)”弱點的密鑰安全問題。“不變性”弱點是指RC4密鑰中存在的L型模式。RC4密鑰中一旦存在這種模式,將導(dǎo)致在KSA算法初始化完成后,密鑰的部分信息被保留下來。如圖7.33所示的部分最低有效位(LeastSignificantBit,LSB),在后續(xù)的PRGA算法處理過程中,這些LSB會出現(xiàn)在偽隨機(jī)密鑰字節(jié)流的LSB中。

圖7.33L型弱密鑰

有關(guān)此類L型模式的詳細(xì)信息可以參考文獻(xiàn)。這些有明顯偏差的偽隨機(jī)密鑰字節(jié)流,最終會與明文進(jìn)行XOR,從而導(dǎo)致明文的大量信息可以從密文中得到。

在RC4密鑰調(diào)度算法中,存在上述模式的密鑰出現(xiàn)的概率非常高。LSB的比特位數(shù)不同,有單個比特LSB、兩個比特LSB、3~7個比特LSB三種類型,分別對應(yīng)不同類型的RC4弱密鑰,其中單個比特類型的數(shù)量是最多的,也稱為主類(MainClass)。

對于字節(jié)長度為L的密鑰,每個類別出現(xiàn)的概率為2

-(qL+(9-q))。例如,對于16字節(jié)密鑰,主類的出現(xiàn)概率為2-24(q=1,L=16),2個比特出現(xiàn)的概率為2-39(q=2,L=16),更多類別的出現(xiàn)概率如表7.3所示。

上述類別的密鑰經(jīng)過PRGA產(chǎn)生的密鑰流中,q個LSB在偽隨機(jī)串的前K個字節(jié)中被保存下來的概率如圖7.34所示。圖中縱軸為概率值,橫軸為K值。從圖可以看出,前20個字節(jié)中,LSB被保存下來的概率相當(dāng)可觀。

圖7.34單個比特和兩個比特的密鑰流表現(xiàn)出來的確定性模式

2.密鑰流安全分析

針對RC4密鑰流生成算法的安全研究,主要集中在密鑰流的統(tǒng)計特性分析上,特別是最初的256個密鑰流字節(jié)中某些位置的值出現(xiàn)的概率顯著地偏離均勻分布所導(dǎo)致的偏移(Bias),是目前各類RC4算法攻擊的基礎(chǔ)。

在RC4算法完成KSA步驟之后得到初始化好的狀態(tài)數(shù)組S,接下來進(jìn)入密鑰流生成過程。需要注意的是,后續(xù)密鑰流的產(chǎn)生只和數(shù)組S有關(guān)。

1)單字節(jié)偏差攻擊

第一個發(fā)現(xiàn)有顯著偏差的字節(jié)是RC4密鑰流中的第二個字節(jié)Z2。該字節(jié)等于0的概率近似為1/128,而不是正常均勻分布的1/256。

如圖7.35所示,在初始置換開始之前,假設(shè)S[1]=X(X≠2),S[2]=0,那么密鑰流輸出的第二個字節(jié)等于0的概率為1。

圖7.35RC4加密前兩輪的輸出

研究人員SenGupta和Maitra進(jìn)一步擴(kuò)展了上述結(jié)論:RC4算法輸出的第r(3≤r≤255)個密鑰流字節(jié)Zr=0的概率為

其中,密鑰是隨機(jī)選擇的,c3=0.351089,c4、c5、…、c255是一個遞減序列,滿足以下界限范圍:0.242811≤cr≤1.337057,換句話說,密鑰流的第3到第255字節(jié)偏向0的概率近似為1/216。

圖7.36給出了密鑰流中某些位置存在的偏移。

圖7.36其他位置處的密鑰字節(jié)也存在偏移現(xiàn)象

除了上述可以通過理論進(jìn)行計算和量化的偏移字節(jié),有些偏移是靠實驗發(fā)現(xiàn)的,并沒有相應(yīng)的理論計算公式。例如,AlFardan[23]發(fā)現(xiàn)的如圖7.37所示的偏移字節(jié)就屬于這一類型。

圖7.37RC4密鑰流在位置Z16(top)、Z32(middle)和Z50(bottom)的分布

2)多字節(jié)偏移

多字節(jié)偏移又稱長效偏移(LongTermBiase),通常出現(xiàn)在起始256個密鑰流字節(jié)之后的序列中。相比于單字節(jié)偏移,多字節(jié)偏移通常會重復(fù)地、周期性地出現(xiàn)在密鑰流中。Fluhrer和McGrew等人發(fā)現(xiàn)了迄今為止最多的多字節(jié)偏移。

本書作者對連續(xù)兩個字節(jié)值進(jìn)行了統(tǒng)計分析,得到了字節(jié)流位置對(Zr,Zr+1),r≥1的有效偏移,如表7.4所示

假設(shè)S表示密文數(shù)量,即有密文C1,…,CS,對于1≤j≤S,Cj,r表示第j個密文Cj的第r個字節(jié)。攻擊者首先提前計算所有位置密鑰流字節(jié)Zr的概率分布,即第r個字節(jié)等于k的概率pr,k:

由此概率值pr,k,攻擊者可以使用最大似然估計方法恢復(fù)最優(yōu)明文。

對于任意一個固定位置r,其候選明文值為u,用Nk(u)表示在密鑰流的第r個字節(jié)出現(xiàn)明文為u,密鑰為k的密文個數(shù),計算公式如下:

由Nk(u)組成向量(N(u)0x00,…,(N(u)0xff))表示Zr的概率分布。將該分布同前面提前計算得到的精準(zhǔn)分布pr,0x00,…,pr,0xff進(jìn)行匹配,可以得到最佳候選明文u=pr。

對于最大似然估計理論來說,就是找到使得以下概率最大的u(0x00≤u≤0xff):

λu表示在位置r處明文字節(jié)u加密得到密文字節(jié){Cj,r}1≤j≤S的概率,它服從多項式分布。完整的單字節(jié)偏移攻擊(Single-byteBiasAttack)算法如下。

圖7.38明文恢復(fù)成功率

7.7.3實例分析

上述代碼和RC4算法非常相似,最大的區(qū)別是以下兩點:

(1)密鑰流字節(jié)值相比RC4多除了一個2(代碼第22行),使得字節(jié)值不大于127;

(2)在加密階段,使用加法代替了異或運算(代碼第23行),注意密文值不大于255。服務(wù)器端提供兩個功能:①用隨機(jī)產(chǎn)生的密鑰(代碼第25行)加密用戶輸入的信息(代碼第33行),然后返回給用戶;②輸出由隨機(jī)產(chǎn)生的密鑰加密flag后的結(jié)果。

輸出的結(jié)果均以十六進(jìn)制顯示。圖7.39給出了兩次flag加密的結(jié)果,其密文是不同的,這顯然是因為兩次加密時使用的密鑰不一樣。

圖7.39選項p輸出flag密文

由于加密是密鑰流字節(jié)和明文字節(jié)相加得到的,即

對于Pi,也就是明文flag保持不變且是可打印字符(范圍在0x20~0x7f),而密鑰Ki取值在0~127之間,因此,可以通過多次使用選項p獲得flag密文Ci,利用式(7.15)逐步縮小明文Pi的取值空間。

7.8快速相關(guān)攻擊

7.8.1快速相關(guān)攻擊簡介快速相關(guān)攻擊(FastCorrelationAttack)最早由Siegenthaler提出,是對非線性組合生成器的一種攻擊方式。其原理是利用NFSR密鑰發(fā)生器的輸出序列與其源LFSR的輸出序列之間具有的相關(guān)性,還原LFSR的初始狀態(tài)。如果非線性函數(shù)的某個輸入序列{ui}和輸出序列{zi}之間存在相關(guān)性,即p=[P(ui=zi)]>0.5,可以抽象為如圖7.40所示的BSC(BinarySymmetricChannel,二進(jìn)制對稱信道)模型。

圖7.40相關(guān)攻擊的BSC模型

7.8.2快速相關(guān)攻擊算法

Meier和Staffelbach在相關(guān)攻擊的基礎(chǔ)上提出了兩種快速相關(guān)攻擊算法,降低了相關(guān)攻擊的復(fù)雜度。這兩種算法又可以代表兩種快速相關(guān)攻擊的類型。

第一種是一次通過型算法。該算法首先將截取的密鑰流序列按照LFSR的長度進(jìn)行分割,接著對每個分割得到的序列片段使用校驗多項式進(jìn)行校驗,選擇出其中滿足校驗多項式最多的序列片段去恢復(fù)LFSR的初始狀態(tài)

第二種是利用概率迭代譯碼算法。該算法認(rèn)為截取序列的每個比特都有一個先驗概率p,著重關(guān)注滿足校驗多項式最少的比特位,通過幾次更新和迭代,修正BSC帶來的錯誤,恢復(fù)出LFSR的輸出序列,再進(jìn)一步地恢復(fù)出LFSR的初始序列。

兩種算法適用LFSR的特征多項式比較簡單,或者說抽頭數(shù)(指LFSR反饋多項式中值為1的個數(shù)或參與反饋的寄存器個數(shù))比較少的情況。

在上面提到的兩種算法中,都用到了校驗多項式,實質(zhì)上這里的校驗多項式就是我們熟知的奇偶校驗多項式。奇偶校驗多項式簡單來說,就是加上一個奇偶校驗位,使得要校驗的所有比特與奇偶校驗位之和為奇數(shù)(偶校驗則為偶數(shù))。而多項式的生成方式,就是利用迭代乘方:

例如一個級數(shù)為48的LFSR的抽頭數(shù)是2,抽頭位置分別是23和48,那么寫成反饋多項式的形式是

或

寫成f(x)的形式為

那么對它進(jìn)行迭代乘方的結(jié)果為

在討論快速相關(guān)攻擊算法之前,先定義S(p,t)表示截取序列{z}的t個比特和與源LFSR輸出序列{u}的相應(yīng)t個比特之和相同的概率,轉(zhuǎn)換成BSC模型下的說法是傳輸?shù)倪^程中t個比特有多大的概率均傳輸正確。其計算公式為

7.8.3快速相關(guān)攻擊算法A

如果一個LFSR的級數(shù)為n,那么只需要n個連續(xù)比特,就可以確定整個LFSR序列。算法A從截取序列{z}中選擇滿足最多校驗關(guān)系式的連續(xù)n位,記作{I0},作為源LFSR輸出序列{u}的某一段的估計。如果用這n個位擴(kuò)展成的整個LFSR序列與截取序列之間的相關(guān)性達(dá)到了預(yù)期值,則認(rèn)為這n個比特是源LFSR輸出序列的一段;否則對其進(jìn)行距離為1,2,3,…的漢明變換,直到求得正確結(jié)果。

算法A實現(xiàn)步驟

第8步,解線性方程組。若各方程是線性相關(guān)的,則使用附加比特位選擇一個線性無關(guān)的子方程組,將解出來的n個連續(xù)比特擴(kuò)展為整個LFSR序列,并與原來的截取序列{z}的n位進(jìn)行比較,若相關(guān)概率在(p-e,p+e)之間(通常取e為0.05),則認(rèn)為求解成功。若相關(guān)概率不在此區(qū)間之內(nèi),則認(rèn)為求解失敗,并對I0依次做距離為1,2,3,…的漢明變換進(jìn)行修正,每進(jìn)行一次漢明變換都轉(zhuǎn)入第7步,直到成功求解為止。

7.8.4快速相關(guān)攻擊算法B

算法B的基本思想:當(dāng)某一位zn滿足的校驗等式較少時,出錯的概率很大,對這些出錯概率較大的比特取補(bǔ),則新序列更接近源LFSR的輸出序列。計算出各比特的正確概率后,以此概率為先驗概率,再次計算各比特的正確概率。幾輪迭代計算后,正確比特的概率變得更高,錯誤比特的概率變得更低,再根據(jù)某個選定的門限值,決定是否對zn取補(bǔ)。如果仍未恢復(fù)出LFSR的輸出序列,則把各比特的先驗概率重置為p。重復(fù)以上過程,直至恢復(fù)源LFSR序列。

算法B實現(xiàn)步驟

第1步,計算校驗序列{z}每比特所需要的校驗方程平均數(shù):

第2步,將之前的S(p,t)