Computer Science CSC/ECE 574 By Dr. Peng Ning 1 CSC/ECE 574 Computer and Network Security Topic 2. Introduction to Cryptography Computer Science Outline • Basic Crypto Concepts and Definitions • Some Early (Breakable) Cryptosystems • “Key” Issues CSC/ECE 574 2 By Dr. Peng Ning Computer Science CSC/ECE 574 3 Basic Concepts and Definitions By Dr. Peng Ning Computer Science Cryptography • Cryptography: the art of secret writing • Converts data into unintelligible (random-looking) form – Must be reversible (can recover original data without loss or modification) • Not the same as compression – n bits in, n bits out – Can be combined with compression • What’s the right order? CSC/ECE 574 4 By Dr. Peng Ning Computer Science CSC/ECE 574 5 Cryptography vs. Steganography • Cryptography conceals the contents of communication between two parties • Anonymous communication conceals who is communicating • Steganography (hiding in plain sight) conceals the very existence of communication – Examples? By Dr. Peng Ning Computer Science CSC/ECE 574 By Dr. Peng Ning 6 plaintext encryption ciphertext decryption plaintext key key Encryption/Decryption • Plaintext: a message in its original form • Ciphertext: a message in the transformed, unrecognized form • Encryption: the process that transforms a plaintext into a ciphertext • Decryption: the process that transforms a ciphertext to the corresponding plaintext • Key: the value used to control encryption/decryption.Computer Science Cryptanalysis • “code breaking”, “attacking the cipher” • Difficulty depends on – sophistication of the cipher – amount of information available to the code breaker • Any cipher can be broken by exhaustive trials, but rarely practical – When can you recognize if you have succeeded? CSC/ECE 574 7 By Dr. Peng Ning Computer Science Ciphertext Only Attacks • Ex.: attacker can intercept encrypted communications, nothing else – when is this realistic? • Breaking the cipher: analyze patterns in the ciphertext – provides clues about the encryption method/key CSC/ECE 574 8 By Dr. Peng Ning Computer Science Known Plaintext Attacks • Ex.: attacker intercepts encrypted text, but also has access to some of the corresponding plaintext (definite advantage) – When is this realistic? • Makes some codes (e.g., mono-alphabetic ciphers) very easy to break CSC/ECE 574 9 By Dr. Peng Ning Computer Science Chosen Plaintext Attacks • Ex.: attacker can choose any plaintext desired, and intercept the corresponding ciphertext – When is this realistic? • Allows targeted code breaking (choose exactly the messages that will reveal the most about the cipher) CSC/ECE 574 10 By Dr. Peng Ning Computer Science Chosen Ciphertext Attacks • Ex.: attacker can present any ciphertext desired to the cipher, and get the corresponding plaintext – When is this realistic? • Isn’t this the goal of cryptanalysis??? CSC/ECE 574 11 By Dr. Peng Ning Computer Science CSC/ECE 574 12 The “Weakest Link” in Security • Cryptography is rarely the weakest link • Weaker links – Implementation of cipher – Distribution or protection of keys By Dr. Peng NingComputer Science Perfectly Secure Ciphers 1. Ciphertext does not reveal any information about which plaintexts are more likely to have produced it – i.e., the cipher is robust against chosen ciphertext attacks and 2. Plaintext does not reveal any information about which ciphertexts are more likely to be produced – i.e, the cipher is robust against chosen plaintext attacks CSC/ECE 574 13 By Dr. Peng Ning Computer Science Computationally Secure Ciphers 1. The cost of breaking the cipher quickly exceeds the value of the encrypted information and/or 2. The time required to break the cipher exceeds the useful lifetime of the information • Under the assumption there is not a faster / cheaper way to break the cipher, waiting to be discovered CSC/ECE 574 14 By Dr. Peng Ning Computer Science CSC/ECE 574 By Dr. Peng Ning 15 Secret Keys v.s. Secret Algorithms • Security by obscurity – We can achieve better security if we keep the algorithms secret – Hard to keep secret if used widely – Reverse engineering, social engineering • Publish the algorithms – Security of the algorithms depends on the secrecy of the keys – Less unknown vulnerability if all the smart (good) people in the world are examine the algorithms Computer Science CSC/ECE 574 By Dr. Peng Ning 16 Secret Keys v.s. Secret Algorithms (Cont’d) • Commercial world – Published – Wide review, trust • Military – Keep algorithms secret – Avoid giving enemy good ideas – Military has access to the public domain knowledge anyway. Computer Science CSC/ECE 574 17 Some Early Ciphers By Dr. Peng Ning Computer Science CSC/ECE 574 18 Caesar Cipher • Replace each letter with the one 3 letters later in the alphabet – ex.: plaintext CAT ciphertext FDW A B C D E F G H I J K … A B C D E F G H I J K … plaintext alphabet ciphertext alphabet Trivial to break By Dr. Peng NingComputer Science CSC/ECE 574 19 “Captain Midnight Secret Decoder” Ring • Replace each letter by one that is δ positions later, where δ is selectable (i.e., δ is the key) – example: IBM HAL (for δ=25) • Also trivial to break with modern computers (only 26 possibilities) A B C D E F G H I J K … A B C D E F G H I J K … … … plaintext alphabet ciphertext alphabet By Dr. Peng Ning Computer Science CSC/ECE 574 20 Mono-Alphabetic Ciphers • Generalized substitution cipher: an arbitrary (but fixed) mapping of one letter to another – 26! (≈ 4.0*1026 ≈ 288) possibilities • The key must specify which permutation; how many bits does that take? A B C D E F G H I J K … A B C D E F G H I J K … plaintext alphabet ciphertext alphabet By Dr. Peng Ning Computer Science Attacking Mono-Alphabetic Ciphers • Broken by statistical analysis of letter, word, and phrase frequencies of the language • Frequency of single letters in English language, taken from a large corpus of text: CSC/ECE 574 21 By Dr. Peng Ning Computer Science Attacking… (Cont’d) • If all
View Full Document