128bit security and 40bit misconceptions

[Goosemaster]

I CONSISTENTLY hear ramblings about how 128bit WEP encryption is only 40bit strong. What is the truth to that if at all.

Being as a computer in 1996 was able to crack a 40bit key in 8 days, I assume modern resutls are exponentially greater(or lesser in the amount of time in takes).

 

[buleyb]

What they typically refer to as 40bit strong means that the methods use to break WEP apply equally to either 40 or 104 bit keys.

128bit WEP is a 104bit key with a 24 bit init vector. 64bit WEP is a 40bit key with a 24bit init vector.

Because WEP isn't cracked using brute force, this isn't a problem that goes away with key length. This is why they say its only 40 bit strong, because if you have a 104bit key, the time is still the same as a 40bit key, so it buys you nothing in the traditional sense.

Edit: To be more clear, the 24bit init vector is always sent plaintext, and as a further security hole, the 24bit init vector has certain values that are known to be `weak`, and easier to crack. Thats the primary reason for collecting so much data to be able to break WEP.

 

[eigen]

To elaborate a little further the initializtion vector provides an almost perfect opputrtunity to mount a known plaintext assualt on the key in turn this reduces the time/key space to approximately a 40 bit key.


......I am currently reading " Real 802.11 Securtiy" you may want to check it out....

 

[cmetz]

Goosemaster, this statement is not correct.

128 bit WEP has 112 bits of key significance. 64 bit WEP has 40 bits of key significance.

There is a design flaw in WEP that allows an attack in which the key can be recovered more quickly than a brute-force attack on the key space. The attack requires a volume of captured data, (mostly but not all of which is ciphertext) of which some of the contents is known plaintext per the protocol. Key recovery in this manner for a 128 bit WEP key takes longer than key recovery for a 64 bit WEP key, but the fact that it's practical is already disastrous. A 128 bit, or even 112 bit, key is pretty much beyond brute force and will be for quite a while to come.

TKIP basically works by generating a sequence of WEP keys based on a master key, and re-keying periodically before enough volume of ciphertext could be captured to allow recovery of the WEP key. It's a bit of a kluge, but since WEP is already in deployed hardware, it's good to be able to patch up the existing hardware. Too bad the software support for TKIP on older hardware mostly never came.

 

[groovin]

cmetz,

but even with TKIP, how easy can the WEP key be found? is there a minimum limit of ciphertext needed?

dang, i just put up a WAP at work, dont think it supports TKIP though. Does TKIP only come on more expensive hardware or do SOHO's implement them now?

 

[Dark]

Originally posted by: groovin
cmetz,

but even with TKIP, how easy can the WEP key be found? is there a minimum limit of ciphertext needed?

dang, i just put up a WAP at work, dont think it supports TKIP though. Does TKIP only come on more expensive hardware or do SOHO's implement them now?

You approximately need 2500-4000 weak packets (some hardware are weakers than others) to be able to crack the wep key which translates to roughly 1.3 millions packets. With TKIP you can set it to a per session or per packet key change, the trade off of course is a huge hit performance wise because of the overhead. Tkip is not the only solution...I believe Cisco came out first with their TKIP solution + MIC to make sure that the packets are not tampered with. There are also other solutions out there to patch the wep weakness but AES solve all those problems So if You use AES you are not concerned

 

[cmetz]

groovin, this is exactly it - there's a volume of capture needed to recover the WEP key, so if you change the key before that volume could have been transmitted, then you avoid the attack.

Most 802.11g stuff supports WPA TKIP - I think it's manadatory for full standards compliance? Lucent/Avaya/Proxim Wavelan/Orinoco and Cisco's Aironet I believe support TKIP on 802.11b-only gear, but they may be it. I think on pre-g stuff it's spotty because vendors really want to sell you new stuff. It's a shame, because the whole reason to do TKIP in the first place was the easy retrofit.

 

[JackMDS]

