简化版Trivium算法的线性逼近研究

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

摘要/Abstract

摘要：

针对初始化轮数为288个时钟的简化版Trivium算法（又称2轮Trivium）进行了线性逼近研究，设计了搜索

Abstract:

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,

Key words: stream ciphers, Trivium, mutiple linear cryptanalysis, linear approximation

马猛,赵亚群. 简化版Trivium算法的线性逼近研究[J]. 通信学报, 2016, 37(6): 185-191.

Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium[J]. Journal on Communications, 2016, 37(6): 185-191.

图/表 3

表1

t1=144时z1的16个偏差为2?23.42线性近似"

第1轮非线性逼近式	指定为零的比特	z₁的线性近似
$z_{1} = R \oplus s_{144} (82) s_{144} (83)$	$E, i v_{34} = 0$	$z_{1} = F \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (82) s_{144} (83) \oplus s_{144} (163)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{61} \oplus i v_{4} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (82) s_{144} (83) \oplus s_{144} (164)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{20} \oplus k_{62} \oplus i v_{5} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (82) s_{144} (83) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{26}$
$z_{1} = R \oplus s_{144} (82) s_{144} (83) \oplus s_{144} (163) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{26} \oplus k_{61} \oplus i v_{4}$
$z_{1} = R \oplus s_{144} (82) s_{144} (83) \oplus s_{144} (164) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{20} \oplus k_{26} \oplus k_{62} \oplus i v_{5}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (82)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{7} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (83)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{8} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (163) \oplus s_{144} (83)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{8} \oplus k_{61} \oplus i v_{4} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (163) \oplus s_{144} (82)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{7} \oplus k_{61} \oplus i v_{4} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (83) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{8} \oplus k_{26}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (82) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{7} \oplus k_{26}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (163) \oplus s_{144} (82) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{7} \oplus k_{26} \oplus k_{61} \oplus i v_{4}$
$z_{1} = R \oplus s_{144} (163) s_{144} (88) \oplus s_{144} (163) \oplus s_{144} (83) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{8} \oplus k_{26} \oplus k_{61} \oplus i v_{4}$
$z_{1} = R \oplus s_{144} (164) s_{144} (88) \oplus s_{144} (164) \oplus s_{144} (83) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{8} \oplus k_{20} \oplus k_{26} \oplus k_{62} \oplus i v_{5}$
$z_{1} = R \oplus s_{144} (164) s_{144} (88) \oplus s_{144} (164) \oplus s_{144} (82) \oplus s_{144} (32)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{7} \oplus k_{20} \oplus k_{26} \oplus k_{62} \oplus i v_{5}$

表1

表2

t1=141时z1的6个线性近似"

第1轮非线性逼近式G₁	指定为零的比特	z₁的线性近似
$z_{1} = R \oplus s_{141} (91) s_{141} (92)$	$E, i v_{34} = 0$	$z_{1} = F \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{141} (91) s_{141} (92) \oplus s_{141} (80)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{8} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{141} (91) s_{141} (92) \oplus s_{141} (79)$	$E, i v_{34} = 0$	$z_{1} = F \oplus k_{7} \oplus i v_{23} \oplus i v_{38} \oplus i v_{68}$
$z_{1} = R \oplus s_{141} (91) s_{141} (92) \oplus s_{141} (29)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{26}$
$z_{1} = R \oplus s_{141} (91) s_{141} (92) \oplus s_{141} (80) \oplus s_{141} (29)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{8} \oplus k_{26}$
$z_{1} = R \oplus s_{141} (91) s_{141} (92) \oplus s_{141} (79) \oplus s_{141} (29)$	$E, i v_{67} = 0$	$z_{1} = F \oplus k_{20} \oplus k_{26} \oplus k_{62} \oplus i v_{5}$

表2

表3

结果对比"

$(\| O_{K} \|, \| O_{I V} \|)$	方法	偏差	线性近似个数	数据量	线性攻击成功率
(10,8)	文献[12]	2^－29	1	2⁵⁸	97.77%
	本文	2^－25.42	16	2^46.84	97.77%
	文献[9]	2^－31	1	2⁶²	97.77%
	文献[10]	2^－31	2	2⁶¹	97.77%
(10,10)	文献[11]	2^－25	1	2⁵⁰	97.77%
	文献[12]	2^－30	8	2⁵⁷	97.77%
	本文	2^－23.42	16	2^42.84	97.77%
	文献[10]	2^－31	2	2⁶¹	97.77%
(10,13)	文献[11]	2^－22	1	2⁴⁴	97.77%
	本文	2^－20.42	16	2^36.84	97.77%

表3

参考文献 15

[1]	CANNIàRE C , PRENEEL B . Trivium specifications[EB/OL]. , 2007.
[2]	MAXIMOV A , BIRYUKOV A . Two trivial attacks on Trivium[C]// 2007: 36-55.
[3]	DINURA , SHAMIR A , . Cubic attacks on tweakable black box polynomials[C]// Advances in Cryptology-EUROCRYPT 2009. 2009: 278-299.
[4]	STANKOVSKI P , . Greedy distinguishers and nonrandomness detectors[C]// INDOCRYPT 2010. 2010: 210-226.
[5]	HOJSíK M , RUDOLF B . Differential fault analysis of Trivium[C]// FSE 2008. 2008: 158-172.
[6]	HU Y P , GAO J T , LIU Q ,et al. Fault analysis of Trivium[C]// Designs,Codes and Cryptography. 2011: 289-311.
[7]	AVIJIT D , GOUTAM P . Deterministic hard fault attack on trivium[C]// Advances in Information and Computer Security. 2014: 134-145.
[8]	PRAKASH D , AVISHEK A . Improved multi-bit differential fault analysis of trivium[C]// Progress in Cryptology. 2014: 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, 2007: 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]	孙文龙, 关杰, 刘建东 . 针对简化版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]	李世取, 曾本胜, 廉玉忠 ,等. 密码学中的逻辑函数[M]. 北京: 中软电子出版社, 2003: 254-255. LI S Q , ZENG B S , LIAN Y Z ,et al. Logical functions in cryptography[M]. Beijing: Software and Electronic PressPress, 2003: 254-255.
[14]	DOUGLAS R , STINSON STINSON . 密码学原理与实践[M]. 北京: 电子工业出版社, 2010: 123-124. DOUGLAS R , STINSON . Cryptography theory and practice[M]. Beijing: Publishing House of Electronics IndustryPress, 2010: 123-124.
[15]	丁存生, 肖国镇 . 流密码及其应用[M]. 北京: 国防科学出版社, 1994: 28-29. DING C S , XIAO G Z . Stream cipher and its applications[M]. Beijing: National Defense Industry PressPress, 1994: 28-29.