This preview shows page 1-2-3-4-5-6-7-8-55-56-57-58-59-60-61-62-111-112-113-114-115-116-117-118 out of 118 pages.
University of Washington CSEP 590TU – Practical Aspects of Modern CryptographyNew Lecture ScheduleSlide 3Communications Engineers Coat of ArmsSymmetric EncryptionWhy go Ugly?Ugly IIUgly IIISuite B - Computation CostAdversaries and their DiscontentsAdversariesCipher RequirementsPractical AttacksSome Formal Attack RequirementsSecurity In PracticeBlock CipherBlock Ciphers: ModesStream Cipher – Definition and ExampleThe “Manual” CiphersGroup Theory in Cryptography - 1Group Theory in Cryptography - 2TranspositionsBreaking Completely filled Columnar TranspositionAnagrammingAlphabetic SubstitutionEt Tu Brute?: SubstitutionsAttacks on Monoalphabetic SubstitutionPolygraphic FrequenciesLetter Frequency Bar GraphSlide 30Shifted Letter Frequency Bar GraphVigenere Multialphabetic CipherConstructing Vig AlphabetsSolving VigenereStatistical Tests for Alphabet IdentificationReview of Attacks on PolyalphabetPolygraphic SubstitutionHill CipherBreaking HillInformation Theory MotivationInformation TheoryInformation Theory in CryptographySlide 43Slide 44Equivocation and Bayes TheoremSome Information Theory TheoremsUnicity and Random CiphersUnicity for Random CiphersUnicity Distance for MonoalphabetApplication: One Time Pads are “unbreakable”Information Theoretic Estimates to break monoalphabetMixing cryptographic elements to produce strong cipherThe “Machine” CiphersJefferson CipherEnigmaGroup Theory for RotorsDiagrammatic Enigma StructureMilitary EnigmaEnigma DataMilitary Enigma Key LengthMethod of BatonsGerman Key Management before 5/40Changes German use of EnigmaPolish (Rejewski) AttackHow Rejewski did itHow Rejewski did it (continued)How Rejewski did it (conclusion)How Rejewski did it (postscript)Digital Block CiphersData Encryption StandardHorst Feistel: LuciferFrom Lucifer to DESIterated Feistel CipherFeistel RoundDES Round FunctionChaining Feistel RoundsFeistel Ciphers defeat simple attacksDESDES RoundSlide 80Slide 81Slide 82DES Described AlgebraicallyDES Key ScheduleSlide 85Slide 86DES DataSlide 88S Boxes as Polynomials over GF(2)Slide 90HomeworkSlide 92Cryptographic HashesObservations on Cryptographic HashesObservationsWhat are Hash Functions Good for?Slide 97One-Way FunctionsChaum-vanHeijst-Pfitzmann Compression FunctionMerkle/Damgard ConstructionA Cryptographic Hash: SHA-1Slide 102PaddingTechnique for CHs from Block CiphersBirthday AttacksAttacks on Cryptographic HashesMACs using HashesWinnowing and Chaffing (Rivest)Homework 1-Question 1Homework 1-Question 1 (addendum)Homework 1-Question 2Homework 1-Question 3Homework 1-Question 4Homework 1-Question 5 (Extra Credit)Homework 1-Question 5 (cont)General Modern ReferencesSlide 117End PaperJLM 20060107 22:16 1University of WashingtonCSEP 590TU – Practical Aspects of Modern CryptographyInstructors: Josh Benaloh, Brian LaMacchia, John ManferdelliTuesdays: 6:30-9:30, Allen Center 305Webpage: http://www.cs.washington.edu/education/courses/csep590/06wi/Recommended texts: Stinson, Cryptography, Theory and Practice. 2nd Edition, CRC Press, 2002.Menezes, vanOrtshot, Vanstone. Handbook of Applied Cryptography.Ferguson and Schneier, Practical Cryptography.JLM 20060107 22:16 2New Lecture ScheduleDate Topic Lecturer1 1/3 Practical Aspects of Cryptography Josh2 1/10 Symmetric Key Ciphers and Hashes John3 1/17 Public Key Ciphers Josh4 1/24 Cryptographic Protocols I Brian5 1/31 Cryptographic Protocols II Brian6 2/7 Security of Block Ciphers John7 2/14 AES and Cryptographic Hashes John8 2/21 Trust, PKI, Key Management [Last HW Assignment)Brian9 3/1 Random Numbers/Elliptic Curve Crypto Josh10 3/8 Three topics: Elections, ITAR/Politics, Side Channels/Timing Attacks, DRM, BigNum ImplementationAllJLM 20060107 22:16 3Symmetric Key Cryptographyand Cryptographic Hashes - IJohn [email protected]@microsoft.comPortions © 2004-2005, John Manferdelli. This material is provided without warranty of any kind including, without limitation, warranty of non-infringement or suitability for any purpose. This material is not guaranteed to be error free and is intended for instructional use only.JLM 20060107 22:16 4Communications Engineers Coat of ArmsPlaintext (P)Noisy insecurechannelCompress(to save space)The SourceSender: AliceThe SinkReceiver:BobPlaintext(P)Encrypt(for confidentiality)Encode(to correct errors)Noisy insecurechannelDecompress(to save space)Decrypt(for confidentiality)Decode(to correct errors)JLM 20060107 22:16 5Symmetric Encryption•Symmetric Key cryptographic algorithms use a secret known to the authorized parties called a “key”. Encryption and Decryption use the same key.–The transformations are simple and fast enough for practical use and implementation.– “Keyspace” large enough to protect against exhaustive search.–The encryption algorithm must be efficiently invertible.–Two major types: Stream ciphers and Block ciphersKey (k)Ciphertext (C)Encrypt Ek(P)Plaintext (P)Key (k)Plaintext (P)Decrypt Dk(P)Ciphertext (C)JLM 20060107 22:16 6Why go Ugly? Algorithm SpeedRSA-1024 Encrypt .32 ms/op (128B), 384 KB/secRSA-1024 Decrypt 10.32 ms/op (128B), 13 KB/secAES-128.53 s/op (16B), 30MB/secRC4.016 s/op (1B), 63 MB/secDES.622 s/op (8B), 12.87 MB/secRSA implementation uses CRT, Karasuba and Montgomery. Timings do not include setup. All results are for an 850MHz x86.JLM 20060107 22:16 7Ugly IIAlgorithm SpeedSHA-1 48.46 MB/secSHA-256 24.75 MB/secSHA-512 8.25 MB/secTimings do not include setup. All results are for an 850MHz x86.JLM 20060107 22:16 8Ugly IIISymmetric KeySizeRSA/DH Key SizeElliptic Curve Key Size80 1024 160112 2048 224128 3072 256192 8192 384256 15360 521JLM 20060107 22:16 9Suite B - Computation CostSymmetric Key Size Ratio RSA/DH:EC80 3:1112 6:1128 10:1192 32:1256 64:1JLM 20060107 22:16 10Adversaries and their DiscontentsEvePlaintext (P)ChannelEncryptDecryptAliceBobPlaintext(P)Wiretap AdversaryMan in the Middle AdversaryMalloryPlaintext (P)Encrypt DecryptAliceBobPlaintext(P)ChannelJLM 20060107 22:16 11Adversaries•Cryptography is computing/communicating in the presence of an Adversary•An Adversary’s strength is characterized by:–Computational resources available to the adversary:–Exponential time/memory–Polynomial time/memory–Nature of access to cryptographically protected data: –Probable plaintext attacks–Known plaintext/ciphertext attacks–Chosen plaintext attacks–Adaptive interactive chosen plaintext attacks (oracle model) –Physical
View Full Document
Unlocking...