Each packet has 24bits Initialization vector .

40bits (encryption)+ 24bits(init. vector)=64bits.

104bit(encryption)+ 24bits(init. vector)=128bits.

WEP uses RC4 stream encryption, for a fresh key stream for each packet.

The Init Vector & key combine to get per-packet key which is used to generate RC4 keys stream.

The RC4 is one of the major culprits in the security issues (it is too long story to explain it here).

In breaking security Codes, the base key size is significant only to brute force attacks; it is irrelevant to the RC4 use.

The hopefully soon coming 802.11i

Likely to include:

Temporal Key Integrity Protocol (TKIP)
Replace RC4, probably with AES
Message Integrity Code (MIC)

Mean time: Basic Protection for Broadband Internet Installation.

:light:

 

[Boscoh]

TKIP was ONLY designed as a stop-gap measure to implement until vendors could introduce AES support into their hardware. TKIP is a temporary patch to WEP, but not an overall solution. If you can, use AES.

That said, one of the things TKIP does is extend the IV to 48 bits. This adds complexity to the algorithm and increases the number of packets that an attacker has to get before they can find the key. TKIP will rekey every 10,000 packets, which should be quick enough to foil any statistical methods an attacker might use to analyze ciphertext. TKIP also adds into the picture the Message Integrity Code (MIC, or Michael, or Mike) to ensure authenticity. Whenever a device recieves a transmission, it checks the CRC, the IV, and ICV (Integrity Check Value) before it checks the MIC. If the packet was tampered with enroute, there is going to be something that does not compute like it is supposed to. This gives you reasonable assurance that the message was tampered with. WPA immediately stops using all the current keys and rekeys if this is detected.

TKIP is not impenetrable, it's only a bandage to WEP. AES is the current government standard for strong encryption, and it's what you should use without a doubt if you hardware supports it.

EDIT: Most 11G units should either support WPA+TKIP now, or have a firmware update to support it. The only B units I know of that support TKIP are Cisco and some Orinoco gear.

 

[groovin]

what is AES besides Adv Encryp Standard?

googling it, ive read its a replacement for 3DES, but that doesnt tell me exactly how it operates in wireless. I am familiar with using ipsec over wifi, is this something similar?

 

[buleyb]

Originally posted by: groovin
what is AES besides Adv Encryp Standard?

googling it, ive read its a replacement for 3DES, but that doesnt tell me exactly how it operates in wireless. I am familiar with using ipsec over wifi, is this something similar?

Actually, its a replacement for DES, to be more specific. AES is cipher also know as Rijn-Dael, and is a secure (so-far), fast symmetric cipher that is easily implementable in hardware.

Its use in wireless is based on the speed of the cipher in hardware. Actually, for WPA and 802.11i, AES will only be allowed if implemented in hardware, otherwise TKIP is the backup for WPA.

 

[Boscoh]

AES was an initiative by the government to find a suitable replacement for 3DES. It was a competition between numerous candidate algorithms against a set of defined guidelines defined by the NIST (www.NIST.gov). Some of the criteria the government was looking for were:
Good security - the algorithm should be resistant to every form of known attack
Fast - it should be able to be implemented in hardware or software across a variety of platforms
Adaptable - it should be able to be implemented in a range of environments, ie ATM, Satellite, Cable, wireless, etc. It should also support different block and key sizes.

There were numerous other criteria, but those were some of the major ones.

The Rijndael algorithm eventually beat out all the other candidates and became the basis for AES. The primary difference between the submitted Rijndael and the final product of AES is that Rijndael supported 128, 192, and 256 bit block sizes, the NIST limited this to only 128 for AES. It can still use 128, 192, or 256 bit keys.

AES was needed because
1) 3DES had a known weakness in the mathematical algorithm.
2) 3DES was not the most efficient algorithm in the world to implement.
3) The government wanted a new toy to play with.

