The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -