Walking Through the KSA
As previously mentioned, the IV is sent as plaintext. This can be easily sniffed out of the air and used to re-create the first three iterations of the KSA. To illustrate, we will do just that. Follow closely and pay attention to the math...this will get a bit technical!
Before getting into the details, we need to define a few values.
The captured weak IV is 3, 255, 7. This value was chosen because it was tested and is known to be a real weak IV.
The pre-shared password is 22222. Although a hacker would not know this before cracking WEP, we need to define it so you can see the cracking process in action.
N is 256.
If a value exists that is greater than N (256), a modulus operation must be performed on it. This basically divides the number by 256, which results in a leftover number called the modulus. This is the value that is passed on through the calculation.
The initialization process of the state array has already occurred and seeded the state array with the 256 values.
First, we need to clarify our key array as a hacker would see it after capturing the IV.
Next, we need to define and track the state array values, i value, and j value. This will be done before each loop is processed, so you can see how the values change. We will not show all 256 state array values because they are useless to the cracking WEP process. Only the first four state array values and any value that has changed will be shown.
KSA Loop 1
j=j + S[i] + K[i mod l] = 0 + S + K = 0 + 0 + 3 = 3 ‡ j = 3
In this equation, you can see that the j and i value were 0, which is used by the S array (S = 0) and the K array (K = 3). This resulted in the values of 0, 0, and 3 being added together to assign the value of 3 to j. This value is then passed on to the swap function below.
i=0, j=3 Swap (S[i], S[j]) ‡ Swap (S , S) ‡ S = 0 , S = 3 ‡ S = 3 , S = 0
In this process, you can see that values held in S and S are swapped. This is an important process to watch, but remember there is a 5% chance that the values held in S ‡ S will not change after the first 4 KSA/PRGA loops.
KSA Loop 2
j=j + S[i] + K[i mod l] = 3 + S + K[1 mod 8] = 3 + 1 + 255 = 259 mod 256 = 3 ‡ j = 3 i=1, j=3 Swap(S[i], S[j]) ‡ Swap (S , S) ‡ S=1 , S=0 ‡ S=0 , S=1
Note that in this loop the value of i increases by one and that a modulus operation was performed to determine the value of j. It is only coincidental that j = 3 again.
KSA Loop 3
j=j + S[i] + K[i mod l] = 3 + S + K = 3 + 2 + 7 = 12 ‡ j = 12 i=2, j=12 Swap(S[i], S[j]) ‡ Swap (S , S) ‡ S=2 , S=12 ‡ S=12 , S=2
Note that up to this point, only KNOWN values are used. Any hacker can reproduce this process up to this point. However, in the next step, the secret key is unknown, so a hacker has to stop.
KSA Loop 4
j=j + S[i] + K[i mod l] = 12 + S + K = 12 + 1 + ? = ? i=3, j=? Swap(S[i], S[j]) ‡ Swap (S , S[?]) ‡ S=1 , S[?]=? ‡ S=?? , S[??]=1
So, now a hacker is up against a wall. However, what if there were a way to determine the j value at this point? Fortunately, for a hacker, there is a way. A simple XOR calculation, and he can determine this value from the first iteration of the PRGA process.
Knowing this, let's reflect on the XOR process that creates the encrypted data. The final step of the RC4 process is to XOR a PRGA byte with a byte of the plaintext data. Because XOR works in both directions, we also know that we can deduce the first byte of the PRGA if we XOR the first byte of the encrypted data with the first byte of plaintext. Fortunately, for a hacker this is easy, thanks to the SNAP header (170 in decimal) and the use of a sniffer to capture the encrypted byte. In our example, we will provide the captured encrypted byte value (165 in decimal), which changes from packet to packet. The following equation illustrates the XOR process:
z = 0xAA(SNAP) XOR Ciphertext byte1 = 170 (Dec) XOR 165 (Dec) = 15 Ë z = 15
As a result of this XOR calculation, a hacker can deduce that the PRGA value is 15 (decimal). Now, he can reverse-engineer the PRGA process, and use this to determine the missing j value. First, let's remind ourselves of the known loop values as they would occur entering Loop 4 of the KSA. Remember, these values can be easily reproduced by the use of the IV values.
KSA Loop 4
1. Initialization: 2. i=0 3. j=0 4. Generation: 5. i = i + 1 = 0 + 1 = 1 6. j = j + S[i] = 0 + S = 0 + 0 = 0 7. Swap (S[i], S[j]) ‡ Swap (S , S) ‡ S=0 , S=3 ‡ S=3 , S=0 8. z = S[S[i] + S[j]] = S[S + S] = S[3 + 0] = S = ? 9. ?=15 Ë S =15 at KSA4
From the previous discussion, you know that i will always equal 1 for the first iteration of the PRGA (line 5). This then means that j will always equal S (line 6). As we can see from the KSA loop 4 input values, S = 0. This then results in j being assigned the value of 0 (line 6). The values held in S[i] and S[j] are then swapped, which means that S is swapped with S resulting in S = 3 and S = 0 (line 7). These values are then added together, and used to pull a value from the state array. In this case, the combined S[i] and S[j] values = 3 (line 8). However, the S value referenced to here is from the completion of KSA loop 4, which is unknown to us. Fortunately, due to the XOR process, we know that the resulting value is 15, which means that S will equal 15 at the output of KSA loop 4. Knowing this, a hacker only needs to reverse the KSA loop 4 process to deduce the secret key value.
Let's now walk though this as a hacker would.
KSA Loop 4
S=15 , S=St-1 ‡ S=15 , S=1
First, we know that the final step in the KSA loop is to swap values. Knowing the values of the state array after loop 4 completes and before it starts is important. Thanks to the XOR weakness, we know S will equal 15, and we can make an educated guess that S will hold the value held by S before loop 4, which is 1 in this case. As a result, a hacker can deduce that S=15 and S=1 after the swap.
Swap (S , S) ‡ S=1 , S=15
Next, a hacker swaps the values held in these positions, which leaves S equaling 1.
j=j + S[i] + K[i mod 256] = 12 + S + K = 12 + 1 + K = 15
A hacker then plugs the values into the equation that would produce the j value. This fills in all the fields except the value of the secret key array.
‡ K = 15 12 1 = 2
After a simple reverse calculation, the value 2 is produced, which is the first byte of out secret key!