In my own testing I've found that using 256-bit AES usually takes the same CPU/memory toll on the system as 168-bit 3DES, perhaps just a little bit less. It is a very efficient algorithm.

It is intended as a replacement to 3DES. IPSec can use AES or 3DES. The way 3DES works over wireless is very similar to how AES works.

AES has it's own mechanism for dynamic subkey generation so you dont have to worry about the key retrieval attack as you do with WEP or TKIP (if they can get your key before you rekey). It's also resistant to statistical analysis of the ciphertext (finding which letter appears most often in the ciphertext, and assuming that letter is the one which is known to be the most commonly used in the English language, etc), which is a weakness of the RC4 algorithm used in WEP, WPA, WPA+TKIP.

Does that answer your question?

 

[buleyb]

Originally posted by: Boscoh

It's also resistant to statistical analysis of the ciphertext (finding which letter appears most often in the ciphertext, and assuming that letter is the one which is known to be the most commonly used in the English language, etc), which is a weakness of the RC4 algorithm used in WEP, WPA, WPA+TKIP.

Can you provide some info regarding this? I wasn't aware of any statistical analysis against RC4, besides implementations in things like WEP where the key schedule is weak. You can't do "english language" frequency analysis against it anyway, because its not a straight substitution cipher.

I'm willing to except it if you can provide some background though...

 

[JEDI]

Originally posted by: Boscoh
TKIP was ONLY designed as a stop-gap measure to implement until vendors could introduce AES support into their hardware. TKIP is a temporary patch to WEP, but not an overall solution. If you can, use AES.

That said, one of the things TKIP does is extend the IV to 48 bits. This adds complexity to the algorithm and increases the number of packets that an attacker has to get before they can find the key. TKIP will rekey every 10,000 packets, which should be quick enough to foil any statistical methods an attacker might use to analyze ciphertext. TKIP also adds into the picture the Message Integrity Code (MIC, or Michael, or Mike) to ensure authenticity. Whenever a device recieves a transmission, it checks the CRC, the IV, and ICV (Integrity Check Value) before it checks the MIC. If the packet was tampered with enroute, there is going to be something that does not compute like it is supposed to. This gives you reasonable assurance that the message was tampered with. WPA immediately stops using all the current keys and rekeys if this is detected.

TKIP is not impenetrable, it's only a bandage to WEP. AES is the current government standard for strong encryption, and it's what you should use without a doubt if you hardware supports it.

EDIT: Most 11G units should either support WPA+TKIP now, or have a firmware update to support it. The only B units I know of that support TKIP are Cisco and some Orinoco gear.

i have an orinoco 802.11b. how do i upgrade to tkip?

 

[groovin]

boscoh, thanks.

I have heard of AES then from a VPN standpoint (rijndael)... I've actually tried it out on my *nix routers, but opted for 3DES instead because of compatibility reasons.

Does windows have support for AES or would that usually be something that would be provided by the wifi vendor for the user to install?

 

[Boscoh]

Originally posted by: buleyb

Originally posted by: Boscoh

It's also resistant to statistical analysis of the ciphertext (finding which letter appears most often in the ciphertext, and assuming that letter is the one which is known to be the most commonly used in the English language, etc), which is a weakness of the RC4 algorithm used in WEP, WPA, WPA+TKIP.

Can you provide some info regarding this? I wasn't aware of any statistical analysis against RC4, besides implementations in things like WEP where the key schedule is weak. You can't do "english language" frequency analysis against it anyway, because its not a straight substitution cipher.

I'm willing to except it if you can provide some background though...

That's what I was referring to. This statistical analysis method doesn't exist if RC4 is implemented correctly. I used the english language analysis as an example of what statisical analysis was. I've seen publications on other *theoretical* statistical analysis methods of RC4, but a lot of them say there is no practical way to implement their methods when the paper was written, these are very complicated and are more similar to the substitution cipher-style methods than the methods you use for RC4 to analyze for weak keys. You can also do a wordlist attack, since a lot of software lets you generate WEP keys from a passphrase, unless you dont use a word in the dictionary as your passphrase.


