Next generation of WEP attacks?

Any news wireless related or otherwise

Next generation of WEP attacks?

Postby peekitty » Mon Aug 30, 2004 3:44 pm

I don't want to drag the WEP cracking in XP thread further offtopic, so I'll post this here because I think it might be news to some.

I've been following two roughly parallel threads for several months (here and here) on WEP cracking and I think it's important for casual wireless users to understand the implications. The most crucial thing to note is that we're witnessing the development of a second generation of optimized WEP attacks that actually live up to the media hype that surrounded the release of FMS whitepaper. ** .pdf file!

A little background: After Fluhrer, Mantin, & Shamir released their research, most (if not all) vendors adopted weak key avoidance techniques that reduced the practicality (which was never very high to begin with) of tools exploiting the weaknesses described by the FMS paper. Because of this, it has been common wisdom that the state of WEP insecurity is at an acceptable level for home users and non-critical applications. The tools that were recently released by TopoLB, devine, and KoreK take advantage of statistical optimizations described by h1kari that are not reliant on weak key attacks, taking the ineffectiveness of WEP to a new level. It is now possible to circumvent WEP in a few hours versus the several days it once took to gather weak packets, and based on the progress I've seen over the last few months, these applications will likely improve. When the dust settles and the tools are mature, it will be painfully clear how truly inadequate WEP is.

While it remains true that there are plenty of unsecured networks that present no barriers to attackers, I think it’s important for even casual wireless users to understand that WEP no longer offers any protection. While it’s been stated on this forum many times that WEP should only be considered the first barrier in a layered approach to security, the height of that barrier has fallen. I don't think we'll need to wait for a rise in WEP attacks to understand this, it's been clear since TopoLB first described the function of weplab. If the number of views these threads have had are any indication, people in this forum are taking notice, but I think this information needs to get out to the wireless public.

Thanks to TopoLB, devine, KoreK, and the others who have worked on the exploits. Whatever the motives, the result will be a greater awareness of false security.

Note to 133t h4xx0rz: No, weplab and aircrack don't run on PPC. Do I really have to point out what a stupid question that is?
User avatar
peekitty
 
Posts: 1054
Joined: Wed Sep 04, 2002 6:14 am
Location: S. Florida

Postby KoreK » Mon Aug 30, 2004 4:30 pm

That's the official history, the real story (at least from my point of view) is
a) 1995: Wagner discusses potential vulnerability of RC4 (on sci.crypt).
b) 1999: Braindead WEP is born, implementing Wagner's vulnerability
c) 2001: FMS publish WEP paper (citing notably Wagner 1995, in one version of their paper). The amusing thing is that the published attack (that will be implemented later by airsnort, and a bit extended h1kari) is weaker than Wagner's (at least in the earlier stage of cracking).
d) 2001: Arbaugh publishes WEP inductive attack. Once again the published attack is pretty tame compared to the damage that can be inflicted. Arbaugh's inductive attack extends the wep stream. But going the other way (ie decrypting) is as easy. I doubt this was unknown to Arbaugh. No public exploit available.
e) Unreleased tools implements broader FMS attacks. I implement broader FMS attack. Nevertheless they are more or less a generalization (and reimplementation) of Wagner's.
f) I have to finish chopchop (=inverted Arbaugh). A few months ago, I thought I knew something that (almost) nobody knew. I am realizing I am just rediscovering 3-year old and 10-year old vulnerabilities. The joy.

I would not be surprised if the security of a WEP wireless network (on average and under attack) lasts less than 30 minutes.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby KoreK » Mon Aug 30, 2004 5:28 pm

Minor points I forgot about WEP:
1) WEP-64 passphrase actually downgraded the strength of the key to 24bits (IIRC).
2) Reinjecting (modified) packets is trivial.
3) Apparently weak-IV filtering is only done by Cisco and Linksys, according to this slashdot post. Proper weak IVs would mean something like IV[0]>32, 224>IV[0]+IV[1]+1>32. Is it done correctly? And what use is it anyway, when the user is using a centrino laptop, a netgear card...
4) Proper security is WPA. S-boxes look tough.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby peekitty » Mon Aug 30, 2004 5:36 pm

KoreK wrote:Minor points I forgot about WEP:

It's official, you've forgotten more about WEP than I know about it...
4) Proper security is WPA.

You're preaching to the choir.
User avatar
peekitty
 
Posts: 1054
Joined: Wed Sep 04, 2002 6:14 am
Location: S. Florida

Postby Novilio » Fri Sep 03, 2004 7:15 pm

KoreK wrote:Minor points I forgot about WEP:
3) Apparently weak-IV filtering is only done by Cisco and Linksys, according to this slashdot post.

Only of the brands he checked, and probably only newer ones at that. My old Linksys b card does not filter weak IVs, and our beloved Orinoco Gold has been filtering them since one of the early firmware updates in 2002.

I haven't seen it anywhere, but a list of what gear filters weak IVs would be useful to have. Of course, if this new attack is as good as it's supposed to be, I suppose the whole weak IV thing is academic.

--73--

--Novilio
Novilio
 
Posts: 254
Joined: Mon Jul 08, 2002 2:22 pm
Location: Colorado Springs, CO

Postby KoreK » Fri Sep 03, 2004 8:59 pm

Novilio wrote:Only of the brands he checked, and probably only newer ones at that. My old Linksys b card does not filter weak IVs, and our beloved Orinoco Gold has been filtering them since one of the early firmware updates in 2002.

That's not what he wrote, WPA does not run on old hardware. And if Orinoco is filtering the weak IVs from the FMS paper, they are not filtering much.
And you don't need a key to decrypt a packet, you just use the AP. Not fast, as a matter of fact 10-20 time slower than what I was expecting (40 minute for a 60-byte packet), but it works. Some limitation might come from 802.11, but injecting in monitor mode isn't fast either (apparently).

Post-edit: Misread your post. Sorry. So, that's what he wrote. But the problem remains.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby Chris » Fri Sep 03, 2004 10:10 pm

Novilio wrote:Of course, if this new attack is as good as it's supposed to be, I suppose the whole weak IV thing is academic.

--73--

--Novilio



It is. The work that Devine, Kotek, and Topo [LB] have done on this is fantastic. I still stand by my statement that WEP is good enough for the home user...but there can be ZERO doubt (if there was before) that any corp/gov user can't even consider WEP.
perl -e 'print pack(c5, (41*2), sqrt(7056), (unpack(c,H)-2), oct(115), 10)'
User avatar
Chris
 
Posts: 1141
Joined: Mon Jul 15, 2002 4:00 am

Postby KoreK » Sat Sep 04, 2004 7:39 am

Chris wrote:I still stand by my statement that WEP is good enough for the home user...

What would make WEP unsuitable for the home user?
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby sylvain » Sat Sep 04, 2004 8:55 am

KoreK wrote:That's the official history, the real story (at least from my point of view) is
a) 1995: Wagner discusses potential vulnerability of RC4 (on sci.crypt).
b) 1999: Braindead WEP is born, implementing Wagner's vulnerability
c) 2001: FMS publish WEP paper (citing notably Wagner 1995, in one version of their paper). The amusing thing is that the published attack (that will be implemented later by airsnort, and a bit extended h1kari) is weaker than Wagner's (at least in the earlier stage of cracking).
d) 2001: Arbaugh publishes WEP inductive attack. Once again the published attack is pretty tame compared to the damage that can be inflicted. Arbaugh's inductive attack extends the wep stream. But going the other way (ie decrypting) is as easy. I doubt this was unknown to Arbaugh. No public exploit available.
e) Unreleased tools implements broader FMS attacks. I implement broader FMS attack. Nevertheless they are more or less a generalization (and reimplementation) of Wagner's.
f) I have to finish chopchop (=inverted Arbaugh). A few months ago, I thought I knew something that (almost) nobody knew. I am realizing I am just rediscovering 3-year old and 10-year old vulnerabilities. The joy.

I would not be surprised if the security of a WEP wireless network (on average and under attack) lasts less than 30 minutes.


Can you explain what is inverted Arbaugh and do you plan to release the code of chopchop to make us understand how the attack works.
sylvain
 
Posts: 175
Joined: Mon Jun 21, 2004 5:57 am
Location: Paris, France

Postby sylvain » Sat Sep 04, 2004 8:56 am

KoreK wrote:That's not what he wrote, WPA does not run on old hardware. And if Orinoco is filtering the weak IVs from the FMS paper, they are not filtering much.
And you don't need a key to decrypt a packet, you just use the AP. Not fast, as a matter of fact 10-20 time slower than what I was expecting (40 minute for a 60-byte packet), but it works. Some limitation might come from 802.11, but injecting in monitor mode isn't fast either (apparently).

Post-edit: Misread your post. Sorry. So, that's what he wrote. But the problem remains.



will chopchop implement this attack (decrypt a packet without the key ) ?
sylvain
 
Posts: 175
Joined: Mon Jun 21, 2004 5:57 am
Location: Paris, France

Postby KoreK » Sat Sep 04, 2004 12:04 pm

