对不同种子密钥长度的RC4算法的明文恢复攻击
|
摘要
针对不同种子密钥长度的RC4算法的明文恢复问题,提出了对经过不同种子密钥长度(8字节、16字节、22字节)的RC4算法加密的明文的明文恢复攻击。首先利用统计算法在2~(32)个不同种子密钥的条件下统计了RC4算法每个密钥流输出字节的t值分布,发现了RC4算法密钥流输出序列存在偏差;然后,利用单字节偏差规律和双字节偏差规律给出了对经RC4算法加密的明文的前256字节的攻击算法。实验结果表明,在密文量为2~(31)的条件下,除了第4字节外,攻击算法能够以100%的成功率恢复明文的前196字节。对于种子密钥长度为8字节的RC4算法,前256字节的恢复成功率都超过了91%;相应的,种子密钥长度为16字节的RC4算法,前256字节的恢复成功率都超过87%;种子密钥长度为22字节的RC4算法,前256字节的恢复成功率都超过了81%。所提攻击算法拓展了原有攻击密钥长度为16字节的RC4算法的范围,且在实际应用中能够更好地恢复经RC4算法加密的明文。
Aiming at the plaintext recovery on plaintexts encrypted by RC4( Rivest Cipher 4) algorithm with different lengths of seed key, a plaintext recovery attack on plaintexts encrypted by RC4 algorithm with different lengths of seed key( 8 bytes, 16 bytes, 22 bytes) was proposed. Firstly, by using the statistical algorithm, the t-value distribution of each output byte of key stream of RC4 was calculated under the condition of 2~(32) different seed keys, and biases were found. Then the attack on the first 256 bytes of the plaintext encrypted by the RC4 was given by using single-byte biases and double-bytes biases. The experimental results show that with 2~(31) ciphertexts, the first 196 bytes of the plaintext can be recovered with the success probability of 100% except the 4th Byte. Besides, the first 256 bytes can be recovered with the success probability over 91%,87% and 81% for 8-byte, 16-byte and 22-byte seed key, respectively. The proposed attack algorithm extends the scope of RC4 algorithm with seed key length of 16 bytes, and it can recover the plaintexts encrypted by RC4 algorithm in practice.
Aiming at the plaintext recovery on plaintexts encrypted by RC4( Rivest Cipher 4) algorithm with different lengths of seed key, a plaintext recovery attack on plaintexts encrypted by RC4 algorithm with different lengths of seed key( 8 bytes, 16 bytes, 22 bytes) was proposed. Firstly, by using the statistical algorithm, the t-value distribution of each output byte of key stream of RC4 was calculated under the condition of 2~(32) different seed keys, and biases were found. Then the attack on the first 256 bytes of the plaintext encrypted by the RC4 was given by using single-byte biases and double-bytes biases. The experimental results show that with 2~(31) ciphertexts, the first 196 bytes of the plaintext can be recovered with the success probability of 100% except the 4th Byte. Besides, the first 256 bytes can be recovered with the success probability over 91%,87% and 81% for 8-byte, 16-byte and 22-byte seed key, respectively. The proposed attack algorithm extends the scope of RC4 algorithm with seed key length of 16 bytes, and it can recover the plaintexts encrypted by RC4 algorithm in practice.
引文
[1]胡亮,迟令,袁巍,等.RC4算法的密码分析与改进[J].吉林大学学报(理学版),2012,50(3):511-516.(HU L,CHI L,YUANW,et al.Cryptanalysis and improvements of RC4 algorithm[J].Journal of Jilin University(Science Edition),2012,50(3):511-516.)
[2]侯整风,孟毛广,朱晓玲,等.RC4流密码算法的分析与改进[J].计算机工程与应用,2015,51(24):97-101.(HOU Z F,MENGM G,ZHU X L,et al.Analysis and improvement of RC4 stream cipher algorithm[J].Computer Engineering and Applications,2015,51(24):97-101.)
[3]TSCHOFENIG H,SHEFFERY,NIR Y,et al.A flexible authentication framework for the Transport Layer Security(TLS)protocol using the Extensible Authentication Protocol(EAP)[J].Journal for the Study of the Pseudepigrapha,2011,7(1):243-243.
[4]KRISTOL D,MONTULLI L.RFC 6265,HTTP state management mechanism[S].Geneva:IETF,1997:82-89.
[5]BIHAM E,CARMELI Y.Efficient reconstruction of RC4 keys from internal states[C]//FSE 2008:Proceedings of the 2008 International Workshop on Fast Software Encryption,LNCS 5086.Berlin:Springer,2008:270-288.
[6]ALFARDAN N J,PATERSON K J.Lucky thirteen:breaking the TLS and DTLS record protocols[C]//SP 2013:Proceedings of the2013 IEEE Symposium on Security and Privacy.Piscataway,NJ:IEEE,2013:526-540.
[7]PATERSON K G,YAU A.Padding oracle attacks on the ISO CBCmode encryption standard[C]//CT-RSA 2004:Proceedings of the2004 Cryptographers'Track at the RSA Conference,LNCS 2964.Berlin:Springer,2004:305-323.
[8]ALFARDAN N J,BERNSTEIN D J,PATERSON K G,et al.On the security of RC4 in TLS[C]//Proceedings of the 22nd USENIXConference on Security.Berkeley,CA:USENIX Association,2013:305-320.
[9]VANHOEF M,PIESSENS F.All your biases belong to us:breaking RC4 in WPA-TKIP and TLS[C]//Proceedings of the 24th USENIXConference on Security Symposium.Berkeley,CA:USENIX Association,2015:97-112.
[10]OHIGASHI T,ISOBE T,WATANABE Y et al.How to recover any byte of plaintext on RC4[C]//SAC 2013:Proceedings of the2013 International Conference on Selected Areas in Cryptography,LNCS 8282.Berlin:Springer,2014:155-173.
[11]ISOBE T,OHIGASHI T,WATANABE Y,et al.Full plaintext recovery attack on broadcast RC4[C]//FSE 2013:Proceedings of the 2013 International Workshop on Fast Software Encryption,LNCS 8424.Berlin:Springer,2013:179-202.
[12]常亚勤.对流密码RC4的区分攻击[J].计算机工程,2011,37(3):119-122.(CHANG Y Q.Distinguishing attack on stream cipher RC4[J].Computer Engineering,2011,37(3):119-122.)
[13]师国栋,康绯,顾海文.随机性测试的研究与实现[J].计算机工程,2009,35(20):145-150.(SHI G D,KANG F,GU H W.Research and implementation of randomness tests[J].Computer Engineering,2009,35(20):145-150.)
[14]王信敏,郑世慧.PRGA的初始状态与RC4算法的安全性[J].计算机工程与应用,2009,45(8):107-108.(WANG X M,ZHENG S H.PRGA's initial state and RC4's security[J].Computer Engineering and Applications,2009,45(8):107-108.
[2]侯整风,孟毛广,朱晓玲,等.RC4流密码算法的分析与改进[J].计算机工程与应用,2015,51(24):97-101.(HOU Z F,MENGM G,ZHU X L,et al.Analysis and improvement of RC4 stream cipher algorithm[J].Computer Engineering and Applications,2015,51(24):97-101.)
[3]TSCHOFENIG H,SHEFFERY,NIR Y,et al.A flexible authentication framework for the Transport Layer Security(TLS)protocol using the Extensible Authentication Protocol(EAP)[J].Journal for the Study of the Pseudepigrapha,2011,7(1):243-243.
[4]KRISTOL D,MONTULLI L.RFC 6265,HTTP state management mechanism[S].Geneva:IETF,1997:82-89.
[5]BIHAM E,CARMELI Y.Efficient reconstruction of RC4 keys from internal states[C]//FSE 2008:Proceedings of the 2008 International Workshop on Fast Software Encryption,LNCS 5086.Berlin:Springer,2008:270-288.
[6]ALFARDAN N J,PATERSON K J.Lucky thirteen:breaking the TLS and DTLS record protocols[C]//SP 2013:Proceedings of the2013 IEEE Symposium on Security and Privacy.Piscataway,NJ:IEEE,2013:526-540.
[7]PATERSON K G,YAU A.Padding oracle attacks on the ISO CBCmode encryption standard[C]//CT-RSA 2004:Proceedings of the2004 Cryptographers'Track at the RSA Conference,LNCS 2964.Berlin:Springer,2004:305-323.
[8]ALFARDAN N J,BERNSTEIN D J,PATERSON K G,et al.On the security of RC4 in TLS[C]//Proceedings of the 22nd USENIXConference on Security.Berkeley,CA:USENIX Association,2013:305-320.
[9]VANHOEF M,PIESSENS F.All your biases belong to us:breaking RC4 in WPA-TKIP and TLS[C]//Proceedings of the 24th USENIXConference on Security Symposium.Berkeley,CA:USENIX Association,2015:97-112.
[10]OHIGASHI T,ISOBE T,WATANABE Y et al.How to recover any byte of plaintext on RC4[C]//SAC 2013:Proceedings of the2013 International Conference on Selected Areas in Cryptography,LNCS 8282.Berlin:Springer,2014:155-173.
[11]ISOBE T,OHIGASHI T,WATANABE Y,et al.Full plaintext recovery attack on broadcast RC4[C]//FSE 2013:Proceedings of the 2013 International Workshop on Fast Software Encryption,LNCS 8424.Berlin:Springer,2013:179-202.
[12]常亚勤.对流密码RC4的区分攻击[J].计算机工程,2011,37(3):119-122.(CHANG Y Q.Distinguishing attack on stream cipher RC4[J].Computer Engineering,2011,37(3):119-122.)
[13]师国栋,康绯,顾海文.随机性测试的研究与实现[J].计算机工程,2009,35(20):145-150.(SHI G D,KANG F,GU H W.Research and implementation of randomness tests[J].Computer Engineering,2009,35(20):145-150.)
[14]王信敏,郑世慧.PRGA的初始状态与RC4算法的安全性[J].计算机工程与应用,2009,45(8):107-108.(WANG X M,ZHENG S H.PRGA's initial state and RC4's security[J].Computer Engineering and Applications,2009,45(8):107-108.