Utilizing Probabilistic Linear Equations in Cube Attacks

ISCAS OpenIR

	Utilizing Probabilistic Linear Equations in Cube Attacks
	Yao, Y; Zhang, B; Wu, WL
	2016
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	31 期号:2 页码:317-325
摘要	Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test (SPRT) for linearity test in the preprocessing phase, and use maximum likelihood decoding (MLD) for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.; Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test (SPRT) for linearity test in the preprocessing phase, and use maximum likelihood decoding (MLD) for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.
收录类别	SCI
关键词	Cube Attack Sequential Probability Ratio Test Maximum Likelihood Decoding Trivium
部门归属	Chinese Acad Sci, Inst Software, Trusted Comp & Informat Assurance Lab, Beijing 100190, Peoples R China. Univ Chinese Acad Sci, Beijing 100190, Peoples R China.
语种	英语
WOS记录号	WOS:000372154100007
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/17344
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Yao, Y,Zhang, B,Wu, WL. Utilizing Probabilistic Linear Equations in Cube Attacks[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2016,31(2):317-325.
APA	Yao, Y,Zhang, B,&Wu, WL.(2016).Utilizing Probabilistic Linear Equations in Cube Attacks.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,31(2),317-325.
MLA	Yao, Y,et al."Utilizing Probabilistic Linear Equations in Cube Attacks".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 31.2(2016):317-325.