Grain型級(jí)聯(lián)反饋移存器的非奇異性判定

王秋艷，金晨輝

?

Grain型級(jí)聯(lián)反饋移存器的非奇異性判定

王秋艷，金晨輝

(解放軍信息工程大學(xué)三院，鄭州 450004)

Grain算法是歐洲序列密碼工程eSTREAM最終入選的面向硬件實(shí)現(xiàn)的3個(gè)序列密碼算法之一，它由2個(gè)反饋移存器和前饋函數(shù)組成，能有效抵御基于線性反饋移存器的序列密碼攻擊。針對(duì)以Grain算法為特例的Grain型級(jí)聯(lián)反饋移存器的非奇異性判定問(wèn)題，給出Grain型級(jí)聯(lián)反饋移存器在初始化過(guò)程和密鑰流生成過(guò)程中，狀態(tài)刷新變換均構(gòu)成雙射的充分條件，并通過(guò)反例說(shuō)明對(duì)于有限域上的Grain型級(jí)聯(lián)反饋移存器，即使所使用的2個(gè)移存器都是非奇異的，并且前饋函數(shù)滿足相應(yīng)性質(zhì)，其狀態(tài)刷新變換仍可能不構(gòu)成雙射。利用Grain v1算法驗(yàn)證了該非奇異性判定結(jié)果的正確性。

序列密碼；Grain算法；非線性反饋移存器；非奇異性；狀態(tài)刷新變換；雙射性

1 概述

線性反饋移存器的輸出序列具有良好的密碼學(xué)性質(zhì)，目前很多序列密碼算法都由線性反饋移存器和非線性前饋函數(shù)(或非線性有記憶變換)構(gòu)成。然而，由于線性反饋移存器的輸出信號(hào)之間存在線性制約性，從而產(chǎn)生很多針對(duì)基于線性反饋移存器設(shè)計(jì)的序列密碼的攻擊方法，如代數(shù)攻擊[1]、快速相關(guān)攻擊[2]等，促使人們尋找新的序列密碼結(jié)構(gòu)。在eSTREAM工程中，最終勝出的3個(gè)面向硬件實(shí)現(xiàn)的序列密碼算法Grain算法[3]、Trivium算法[4]和Mickey算法[5]都是基于非線性反饋移存器設(shè)計(jì)。目前，基于非線性反饋移存器的設(shè)計(jì)已逐漸發(fā)展為序列密碼設(shè)計(jì)的重要方式。

Grain算法[6-7]是一個(gè)典型的基于非線性反饋移存器設(shè)計(jì)的序列密碼算法，為保證Grain序列密碼算法的輸出序列具有良好的密碼學(xué)性質(zhì)，Grain算法通過(guò)利用一個(gè)周期達(dá)到最大的線性反饋移存器控制一個(gè)非線性反饋移存器的方法設(shè)計(jì)其亂源結(jié)構(gòu)。這種將線性反饋移存器和非線性反饋移存器有機(jī)結(jié)合的方式，為序列密碼的設(shè)計(jì)提供了一個(gè)典型的模型。文獻(xiàn)[8]對(duì)該模型的安全性進(jìn)行了分析，對(duì)這種模型給出了一種區(qū)分攻擊。文獻(xiàn)[9]對(duì)該模型進(jìn)行了代數(shù)攻擊和相關(guān)攻擊。文獻(xiàn)[10]研究了其輸出序列的周期性質(zhì)。

反饋移存器的非奇異性[11]，也就是反饋移存器的狀態(tài)刷新變換構(gòu)成雙射，是序列密碼設(shè)計(jì)中對(duì)反饋移存器的基本要求。如果反饋移存器是奇異的，則其狀態(tài)圖將出現(xiàn)分叉現(xiàn)象，從而存在2個(gè)能產(chǎn)生相同的后續(xù)狀態(tài)的移存器狀態(tài)，此時(shí)基于該移存器設(shè)計(jì)的序列密碼可能存在等效密鑰，甚至可能遭遇基于相關(guān)(密鑰-IV)對(duì)的差分攻擊[12]。因此，在設(shè)計(jì)序列密碼時(shí)，應(yīng)該確保反饋移存器的非奇異性，以避免可能存在的安全隱患。

