基于E0算法的猜测决定攻击

doi:10.3969/j.issn.1000-436x.2012.11.024

Abstract

Abstract:

A guess and determine attack on E₀was presented,the stream cipher that was used in the short-range wireless technology Bluetooth.In the attack,an ingenious assumption by linear approximation to diminish the number of values that have to be guessed was made.Futher more,a test equation to reduce the number of the guessed candidates was used.The guess and determine attack on E₀with time complexity of O(2⁷⁶)required about 988 keystream bit.Compared with long keystream attacks,short keystream attacks were more threatening to E₀cipher which require less than 2 745 bit.This attack which belongs to short keystream attack was the fastest state recovery attack on E₀so far compared with any other existed short keystream attacks.

Key words: cryptanalysis, E₀algorithm, guess and determine attack, test equation

Ying-jie ZHAN,Lin DING,Jie GUAN. Guess and determine attack on E₀algorithm[J]. Journal on Communications, 2012, 33(11): 185-190.

Figures/Tables 3

步骤	时刻t+i	假设	猜测比特	决定比特	候选
1	i=0,1,…,24	$s_{t + 1 + i}^{1} \oplus c_{t + i}^{1} = 0$	$c_{t - 1}^{0}, c_{t}^{0}, \dots, c_{t + 25}^{0}, c_{t - 1}^{1}, c_{t}^{1}, x_{t}^{1} \oplus x_{t}^{2}, x_{t + 1}^{1} \oplus x_{t + 1}^{2}, \dots, x_{t + 24}^{1} \oplus x_{t + 24}^{2}$	$x_{t + i}^{1}, x_{t + i}^{2}, x_{t + i}^{3}, x_{t + i}^{4}$	2^66.20
2	i=25,…,30	$s_{t + 1 + i}^{1} \oplus c_{t + i}^{1} = 0$	$c_{t + 26}^{0}, \dots, c_{t + 31}^{0}$	$x_{t + i}^{2}, x_{t + i}^{3}, x_{t + i}^{4}$	2^70.78
3	i=31,32	$s_{t + 1 + i}^{1} \oplus c_{t + i}^{1} = 0$	…	$x_{t + i}^{3}, x_{t + i}^{4}$	2^69.10
4	i=33,…,38		…	$x_{t + i}^{4}$	2^65.86

References 13

[1]	Bluetooth TM . Bluetooth specification,version 1.2[EB/OL]. , 2003.
[2]	ARMKNECHT F , KRAUSE M . Algebraic attacks on combiners with memory[A]. Cryptology CRYPTO 2003,Lecture Notes in Computer Science[C]. California,America, 2003. 162-175.
[3]	COURTOIS N T . Fast algebraic attacks on stream ciphers with linear feedback[A]. Cryptology-CRYPTO 2003,Lecture Notes in Computer Science[C]. California America, 2003. 176-194.
[4]	LU Y , VAUDENAY S . Faster correlation attack on Bluetooth keystream generator E0[A]. Cryptology-CRYPTO 2004,Lecture Notes in Computer Science[C]. California,America, 2004. 407-425.
[5]	LU Y , MEIER W , VAUDENAY S . The conditional correlation attack:a practical attack on Bluetooth encryption[A]. Cryptology CRYPTO'05[C]. California,America, 2005. 97-117.
[6]	BLEICHENBACHER D . Security weaknesses in Bluetooth[A]. Proc RSA Security Conf Cryptographer’s Track[C]. San Francisco,America, 2001. 176-191.
[7]	FLUHRER S , LUCKS S . Analysis of the E0encryption system[A]. Selected Areas in Cryptography,Lecture Notes in Computer Science[C]. Toronto,Canada, 2001. 38-48.
[8]	KRAUSE M . BDD-based cryptanalysis of keystream generators[A]. Advances in Cryptology-EUROCRYPT 2002[C]. Amsterdam:The Netherlands, 2002. 222-237.
[9]	OPHIR L , AVISHAI W . A uniform framework for cryptanalysis of the Bluetooth E0cipher[A]. Proc of 1st International Conference on Security and Privacy for Emerging Areas in Communication Networks (SecureComm)[C]. Athens,Greece, 2005. 365-373.
[10]	SHAKED Y , WOOL A . Cryptanalysis of the Bluetooth E0cipher using OBDD's[EB/OL]. , 2006.
[11]	郭峰, 庄弈琪 . 蓝牙 E0加密算法安全分析[J]. 电子科技大学学报, 2006,35(2): 160-164. GUO F , ZHANG Y Q . Analysis of the E0encryption system in Bluetooth[J]. Journal of UEST of China, 2006,35(2): 160-164.
[12]	PILLAI N R , BEDI S S , KUMAR S , et al. Relation for algebraic attack on E0 combiner[EB/OL]. , 2010.
[13]	ARMKNECHT F , KRAUSE M . Algebraic attacks on combiners with memory[A]. Lecture Notes in Computer Science[C]. California,America, 2003. 162-175.

