1
Introduction to Cryptography
Slide 1
Denition
process data into unintelligible form, reversibly, without data loss typically digitally usually one-to-one in size compression analog cryptography: voice changers, shredder other services: integrity checking: no tampering authentication: not an impostor
plaintext
encryption
ciphertext
decryption
plaintext
Slide 2
Cryptography Caveats
Cannot prove that code is secure assume until otherwise but: can prove (some) systems/protocols secure (assuming secure code) Difcult to explain algorithm securely Cryptographic system = algorithm (published or secret) + secret value (key) Assume Trudy has algorithm
Slide 3
Computational Difculty
algorithm needs to be efcient may use inefcient for short key brute-force cryptanalysis: try all keys until looks like plaintext any scheme can be broken depends on $ = longer key more secure: brute-force cryptanalysis: twice as hard cryptanalysis tools: special-purpose hardware parallel machines Internet coarse-grain parallelism ... Slide 4 encryption:
Secret Key vs. Secret Algorithm
secret algorithm additional hurdle hard to keep secret if widely used: reverse engineering, social engineering commercial: published wide review, trust military: avoid giving enemy good ideas (not just messages)
Slide 5
Trivial Codes
Caesar cipher: substitution cipher: A D, B E
Captain Midnight secret Decoder ring: shift by variable : IBM HAL only 26 possibilities monoalphabetic cipher: generalization arbitrary mapping letter to letter possibilities statistical analysis of letter frequencies larger codebook
Slide 6
Cryptanalysis
Ciphertext only: exhaustive search until recognizable plaintext (unless limited base set) need enough ciphertext Known plaintext: secret may be revealed (by spy, time) pair (ciphertext, plaintext) great for monoalphabetic ciphers Chosen plaintext: choose text, get encrypted useful if limited set of messages or initial strings
Slide 7
Some Large Numbers
Time to next ice age DES 56 bits probability of MD5 collision Age of planet Time until sun goes nova Age of universe Number of atoms in universe 14,000 yrs keys
yrs yrs
yrs
Slide 8
Brute Force Attacks
Number of encryptions/sec: 1 million to 1 billion bits/sec 1999: 56-bit key broken in 22.5 h with 1,800 chips ($250,000) (245 keys/s, see eff.org); helped by distributed.net 1995: 56-bit key broken in 1 week with 120,000 processors ($6.7M) 56-bit key broken in 1 month with 28,000 processors ($1.6M) 64-bit key broken in 1 week with processors ($1.7B) 128-bit key broken in 1 week with
processors
Chinese Lottery: With machines that test at the rate of a million keys every second, take 64 seconds to break DES with a billion such machines running in parallel. Slide 9
DESosaur: With suitable advances in biotechnology, a celled DESosaur can break DES in 0.2 secs.
Slide 10
Types of Cryptography
hash functions: no key secret key cryptography: one key public key cryptography: two keys public, private
Slide 11
Secret Key Cryptography
plaintext encryption key ciphertext decryption plaintext ciphertext
ciphertext
same length as plaintext
symmetric cryptography substitution codes, DES, IDEA
Message transmission: agree on key (how?), communicate over insecure channel Secure storage: crypt dangerous, no indication of trouble, no redundancy Slide 12
Strong Authentication
= prove knowledge of key without revealing it
Fred Alice challenge R1 Bob response {R1} AB challenge R2 response {R2}AB
Fred: obtain chosen plaintext, ciphertext pairs not completely secure!
Integrity check = xed-length checksum for message CRC not sufcient easy to pick new message with same CRC encrypt MIC (message integrity check) Slide 13
Public Key Cryptography
asymmetric cryptography publicly invented in 1975 two keys: private ( ), public ( ) much slower than secret key cryptography
plaintext encryption public key private key ciphertext decryption plaintext ciphertext
Slide 14
Public Key Cryptography
Data transmission: Alice encrypt using decrypt to using
Bob decrypt to using encrypt using
Storage: safety copy: use public key of trusted person Authentication: with
secret keys: need secret key for every person to communicate
secret key: Alice could share key with enemies of Bob need to store no secrets:
Alice encrypt using
Bob decrypt to using
Slide 15
Digital Signatures
encrypt hash
with private key
doesnt reveal text semi-trusted party authorship integrity non-repudiation: cant do with secret-key cryptography
Slide 16
Hash Algorithms
= message digest, one-way transformation length(
length()
usually xed lengths: 48 128 bits easy to compute given
but not , no easy way to nd
computationally infeasible to nd example:
, take middle digits
with
Slide 17
Password Hashing
dont need to know password to verify it store
, with salt
salt makes dictionary attack more difcult compare entry with
password le could be world-readable Unix: non-standard DES, 4096 salt values
Slide 18
10
Message Integrity using Hash
agree on password compute
, send
doesnt require encryption algorithm exportable! virus protection, downline load, Java applets: write-once storage
program with secure program on
Slide 19
