Generalized Analysis on Key Collisions of Stream Cipher RC4

Jiageng CHEN; Atsuko MIYAJI

doi:10.1587/transfun.E94.A.2194

Generalized Analysis on Key Collisions of Stream Cipher RC4

Jiageng CHEN, Atsuko MIYAJI

Full Text Views

0

Cite this

Summary :

The fact that the stream cipher RC4 can generate colliding key pairs with hamming distance one was first discovered by Matsui in FSE 2010. This kind of weakness demonstrates that two different secret keys have the same effect on the cipher's encryption and the corresponding decryption procedure. In this paper, we further investigate the property of RC4 key collisions and achieved the following results:
1. We show that RC4 can generate colliding key pairs with various hamming distances, which cannot be generated by Matsui's pattern. We also give concrete examples of colliding key pairs with hamming distances greater than one.
2. We formalize RC4 colliding key pairs into two large patterns, namely, Transitional pattern and Self-Absorbing pattern. All the currently known colliding key pairs can be categorized into either two patterns.
3. We analyze both patterns and clarified the relations among the probability of key collision, key length and hamming distances which yield the colliding key pairs.
4. We demonstrate the vulnerability of key collisions by showing collisions of RC4-Hash function proposed in INDOCRYPT 2006. Some concrete experimental results of RC4-Hash collision are also given in this paper.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.11 pp.2194-2206

Publication Date: 2011/11/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.2194

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Cryptography and Information Security

Cite this

Copy

Jiageng CHEN, Atsuko MIYAJI, "Generalized Analysis on Key Collisions of Stream Cipher RC4" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 11, pp. 2194-2206, November 2011, doi: 10.1587/transfun.E94.A.2194.
Abstract: The fact that the stream cipher RC4 can generate colliding key pairs with hamming distance one was first discovered by Matsui in FSE 2010. This kind of weakness demonstrates that two different secret keys have the same effect on the cipher's encryption and the corresponding decryption procedure. In this paper, we further investigate the property of RC4 key collisions and achieved the following results:
1. We show that RC4 can generate colliding key pairs with various hamming distances, which cannot be generated by Matsui's pattern. We also give concrete examples of colliding key pairs with hamming distances greater than one.
2. We formalize RC4 colliding key pairs into two large patterns, namely, Transitional pattern and Self-Absorbing pattern. All the currently known colliding key pairs can be categorized into either two patterns.
3. We analyze both patterns and clarified the relations among the probability of key collision, key length and hamming distances which yield the colliding key pairs.
4. We demonstrate the vulnerability of key collisions by showing collisions of RC4-Hash function proposed in INDOCRYPT 2006. Some concrete experimental results of RC4-Hash collision are also given in this paper.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.2194/_p

Copy

@ARTICLE{e94-a_11_2194,
author={Jiageng CHEN, Atsuko MIYAJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Analysis on Key Collisions of Stream Cipher RC4},
year={2011},
volume={E94-A},
number={11},
pages={2194-2206},
abstract={The fact that the stream cipher RC4 can generate colliding key pairs with hamming distance one was first discovered by Matsui in FSE 2010. This kind of weakness demonstrates that two different secret keys have the same effect on the cipher's encryption and the corresponding decryption procedure. In this paper, we further investigate the property of RC4 key collisions and achieved the following results:
1. We show that RC4 can generate colliding key pairs with various hamming distances, which cannot be generated by Matsui's pattern. We also give concrete examples of colliding key pairs with hamming distances greater than one.
2. We formalize RC4 colliding key pairs into two large patterns, namely, Transitional pattern and Self-Absorbing pattern. All the currently known colliding key pairs can be categorized into either two patterns.
3. We analyze both patterns and clarified the relations among the probability of key collision, key length and hamming distances which yield the colliding key pairs.
4. We demonstrate the vulnerability of key collisions by showing collisions of RC4-Hash function proposed in INDOCRYPT 2006. Some concrete experimental results of RC4-Hash collision are also given in this paper.},
keywords={},
doi={10.1587/transfun.E94.A.2194},
ISSN={1745-1337},
month={November},}

Copy

TY - JOUR
TI - Generalized Analysis on Key Collisions of Stream Cipher RC4
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2194
EP - 2206
AU - Jiageng CHEN
AU - Atsuko MIYAJI
PY - 2011
DO - 10.1587/transfun.E94.A.2194
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2011
AB - The fact that the stream cipher RC4 can generate colliding key pairs with hamming distance one was first discovered by Matsui in FSE 2010. This kind of weakness demonstrates that two different secret keys have the same effect on the cipher's encryption and the corresponding decryption procedure. In this paper, we further investigate the property of RC4 key collisions and achieved the following results:
1. We show that RC4 can generate colliding key pairs with various hamming distances, which cannot be generated by Matsui's pattern. We also give concrete examples of colliding key pairs with hamming distances greater than one.
2. We formalize RC4 colliding key pairs into two large patterns, namely, Transitional pattern and Self-Absorbing pattern. All the currently known colliding key pairs can be categorized into either two patterns.
3. We analyze both patterns and clarified the relations among the probability of key collision, key length and hamming distances which yield the colliding key pairs.
4. We demonstrate the vulnerability of key collisions by showing collisions of RC4-Hash function proposed in INDOCRYPT 2006. Some concrete experimental results of RC4-Hash collision are also given in this paper.
ER -