Metrics

Recommended 0

No Suggested Reading articles found!

攻击方法	所需密钥流比特	计算复杂度	存储复杂度
Bleichenbacher^[6]	132	2¹⁰⁰	—
Fluhrer-Lucks^[7]	132	2⁸⁴	—
Levy-Wool^[8]	128	2⁸⁶	—
Yaniv-Wool^[9]	128	2⁸⁷	2²³
Krause^[10]	128	2⁸¹	2⁷⁷
郭锋，庄奕琪^[11]	1146	2⁸³	—
本文	988	2⁷⁶	—

[1]	Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo [J]. Journal on Communications, 2023, 44(6): 175-182.
[2]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[3]	Zhengbin LIU, Yongqiang LI, Chaoxi ZHU. Fast algorithm to search for the minimum number of active S-boxes of block cipher [J]. Journal on Communications, 2023, 44(1): 118-128.
[4]	Nianping WANG, Qing YIN. Differential security evaluation of Piccolo-like structure [J]. Journal on Communications, 2022, 43(2): 55-64.
[5]	Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis [J]. Journal on Communications, 2022, 43(11): 183-198.
[6]	Nianping WANG, Zhicheng GUO. Security evaluation against differential cryptanalysis for dynamic cryptographic structure [J]. Journal on Communications, 2021, 42(8): 70-79.
[7]	Guoshuang ZHANG,Xiao CHEN,Dongdai LIN,Fengmei LIU. State recovery attack on ACORN v3 in nonce-reuse setting [J]. Journal on Communications, 2020, 41(8): 11-21.
[8]	Jie CUI,Hai-feng ZUO,Hong ZHONG. Biclique cryptanalysis on lightweight block ciphers I-PRESENT-80 and I-PRESENT-128 [J]. Journal on Communications, 2017, 38(11): 13-23.
[9]	Zhi-yan XU,Li-bing WU,Li LI,De-biao HE. New certificateless aggregate signature scheme with universal designated verifier [J]. Journal on Communications, 2017, 38(11): 76-83.
[10]	Jing HUANG,Xin-jie ZHAO,Fan ZHANG,Shi-ze GUO,Ping ZHOU,Hao CHEN,Jian YANG. Improvement and evaluation for algebraic fault attacks on PRESENT [J]. Journal on Communications, 2016, 37(8): 144-156.
[11]	IRong-jia L,INChen-hui J. Meet-in-the-middle attacks on FOX block cipher [J]. Journal on Communications, 2016, 37(8): 185-190.
[12]	Jian-sheng GUO,Jing-yi CUI,Zhi-shu PAN,Yi-peng LIU. Integral attack on HIGHT block cipher [J]. Journal on Communications, 2016, 37(7): 71-78.
[13]	Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium [J]. Journal on Communications, 2016, 37(6): 185-191.
[14]	Qing-cong LIU,Ya-qun ZHAO,Meng MA,Feng-mei LIU. Zero correlation-integral attack of MIBS block cipher [J]. Journal on Communications, 2016, 37(11): 189-195.
[15]	Zhi-shu PAN,Jian-sheng GUO,Jin-ke CAO,Wei LUO. Integral attack on MIBS block cipher [J]. Journal on Communications, 2014, 35(7): 157-163.

Guess and determine attack on E₀algorithm

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 13

Related Articles 15

Metrics

Recommended 0

Guess and determine attack on E0algorithm

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 13

Related Articles 15

Metrics

Recommended 0

Guess and determine attack on E₀algorithm