Additional weak IV classes for the FMS attack
=============================================
by Andrea Bittau (sorbo )
9/12/2003
This paper is heavily influenced (copied) by h1kari's document both in content
and layout
0. Abstract
This document will describe how to detect IV's that rely on two key state
elements not changing, in order to calculate the desired key byte. It also
suggests how to detect IV's which become resolved in the successive key setup
stage of the one we can calculate.
1. Introduction
Current mechanisms of wep cracking heavily rely on the FMS [1] attack.
Extensions to the attack were postulated by h1kari [2], where additional output
bytes of the PRGA are being used to recover key bytes. However, such an attack
is not seen in dwepcrack version 0.5 probably because:
h1kari [2]:
"In tests, this method doesn't prove entirely useful, mainly due to the amount
of processing that is required to determine if certain ivs have this property."
What drove my interest in wep was this:
h1kari [2]:
... "and sometimes e ** -2 =~ 13% of the time in some cases when we only rely
on 2 elements in the S permutation staying the same"
this is also mentioned in SIR [3] section 4.3 "Special resolved cases". They
also write "as Shamir pointer to us..." but I frankly did not see that written
anywhere on Shamir's paper (at least explicitly).
After some analysis, I concluded that this 13% family of IV's is not detectable
with the standard IV filtering equation presented in the FMS paper.
Part 1: Background Knowledge (skip)
===================================
1. WEP
This will be a quick overview of WEP and some definitions. Please refer to the
IEEE 802.11 standard.
WEP is the encryption standard for the 802.11b protocol. If wep is used, a
secret key must be distributed to the users of the network by some mean (key
distribution is not part of the protocol). This is known as the shared key,
which is also used for authentification when clients associate. The IEEE
standard specifies to use 64bit keys, but common implementation allow 128bit.
Only data packets, of which only the actual data payload is encrypted using WEP,
so management frames for example are all in plain text.
A standard 802.11 frame:
[802.11 header] [ data ] [ crc ]
A wep 802.11 frame:
[802.11 header] [IV:4] [DATA] [ICV:4] [ crc ]
If this was a data frame, only data and icv would be ciphered.
The first 3 bytes of the IV are known as the Initialization Vector (IV).
The last byte contains 2 bits of key index and 6 bits of padding (big endian).
The ICV is the crc of the [DATA] portion (unciphered).
The initialization vector is prepended to the shared key resulting in a seed
which is fed into the ciphering algorithm. The key index is the identifier of
the shared key to use with that IV to form the seed.
The ICV is the crc32 algorithm run over the plain text version of data. This is
used to see if decryption was successfull.
Once the seed is setup, the algorithm used is standard RC4 which is a stream
chipher (or more correctly a pseudo random generation algorithm). The output of
RC4 is then bitwise xor'ed with the plain text to produce the cipher text.
Important things to note:
- IV will range from 0x000000 - 0xffffff resulting in 0x1000000 total possible
iv's.
- Key index is only 2 bits, resulting in only 4 possible keys per network.
- 64bit key is referred to the seed, so the actualy shared key will only be
64-38 = 40bit.
Common implementation interesting points:
- IV is usually a little endian counter: 0x000000,0x100000,0x200000...
- Hex keys are "hard to remember" so passphrase->key translation algorithm may
be used
- Windows XP maps passphrase->key using the ASCII value of each byte, also
allows only passphrase lengths of 5 or 13 ONLY.
2. RC4
RC4 consists of two stages:
1) The key setup algorithm (KSA)
2) The pseudo random number generator algorithm (PRGA)
From [2]:
KSA(K)
Initialization:
For i = 0 ... N - 1
S[i] = i
j = 0
Scrambling:
For i = 0 ... N - 1
j = j + S[i] + K[i mod l]
Swap(S[i], S[j])
PRGA(K)
Initialization:
i = 0
j = 0
Generation Loop:
i = i + 1
j = j + S[i]
Swap(S[i], S[j])
Output z = S[S[i] + S[j]]
All operations are carried out modulo N. where N is 256.
Definitions/Conventions:
- byte: The seed byte starting from 0. (note key byte will be byte-3(IV len) ).
- state: the S array.
- stage x: the state when scrambling section of KSA reaches i=x
Important things to note:
- If we know seed untill byte x, we may calculate KSA untill stage x-1
- First output byte of PRGA is s[ (s[1] + s[s[1]]) % N ]
3. FMS attack (class 1)
This is a brief overview of current public attacks. Plese refer to documentation
in the reference section ad the end of this paper.
As noted, first output byte relies on three elements:
X=s[1], Y=s[X] and Z=s[ (X+Y) % N]
where Z is the output.
Definitions:
- resolved: If at stage r X,Y,Z are equal to X,Y,Z of the final stage, then this
particular seed results in a resolved condition at stage r. (FMS)
If X,Y,Z are 3 distinct values, then the probability of resulting in a resolved
state at stage r is e^(-3) approx 5%.
Notice however that r must not be less than &X,&Y,&Z (& denotes 'index of').
This is so because in the KSA, i is incremental, so elements at index > current
stage will swap no matter what.
Also notice that we alwats know the first 3 bytes of the seed (it is the IV) so
we may simulate KSA up to stage 2. We also notice that the key data is only used
in the j pointer. If we somehow can calculate j of the next stage (3) we may be
able to recover byte 3 of the seed (first key byte). Supposing we knew j3 (j
stage 3), all we would have to do is:
key[0] = seed[3] = ( j3-j2-S[3] % N );
The cleverness:
Analysing further we see that at stage 3 S[j3] is swapped into S[3]. Suppose that with this seed, the KSA is resolved at stage 3 and that Z (output) = S[3].
So effectively the output will be S[j3] of stage 3 before the swap. Note that
S[j3] of stage 3 is the same of S[j3] of stage 2 (the stage we can calculate).
By simply searching for S[j3] (the output of PRGA which we know) in S2 (state at
stage 2) we will recover j3 which will allow us to calculate seed[3] (i.e. the
first shared key byte key[0]).
Note: the output of the PRGA may be recovered by a xor of cipher text versus
plain text (the plain text of the first few bytes is usually known:
\xaa\xaa\x03). (would be interesting to put about 16 random bytes before the
actual llc header...).
We can re iterate through the process to attack the 4rth byte of the seed and so
on. Notice that it is an incremental attack, so recovery of early seed bytes is
crutial. I do not quite agree with h1kari here...
From [2]:
...
"ivs that match:
(A + 3, N - 1, X)
This is a particular condition that works almost all of the time and is not
dependent on the preceding keys. "
This attack relies on these points:
- output is S[byte] (I call this partially resolved)
- seed resolves at stage byte
There is a subtle point here... resolves at stage BYTE. We only know stage
byte-1 however. Infact we may only check if it resolves at stage b-1 which is ok
but the case where the actual seed resolves at the next stage may exist (more about this later).
We can check for the first condition, which is effectivly our IV filter. For the
first output byte of the PRGA:
&Z depends on X and Y
&Y depends on X
&X is 1
Note: We only know values of S which are at a position < byte because of the
point made before that i is incremental.
This means that X < byte (so we can calculate Y)
and X+Y % N == byte.
This is infact the suggested IV filter formula of KSA.
Part 2: New? stuff
==================
1. Extension to KSA's IV filter (class 4)
The SIR [3] paper suggests to check for this 13% class. Their approach was to
check for duplicate values among X,Y,Z. Note that there is a unique element per
index in the S array so we are effectively checking if we rely on only 2
elements in the S array. The way I saw the "problem" was:
Is there duplication among the INDEX of X,Y or Z.
Well for the FMS attack to work we know that &Z is byte.
We also know that &X is 1 (for the first output byte).
The first key byte is 3 so we will never get &Z to be 1.
This leaves us with &Y which has to be 1 or byte.
If &Y is 1, then X has to be 1 and so will Y, resulting in Z == 2. No good.
This leaves us with &Y == byte. Which means X == byte.
The FMS IV filter will fail since we do not know bytes at index > byte-1
(because of the usual i is incremental...). This is why I doubt that current
software based on the FMS IV filter is able to detect such classes of iv's.
However the whole attack relies on the output being S[byte] se we can safely
assume we know S[byte] (it will just be the output).
This will simply modify the FMS equation with X <= byte.
Going back to the previous discussion, we now have:
X = byte
Y = Z = output
Our goal is to output S[byte] so we need X+Y = byte. This leaves us with only
one option for Y: 0.
So if we have an output of Z = Y = 0, X = byte, we only rely on two elements not
swapping, resulting in a probability of e^(-2) approx 13%.
However notice in PRGA there is a swap before the actual output. &X and &Y are
swapped. Normally this is not an issue since &Z is distinct from &X and &Y.
However here &Z == &Y. This means that &X and &Z will swap before the output,
resulting in X being the output. This may be used as a pre-ksa filter (such as
h1kari's "fast iv filter") since we know that if a IV outputs byte it may be
interesting. In the key recovery process however we treat everything before the
PRGA swap and assume the output was a 0, so we search for a 0 in state at stage
byte-1.
2. Cases that resolve at stage byte (and not byte-1)
As previously noted, the correct definition of resolved is if at stage byte the
wanted elements do not swap. The problem is that we may only check at stage
byte-1 and there are circumstances in which the seed resolves at the next
stage. There are some methos of detecting them but they rely on j being a
specific value (thus are key dependant). For this reason, they might not
reliable for use in practice.
2.1 5% Family "late resolve" cases
Class 2:
If at stage byte-1 we have:
X=0 S[byte]=byte S[0]=Y=output
If at the next step (i=byte), J=indexofy we will have (because of swap(&Y,byte))
X=0 S[byte]=output S[0]=Y=byte
Which is a possible candidate.
Class 3:
Stage byte-1:
X=output s[byte]=0 s[0]=Y=byte
Next step J=indexofx swap(&X,byte)
X=0 s[byte]=output s[0]=Y=byte
2.2 13% Family "late resolve cases"
Class 5:
Stage byte-1:
X=0 s[byte]=byte
Next step J=indexofx swap(&X,byte)
X=byte s[byte]=Y=0
Note the other case J=indexofy does not "exist" since we will swap(byte,byte)
3. Other classes
Class 7:
Stage byte-1:
X=indexofx-byte s[byte]=byte
Next step J=indexofx swap(&X,byte)
X=byte s[byte]=Y=indexofx-byte
PRGA:
I=indexofx X=byte
J=byte Y=indexofx-byte
X+Y=byte+indexofx-byte=indexofx
swap(X,Y)
Z=S[indexofx]=X=indexofx-byte
(this relies on 2 elements only aswell)
Class 6:
Stage byte-1:
X=byte
Next step J=indexofx-byte swap(j,byte)
X=byte s[byte]=Y=s[indexofx-byte]
s[indexofx-byte] is usually equal to indexofx-byte because it is a value > byte-1 and it probably didn't get scrambled yet.. remember modulo N. Anyway that is the output so we can check. Then just follow the discussion above.
4. Mathematics (greetz Rafterman@freenode#math)
The general formula for the probability of n elements not swapping after stage
x is:
P = [ (N-n)/N ] ^ (N-x) in our case N = 256;
e.g. P = [ (256-3)/256 ] ^ (256-3) = ~.051 P = [ (256-2)/256 ] ^ (256-3) =
~.137
Once we calculate the probability for an individual iv we need to add the
probabilities of all candidates. Suppose we have 5 candidates that say correct
key value is 10 and each candidate has a 5% chance of being right. The general
formula is:
P(k) = 1 - (1-p1)^n1*(1-p2)^n1*(1-p3)^n3....
where p1 is the probability of candidate class 1 and n is count of candidates
of class 1 and so on.
e.g. P(k) = 1 - (1-.051)^60 = ~.957
That is why FMS reccomend 60 weak iv's.
5. Practical implementation
I'm working on it... no info at this point...
check out:
http://sorbo.darkircop.org
6. Conclusion
These additional IV's are crucial when performing the KSA attack where collected
data is minimal. Also, it will reduce the time of the attack as the correct
candidate for the key byte will have a higher probability than the rest.
Why all this? well here is a little story...
Once upon a time,
22 megs flew through the sky
then one second on my laptop went by
and now finally on the internet I can fly.
Basically a guy that lives opposite my road uses wep.
7. References
[1] Fluhrer, S. Mantin, I. and Shamir A. - Weaknesses in the Key Scheduling
Algorithm of RC4.
[2] Hulton, David (h1kari) - Practical Exploitation of RC4 Weaknesses in WEP
Environments
[3] Stubblefield, A. Ioannidis, J. and Rubin, A. - Using the Fluhrer, Mantin,
and Shamir Attack to Break WEP