4
$\begingroup$

OK, so lots of questions get asked about RC4 but I want to make mine specific and hopefully answerable.

RC4 Design as I'm sure anyone reading this knows, uses self permutation in stage 1 of the KSA.

Is this KSA any better? Can we know easily? Is there proof from a security point of view, this is actually worse, can we safely assume it suffers most the flaws RC4 KSA suffers anyway and if we don't use this code:

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

****but instead use:****

    s[0] = 181: s[1] = 172: s[2] = 179: s[3] = 178: s[4] = 177: s[5] = 168: s[6] = 175: s[7] = 174: s[8] = 173: s[9] = 164: s[10] = 171: s[11] = 170: s[12] = 169: s[13] = 160: s[14] = 167: s[15] = 166: s[16] = 197: s[17] = 188: s[18] = 195: s[19] = 194: s[20] = 193: s[21] = 184: s[22] = 191: s[23] = 190: s[24] = 189: s[25] = 180: s[26] = 187: s[27] = 186: s[28] = 185: s[29] = 176: s[30] = 183
    s[31] = 182: s[32] = 213: s[33] = 204: s[34] = 211: s[35] = 210: s[36] = 209: s[37] = 200: s[38] = 207: s[39] = 206: s[40] = 205: s[41] = 196: s[42] = 203: s[43] = 202: s[44] = 201: s[45] = 192: s[46] = 199: s[47] = 198: s[48] = 101: s[49] = 92: s[50] = 99: s[51] = 98: s[52] = 97: s[53] = 216: s[54] = 223: s[55] = 222: s[56] = 221: s[57] = 212: s[58] = 219: s[59] = 218: s[60] = 217
    s[61] = 208: s[62] = 215: s[63] = 214: s[64] = 117: s[65] = 108: s[66] = 115: s[67] = 114: s[68] = 113: s[69] = 104: s[70] = 111: s[71] = 110: s[72] = 109: s[73] = 100: s[74] = 107: s[75] = 106: s[76] = 105: s[77] = 96: s[78] = 103: s[79] = 102: s[80] = 133: s[81] = 124: s[82] = 131: s[83] = 130: s[84] = 129: s[85] = 120: s[86] = 127: s[87] = 126: s[88] = 125: s[89] = 116: s[90] = 123
    s[91] = 122: s[92] = 121: s[93] = 112: s[94] = 119: s[95] = 118: s[96] = 149: s[97] = 140: s[98] = 147: s[99] = 146: s[100] = 145: s[101] = 136: s[102] = 143: s[103] = 142: s[104] = 141: s[105] = 132: s[106] = 139: s[107] = 138: s[108] = 137: s[109] = 128: s[110] = 135: s[111] = 134: s[112] = 37: s[113] = 28: s[114] = 35: s[115] = 34: s[116] = 33: s[117] = 152: s[118] = 159: s[119] = 158: s[120] = 157
    s[121] = 148: s[122] = 155: s[123] = 154: s[124] = 153: s[125] = 144: s[126] = 151: s[127] = 150: s[128] = 53: s[129] = 44: s[130] = 51: s[131] = 50: s[132] = 49: s[133] = 40: s[134] = 47: s[135] = 46: s[136] = 45: s[137] = 36: s[138] = 43: s[139] = 42: s[140] = 41: s[141] = 32: s[142] = 39: s[143] = 38: s[144] = 69: s[145] = 60: s[146] = 67: s[147] = 66: s[148] = 65: s[149] = 56: s[150] = 63
    s[151] = 62: s[152] = 61: s[153] = 52: s[154] = 59: s[155] = 58: s[156] = 57: s[157] = 48: s[158] = 55: s[159] = 54: s[160] = 85: s[161] = 76: s[162] = 83: s[163] = 82: s[164] = 81: s[165] = 72: s[166] = 79: s[167] = 78: s[168] = 77: s[169] = 68: s[170] = 75: s[171] = 74: s[172] = 73: s[173] = 64: s[174] = 71: s[175] = 70: s[176] = 229: s[177] = 220: s[178] = 227: s[179] = 226: s[180] = 225
    s[181] = 88: s[182] = 95: s[183] = 94: s[184] = 93: s[185] = 84: s[186] = 91: s[187] = 90: s[188] = 89: s[189] = 80: s[190] = 87: s[191] = 86: s[192] = 245: s[193] = 236: s[194] = 243: s[195] = 242: s[196] = 241: s[197] = 232: s[198] = 239: s[199] = 238: s[200] = 237: s[201] = 228: s[202] = 235: s[203] = 234: s[204] = 233: s[205] = 224: s[206] = 231: s[207] = 230: s[208] = 5: s[209] = 252: s[210] = 3
    s[211] = 2: s[212] = 1: s[213] = 248: s[214] = 255: s[215] = 254: s[216] = 253: s[217] = 244: s[218] = 251: s[219] = 250: s[220] = 249: s[221] = 240: s[222] = 247: s[223] = 246: s[224] = 21: s[225] = 12: s[226] = 19: s[227] = 18: s[228] = 17: s[229] = 8: s[230] = 15: s[231] = 14: s[232] = 13: s[233] = 4: s[234] = 11: s[235] = 10: s[236] = 9: s[237] = 0: s[238] = 7: s[239] = 6: s[240] = 165
    s[241] = 156: s[242] = 163: s[243] = 162: s[244] = 161: s[245] = 24: s[246] = 31: s[247] = 30: s[248] = 29: s[249] = 20: s[250] = 27: s[251] = 26: s[252] = 25: s[253] = 16: s[254] = 23: s[255] = 22

