簡化版Trivium算法的線性逼近研究

馬猛，趙亞群

?

簡化版Trivium算法的線性逼近研究

馬猛，趙亞群

（信息工程大學數(shù)學工程與先進計算國家重點實驗室，河南鄭州 450001）

針對初始化輪數(shù)為288個時鐘的簡化版Trivium算法（又稱2輪Trivium）進行了線性逼近研究，設(shè)計了搜索最佳線性近似式算法，并通過對第1輪關(guān)于密鑰、初始化向量和密鑰流比特的表達式做非線性逼近，結(jié)合該算法，在同等條件下給出了2輪Trivium 16個偏差為的線性近似式，使通過多線性攻擊去識別2輪Trivium的一個具有特定比特的密鑰所需要的數(shù)據(jù)量降為個選擇，為Turan方案所需數(shù)據(jù)量的，且成功率保持不變。

流密碼；Trivium算法；多線性密碼分析；線性逼近

1 引言

由Canniàre和Preneel[1]于2005年設(shè)計的Trivium算法是2004年歐洲序列密碼計劃最終勝選的標準算法之一，該算法面向硬件實現(xiàn)，具有設(shè)計簡潔、安全、速度快和靈活性好等特點。因此，Trivium在發(fā)布之初就引起了廣泛關(guān)注，針對Trivium的安全性分析一直是流密碼的熱點研究方向之一。

目前針對Trivium的主要攻擊方法有線性攻擊、區(qū)分攻擊、代數(shù)攻擊、滑動攻擊、立方攻擊、錯誤引入攻擊等。Maximov和Biryukov[2]在2007年提出了Trivium的代數(shù)攻擊方法，攻擊的計算復(fù)雜度為，其中，常數(shù)是求解線性方程組的復(fù)雜度。2009年，Dinur和Shamir[3]針對初始化輪數(shù)為767個時鐘的簡化版 Trivium提出了立方攻擊，攻擊的計算復(fù)雜度為。2010年，Stankovski[4]對初始化輪數(shù)為1 078個時鐘的簡化版Trivium 進行了區(qū)分攻擊，攻擊的計算復(fù)雜度為。2011年，Hu等[5]通過重復(fù)錯誤注入的方式，提出了一種校驗部分原始密鑰流和部分錯誤密鑰流的方法，確定錯誤注入時間及位置，進而說明Trivium在故障攻擊下的脆弱性，較Hojsík等的故障攻擊方法[6]，該模型有更弱的假設(shè)條件。2014年，Avijit等[7]提出了一種故障攻擊方法，在已知117 bit原始密鑰流和236 bit錯誤密鑰流的條件下，攻擊的計算復(fù)雜度是。Prakash等在文獻[8]中給出了一種條件很弱的差分錯誤攻擊模型，具有很好的通用性。

Turan等[9]將Trivium的初始化輪數(shù)由1 152個時鐘數(shù)降低為288個，得到了一個簡化的版本（即2輪Trivium），在某種弱密鑰條件下，找到了該簡化版本的一個偏差為的線性近似式，從而可以對其進行單線性密碼分析。在此基礎(chǔ)上，賈艷艷等[10]找到另一個偏差為的線性逼近，基于多線性密碼分析理論，提出了具體的攻擊算法，從而可以對其進行多線性密碼分析，同時指出，若能找到個相同偏差的線性近似式，多線性密碼分析所需的數(shù)據(jù)量只有單線性密碼分析的，且攻擊成功的概率保持不變。孫文龍等[11]給出了在弱密鑰和選擇攻擊的條件下搜索最佳線性近似式的算法，據(jù)此算法找到了3個偏差為的線性近似式，但是由于密鑰不同，不能進行多線性密碼分析。歐智慧等[12]通過改變2輪Trivium第一輪的時鐘個數(shù)，給出了1個偏差為的線性近似式和8個偏差為的線性近似式，使多線性密碼分析所需要的數(shù)據(jù)量降為文獻[9]的，具體的攻擊算法可見文獻[10]。

本文的目的是尋找偏差更大、個數(shù)更多的2輪Trivium線性近似式，從而降低對2輪Trivium進行多線性密碼分析所需要的數(shù)據(jù)量，主要工作體現(xiàn)在如下2點：1）在某種弱密鑰條件下，通過搜索最佳線性近似式算法給出了偏差為的線性近似式；2）對2輪Trivium的第1輪關(guān)于密鑰、初始化向量和密鑰流比特的表達式做非線性逼近，找到了2輪Trivium的16個偏差為的線性近似式。

2 基礎(chǔ)知識

定義1[13]稱是隨機變量的偏差，稱是函數(shù)的偏差。若的偏差為，則稱函數(shù)以偏差逼近。

引理1[14]堆積引理。設(shè)是上個獨立隨機變量，表示的偏差。表示隨機變量的偏差，則。

引理2[15]最佳仿射逼近定理。設(shè)是元布爾函數(shù)，如果，那么當時，為的最佳仿射逼近，當時，為的最佳仿射逼近。