Excerpt from chopchop DOC file:
Code: Select all
Quick explanation of the inner workings of chopchop.

Theory:
WEP frames are appended with a CRC (called ICV). Unfortunately, this
CRC doesn't preserve any integrity: CRC is based on a xor operation,
just like WEP, and xor "commutes".

Given a plaintext P, WEP appends the ICV to it, and xor it with RC4
encryption stream. The encrypted message is
   M = (P + ICV(P) ) xor RC4.
An attacker intercepts the encrypted message M, and wishes to flip
some bits inside P (ie a xor operation), and inject the plaintext P'
into the wireless network. Technically P'=P xor Mod, where Mod is the
bitmask of the flips. Since the ICV of P' is the ICV of P xored with
a "modified" CRC of Mod, the relation between the plain texts are
   P' + ICV(P') = ( P + ICV(P) ) xor ( Mod + ModCRC (Mod) )
and the corresponding encrypted messages are
   M' = ( P' + ICV(P') ) xor RC4
      = ( P + ICV(P) ) xor RC4 xor ( Mod + ModCRC (Mod) )
      = M xor ( Mod + ModCRC ( Mod ) )

So an attacker can inject any arbitrary modification of a valid
encrypted packet.

chopchop exploits another vulnerability of the ICV. If the encrypted
message M (ie P + ICV(P) ) is truncated of its last character, then
the message becomes invalid. Nevertheless xored with a certain value,
the truncated M will become valid again. Basic maths say that the
value does only depend on the truncated byte (of the unencrypted
message). So chopchop truncates the message, guesses the last value
being 0, corrects the truncated message, injects it into the AP,
then repeats the operation for 1,2,...,255. The packet that comes
thru will give the last byte of (P + ICV(P)) and of the RC4 stream.
Repeating the operation decrypts M.

Note that the inverse transformation is also possible: An encrypted
packet can be enlarged by 1 byte,  thus revealing other bytes of the
WEP stream (aka Arbaugh inductive attack).


The math:
A message with a CRC, is (with a little simplification) a polynome P(x),
with coefficient in Z/2Z, verifying the property

P = x^31 + ... + x + 1 (mod R)     (where R is the CRC polynomial)

Now split P in two parts: the constant term P_0 and the polynomial of
the coefficients of degree >0.

P = Q x + P_0

Q is the polynomial associated with the message and CRC, truncated by
1 bit. First we need to get the value of Q (mod R).

Q x = x^31 + ... + x + (1+P_0) (mod R)

Since R_0=1, x is invertible mod R with inverse A ( ie A x = 1 mod (R),
with A = (R-1)/x )

So

Q = A (x^31 + ... + x + (1+P_0)) (mod R)
Q + (A + 1) (x^31 + ... + (1+P_0)) + P_0 =
               x^31 + ... + 1 (mod R)

So the modification to apply to a message + crc truncated by one bit
only depends on the value of the last bit (P_0). Repeat it another 7
times and the modification to apply to a message + crc truncated by
one byte only depends on the value of the last byte.

Note that extending a message + CRC is easier, if P is a valid message,
then

Q = P x + x^32 + 1

is also valid (Arbaugh inductive attack).

----
KoreK

Release will be probably tomorrow. I am cleaning up, adjusting things, toying one last time the wlan-ng module. I am so slow.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby sylvain » Sat Sep 04, 2004 2:26 pm

KoreK wrote:Excerpt from chopchop DOC file:
Code: Select all
Quick explanation of the inner workings of chopchop.

Theory:
WEP frames are appended with a CRC (called ICV). Unfortunately, this
CRC doesn't preserve any integrity: CRC is based on a xor operation,
just like WEP, and xor "commutes".

Given a plaintext P, WEP appends the ICV to it, and xor it with RC4
encryption stream. The encrypted message is
   M = (P + ICV(P) ) xor RC4.
An attacker intercepts the encrypted message M, and wishes to flip
some bits inside P (ie a xor operation), and inject the plaintext P'
into the wireless network. Technically P'=P xor Mod, where Mod is the
bitmask of the flips. Since the ICV of P' is the ICV of P xored with
a "modified" CRC of Mod, the relation between the plain texts are
   P' + ICV(P') = ( P + ICV(P) ) xor ( Mod + ModCRC (Mod) )