j := 0
       for i from 0 to 255
        j := (j + S[i] + key[i mod keylength]) mod 256
        swap values of S[i] and S[j]
    endfor

I can see we probably have probably created new problems and probably fixed some old ones. Does anyone know how effective if at all, this less elegant KSA is? (it's just as fast, in software at least but it loses all it's elegance. Is this AT BEST, "security through confusion" or does it have real advantages?

$\endgroup$
  • $\begingroup$ Likely, there exists some key that would result in the same initial setup of the $s$ array using regular RC4 that you are getting by using your initial setup of the $s$ array. So really, it would seem that given that key, your setup is equivalent to regular RC4 using a concatenated key (the special key I just mentioned and the actual key). So I doubt that your setup helps any. $\endgroup$ – mikeazo Jan 8 '16 at 12:54
  • $\begingroup$ @mikeazo Cheers for the response, like that's exactly what I suspect, I just wondered if anyone could elaborate on proof. I have actually used this permuation (that wasn't reached using the KSA but if I understand you right, you're saying it could be with some obscure multiple of bytes as a key. I guess my sub-question was does anyone know if this set-up makes RC4 any WORSE? (As I say, it's very fast to implement in software some set of numbers like this and the RC4 KSA is something I'm using inside another wider function, it's not being used as a stream cipher) $\endgroup$ – Iam Nick Jan 8 '16 at 16:55
  • $\begingroup$ @mikeazo I just want to add, your answer is actually fantastic: you made what I thought was a semi-difficult problem, trivial as anything. The "...using a concatenated key", bit answers my entire question, when I think about it. Kudos. $\endgroup$ – Iam Nick Jan 9 '16 at 3:14
6
$\begingroup$

Wanted to expand on my comment as an answer.

The KSA in RC4 permutes the bytes [0,1,...,255] using a key, say $k_u$. For any permutation of these bytes, there exists a key that will get you that permutation.

The idea you outline is basically to start by permuting the bytes [0,1,...,255] according to some fixed initial permutation, then permuting the bytes according to the key. Since that initial permutation could be described by some key, call it $k_{ip}$, what you in effect have is the bytes [0,1,...,255] permuted by $k_{ip}\;|\;k_u$ (where $|$ is concatenation).

