CS 380S 0x1A Great Papers in Computer Security Vitaly Shmatikov http www cs utexas edu shmat courses cs380s slide 1 Stream Ciphers One time pad Ciphertext Key Message Message Key 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 No efficient algorithm can tell this sequence from truly random Ciphertext Key Msg IV Msg PRNG IV Key Message processed bit by bit unlike block cipher slide 2 Stream Cipher Terminology The seed of 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 keystream Encrypt message by XORing with keystream ciphertext message keystream slide 3 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 secure slide 4 Weaknesses of Stream Ciphers No integrity Associativity commutativity X Y Z X Z Y M1 PRNG seed M2 M1 M2 PRNG seed Known plaintext attack is very dangerous if keystream is ever repeated Self cancellation property of XOR X X 0 M1 PRNG seed M2 PRNG seed M1 M2 If attacker knows M1 then easily recovers M2 Most plaintexts contain enough redundancy that knowledge of M1 or M2 is not necessary to recover both from M1 M2 slide 5 How Random is Random slide 6 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 attacker learns 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 secure slide 7 LFSR Linear Feedback Shift Register Example 4 bit LFSR b0 b1 b2 b3 add to pseudo random sequence Key is used as the seed For example if the seed is 1001 the generated sequence is 1001101011110001001 Repeats after 15 bits 24 1 slide 8 Content Scrambling System CSS DVD encryption scheme from Matsushita and Toshiba Each player has its own PLAYER KEY 409 player manufacturers each has its player key KEY DATA BLOCK contains disk key encrypted with 409 different player keys Each DVD is encrypted with a disk specific 40 bit DISK KEY 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 9 Attack on CSS Decryption Scheme Frank Stevenson 1 seeded in 1st bit 16 key bits disk key 4th EncryptDiskKey DiskKey stored on disk mod 256 24 key bits 1 seeded in LFSR 17 bit LFSR 25 Decrypted title key invert carry Encrypted title key Table based mangling 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 This attack takes O 225 Clock out 16 more bits out of both LFSRs verify the key slide 10 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 decryption key Recall that every CSS disk contains the master disk key encrypted under Xing s key One bad player entire system is broken Easy to use DeCSS software slide 11 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 From Wired News slide 12 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 loop slide 13 RC4 Initialization Key can be any length Divide key K into L bytes up to 2048 bits for i 0 to 255 do S i i j 0 for i 0 to 255 do Generate initial permutation j j S i K i mod L mod 256 from key K swap S i S j 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 MantinShamir attack slide 14 N Borisov I Goldberg D Wagner Intercepting Mobile Communications The Insecurity of 802 11 MOBICOM 2001 802 11b Overview Standard for wireless networks IEEE 1999 Two modes infrastructure and ad hoc IBSS ad hoc mode BSS infrastructure mode slide 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 from using an easily guessable SSID But then every user must know SSID in advance slide 17 WEP Wired Equivalent Privacy Special purpose protocol for 802 11b Intended to make wireless as secure as wired network Goals confidentiality integrity authentication Assumes that a secret key is shared between access point and client Uses RC4 stream cipher seeded with 24 bit initialization vector and 40 bit key Terrible design choice for wireless environment slide 18 Shared Key Authentication Prior to communicating data access point may require client to authenticate
View Full Document
Unlocking...