Cristina Nita-Rotaru Spring 2004/Lecture 14 1Security Topics in Networkingand Distributed SystemsCS 590DLecture 14: WEPDepartment of Computer SciencesPurdue UniversityCristina Nita-Rotaru Spring 2004/Lecture 14 2References• Intercepting MobileCommunications: TheInsecurity of 802.11 NikitaBorisov, Ian Goldberg, DavidWagner, INFOCOM 2001.• Using the Fluhrer, Mantin, andShamir Attack to Break WEP ,Adam Stubblefield, JohnIoannidis, and Aviel D. Rubin,NDSS 2002.Cristina Nita-Rotaru Spring 2004/Lecture 14 3Wired Equivalent Privacy• Security goals: protect link-level transmission– Confidentiality– Access control– Data integrity• Security relies on the difficulty of discovering thesecret key through a brute-force attack• Uses stream cipher RC4 for encryption andCRC32 for integrityCristina Nita-Rotaru Spring 2004/Lecture 14 4WEP Details• RC4 is a stream cipher: based on key k andinitialization vector (IV) v, generates a keystreamRC4(v,k)• To send a message M from A to B– Compute integrity checksum (CRC32): c(M)– plaintext P = {M, c(M)}– Encrypt P using RC4: ciphertext C = P ⊕ RC4(v,k)– Transmit C’ = v, (P ⊕ RC4(v,k))• To decipher an encrypted message C’, theencryption process is reversedCristina Nita-Rotaru Spring 2004/Lecture 14 5Some Observations• The integrity check does not depend on a key, butjust on the message M, so anybody can create apair M and CRC32(M)• The WEP standard specifies 40 bit keys and 24 IV,sometimes referred as a 64-bit key. Some vendorimplemented 128-bit keys (24 IV and 104 bit key).• The IV is sent in clear, so is available to theattacker as well.Cristina Nita-Rotaru Spring 2004/Lecture 14 6Risk of Keystream ReuseC1 = P1 ⊕ RC4(v, k)C2 = P2 ⊕ RC4(v, k)C1 ⊕ C2 = P1 ⊕ P2• If P1 or P2 is also known by the attacker, the otherplaintext is easy to compute• If n ciphertexts using the same keystream are availablemakes reading traffic easier (frequency analysis, etc)• Find plaintext P and the encryption C with keystream k,then it is easy to decipher any ciphertext C’ encryptedwith the same keystream k.Cristina Nita-Rotaru Spring 2004/Lecture 14 7Is Keystream Reused?• The pseudorandom keystream is based on theshared key k and the initialization vector IV. Sincethe key k is secret and is difficult to be changed forevery packet, changing the IV is important toprevent keystream reuse.• The IV is sent in clear, so is available to theattacker as well.• The WEP standard recommends, but does notrequire that the IV be changed every packet, butdoes not say anything about how to select the IV.• An implementation can reuse the same IV for allpackets without risking non-compliance !Cristina Nita-Rotaru Spring 2004/Lecture 14 824-bit IV Space• Busy access point sending 1500 byte packets,at an average of 2 Mbps, exhausts the space inhalf a day.• Random generation of IV can produce collisionsevery 5000 packets (due to the birthdayparadox).• Many implementations use for IV a counter thatis incremented for each packet sent and resetevery time the card is inserted in the computer.Cristina Nita-Rotaru Spring 2004/Lecture 14 9Exploiting Keystream Reuse• Methods to obtain pairs (plaintext,ciphertext):– IP fields predictable: login sequences, recognizeshared libraries transfer– Send email and wait for the user to check it viawireless links– Send data to access-points that have accesscontrol disables and observe the encrypted dataCristina Nita-Rotaru Spring 2004/Lecture 14 10Dictionary Attack• Goal: Decrypt traffic• How: Store keystream in a table, indexed by IV.• Remember the IV is sent it clear• When the attacker sees a packet with an IVstored already in the table, look up thecorresponding keystream, XOR it against thepacket, and read the data!• Table is at most 1500 * 2^24 bytes = 24 GBCristina Nita-Rotaru Spring 2004/Lecture 14 11Packet Modification• CRC32 is linear: c(M ⊕ D) = c(M) ⊕ c(D)• Message M was transmitted, and the ciphertext wasC and the IV was IV, C and IV are known to theadversary.• Attacker can find C’ s. t. it decrypts to M’,M’ = M ⊕ DD = arbitrarily chosen by the attacker• C’= C ⊕ <D,c(D)> = RC4(v,k) ⊕ <M,c(M)> ⊕ <D,c(D)> = RC4(v,k) ⊕ <M ⊕ D, c(M) ⊕ c(D)> = RC4(v,k) ⊕ <M’, c(M ⊕ D)> = RC4(v,k) ⊕ <M’, c(M’)>Cristina Nita-Rotaru Spring 2004/Lecture 14 12Packet Injection• The attacker knows the keystream, hecan select any message and computeCRC of the message without knowing thekey.• The base station will accept the packet asvalidCristina Nita-Rotaru Spring 2004/Lecture 14 13WEP Authentication• Base station verifies that a client joining thenetwork really knows the shared secret key k.• The base station sends a challenge string to theclient, and the client sends back the encryptedchallenge• The base station checks if the challenge iscorrectly encrypted, and if so, accepts the client.• If adversary sees a challenge/response pair for agiven key k; he can perform the packet injectionattack previously describe, and trick the basestation.Cristina Nita-Rotaru Spring 2004/Lecture 14 14Fluher, Mantin, and Shamir Attack• This is an known-plaintext attack against RC4,that allows attackers to eventually recover akey.• Attack is based on an assumption that theattacker is able to guess the first byte ofplaintext used by the victim.• Stubblefield, Ionnandis, and Rubin showedthat the attack is possible in practiceCristina Nita-Rotaru Spring 2004/Lecture 14 15RC4• A proprietary cipher owned by RSA DSI, designedby Ron Rivest.• Simple and effective design.• Variable key size, byte-oriented stream cipher.• Widely used (web SSL/TLS, wireless WEP).• Key forms random permutation of all 8-bit values.• Uses that permutation to scramble input infoprocessed a byte at a time.Cristina Nita-Rotaru Spring 2004/Lecture 14 16RC4 Key Schedule• Walks each entry in an array S of numbers: 0..255 turn, using itscurrent value plus the next byte of key to pick another entry in thearray, and swaps their values over.• Total number of possible states is 256!, very big number• S forms internal state of the cipher, L is the size of the key kfor i = 0 to 255 doS[i] = ij = 0for i = 0 to 255 doj = (j + S[i] + k[i mod L])(mod 256)swap (S[i], S[j])Cristina Nita-Rotaru Spring 2004/Lecture 14 17RC4 Encryption• Encryption continues shuffling array values• Sum of shuffled pair selects the
View Full Document
Unlocking...