So what you are really asking is, does prepending some key to the user passed in key make RC4 weaker, stronger, or have no effect. I am not super familiar with the attacks on RC4. It would seem that this initial permutation does not make RC4 any weaker. I doubt it makes it much stronger, if at all.

$\endgroup$
  • $\begingroup$ Technically, since RC4 key length is capped at 256 bytes (and the key is repeated if it's shorter than that), just concatenating $k_{ip}$ and $k_u$ won't work; you'd have to actually run the key setup twice, first with $k_{ip}$ and then with $k_u$. Still, for any initial permutation $p_1$ and any target permutation $p_2$, there is an RC4 key (possibly several, in fact, but at least one is easy to find) that transforms $p_1$ into $p_2$. In that sense, every key in the OP's modified RC4 is provably equivalent to some key in normal RC4. $\endgroup$ – Ilmari Karonen Jan 9 '16 at 8:50
4
$\begingroup$

To build on mikeazo's answer (since it's not really practical to post code in comments), here's a quick Python program that takes any two permutations of $\{0, \dots, 255\}$ and generates a key that transforms one into the other when run through the RC4 key setup:

# source and target permutations
s = range(256)
t = [181, 172, 179, 178, 177, 168, 175, 174, 173, 164, 171, 170, 169,
     160, 167, 166, 197, 188, 195, 194, 193, 184, 191, 190, 189, 180, 187,
     186, 185, 176, 183, 182, 213, 204, 211, 210, 209, 200, 207, 206, 205,
     196, 203, 202, 201, 192, 199, 198, 101, 92, 99, 98, 97, 216, 223, 222,
     221, 212, 219, 218, 217, 208, 215, 214, 117, 108, 115, 114, 113, 104,
     111, 110, 109, 100, 107, 106, 105, 96, 103, 102, 133, 124, 131, 130,
     129, 120, 127, 126, 125, 116, 123, 122, 121, 112, 119, 118, 149, 140,
     147, 146, 145, 136, 143, 142, 141, 132, 139, 138, 137, 128, 135, 134,
     37, 28, 35, 34, 33, 152, 159, 158, 157, 148, 155, 154, 153, 144, 151,
     150, 53, 44, 51, 50, 49, 40, 47, 46, 45, 36, 43, 42, 41, 32, 39, 38,
     69, 60, 67, 66, 65, 56, 63, 62, 61, 52, 59, 58, 57, 48, 55, 54, 85,
     76, 83, 82, 81, 72, 79, 78, 77, 68, 75, 74, 73, 64, 71, 70, 229, 220,
     227, 226, 225, 88, 95, 94, 93, 84, 91, 90, 89, 80, 87, 86, 245, 236,
     243, 242, 241, 232, 239, 238, 237, 228, 235, 234, 233, 224, 231, 230,
     5, 252, 3, 2, 1, 248, 255, 254, 253, 244, 251, 250, 249, 240, 247,
     246, 21, 12, 19, 18, 17, 8, 15, 14, 13, 4, 11, 10, 9, 0, 7, 6, 165,
     156, 163, 162, 161, 24, 31, 30, 29, 20, 27, 26, 25, 16, 23, 22]

# build RC4 key that transforms s into t
k = []
j = 0
for i in range(256):
    k.append( (s.index(t[i]) - j - s[i]) & 255 )
    j = (j + s[i] + k[i]) & 255
    s[i], s[j] = s[j], s[i]

print k

For your specific permutation, shown as t above, this program generates the following key bytes:

