Cryptography OverviewAnnouncement: Homework 1CryptographyBasic Cryptographic ConceptsFive-Minute UniversityExample: network transactionsSecure communicationSecure Sockets Layer / TLSSSL/TLS CryptographyExample cryptosystemsSymmetric EncryptionOne-time padTypes of symmetric encryptionFeistel network: One RoundData Encryption StandardBlock cipher modes (for DES, AES, …)Electronic Code Book (ECB)Cipher Block Chaining (CBC)Comparison (for AES, by Bart Preneel)RC4 stream cipher – “Ron’s Code”RSA Trade SecretEncryption/DecryptionSecurityComplete AlgorithmExample use of stream cipher?Wrong!Public-key CryptosystemComplexity ClassesExample: RSAWhy RSA works (quick sketch)Textbook RSA is insecureOAEP [BR94, Shoup ’01]Problem: IntegrityCryptographic hash functionsApplications of one-way hashIterated hash functionsMAC: Message Authentication CodeBasic CBC-MACHMAC: Keyed Hash-Based MACOrder of Encryption and MACsDigital SignaturesProperties of signaturesRSA Signature SchemePublic-Key Infrastructure (PKI)Public-Key InfrastructureSlide 46Back to SSL/TLSCrypto SummaryLimitations of cryptographySlide 50How well does RSA work?Message integrityCryptography Overview John MitchellCS155 Spring 2008Announcement: Homework 1Posted on webFive problemsDue April 29CryptographyIsA tremendous toolThe basis for many security mechanismsIs notThe solution to all security problemsReliable unless implemented properlyReliable unless used properlySomething you should try to invent yourself unless you spend a lot of time becoming an expertyou subject your design to outside reviewEncryption scheme:functions to encrypt, decrypt data key generation algorithmSymmetric key vs. public keyPublic key: publishing key does not reveal key-1Secret key: more efficient, generally key = key-1 Hash function, MACMap any input to short hash; ideally, no collisionsMAC (keyed hash) used for message integritySignature schemeFunctions to sign data, verify signatureBasic Cryptographic ConceptsFive-Minute UniversityEverything you might remember, five years after taking CS255 … ? This lecture describes basic functions and example constructions. Constructions not needed for CS155.Father Guido SarducciExample: network transactionsAssume attackers can control the networkWe will talk about how they do this in a few weeksAttackers can intercept your packets, tamper with or suppress them, and inject arbitrary packetsSecure communicationBased onCryptographic methodsKey management protocolsSecure Sockets Layer / TLSStandard for Internet securityOriginally designed by NetscapeGoal: “... provide privacy and reliability between two communicating applications”Two main partsHandshake ProtocolEstablish shared secret key using public-key cryptographySigned certificates for authenticationRecord LayerTransmit data using negotiated key, encryption functionSSL/TLS CryptographyPublic-key encryptionKey chosen secretly (handshake protocol)Key material sent encrypted with public keySymmetric encryptionShared (secret) key encryption of data packetsSignature-based authenticationClient can check signed server certificateAnd vice-versa, in principalHash for integrityClient, server check hash of sequence of messagesMAC used in data packets (record protocol)Example cryptosystemsOne-time pad“Theoretical idea,” but leads to stream cipherFeistel construction for symmetric key cryptoIterate a “scrambling function”Examples: DES, Lucifer, FREAL, Khufu, Khafre, LOKI, GOST, CAST, Blowfish, …AES (Rijndael) is also block cipher, but different …Complexity-based public-key cryptographyModular exponentiation is a “one-way” functionExamples: RSA, El Gamal, elliptic curve systems, ...Symmetric EncryptionEncryption keeps communication secretEncryption algorithm has two functions: E and DTo communicate secretly, parties share secret key KGiven a message M, and a key K:M is known as the plaintextE(K,M) → C (C known as the ciphertext)D(K, C) → MAttacker cannot efficiently derive M from C without KNote E and D use same key KReason for the name “symmetric encryption”One-time padShare a random key KEncrypt plaintext by xor with sequence of bitsencrypt(key, text) = key text (bit-by-bit)Decrypt ciphertext by xor with same bitsdecrypt(key, text) = key text (bit-by-bit)AdvantagesEasy to compute encrypt, decrypt from key, textThis is an information-theoretically secure cipherDisadvantageKey is as long as the plaintextHow does sender get key to receiver securely? Idea for stream cipher: use pseudo-random generators for key …Types of symmetric encryptionStream ciphers – pseudo-random padGenerate pseudo-random stream of bits from short keyEncrypt/decrypt by XORing as with one-time padBut NOT one-time PAD! (People who claim so are frauds!)Block cipherOperates on fixed-size blocks (e.g., 64 or 128 bits)Maps plaintext blocks to same size ciphertext blocksToday use AES; other algorithms: DES, Blowfish, . . .Feistel network: One RoundScheme requiresFunction f(Ri-1 ,Ki)Computation for Ki e.g., permutation of key KAdvantageSystematic calculationEasy if f is table, etc.Invertible if Ki knownGet Ri-1 from LiCompute f(R i-1 ,Ki)Compute Li-1 by L i-1R i-1R iL ifK iDivide n-bit input in half and repeatData Encryption Standard Developed at IBM, some input from NSA, widely usedFeistel structurePermute input bitsRepeat application of a S-box functionApply inverse permutation to produce output Worked well in practice (but brute-force attacks now)Efficient to encrypt, decrypt Not provably secureImprovementsTriple DES, AES (Rijndael)Block cipher modes (for DES, AES, …)ECB – Electronic Code Book modeDivide plaintext into blocksEncrypt each block independently, with same keyCBC – Cipher Block ChainingXOR each block with encryption of previous blockUse initialization vector IV for first blockOFB – Output Feedback ModeIterate encryption of IV to produce stream cipherCFB – Cipher Feedback ModeOutput block yi = input xi encyrptK(yi-1)Electronic Code Book (ECB)PlainPlain Text Textt CipCiphe r Tex her TBlock CipherBlock CipherBlock CipherBlock CipherProblem: Identical blocks encrypted identicallyCipher Block Chaining (CBC)PlainPlain Text Textt CipCiphe r Tex her TBlock
View Full Document
Unlocking...