引理3[12]設(shè)為元布爾函數(shù)，。如果，則。如果，則，其中，為中具有形式的個數(shù)。

3 Trivium算法描述

Trivium算法結(jié)構(gòu)由3個移位寄存器構(gòu)成，級數(shù)分別為93、84和111，設(shè)、分別表示算法的密鑰和初始化向量。Trivium算法初始化階段首先將80 bit的密鑰和80 bit的初始化向量載入到3個移位寄存器內(nèi)部狀態(tài)中，93級布態(tài)方式為：，84級布態(tài)方式為：，111級布態(tài)方式為：，然后運行密鑰流生成算法，空跑個時鐘，此階段不輸出密鑰流比特，只為3個寄存器布態(tài)，輸出為Trivium的內(nèi)部狀態(tài)。Trivium算法密鑰流生成階段的算法和初始化階段算法相同，只是此時輸出密鑰流，輸入為內(nèi)部狀態(tài)和密鑰數(shù)，算法描述如下。

賈艷艷等[10]指出，將Trivium算法可以看作是函數(shù)的集合，其中，是由bit和bit生成第個密鑰流比特的函數(shù)，如果找到了的一個偏差為的線性近似式，將密碼再同步次，則一定可以得到密鑰的1 bit信息。文獻[9~12]的思想是：對Trivium算法進行多線性密碼分析時，可以將其初始化階段像分組密碼一樣分成輪，將每一輪的線性近似式有效組合，最終得到Trivium算法一個關(guān)于(,)和密鑰流比特的線性近似式，其偏差可利用堆積引理求得。2輪Trivium的初始化輪數(shù)為288個時鐘，文獻[9~11]選擇對稱分輪，將144個時鐘作為一輪來分析2輪Trivium；文獻[12]選擇不對稱分輪，分別設(shè)定第一輪所占時鐘個數(shù)為141、154來分析2輪Trivium。

4 研究結(jié)果

對于給定的密碼算法，線性密碼分析的關(guān)鍵是找到它的線性近似式。針對2輪Trivium，一般的做法是首先對每輪進行線性逼近，然后將各個線性逼近有效地組合，得到最終的線性近似式。事實上，也可以通過對第1輪求具有較大偏差的非線性近似式，對第2輪求線性近似式，有效組合得到2輪Trivium的線性近似式，這也是本文的思想。

(1)

用非線性二次函數(shù)

(2)

(3)

綜合式(1)~式(3)，由堆積引理得到式(3)成立的偏差為，其中，為密鑰的規(guī)模。但是這個偏差太小，對于實際的線性分析沒有意義。此時，可以通過選擇特殊密鑰和增大式(3)成立的偏差，這對于選擇攻擊來說并不困難。設(shè)表示為零的密鑰比特集合，表示為零的比特集合。、分別表示、的規(guī)模。、分別表示給定、并化簡剩余的二次項、三次項的個數(shù)，由堆積引理，此時式(3)成立的偏差為

算法1 搜索最佳線性近似算法

(5)

式(5)中的各個非線性項數(shù)量相互獨立，有24個線性項，15個二次項，1個三次項，代入式(4)，式(3)成立的偏差為：，由上述分析可知式(6)即為偏差最大的2輪Trivium線性近似函數(shù)。

(6)

孫文龍等[11]在指定10 bit密鑰和10 bit為零的前提下，通過算法得到了偏差為的最佳線性近似式。而對于同樣的目標函數(shù)式，執(zhí)行本文給出的算法1，輸入，最佳線性近似式以偏差成立。用類似于式(2)的多個非線性式去逼近式(1)，可以得到多個不同的2輪Trivium線性近似式。選擇非線性式的原則是：來自式(1)的非線性項，或可以被式(1)的非線性項合并，且使關(guān)于的函數(shù)表達式具有較低次數(shù)和較少非線性項。多線性密碼分析要求識別的是具有特定比特的密鑰，所以指定密鑰為零的比特必須是相同位置上的。另外，選取時，特定比特盡量在相同位置上，這樣選擇攻擊將會易于操作，便于實施。取不同的非線性式逼近式(1)，執(zhí)行算法1，令，輸入，僅搜索，得到了16個偏差為的線性近似式，具體的結(jié)果如表1所示?；谶@16個線性近似式可對2輪Trivium進行多線性密碼分析，具體算法可見文獻[10]。

表1 t1=144時z1的16個偏差為2?23.42線性近似

為了方便表示，給出如下記號

(7)

用非線性二次式

(8)

(9)

(10)

式(10)即為最終的2輪Trivium線性近似式。

表2 t1=141時z1的6個線性近似

表3 結(jié)果對比

5 結(jié)束語

本文對2輪Trivium算法進行了線性逼近研究，用非線性式逼近第1輪關(guān)于密鑰、和密鑰流比特的表達式，給出了在某種弱密鑰條件下搜索最佳線性近似式的算法，據(jù)此算法找到了16個偏差為的線性近似式，使對2輪Trivium算法進行多線性攻擊的數(shù)據(jù)量降低為文獻[10]所需數(shù)據(jù)量的。需要進一步研究的問題：一是算法1的時間復(fù)雜度和存儲復(fù)雜度有待降低；二是能否找到2輪Trivium個數(shù)更多、偏差更大的線性近似式；三是如何利用上述思想方法對更多輪數(shù)的Trivium算法進行線性分析。

