Analysis of Keystream Generation - RC4: Stream Cipher and Its Variants - page 110

Permutation entry S G [y], where y varies from 0 to 255 in row major order

205 1 142 124 195 47 132 187 113 200 109 106 54 65 75 241

190 183 159 157 244 34 115 31 140 138 76 216 251 20 93 180

52 66 119 71 154 72 103 230 55 135 186 172 51 168 82 69

114 253 139 169 161 26 178 44 39 57 121 247 27 77 38 131

133 218 111 42 207 136 53 137 229 217 228 9 40 84 194 48

3 60 107 182 101 203 96 238 243 234 214 45 86 211 173 130

50 78 226 64 146 163 156 14 170 202 174 41 0 36 134 73

246 112 184 49 11 17 160 175 141 13 68 248 151 15 120 108

2 117 25 61 224 250 83 185 166 89 21 32 143 62 59 16

233 221 118 88 199 122 100 7 193 123 179 43 215 254 240 176

94 104 129 209 6 144 58 110 196 125 92 191 164 90 220 149

210 208 192 24 8 225 46 171 213 19 74 242 4 197 237 150

162 127 177 70 167 10 249 67 219 80 212 147 188 18 153 35

152 223 198 181 126 28 95 79 22 99 189 97 206 148 245 102

81 239 231 63 85 91 98 255 158 227 252 56 155 30 222 12

145 5 128 29 235 37 201 236 204 23 87 33 165 232 105 116

TABLE 5.1: Permutation in a Finney state.

shows the keystream, where two consecutive values denote keystream bytes
separated by 255 rounds of the PRGA.

Keystream byte z r corresponding to r = 255n, for n = 1, 2, . . . , 256 in row major order

35 152 223 198 181 126 28 95 79 22 99 189 97 206 148 245

102 81 239 231 63 85 91 98 255 158 227 252 56 155 30 222

12 145 5 128 29 235 37 201 236 204 23 87 33 165 232 105

116 205 1 142 124 195 47 132 187 113 200 109 106 54 65 75

241 190 183 159 157 244 34 115 31 140 138 76 216 251 20 93

180 52 66 119 71 154 72 103 230 55 135 186 172 51 168 82

69 114 253 139 169 161 26 178 44 39 57 121 247 27 77 38

131 133 218 111 42 207 136 53 137 229 217 228 9 40 84 194

48 3 60 107 182 101 203 96 238 243 234 214 45 86 211 173

130 50 78 226 64 146 163 156 14 170 202 174 41 0 36 134

73 246 112 184 49 11 17 160 175 141 13 68 248 151 15 120

108 2 117 25 61 224 250 83 185 166 89 21 32 143 62 59

16 233 221 118 88 199 122 100 7 193 123 179 43 215 254 240

176 94 104 129 209 6 144 58 110 196 125 92 191 164 90 220

149 210 208 192 24 8 225 46 171 213 19 74 242 4 197 237

150 162 127 177 70 167 10 249 67 219 80 212 147 188 18 153

TABLE 5.2: Decimated (at every N − 1 rounds) keystream bytes corre-
sponding to the Finney State in Table 5.1.

Observe that the output bytes shown in Table 5.2 are a shift of the per-
mutation shown in 5.1. After 256×255 rounds the same state is repeated.

5.2 Glimpse Theorem
One of the important results on the weakness of RC4 PRGA is the Glimpse
Theorem, also known as Jenkins' Correlation [78, 108]. It gives a glimpse of
the hidden state in the keystream as follows.

Theorem 5.2.1. [Glimpse Theorem] After the r-th round of the PRGA, r ≥
1,

−z r ) ≈ 2 P(S r [j r ] = i r −z r ) = P(S r [i r ] = j r

N .