0x1A Great Papers in Computer SecurityStream CiphersStream Cipher TerminologyProperties of Stream CiphersWeaknesses of Stream CiphersHow Random is “Random?”Cryptographically Secure PRNGLFSR: Linear Feedback Shift RegisterContent Scrambling System (CSS)Attack on CSS Decryption SchemeDeCSSDeCSS AftermathRC4RC4 InitializationN. Borisov, I. Goldberg, D. Wagner Intercepting Mobile Communications: The Insecurity of 802.11 (MOBICOM 2001)802.11b OverviewAccess Point SSIDWEP: Wired Equivalent PrivacyShared-Key AuthenticationHow WEP WorksRC4 Is a Bad Choice for WirelessRecovering KeystreamKeystream Will Be Re-UsedIt Gets WorseFixing the ProblemHacking MIFARE ChipsMIFARE ChipsMemory Structure of the CardSlide 29Challenge-Response in CRYPTO1PRNG in CRYPTO1Replay AttackExtracting the Key (Reader Only)Acquiring KeystreamInverting the Filter FunctionRolling Back the LFSRSummary: Weaknesses of CRYPTO1Extracting the Key (Card Only)slide 10x1A Great Papers inComputer SecurityVitaly ShmatikovCS 380Shttp://www.cs.utexas.edu/~shmat/courses/cs380s/slide 2Stream 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Ciphertext(Key,Msg)=IV, MsgPRNG(IV,Key)•Message processed bit by bit (unlike block cipher)No efficient algorithm can tellthis sequence from truly randomslide 3Stream 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  keystreamslide 4Properties 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 5Weaknesses 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M2slide 6How Random is “Random?”slide 7Cryptographically 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 secureslide 8LFSR: Linear Feedback Shift Registerb0Example:4-bit LFSRb1b2b3Key is used as the seed•For example, if the seed is 1001, the generated sequence is 1001101011110001001…Repeats after 15 bits (24-1)add to pseudo-random sequenceslide 9Each DVD is encrypted witha disk-specific 40-bit DISK KEYEach player has its own PLAYER KEY(409 player manufacturers,each has its player key)Content Scrambling System (CSS)DVD encryption scheme from Matsushita and ToshibaKEY DATA BLOCK contains disk key encryptedwith 409 different player keys:• EncryptDiskKey(DiskKey)• EncryptPlayerKey1(DiskKey) … EncryptPlayerKey409(DiskKey)This helps attackerverify his guess of disk keyWhat happens if even a singleplayer key is compromised?slide 10Attack 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-17disk keyLFSR-2524 key bits16 key bits“1” seeded in 4th bit“1” seeded in 1st bitinvert+mod 256carryEncrypted title keyTable-based“mangling”Decrypted title keyEncryptDiskKey(DiskKey)stored on diskThis attack takes O(225) [Frank Stevenson]slide 11DeCSS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 softwareslide 12DeCSS 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 Newsslide 13RC4Designed by Ron Rivest for RSA in 1987Simple, fast, widely used•SSL/TLS for Web security, WEP for wirelessByte array S[256] contains a permutation of numbers from 0 to 255i = j := 0loopi := (i+1) mod 256j := (j+S[i]) mod 256swap(S[i],S[j])output (S[i]+S[j]) mod 256end loopslide 14RC4 InitializationDivide key K into L bytesfor i = 0 to 255 do S[i] := ij := 0for i = 0 to 255 doj := (j+S[i]+K[i mod L]) mod 256swap(S[i],S[j])Key can be any lengthup to 2048 bitsGenerate initial permutationfrom 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