Published on January 5, 2008
INLS 187: INLS 187 September 30, 2004 Cryptography Cryptography: Cryptography Greek kryptós (hidden) and gráphien (to write) The study of ways to hide or obscure information, making it unreadable without secret knowledge An interdisciplinary subject Before computers, linguistics dominated the crypto field. Today, it is mathematics, number theory, statistics, computational complexity, and finite mathematics. Engineering is also a majore contributor. Cipher or Cypher?: Cipher or Cypher? A cryptographic algorithm is called a cipher, which is the mathematical function used for encryption and decryption. A (secret) "code" is also often used synonymously with "cipher“ The term has a specialised technical meaning: codes are a method for classical cryptography, substituting larger units of text, typically words or phrases (e.g., "apple pie" replaces "attack at dawn"). In contrast, classical ciphers usually substitute or rearrange individual letters (e.g., "attack at dawn" becomes "buubdl bu ebxo" by substitution.). The secret information in a code is specified in a codebook. "Cipher" is alternatively spelt "cypher"; similarly "ciphertext" and "cyphertext", and so forth. Both spellings have long histories in English, and there is occasional tension between their adherents. Eras: Eras Two distinct eras of cryptography: Pre-computer “classical” Post-computer “modern” Classic Era: Classic Era Long and colorful history Secret writing—types of shorthand or letter substitution (Crypto-Gram in newspaper) Early mechanical devices—rotor machines, Enigma (used by the Germans in WWII) One-time pads—also used extensively in WWII era Photo of Enigma machine: Photo of Enigma machine Modern Era: Modern Era Digital computers heralded the modern era Operates on binary strings, not alphabets Extensive academic research Became more “open” in the 1970s when DES and RSA were published Has been a mainstream technology ever since Users of cryptography: Users of cryptography Formerly the realm of spies, military leaders and diplomats Has become much more widespread as technology has democratized secrecy Still a ways to go before it is common—technological and political hurdles to get over Associated fields: Associated fields Cryptanalysis – code breaking Cryptology – overall name for both cryptography & cryptanalysis Steganography – study of information hiding & watermarking Terminology: Terminology Sender Receiver Cipher Encryption (encipher, if using ISO 7498-2 terminology) Decryption (decipher, as above—”crypt” refers to dead bodies) Plaintext Ciphertext Authentication Symmetric key cryptography Public key (asymmetric) cryptography One-time pads Strength Snake Oil Quantum cryptography Moore’s Law Encryption and Decryption: Encryption and Decryption Plaintext Encryption Decryption ciphertext Original Plaintext Sender Receiver Notation: Notation Sorry, I have to do this… E(M) = C (encrypting message = ciphertext) D(C) = M (decrypting ciphertext = message) D(E(M)) = M (just shorthand) Encryption and decryption using a Key: Encryption and decryption using a Key Plaintext Encryption Decryption ciphertext Original Plaintext Sender Receiver Key Key New notation: New notation EK(M) = C DK(C) = M So DK EK(M) = M (symmetric) Sometimes, two keys are used (public key) EK1(M) = C DK2(C) = M Thus, DK2 EK1(M) = M Cryptanalysis: Cryptanalysis Keeping the plaintext secret is the whole point of cryptography Those who wish to reveal the plaintext: Adversaries, attackers, interceptors, interlopers, intruders, opponents, “the enemy” Cryptanalysis is the science of recovering a plaintext without knowing the key (but an attack could recover the key or the plaintext) Cryptanalysis: Cryptanalysis Four types of cryptanalytic attacks: Ciphertext-only—have access only to ciphertext of several messages Known-plaintext (brute force)—cryptanalyst has access to ciphertext and plaintext of several messages (get someone to encrypt a message for you) Chosen-plaintext attack—cryptanalyst can select a message, know it, and see the ciphertext Adaptive-chosen-plaintext attack—ability to modify #3 based on results of previous efforts. More Cryptanalysis: More Cryptanalysis Chosen-ciphertext attack – ability to choose different ciphertexts to be decrypted with access to decrypted plaintext. Imagine a tamper-proof box that does automatic decryption and having to deduce the key. Chose-key attack—cryptanalyst has some knowledge about the relationship(s) between different keys. Very obscure, but can be used against flawed ciphers. Rubber-hose attack—threats, blackmail, or torture used to obtain a key. Bribery is a “purchase-key” attack. Very low-tech and highly successful. Protocols: Protocols Protocols solve real-world problems Key distribution/exchange is a major issue—public key protocols have resolved this Digital signatures Multiple key public cryptography Secret sharing Zero-knowledge proofs Blind signatures Simultaneous signing Simultaneous exchange of secrets Secure voting Digital cash Algorithms: Algorithms XOR (exclusive or logical operation) DES (old DoD standard) RSA (Rivest, Shamir, Adleman) Diffie-Helman Pohlig-Helman Rabin ElGamal AES (new Dod standard) Rijandael (promising newcomer) LOKI IDEA One-way hashes One-Way functions: One-Way functions Central to public-key cryptography Easy to compute, harder to reverse, given x, easy to do f(x), but with f(x) you can’t get back to x Breaking a plate is a good example of a one-way function No mathematical evidence they exist or can be constructed We have many that no one has been able to reverse though Not useful by themselves—no way to decrypt Solve problems for us—digital signatures, MD5 hashes, and fingerprints Key Length: Key Length Security = strength of algorithm + length of key Key of 8 bits has 28 or 256 possible combinations. Trivial to break even without a computer (50% chance of finding the key after 128 tries) Every bit you add doubles the number of possible combinations. Key Length Cont.: Key Length Cont. Assuming a key of 56 bits, there are 256 possible combinations. If a supercomputer can try 1,000,000 keys a second, it would take 2285 years to find the correct key. A 64-bit key would take 585,000 years. 128 bits requires 1025 years. The universe is somewhere around 1010 years old. Cluster and grid computers are much faster than 1M keys/s these days So how did DES get beat?: So how did DES get beat? The previous examples assumed a perfect algorithm. We have nothing close to that. DES had algorithmic weaknesses that allowed for a more systematic approach than brute force. The security of a cryptosystem should rest in the key, not in the secrecy of the algorithm. Perfect-looking cryptosystems are often extremely weak. Strong cryptosystems with a few minor changes can become weak. Be wary of new algorithms, and walk away from secret ones. Brute force DES machine cost $1M in 1993, can be done with a Beowulf cluster for much less than that now. How long should my key be?: How long should my key be? No single answer, sorry How long does the data need to be secure? A few seconds? A few years? Forever? Many considerations—time it takes to perform the encryption/decryption operations is #2 consideration Key Length Guidelines: Key Length Guidelines Last key length slide: Last key length slide It’s hard to predict future computing power Current hardware performs fast enough to allow much longer key lengths—the examples we did on the listserv had 1792 bit keys, some werer 1028, 2048, etc. If the algorithm is strong, then these key lengths should provide good security Choosing Algorithms: Choosing Algorithms Depends on the application Encrypting streams of data in real-time has different requirements than encryption files on your local computer Time Key length Machine overhead Will it be exported? Laws become a factor, if so NSA has huge resources—who are you trying to secure against? Choosing algorithms: Choosing algorithms Which is better, symmetric key crypto or public key crypto? Kind of a dumb question—each was created to solve different kinds of problems Symmetric—best for data on your hard drive Public—good for messages Prime Numbers: Prime Numbers We always hear about prime numbers when talking about crypto A prime is an integer greater than 1 whose only factors are 1 and itself Examples: 73, 2521, 2365347734339, 2756839 – 1 What role do large primes play? Primes help generate strong keys Key Management: Key Management PKI—Public key infrastructure Keyservers What if someone gets a hold of your private key? Well, that’s why you have a passphrase to protect it! Symmetric keys must be passed face to face or use a trusted courier Man-in-the-middle attacks Authentication: Authentication I will cover this in another class when I talk about Identification Systems Quantum cryptography: Quantum cryptography Fiber optic communications channels make it possible to create sound channels that cannot be intercepted Quantum mechanical principles will alert recipient that the channel has been compromised Quantum computers: Quantum computers A whole different issue than quantum cryptography Relies on Einstein’s wave-particle duality—a photon can exist in a number of states Measuring a photon causes it to behave like a particle If quantum computers can be built, they will be able to brute force keys at astounding rates because they can try many combinations simultaneously It is entirely possible that cryptography as a field will not survive quantum computers Regulation: Regulation US heavily regulates exportation of cryptographic systems, software, and algorithms—considered a “munition” Everyone has it anyways Illegal in many countries—France prohibits use of crypto (people still use it) Steganography Example: Steganography Example Demo Easy to see differences when using a hex editor to look at the files Steganography is not just limited to images—could use any kind of file such as an MP3, would sound like noise Also—secret inks, tiny pin punctures, micro-dots, differences in handwritten words,number of words in paragraphs, errant marks on documents, grilles covering the message except for a few characters Neal Stephenson on crypto: Neal Stephenson on crypto At the 10th Computers, Freedom and Privacy Conference Without a sociopolitical context, cryptography is not going to protect you. He singled out PGP for criticism, saying that relying on the encryption scheme is like trying to protect your house with a fence consisting of a single, very tall picket. A slide showed the lone picket rising into the sky, a bird considering it with bulging eyes. Zimmerman’s response: Zimmerman’s response After Stephenson’s speech, Zimmermann put up his hand, and Stephenson called on him. It's clear Zimmermann had "gotten" the speech. He didn’t go so far as to endorse anything like "social structures," communities of trust, neighborhoods of understanding. Zimmermann had been staunchly against laws, rules, regulations: anything that could be considered a form of social coercion. But he admits that perhaps code is not enough. A few more ideas: A few more ideas The conference went completely off the rails after that. Whitfield Diffie said: "Crypto was a security technique that didn't require trusting anyone else. Now it turns out you have to trust other people." He was younger, he seems to say, he had ideas, he was wrong. "I had a very mathematical and very inapplicable idea about authentication." More ideas: More ideas My personal take is that the conference was invaded by leftists—it became a huge hate-fest against corporations, which was in vogue at the time. One need only look to EU regulations to see that they have utterly failed to protect individuals.