本文研究以Grain算法為特例的一類反饋移存器模型(稱為Grain型級(jí)聯(lián)反饋移存器)的非奇異性判定問(wèn)題。給出能使其在初始化過(guò)程和密鑰流生成過(guò)程中的狀態(tài)刷新變換都構(gòu)成雙射的充分條件，并通過(guò)反例證明在一定條件下Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新函數(shù)不能構(gòu)成雙射。

2 Grain型級(jí)聯(lián)反饋移存器簡(jiǎn)介

圖1 Grain型級(jí)聯(lián)反饋移存器的結(jié)構(gòu)框圖

在初始化過(guò)程和密鑰流生成過(guò)程2種情形下，Grain型級(jí)聯(lián)反饋移存器采取2種不同的狀態(tài)刷新方式：

3 Grain型級(jí)聯(lián)反饋移存器的非奇異性研究

首先給出Grain型級(jí)聯(lián)反饋移存器在密鑰流生成過(guò)程中狀態(tài)刷新變換構(gòu)成雙射的充分條件。

定理1 設(shè)在Grain型級(jí)聯(lián)反饋移存器中FSR1是非奇異的，則以下結(jié)論等價(jià)：

(2)Grain型級(jí)聯(lián)反饋移存器中FSR2是非奇異的；

證明：由引理可知，結(jié)論(2)和結(jié)論(3)等價(jià)。下文證明結(jié)論(1)與結(jié)論(3)等價(jià)。

設(shè)結(jié)論(3)成立。由于Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新變換為：

當(dāng)以下等式成立時(shí)：

由Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新變換定義可知：

且有：

由此即知結(jié)論(1)與結(jié)論(3)等價(jià)。

然后給出Grain型級(jí)聯(lián)反饋移存器在初始化過(guò)程中狀態(tài)刷新變換構(gòu)成雙射的充分條件。

定理2 設(shè)在Grain型級(jí)聯(lián)反饋移存器中FSR1和FSR2都是非奇異的，如果函數(shù)：

證明：Grain型級(jí)聯(lián)反饋移存器在初始化過(guò)程的狀態(tài)刷新變換為：

其中：

假設(shè)：

由Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新變換定義可知：

且有：

由定理1和定理2可知，為保證Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新函數(shù)構(gòu)成雙射，只需將Grain型級(jí)聯(lián)反饋移存器中的2個(gè)FSR都設(shè)計(jì)成非奇異反饋移存器，且前饋函數(shù)的輸入變量都不抽自2個(gè)FSR的最低級(jí)即可。

定理3表明，即使前饋函數(shù)的輸入變量從FSR2的最低級(jí)抽取，在一定條件下仍可保證Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新函數(shù)構(gòu)成雙射。

定理3 設(shè)在Grain型級(jí)聯(lián)反饋移存器中FSR1和FSR2是非奇異的，如果函數(shù)：

證明：Grain型級(jí)聯(lián)反饋移存器在初始化過(guò)程的狀態(tài)刷新變換為：

其中：

假設(shè)：

由Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新變換定義可知：

且有：

下面給出定理3的一個(gè)反例，當(dāng)前饋函數(shù)滿足定理3的條件，輸入變量不從FSR2的最低級(jí)抽取，如果FSR1的反饋函數(shù)不滿足定理3的條件，則Grain型級(jí)聯(lián)反饋移存器的狀態(tài)刷新函數(shù)就有可能構(gòu)不成雙射。

定理4 設(shè)Grain型級(jí)聯(lián)反饋移存器中FSR1和FSR2的反饋函數(shù)滿足：

說(shuō)明：

最后證明Grain v1算法在初始化過(guò)程和密鑰流生成過(guò)程的狀態(tài)刷新函數(shù)都是雙射的。

定理5 Grain v1算法在初始化過(guò)程和密鑰流生成過(guò)程的狀態(tài)刷新變換都是雙射的。

4 結(jié)束語(yǔ)

