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.