Vitaly Shmatikov CS 361S Introduction to Stream Ciphers Attacks on CSS, WEP, MIFAREslide 2 Stream Ciphers One-time pad: Ciphertext(Key,Message)=MessageKey • Key must be a random bit sequence as long as message Idea: replace “random” with “pseudo-random” • Use a pseudo-random number generator (PRNG) • PRNG takes a short, truly random secret seed and expands it into a long “random-looking” sequence – E.g., 128-bit seed into a 106-bit pseudo-random sequence Ciphertext(Key,Msg)=IV, MsgPRNG(IV,Key) • Message processed bit by bit (unlike block cipher) No efficient algorithm can tell this sequence from truly randomslide 3 Stream Cipher Terminology The seed of a pseudo-random generator typically consists of initialization vector (IV) and key • The key is a secret known only to the sender and the recipient, not sent with the ciphertext • IV is usually sent with the ciphertext The pseudo-random bit stream produced by PRNG(IV,key) is referred to as the keystream Encrypt message by XORing with keystream • ciphertext = message keystreamslide 4 Properties of Stream Ciphers Usually very fast (faster than block ciphers) • Used where speed is important: WiFi, DVD, RFID, VoIP Unlike one-time pad, stream ciphers do not provide perfect secrecy • Only as secure as the underlying PRNG • If used properly, can be as secure as block ciphers PRNG must be cryptographically secureslide 5 Using Stream Ciphers No integrity • Associativity & commutativity: (M1PRNG(seed)) M2 = (M1M2) PRNG(seed) • Need an additional integrity protection mechanism Known-plaintext attack is very dangerous if keystream is ever repeated • Self-cancellation property of XOR: XX=0 • (M1PRNG(seed)) (M2PRNG(seed)) = M1M2 • If attacker knows M1, then easily recovers M2 … also, most plaintexts contain enough redundancy that can recover parts of both messages from M1M2slide 6 How Random is “Random”?slide 7 Cryptographically Secure PRNG Next-bit test: given N bits of the pseudo-random sequence, predict (N+1)st bit • Probability of correct prediction should be very close to 1/2 for any efficient adversarial algorithm (means what?) PRNG state compromise • Even if the attacker learns the complete or partial state of the PRNG, he should not be able to reproduce the previously generated sequence – … or future sequence, if there’ll be future random seed(s) Common PRNGs are not cryptographically secureslide 8 LFSR: Linear Feedback Shift Register b0 Example: 4-bit LFSR b1 b2 b3 For example, if the seed is 1001, the generated sequence is 1001101011110001001… Repeats after 15 bits (24-1) add to pseudo-random sequenceslide 9 Each DVD is encrypted with a disk-specific 40-bit DISK KEY Each player has its own PLAYER KEY (409 player manufacturers, each has its player key) Content Scrambling System (CSS) DVD encryption scheme from Matsushita and Toshiba KEY DATA BLOCK contains disk key encrypted with 409 different player keys: • EncryptDiskKey(DiskKey) • EncryptPlayerKey1(DiskKey) … EncryptPlayerKey409(DiskKey) This helps attacker verify his guess of disk key What happens if even a single player key is compromised?slide 10 Attack on CSS Decryption Scheme Given known 40-bit plaintext, repeat the following 5 times (once for each plaintext byte): guess the byte output by the sum of the two LFSRs; use known ciphertext to verify – this takes O(28) For each guessed output byte, guess 16 bits contained in LFSR-17 – this takes O(216) Clock out 24 bits out of LFSR-17, use subtraction to determine the corresponding output bits of LFSR-25 – this reveals all of LFSR-25 except the highest bit “Roll back” 24 bits, try both possibilities – this takes O(2) Clock out 16 more bits out of both LFSRs, verify the key … … LFSR-17 disk key LFSR-25 24 key bits 16 key bits “1” seeded in 4th bit “1” seeded in 1st bit invert +mod 256 carry Encrypted title key Table-based “mangling” Decrypted title key EncryptDiskKey(DiskKey) stored on disk This attack takes O(225) [Frank Stevenson]slide 11 DeCSS In CSS, disk key is encrypted under hundreds of different player keys… including Xing, a software DVD player Reverse engineering the object code of Xing revealed its player key • Every CSS disk contains the master disk key encrypted under Xing’s key • One bad player entire system is broken! Easy-to-use DeCSS softwareslide 12 DeCSS Aftermath DVD CCA sued Jon Lech Johansen (“DVD Jon”), one of DeCSS authors - eventually dropped Publishing DeCSS code violates copyright • Underground distribution as haikus and T-shirts • “Court to address DeCSS T-Shirt: When can a T-shirt become a trade secret? When it tells you how to copy a DVD.” - Wired Newsslide 13 RC4 Designed by Ron Rivest for RSA in 1987 Simple, fast, widely used • SSL/TLS for Web security, WEP for wireless Byte array S[256] contains a permutation of numbers from 0 to 255 i = j := 0 loop i := (i+1) mod 256 j := (j+S[i]) mod 256 swap(S[i],S[j]) output (S[i]+S[j]) mod 256 end loopslide 14 RC4 Initialization Divide key K into L bytes for i = 0 to 255 do S[i] := i j := 0 for i = 0 to 255 do j := (j+S[i]+K[i mod L]) mod 256 swap(S[i],S[j]) Key can be any length up to 2048 bits Generate initial permutation from key K To use RC4, usually prepend initialization vector (IV) to the key • IV can be random or a counter RC4 is not random enough… First byte of generated sequence depends only on 3 cells of state array S - this can be used to extract the key! • To use RC4 securely, RSA suggests discarding first 256 bytes Fluhrer-Mantin-Shamir attackslide 15 802.11b Overview Standard for wireless networks (IEEE 1999) Two modes: infrastructure and ad hoc IBSS (ad hoc) mode BSS (infrastructure) modeslide 16 Access Point SSID Service Set Identifier (SSID) is the “name” of the access point • By default, access point broadcasts its SSID in plaintext “beacon frames” every few seconds Default SSIDs are easily guessable • Manufacturer’s defaults: “linksys”, “tsunami”, etc. • This gives away the fact that access point is active Access point settings can be changed to prevent it from announcing its presence in beacon frames and
View Full Document
Unlocking...