本文研究了Grain型級(jí)聯(lián)反饋移存器的非奇異性問(wèn)題，給出了其在初始化過(guò)程和密鑰流生成過(guò)程中狀態(tài)刷新變換構(gòu)成雙射的2個(gè)充分條件，并舉例說(shuō)明了在一定條件下其狀態(tài)刷新變換可能不構(gòu)成雙射，這些結(jié)果對(duì)于基于Grain型級(jí)聯(lián)反饋移存器的序列密碼的設(shè)計(jì)和分析具有實(shí)際的應(yīng)用價(jià)值。通過(guò)本文分析可知，Grain型級(jí)聯(lián)反饋移存器存在潛在弱點(diǎn)，必須謹(jǐn)慎選擇其反饋函數(shù)和濾波函數(shù)以保證其安全性。在下一步的工作中，將進(jìn)一步對(duì)Grain型級(jí)聯(lián)反饋移存器的密碼學(xué)性質(zhì)進(jìn)行分析，并研究該類移存器的構(gòu)造問(wèn)題。

[1] Courtois N T, Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback[C]//Proc. of EUROCRYPT’03. Warsaw, Poland: Springer-Verlag, 2003: 345-359.

[2] Meier W, Staffelbach O. Fast Correlation Attacks on Stream Ciphers[J]. Journal of Cryptology, 1989, l(3): 159-176.

[3] Hell M, Johansson T, Meier W. Grain——A Stream Cipher for Constrained Environments[EB/OL]. (2005-06-22). http://www. ecrypt.eu.org/stream/ciphers/grain/grain.pdf.

[4] de Cannière C. Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles[C]//Proc. of ISC’06. [S. l.]: Springer-Verlag, 2006: 171-186.

[5] Babbage S. The Stream Cipher MICKEY-128 2.0[EB/OL]. (2006-08-18). http://www.ecrypt.eu.org/stream/p2ciphers/mickey128/ mickey128_p2.pdf.

[6] Maximov A. Cryptanalysis of the “Grain” Family of Stream Cipher[C]//Proc. of ASIACCS’06. New York, USA: ACM Press, 2006: 283-288.

[7] 宋海欣, 范修斌, 武傳坤, 等. 流密碼算法Grain的立方攻擊[J]. 軟件學(xué)報(bào), 2012, 23(1): 171-176.

[8] 黃小莉, 武傳坤. 對(duì)一種新的序列密碼結(jié)構(gòu)的密碼分析[J]. 軟件學(xué)報(bào), 2008, 19(5): 1256-1264.

[9] Berbain C, Gilbert H. Algebraic and Correlation Attacks Against Linearly Filtered Non Linear Feedback Shift Registers[C]//Proc. of SAC’09. [S. l.]: Springer-Verlag, 2009: 184-198.

[10] Hu Honggang. Periods on Two Kinds of Nonlinear Feedback Shift Registers with Time Varying Feedback Functions[J]. International Journal of Foundations of Computer Science, 2011, 22(6): 1317-1329.

[11] Lai Xuejia. Condition for the Nonsingularity of a Feedback Shift Register over a General Finite Field[J]. IEEE Transac- tions on Information Theory, 1987, 33(5): 747-749.

[12] Wu Hongjun, Huang Tao, Nguyen P H. Differential Attacks Against Stream Cipher ZUC[C]//Proc. of ASIACRYPT’12. Beijing, China: [s. n.], 2012: 262-277.

編輯 陸燕菲

Criteria forNonsingularityof Grain-like Cascade Feedback Shift Register

WANG Qiu-yan, JIN Chen-hui

(The Third Institute, PLA Information Engineering University, Zhengzhou 450004, China)

Grain cipher is one of the 3 final hardware-oriented stream ciphers of the eSTREAM project, it is based on two feedback shift registers and a filtering function, and it can effectively resist stream cipher attacks based on linear feedback shift register. In this paper, the nonsingularity of the Grain-like cascade feedback shift registers is investigated, the sufficient conditions of state refresh transformations in initialization phase and key stream generation phase being bijective is given. As a counterexample, for the word-oriented Grain-like cascade feedback shift registers, even if the two feedback shift registers are both nonsingular, and the filtering function satisfies proper conditions, the state update transformation can also be nonbijective. It proves the result of criteria for nonsingularity by using Grain v1 algorithm.

stream cipher; Grain algorithm; nonlinear feedback shift register; nonsingularity; state refresh transformation; bijectivity

1000-428(2014)03-0167-04

A

TN918.1

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272488, 61272041)。

王秋艷(1985－)，女，博士研究生，主研方向：密碼學(xué)；金晨輝，教授、博士生導(dǎo)師。

2013-03-01

2013-04-02 E-mail：wangqiuyan06@gmail.com

10.3969/j.issn.1000-3428.2014.03.034