New Analysis Based on Correlations of RC4 PRGA with Nonzero-Bit Differences
Summary :
RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simplicity and substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation S. Many attacks have been reported so far. No study, however, has focused on correlations in the Pseudo-Random Generation (PRGA) between two permutations S and S' with some differences, nevertheless such correlations are related to an inherent weakness of shuffle-exchange-type PRGA. In this paper, we investigate the correlations between S and S' with some differences in the initial round. We show that correlations between S and S' remain before "i" is in the position where the nonzero-bit difference exists in the initial round, and that the correlations remain with non negligible probability even after "i" passed by the position. This means that the same correlations between S and S' will be observed after the 255-th round. This reveals an inherent weakness of shuffle-exchange-type PRGA.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.6 pp.1066-1077
- Publication Date
- 2010/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.1066
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Cryptography and Information Security
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsuko MIYAJI, Masahiro SUKEGAWA, "New Analysis Based on Correlations of RC4 PRGA with Nonzero-Bit Differences" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 6, pp. 1066-1077, June 2010, doi: 10.1587/transfun.E93.A.1066.
Abstract: RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simplicity and substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation S. Many attacks have been reported so far. No study, however, has focused on correlations in the Pseudo-Random Generation (PRGA) between two permutations S and S' with some differences, nevertheless such correlations are related to an inherent weakness of shuffle-exchange-type PRGA. In this paper, we investigate the correlations between S and S' with some differences in the initial round. We show that correlations between S and S' remain before "i" is in the position where the nonzero-bit difference exists in the initial round, and that the correlations remain with non negligible probability even after "i" passed by the position. This means that the same correlations between S and S' will be observed after the 255-th round. This reveals an inherent weakness of shuffle-exchange-type PRGA.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1066/_p
Copy
@ARTICLE{e93-a_6_1066,
author={Atsuko MIYAJI, Masahiro SUKEGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={New Analysis Based on Correlations of RC4 PRGA with Nonzero-Bit Differences},
year={2010},
volume={E93-A},
number={6},
pages={1066-1077},
abstract={RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simplicity and substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation S. Many attacks have been reported so far. No study, however, has focused on correlations in the Pseudo-Random Generation (PRGA) between two permutations S and S' with some differences, nevertheless such correlations are related to an inherent weakness of shuffle-exchange-type PRGA. In this paper, we investigate the correlations between S and S' with some differences in the initial round. We show that correlations between S and S' remain before "i" is in the position where the nonzero-bit difference exists in the initial round, and that the correlations remain with non negligible probability even after "i" passed by the position. This means that the same correlations between S and S' will be observed after the 255-th round. This reveals an inherent weakness of shuffle-exchange-type PRGA.},
keywords={},
doi={10.1587/transfun.E93.A.1066},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - New Analysis Based on Correlations of RC4 PRGA with Nonzero-Bit Differences
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1066
EP - 1077
AU - Atsuko MIYAJI
AU - Masahiro SUKEGAWA
PY - 2010
DO - 10.1587/transfun.E93.A.1066
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2010
AB - RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simplicity and substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation S. Many attacks have been reported so far. No study, however, has focused on correlations in the Pseudo-Random Generation (PRGA) between two permutations S and S' with some differences, nevertheless such correlations are related to an inherent weakness of shuffle-exchange-type PRGA. In this paper, we investigate the correlations between S and S' with some differences in the initial round. We show that correlations between S and S' remain before "i" is in the position where the nonzero-bit difference exists in the initial round, and that the correlations remain with non negligible probability even after "i" passed by the position. This means that the same correlations between S and S' will be observed after the 255-th round. This reveals an inherent weakness of shuffle-exchange-type PRGA.
ER -
English