JEDI: I dont know where you get the update for Orinoco stuff, just that it can be done. One of our partners was telling us they did it to theirs. You might need to get in touch with Orinoco tech support. Their site is down at the moment.

Groovin: There is an update to Windows XP that allows WPA. You can get it at Windows Update. If you dont want to use Windows for your wireless, you're gonna have to wait for a utility from your vendor that supports it.

 

[JackMDS]

Part of the weakness of RC4 has to do with the combo of Init. Vector and Plain Text chipper.

24 bit Init vector is finishing a cycle of 2 in the power of 24 in about hour and then repeats.

Repeating Init Vector plus knowledge about the plaintext language, makes guessing the plaintexts simpler.

 

[Boscoh]

The method I am talking about is when weak keys that have certain bytes in common tend to generate the same first bytes as each other. There have been publications about which keys that are generated are weak keys. Using thw knowledge of which weak keys generate the same bytes, an attacker can analyze a stream of transmissions for these bytes, if he finds them he knows that RC4 is using weak keys. He can then limit his brute force attack on the algorithm to include only weak keys. This reduces the possibilities substantially. Further, there are apparently certain weak keys that statistically appear more than others, given that RC4 is determined to be using weak keys.

Thats the method I was referring to by 'statistical analysis'.

 

[Rainsford]

Other people (especially Boscoh) have said pretty much all there is to say, but I thought I'd throw my 2 cents in.

Someone said initialization vectors being transmitted in the clear is a security problem with WEP. Actually, in order for an initialization vector to be useful it should be fairly random and transmitted in the clear. If done correctly, knowing the IV doesn't give an attacker enough useful info to make a difference. I'm not going to explain the entire thing here, but if you are really interested look up how AES is used in Cipher Block Chaining (CBC) mode with initialization vectors. It's pretty interesting stuff if you want to see how to really implement secure crypto...not sure if this is what the wireless standard uses or not, I'll have to look into that.

 

[buleyb]

Originally posted by: Boscoh
That's what I was referring to. This statistical analysis method doesn't exist if RC4 is implemented correctly. I used the english language analysis as an example of what statisical analysis was. I've seen publications on other *theoretical* statistical analysis methods of RC4, but a lot of them say there is no practical way to implement their methods when the paper was written, these are very complicated and are more similar to the substitution cipher-style methods than the methods you use for RC4 to analyze for weak keys. You can also do a wordlist attack, since a lot of software lets you generate WEP keys from a passphrase, unless you dont use a word in the dictionary as your passphrase.

Ok, I'm in full agreement with that, and like has been mentioned before, there is a frequency attack against known network control packets.

I'm sure we can all agree that WEP sucks though, right?

 

[Boscoh]

Originally posted by: buleyb


I'm sure we can all agree that WEP sucks though, right?

Yeah, I'll agree with that.

I've seen it mentioned in several articles done by IEEE 802.11 working group members or people that followed the working group's activities that WEP was a great candidate for a standard. While everyone was touting their own methods as the greatest wireless encryption scheme, no one could agree on any one method. Then came WEP. Everyone agreed that it sucked, but that it could be implemented quickly and cheaply...thus, a standard was born.

We are doing a *very* extensive study of how AES works in my cryptology class right now. We are learning the intricacies of how the S-boxes are created in AES right now. I'm sure we are going to be learning how it's implemented in wireless networks as well. Every professor at my school, and some of them come from places like Nasa or the Army Security Agency, have analyzed AES to the core....like all 40+ pages of the algorithm's code. They seem to think that AES is the best thing since sliced bread as far as encryption is concerned. I'm not enough of a mathematician to analyze the algorithm and compare it to others, nor am I old enough to have experience with a lot of the previous algorithms...but compared to 3DES or RC4(WEP) in a practical application, I think AES is a winner.