Cryptography Reference
In-Depth Information
Chapter 5
Analysis of Keystream Generation
The previous two chapters focused on the RC4 KSA. In this chapter, we
present a detailed analysis of the keystream generation component PRGA of
RC4.
Certain impossible states of RC4 PRGA were discovered by Finney [50].
We begin the chapter with a discussion on these states in Section 5.1. Next,
in Section 5.2, we discuss Glimpse Theorem [78,108], a very important result
about the leakage of state information in keystream.
Most of the cryptanalytic materials on RC4 PRGA point out the weak-
nesses for the initial keystream bytes [52, 86, 103, 107, 108, 122, 131, 139, 146,
180,184,185] and many of these works can be used to attack RC4 in IV mode
(e.g., WEP applications). There are comparatively fewer results when RC4 is
considered after throwing away any amount of initial keystream bytes. One
such work is Mantin's digraph distinguisher [109] described in the next chap-
ter (in Section 6.3.1). Another important work that concentrates on studying
the behavior of RC4 at any stage of keystream generation and makes no use of
the RC4 initialization process is [9], which provides a theoretical investigation
into the structure and evolution of RC4 PRGA. Section 5.4 is based on the
analysis of [9]. In this section, a complete characterization of the RC4 PRGA
for a single step is presented. The detailed analysis of the single step itself is
quite involved and tedious, and so the complete analysis of two consecutive
steps becomes harder. Thus, a particular case for two steps is studied, from
which weaknesses of RC4 can be identified.
The next two sections deal with the biases of the keystream output bytes
toward the secret key. Section 5.5 analyzes the first keystream byte of RC4.
As part of this analysis, we present the proof of Roos' experimental observa-
tions [146] that appeared for the first time in [131]. Biases of several forms
toward the secret key in many keystream bytes, that have been reported
in [86,103], are presented in Section 5.6. In addition to the biases in the ini-
tial keystream bytes, biases at much later stages such as in rounds 256, 257
and beyond are discussed in this section.
The last section gives an overview of exhaustive enumeration of all linear
biases in RC4, that has been recently attempted in [158].
