Crypto BlundersIn HistorySlide 3Slide 4Slide 5Slide 6Slide 7Crypto Blunder #1Web SearchRSA Challenge and Ron Rivest’s StatementSecurity ProofSecurity Proof?Ding-RabinOne-Time PadSlide 15Slide 16Crypto Blunder #2Some proposalsSlide 19Microsoft’s PPTPSlide 21Which Algorithm?Slide 23Crypto Blunder #3Best Available Algorithm?New Algorithm?DVD (Digital Video Disc)DVDSlide 29DVD: One way to CheatSlide 31ImplementationSlide 33Crypto Blunder #4Using RSARSA implementationDSA (Digital Signature Algorithm)DSA SecurityJavaSoft DSA ImplementationThe k’sDisaster MitigatedEnigma keysSlide 43Crypto Blunder #5PBE technique to protect keysResponsesCrypto AGSlide 48Clipper ChipSlide 50Slide 51Crypto BlundersSteve Burnett, RSA Security [email protected] Oct. 15, 2002In HistoryScientific American in 1917:The Vigenére Cipher is “impossible oftranslation” . . .In HistoryProblem:Union Army broke the Vigenére Cipherduring the United States Civil War inthe 1860’s.In HistoryDuring WWII:Message from LuftwaffeHigh Command to a fieldofficer declared Enigma“unbreakable”. Thatmessage was encryptedusing Enigma.In HistoryHow do we know about this message?It was cracked by the British shortlyafter being intercepted.In HistoryScientific American in 1977:Martin Gardner published the first RSAchallenge, $100 to the first person whocould crack a message encrypted usingthe algorithm. Gardner claimed thecipher was unresolvable. Ron Rivest(the “R”) declared that it would take “40quadrillion years” to crack.In HistoryResult?They paid up 17 years later.Crypto Blunder #1Declare your algorithm to be “unbreakable”.Web Search•UBE (UnBreakable Encryption) http://www.atlantic-coast.com/ube/•VME (Virtual Matrix Encryption) “100% Security” “Our technology, VME, is quite simply the only unbreakable encryption available.” http://www.meganet.com$1.2 million in challengesRSA Challenge and Ron Rivest’s Statement•“Using current technology . . .”•The algorithm had just been (re)invented that year, more research would yield better security numbers•The challenge was on a 428-bit key (most use today is 1024 or 2048 bits)•RSA as an algorithm is still secureSecurity Proof”This is the first provably unbreakable code that is really efficient.”“We have proved that the adversary is helpless.””It provides everlasting security.”Michael Rabin and Yan Zong Ding (algorithm known as Ding-Rabin)Security Proof?Atjai-Dwork: algorithm proposed in 1997, came with a security proof.Broken in 1998 (attacked assumptions, not math).Ding-RabinOne-time pad with an “unbreakable” pad derivation function.Assumption: Adversary has only one attack.Assumption: Adversary needs to store an inordinate amount of data.Assumption: Algorithm can set the threshold of storage beyond adversary’s capacity.One-Time PadBelief: “The one-time pad is the only unbreakableencryption scheme.” P L A I N T E X T . . .Pad: 05 10 03 21 00 07 14 14 08 . . . U V D D N A S L B . . .One-Time PadMore rigorous declaration: “If the pad is randomand the pad is used only once, the one-time pad hasprovable security properties.”This implies, “If the pad is not random and/orthe pad is used more than once, there aresecurity holes.”One-Time Pad1930’s - 1940’s:Soviet Union used one-time pads to encryptmessages to diplomatic missions throughout theworld.They used some pads more than once. The errorwas in a manufacturer accidentally printing padsmore than once.Crypto Blunder #2Worship at the altar of the one-time padSome proposalsOne-time pads for personal use, where do you get the pad?CD’s or DVD’sGenerate a pad using a PRNG, then store the pad in a file (suggestion from manufacturer: store the pad on a floppy)One-Time Pad1998:Microsoft releases an implementation of thePoint-to-Point Tunneling Protocol (PPTP).They used RC4 to encrypt the bulk data.RC4 is a kind of one-time pad, generating thepad “on-the-fly”, as more pad data is needed.Microsoft’s PPTPServerClientMessages from client to server:One encryption “subsession”Needs a keyMessages from server to client:Another encryption “subsession”,start over from scratchNeeds another keyMicrosoft’s PPTPServerClientMessage from client to server: Send secret dataRC4 “pad”: 38 0C 5D 77 . . .Ciphertext: kisé . . .Message from server to client: Buy ACME at $10RC4 “pad”: 38 0C 5D 77 . . .Ciphertext: zy$W . . .Which Algorithm?1700’s:Many countries established “Black Chambers”which read and tried to decipher most mail sentto diplomatic missions.Strategy for sending messages: Use the bestknown cipher.Which Algorithm?•Vigenére cipher available since 1500’s•1700’s, Vigenére had not been broken yet•Most correspondents knew the ciphers they were using (often simple or complicated letter substitutions) were not secure•Used them anywayCrypto Blunder #3Don’t use the best available algorithmsBest Available Algorithm?Microsoft invented a new block cipher to be used in their Digital Rights Management (DRM) software.Version 2 of the DRM was broken, one byproduct was a reverse-engineering of the new block cipher (dubbed MultiSwap).UC Berkeley team (including David Wagner) shows the algorithm to be very weak.New Algorithm?Why invent a new block cipher?Microsoft had a license to use RC5.They had no way of knowing their new algorithm would be weak, but had no way of knowing it would be strong either.Use a studied cipher.DVD (Digital Video Disc)Disc with movieDVD playerThe movie encrypted: 26D787C34BB7855E 9267F86B25A87B68 6A28E76A6105C991 . . .Copy-protected location100’s of copies of the moviekey, each encrypted with aseparate DVD player unlock key 432D68E70B B48F71A913 6C46A754D9 8B71F9360A . . .Extracts itscopy of the moviekey and uses itsunlock key to decryptthe movie key 97 9B 33 0A E2DVDDisc with movieDVD playerThe movie encrypted: 26D787C34BB7855E 9267F86B25A87B68 6A28E76A6105C991 . . .With the movie key, theplayer decrypts the movie 97 9B 33 0A E2DVD•The movie, encrypted or unencrypted, can be copied•The movie key copies (each encrypted with a different company’s unlock key) cannot be copied•If a licensed DVD player reads a disc without the movie key copies, even if the movie is unencrypted, it will not play the movieDVD: One way to Cheat•Copy the movie onto a new disc•Figure out what the movie key list is supposed to be, must know what each
View Full Document