and the corresponding encrypted messages are
   M' = ( P' + ICV(P') ) xor RC4
      = ( P + ICV(P) ) xor RC4 xor ( Mod + ModCRC (Mod) )
      = M xor ( Mod + ModCRC ( Mod ) )

So an attacker can inject any arbitrary modification of a valid
encrypted packet.

chopchop exploits another vulnerability of the ICV. If the encrypted
message M (ie P + ICV(P) ) is truncated of its last character, then
the message becomes invalid. Nevertheless xored with a certain value,
the truncated M will become valid again. Basic maths say that the
value does only depend on the truncated byte (of the unencrypted
message). So chopchop truncates the message, guesses the last value
being 0, corrects the truncated message, injects it into the AP,
then repeats the operation for 1,2,...,255. The packet that comes
thru will give the last byte of (P + ICV(P)) and of the RC4 stream.
Repeating the operation decrypts M.

Note that the inverse transformation is also possible: An encrypted
packet can be enlarged by 1 byte,  thus revealing other bytes of the
WEP stream (aka Arbaugh inductive attack).


The math:
A message with a CRC, is (with a little simplification) a polynome P(x),
with coefficient in Z/2Z, verifying the property

P = x^31 + ... + x + 1 (mod R)     (where R is the CRC polynomial)

Now split P in two parts: the constant term P_0 and the polynomial of
the coefficients of degree >0.

P = Q x + P_0

Q is the polynomial associated with the message and CRC, truncated by
1 bit. First we need to get the value of Q (mod R).

Q x = x^31 + ... + x + (1+P_0) (mod R)

Since R_0=1, x is invertible mod R with inverse A ( ie A x = 1 mod (R),
with A = (R-1)/x )

So

Q = A (x^31 + ... + x + (1+P_0)) (mod R)
Q + (A + 1) (x^31 + ... + (1+P_0)) + P_0 =
               x^31 + ... + 1 (mod R)

So the modification to apply to a message + crc truncated by one bit
only depends on the value of the last bit (P_0). Repeat it another 7
times and the modification to apply to a message + crc truncated by
one byte only depends on the value of the last byte.

Note that extending a message + CRC is easier, if P is a valid message,
then

Q = P x + x^32 + 1

is also valid (Arbaugh inductive attack).

----
KoreK

Release will be probably tomorrow. I am cleaning up, adjusting things, toying one last time the wlan-ng module. I am so slow.



ok very interesting..but why did you say you are slow ?
otherwise what's the difference between chopper and chopchop ? attacks 6 of chopper seems to be close to chopchop ..
sylvain
 
Posts: 175
Joined: Mon Jun 21, 2004 5:57 am
Location: Paris, France

Postby devine » Sun Sep 05, 2004 4:21 am

The tools that were recently released by TopoLB, devine, and KoreK take advantage of statistical optimizations described by h1kari[/URL]

Actually, David Hulton's statistical optimizations, as implemented in dwepcrack, are just a slightly enhanced version of the standard FMS attack. David described some 13% attacks on the second output byte but removed them from dwepcrack, saying they were slow and ineffective... On the other hand, KoreK's attacks go far beyond FMS, and broadly extend the Roos/Wagner cryptanalysis. Amusing excerpt from Wagner's post (circa '95):

I hope I didn't make any arithmetic mistakes in there. Anyhow, this is of very limited practical interest, but maybe someone'll be able to expand it to be more interesting.

Note to 133t h4xx0rz: No, weplab and aircrack don't run on PPC.

Well, one aircrack user reported being able to compile and run aircrack on his Mac OSX; he eventually cracked his WEP key ;)
devine
 
Posts: 389
Joined: Thu Jul 29, 2004 10:09 am
Location: Paris

Postby KoreK » Sun Sep 05, 2004 5:26 am

devine wrote:David described some 13% attacks on the second output byte but removed them from dwepcrack, saying they were slow and ineffective...

I think those were 3% (exp(-4)) attacks.
Amusing excerpt from Wagner's post (circa '95):

I hope I didn't make any arithmetic mistakes in there. Anyhow, this is of very limited practical interest, but maybe someone'll be able to expand it to be more interesting.

Mine is

So the only moral of this story is ``thank god SSL hashes before using RC4''.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Postby KoreK » Sun Sep 05, 2004 5:37 am

sylvain wrote:ok very interesting..but why did you say you are slow ?
otherwise what's the difference between chopper and chopchop ? attacks 6 of chopper seems to be close to chopchop ..

chopchop is an active attack, you inject packets to decrypt 1 packet.
chopper is a passive attack. From recovered packets, you decode the key. You might inject packets to accelerate the process, but you don't need to.
User avatar
KoreK
 
Posts: 102
Joined: Wed Jul 21, 2004 5:25 pm

Next

Return to News

Who is online

Users browsing this forum: No registered users and 3 guests

cron