11CSE 380Computer Operating SystemsInstructor: Insup Lee and Dianna XuUniversity of PennsylvaniaFall 2003Lecture Note: Security2Prefaceq Early (unix systems) securityß Security by obscurityß Those that know enough to break the system also know enoughnot toq RTMß The Great Internet Worm of 1988ß Devastating watershed event in hacker historyß First awareness of internet securityq Legendary literatures:ß Hackers – Steven Levyß Cyberpunk – Hafner and Markoffß The Cuckoo’s Egg – Clifford Stollß The Jargon File3Hackers vs Crackersq The word hack doesn’t have 69 different meaningsß an appropriate application of ingenuityß a creative/brilliant practical jokeq Legendary hacks are revered as urban folkloresß The element of clevernessß A flare for classic hacker’s humor and style, which includesreferences to Adams, Tolkien as well as jargonsß Mostly harmlessß Caltech/MIT football pranksß Robin Hood/Friar Tuck against Xeroxq There is no cure against bored students4Robin Hood/Friar Tuck!X id1id1: Friar Tuck... I am under attack! Pray save me!id1: Off (aborted)id2: Fear not, friend Robin! I shall rout the Sheriff of Nottingham's men!id1: Thank you, my good fellow!25Terminologyq Vulnerability (weakness/defects that can be exploited)ß Ill-chosen passwordsß Software bugsß Communication without encryptionß Incorrect set-upsq Attack (ways of exploiting vulnerability)ß Password crackersß Viruses and wormsß Denial of serviceq Intruders (adversaries that try to attack)ß Terroristsß Espionageß Hackers6Security Goalsq Data Confidentialityß Keep data and communication secretß Privacy of personal financial/health records etcß Military and commercial relevanceq Data Integrityß Protect reliability of data against tamperingß Can we be sure of the source and content of information?q System Availabilityß Data/resources should be accessible when neededß Protection against denial of service attacks7Sample Toolsq Cryptographyß Can ensure confidentiality and integrityß Typically used for authenticationq Firewalls, passwords, access controlß Authorization mechanismsq Operating systemsß Resource allocationß Monitoring and logging for auditsq Java bytecode verifierß Memory safety against malicious/defective codeWe do not have adequate technology today!8BasicsTerminologyß Authentication: Verifying identity of sender and/or message integrityß Integrity: Message tampering detectionß Plaintext: Original messageß Ciphertext: Encrypted messageß Key: Input for en- and decryption algorithmß Encryption: Plaintext + Key → Ciphertextß Decryption: Ciphertext + Key → Plaintext39Basic Set-up of CryptographyRelationship between the plaintext and the ciphertext10Encryption AlgorithmsSymmetricß Encryption and decryption use the same keyß Key must be secret (secret key)ß Best known: DES, AES, IDEA, Blowfish, RC5Asymmetricß Also known as Public Key Encryptionß Encryption and decryption keys differentDES – Data Encryption Standard, IDEA – International Data Encryption Algorithm, AES – Advanced Encryption System11Symmetric EncryptionAliceBobEncryption DecryptionSharedkeyConfidentialitySharedkeyOut of band key exchange12q Classical way of encoding text strings (Caesar Cipher)q Permutation of the alphabet (rot13)q The key for decoding is the inverse permutationq Encoding and decoding are efficientq Theoretically sound: the number of permutations of ASCII alphabet isVERY large (128!), and an intruder cannot possibly try out allpossible permutations to decipherq Main problem: Any human language has distinct frequent letter (e.g.vowels) combosß E.g. e is the most common letter in English text, th is the most commonsequence of adjacent symbolsß Given enough cipher text, one doesn’t need to be Shelock Holmes tobreak the codeMonoalphabetic Ciphers413q Sender and receiver share the secret keyq This is also called symmetric key cryptographyq A popular scheme for many years: DES (Data EncryptionStandard) promoted by NSAß Key is 56 bits (extended to 64 bits using 8 parity bits)ß Input data is processed in chunks of 64-bit blocks, by subjectingto a series of transformations using the keyq Distribution of keys is a problemSecret-Key Cryptography14Asymmetric Encryptionq Two complementary keysß Private key (kept secret)ß Public key (published)q Private key VERY difficult to compute from public keyq Encryption with one key can only be reversed withthe other keyq Used in PGP (Pretty Good Privacy) &PKI (Public Key Infrastructure)q Best known RSA & ECC, DSA for signaturesRSA Rivest Shami Adleman, ECC – Eliptic Curve Cryptography, DSA – Digital Signature Algorithm15One-Way Functionsq Function such that given formula for f(x)ß easy to evaluate y = f(x) given xq But given yß computationally infeasible to find xq There is a rich theory of one-way functionsß Many candidates proposedß None of them “proved” to be one wayß Existence of one-way functions linked to encryption, randomnumber generators, (and other crypto concepts) in a precisesense16Asymmetric Encryption cont’dAliceBobEncryption DecryptionBobPublicBobPrivateEncryption DecryptionAlicePrivateAlicePublicConfidentialityAuthentication & Integrity517Public-Key Cryptographyq All users pick a public key/private key pairß publish the public keyß private key not publishedq Public key is the encryption keyß To send a message to user Alice, encrypt the message withAlice’s public keyq Private key is the decryption keyß Alice decrypts the ciphertext with its private keyq Popular schemes (1970s): Diffie-Hellman, RSA18More on RSAq Introduced by Rivest, Shamir, and Adleman in 1979q Foundations in number theory and computational difficulty of factoringq Not mathematically proven to be unbreakable, but has withstood attacksand analysisß Ideally, we would like to prove a theorem saying “if intruder does not knowthe key, then it cannot construct plaintext from the ciphertext by executing apolynomial-time algorithm”q Public and private keys are derived from secretly chosen large primenumbers (512 bits)q Plaintext is viewed as a large binary number and encryption isexponentiation in modulo arithmeticq Intruder will have to factor large numbers (and there are no knownpolynomial-time algorithms for this)ß 2002’s major result: polynomial-time test to check if a number is prime19Hash Functionsq Produce hash values for data access or securityqHash value: Number generated from a string of textq Hash is