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

馬猛，趙亞群

?

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

馬猛，趙亞群

（信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南鄭州 450001）

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

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

1 引言

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

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

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

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

2 基礎(chǔ)知識(shí)

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

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

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

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

3 Trivium算法描述

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

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

4 研究結(jié)果

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

(1)

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

(2)

(3)

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

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

3.2 社區(qū)糖尿病患者自行注射胰島素不規(guī)范 《中國糖尿病藥物注射技術(shù)指南2011版》［8］指出，注射技術(shù)在糖尿病注射治療中扮演著重要角色，與注射藥物同樣重要。全球范圍內(nèi)，不規(guī)范注射現(xiàn)象普遍存在，而我國糖尿病患者的注射現(xiàn)狀更是不容樂觀，這在一定程度上影響了胰島素治療的效果，最終導(dǎo)致血糖達(dá)標(biāo)率低。通過本次調(diào)查發(fā)現(xiàn)，社區(qū)糖尿病患者胰島素注射操作水平處于中等，大部分操作能夠達(dá)標(biāo)，突出地表現(xiàn)在以下幾個(gè)環(huán)節(jié)。

(5)

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

(6)

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

表1 t1=144時(shí)z1的16個(gè)偏差為2?23.42線性近似

為了方便表示，給出如下記號(hào)

(7)

用非線性二次式

(8)

(9)

(10)

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

表2 t1=141時(shí)z1的6個(gè)線性近似

5 結(jié)束語

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

[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]. 電子與信息學(xué)報(bào), 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].計(jì)算機(jī)學(xué)報(bào),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].計(jì)算機(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] 李世取, 曾本勝, 廉玉忠, 等.密碼學(xué)中的邏輯函數(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. 密碼學(xué)原理與實(shí)踐[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].北京:國防科學(xué)出版社,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ù)重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目（No.KJ-13-009）

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

馬猛（1986-），男，河南南陽人，信息工程大學(xué)碩士生，主要研究方向?yàn)榱髅艽a分析、概率統(tǒng)計(jì)在密碼學(xué)中的應(yīng)用。

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