k = [181, 246, 5, 252, 251, 242, 1, 248, 247, 238, 253, 244, 243, 234,
     249, 240, 15, 230, 245, 236, 235, 226, 241, 232, 231, 222, 237, 228,
     227, 218, 233, 224, 255, 214, 229, 220, 219, 210, 225, 216, 215, 206,
     221, 212, 211, 202, 217, 208, 111, 198, 213, 204, 203, 66, 209, 200,
     199, 190, 205, 196, 195, 186, 201, 192, 95, 182, 197, 188, 187, 178,
     193, 184, 183, 174, 189, 180, 179, 170, 185, 176, 207, 166, 181, 172,
     171, 162, 177, 168, 167, 158, 173, 164, 206, 154, 169, 160, 210, 195,
     212, 205, 182, 199, 184, 177, 186, 171, 188, 181, 190, 175, 192, 185,
     229, 173, 214, 191, 160, 140, 168, 161, 170, 198, 172, 165, 174, 159,
     176, 169, 250, 157, 119, 173, 182, 233, 179, 186, 201, 208, 175, 182,
     197, 204, 171, 178, 174, 187, 167, 174, 178, 191, 163, 170, 185, 163,
     188, 166, 93, 151, 192, 162, 212, 112, 96, 92, 233, 111, 232, 241, 10,
     208, 7, 245, 14, 239, 240, 249, 2, 243, 4, 253, 230, 244, 235, 225,
     213, 245, 247, 229, 225, 233, 243, 233, 18, 227, 244, 237, 246, 231,
     1, 248, 234, 235, 253, 244, 238, 223, 249, 240, 239, 126, 68, 93, 91,
     31, 241, 232, 90, 91, 237, 228, 251, 239, 233, 224, 223, 222, 109, 92,
     222, 234, 231, 243, 254, 235, 230, 247, 242, 239, 239, 251, 241, 227,
     91, 95, 245, 236, 223, 227, 246, 230, 227, 231, 232, 241, 234, 235]

Note that RC4 has equivalent keys, as easily shown by a pigeonhole argument: the key space, even after unrolling keys to the full length, has $256^{256}$ elements, while the internal state space (ignoring $i$ and $j$, which are always initialized to $0$) has only $256! \approx 256^{210.5}$ possible initial states.

Thus, the key returned by the code above is typically not the only solution. It is, however, the unique full-length RC4 key mapping $s$ to $t$ while also satisfying the additional constraint that $j \ge i$ after every iteration of the key setup loop.

In particular, this program demonstrates that:

  • every possible permutation of the RC4 internal state array is obtainable using the standard RC4 key setup algorithm, and
  • this holds regardless of the initial permutation; changing this permutation thus effectively only amounts to a remapping of the key space.

(Note that this does not contradict the well known existence of unreachable Finney states in RC4; the reason those states are unreachable is because the $i$ and $j$ indices are both reset to zero after the key setup, and thus the initial state can never satisfy the Finney invariant $j = i+1 \bmod 256, S[j] = 1$.)

$\endgroup$
  • 1
    $\begingroup$ @IamNick: All the 256! permutations can, indeed, be reached; to show this, first note that a Fisher-Yates shuffle can produce any permutation, and then that any execution of the Fisher-Yates shuffle on {0, ..., 255} can be simulated by RC4 key setup with a suitably chosen key. In fact, this directly yields an algorithm for reconstructing the key based on the final permutation, which is exactly what I've presented above. [...] $\endgroup$ – Ilmari Karonen Jan 9 '16 at 15:07
  • $\begingroup$ ... However, the RC4 internal state also includes the $i$ and $j$ indices, which are initialized to fixed values; thus, the full RC4 state space has $256^2 \cdot 256!$ states, of which only $256!$ (those with $i=j=0$) are possible on the first round (and some, like the Finney states, are provably unreachable on any round). $\endgroup$ – Ilmari Karonen Jan 9 '16 at 15:07
  • $\begingroup$ That's some very informative extra info, thank you. I had always realised the initial possible states should be 256! (or 8.5781777510 e+507) at most. My problem was, I thought, I read somewhere that, not all 256! permutations could exist, not even from a 2048 bit key. That said since I'm here to ask and learn or I wouldn't have asked, I'll happily take the collective wisdom of both of you. The question was always specifically about the KSA, so I consider it well and truly answered. Many Thanks. $\endgroup$ – Iam Nick Jan 9 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.