[1] CANNIàRE C, PRENEEL B. Trivium specifications [EB/OL]. http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf, 2007.

[2] MAXIMOV A, BIRYUKOV A. Two trivial attacks on Trivium[C]// c2007:36-55.

[3] DINUR, SHAMIR A. Cubic attacks on tweakable black box polynomials[C]//Advances in Cryptology-EUROCRYPT 2009. c2009: 278-299.

[4] STANKOVSKI P. Greedy distinguishers and nonrandomness detectors[C]//INDOCRYPT 2010. c2010: 210-226.

[5] HOJSíK M, RUDOLF B. Differential fault analysis of Trivium[C]// FSE 2008. c2008: 158-172.

[6] HU Y P, GAO J T, LIU Q, et al. Fault analysis of Trivium[C]//Designs, Codes and Cryptography. c2011: 289-311.

[7] AVIJIT D, GOUTAM P. Deterministic hard fault attack on trivium[C]//Advances in Information and Computer Security. c2014: 134-145.

[8] PRAKASH D, AVISHEK A. Improved multi-bit differential fault analysis of trivium[C]//Progress in Cryptology. c2014: 37-52.

[9] TURAN M S, KARA O. Linear approximations for 2-round Trivium[C]//Workshop on the State of the Art of Stream Cipher (SASC2007). Bochum, c2007: 22-31.

[10] 賈艷艷, 胡予濮, 楊文峰, 等. 2輪Trivium的多線性密碼分析[J]. 電子與信息學報, 2011, 33(1): 223-227.

JIA Y Y, HU Y P, YANG W F, et al. Linear cryptanalysis of 2-round Trivium with multiple approximations[J]. Journal of Electronics & Information Technology, 2011, 33(1): 223-227.

[11] 孫文龍, 關(guān)杰, 劉建東. 針對簡化版Trivium算法的線性分析[J].計算機學報,2012,35(9): 1890-1896.

SUN W L, GUAN J, LIU J D. Linear cryptanalysis of simplified Trivium[J]. Chinese Journal of Computers, 2012,35(9): 1890-1896.

[12] 歐智慧, 趙亞群. 2輪Trivium的線性逼近研究[J].計算機工程,2013,39(11): 31-34.

OU Z H, ZHAO Y Q. Study on linear approximation of 2-round Trivium[J]. Computer Engineering, 2013,39(11): 31-34.

[13] 李世取, 曾本勝, 廉玉忠, 等.密碼學中的邏輯函數(shù)[M].北京:中軟電子出版社,2003: 254-255.

LI S Q, ZENG B S, LIAN Y Z, et al. Logical functions in cryptography[M]. Beijing: Software and Electronic Press, 2003: 254-255.

[14] DOUGLAS R, STINSON. 密碼學原理與實踐[M]. 北京:電子工業(yè)出版社,2010: 123-124.

DOUGLAS R. STINSON. Cryptography theory and practice[M]. Beijing: Publishing House of Electronics Industry, 2010: 123-124.

[15] 丁存生,肖國鎮(zhèn). 流密碼及其應(yīng)用[M].北京:國防科學出版社,1994: 28-29.

DING C S, XIAO G Z. Stream cipher and its applications[M]. Beijing: National Defense Industry Press, 1994: 28-29.

Research on linear approximations of simplified Trivium

MA Meng, ZHAO Ya-qun

(State Key Lab of Mathematical Engineering and Advanced Computing, Information Engineering University, Zhengzhou 450001, China)

The linear approximations of simplified Trivium with the initialization of 288 clocks (2-round Trivium) was studied. An algorithm was designed to search optimal linear approximations. Moreover, a method was presented to conduct a linear approximation of 2-round Trivium by approximating the first round equation which involved the key bits,bits and the first keystream bit with a nonlinear equation. Based on this method, 16 linear approximations with the same biaswere found using proposed algorithm. Furthermore, multiple linear cryptanalysis was made on 2-round Trivium. The result shows that it can approach the same success rate withchosens, that is to say, the data complexity isof that in Turan’s scheme.

stream ciphers, Trivium, mutiple linear cryptanalysis, linear approximation

TN918.1

A

10.11959/j.issn.1000-436x.2016108

2015-06-25；

2015-12-16

信息保障技術(shù)重點實驗室開放基金資助項目（No.KJ-13-009）

The Foundation of Science and Technology on Information Assurance Laboratory (No.KJ-13-009)

馬猛（1986-），男，河南南陽人，信息工程大學碩士生，主要研究方向為流密碼分析、概率統(tǒng)計在密碼學中的應(yīng)用。

趙亞群（1961-），女，江蘇淮安人，信息工程大學教授、碩士生導(dǎo)師，主要研究方向為密碼基礎(chǔ)理論及概率統(tǒng)計應(yīng)用。