Share
Embed
CSCD27 Modern Cryptography
ThierrySans
September 22, 2016
Transcript
45 slides
-
Design principles (reminder) 1. Kerkoff Principle The security of a
cryptosystem must not rely on keeping the algorithm secret 2. Diffusion Mixing-up symbols 3. Confusion Replacing a symbol with another 4. Randomization Repeated encryptions of the same text are different -
Functional Requirements E D ➡ The same key k is
used for encryption E and decryption D 1. Dk(Ek(m))=m for every k, Ek is an injection with inverse Dk 2. Ek(m) is easy to compute (either polynomial or linear) 3. Dk(c) is easy to compute (either polynomial or linear) 4. c = Ek(m) finding m is hard without k (exponential) -
Outline Stream cipher RC4 - Rivest Cipher 4 Block cipher
• Encryption standards DES (and 3DES) - Data Encryption Standard AES - Advanced Encryption Standard • Block cipher mode of operations -
Vernham Cipher - a modern version of Vigenere Use ⊕
to combine the message and the key Ek(m) = k ⊕ m Dk(c) = k ⊕ c Problem : known-plaintext attack Dk(Ek(m)) = k ⊕ (k ⊕ m) = m so k = (k ⊕ m) ⊕ m x ⊕ x = 0 x ⊕ 0 = x -
Mauborgne Cipher - an improve version of Vernham Use a
random stream as encryption key ➡ Defeats the know-plaintext attack Problem : Key-reused attack C1 = k ⊕ m1 C2 = k ⊕ m2 so C1 ⊕ C2 = (k ⊕ m1 ) ⊕ (k ⊕ m2 ) = (m1⊕ m2 ) ⊕ 0 = (m1⊕ m2 ) x ⊕ x = 0 x ⊕ 0 = x -
MS Word and Excel 2003 used the same key to
re-encrypt documents after editing changes -
Random Number Generator True Random Number Generator ➡ No, because
we want to be able to encrypt and decrypt Pseudo-Random Generator ➡ Stretch a a fixed-size seed to obtain an unbounded random sequence -
Stream cipher Can we use k as a seed? Ek(m)
= m ⊕ RNG(k) ➡ key reused attack ! Typical usage : choose a new s and send it using another encryption scheme E’ Ek(m) = (E’k(s) , m ⊕ RNG(s)) -
RC4 - Rivest Cipher 4 Key Size 40 - 2048
bits Speed ~ 8 cycles / byte Very simple implementation (lab 3 and assignment 1) -
DES - Data Encryption Standard Timeline • 1972 NBS call
for proposals • 1974 IBM Lucifer proposal analyzed by DOD and enhanced by NSA • 1976 adopted as standard • 2004 NIST withdraws the standard Block size 64 bits Key Size 56 bits Speed ~ 50 cycles per byte Algorithm 16 round Feistel Network -
Feistel Network Li = Ri-1 Ri = Li-1 ⊕ Fi(Ri-1,ki)
Properties: • F is an arbitrary function that scrambles the input based on a key • F is not necessary invertible • A Feistel Network is invertible ➡ Achieves confusion and diffusion “Cryptography and Network Security” by William Stalllings -
Security of DES - DES Challenges (brute force contests)
1998 Deep Crack, the EFF's DES cracking machine used 1,856 custom chips • Speed : matter of days • Cost : $250,000 2006 COPACOBANA, the COst-optimized Parallel COdeBreaker used 120 FCPGAs • Speed : less than 24h • Cost : $10,000 -
How about 2DES ? 2DESk1,k2 (m) = Ek2 (Ek1 (m))
Meet-in-the-middle attack - known-plaintext attack 1. Brute force Ek1 (m) and save results in a table called TE (256 entries) 2. Brute force Dk2 (c) and save results in a table called TD (256 entries) 3. Match the two tables together to get the key candidates ➡ The more plaintext you know, the lesser key candidates ➡ Effective key-length is 57 bits ➡ This attacks applies to every encryption algorithm used as such -
3DES (Triple DES) 3DESk1,k2,k3(m) = Ek3(Dk2(Ek1(m))) ➡ Effective key length
: 112 bits ✓ Very popular, used in PGP, TLS (SSL) … ๏ But terribly slow -
AES - Advanced Encryption Standard Timeline • 1996 NIST issues
public call for proposal • 1998 15 algorithms selected • 2001 winners were announced -
Rijindael by J. Daemen and V. Rijmen Adopted by the
NIST in December 2001 Block size 128 bits Key Size 128, 192, 256 bits Speed ~18-20 cycles / byte Mathematical Foundation Galois Fields Implementation • Basic operations : ⊕, + , shift • Small code : 98k -
Encryption Modes a.k.a. how to encrypt long messages ECB -
Electronic Code Book CBC - Cipher Block Chaining CFB - Cipher Feedback OFB - Output Feedback CTR - Counter -
ECB - Electronic Code Book Each plaintext block is encrypted
independently with the key ✓ Block can be encrypted in parallel ๏ The same block is encrypted to the same ciphertext -
CBC - Cipher Block Chaining Introduce some randomness using the
previous ciphertext block ✓ Repeating plaintext blocks are not exposed in the ciphertext ๏ No parallelism ➡ The Initialization Vector should not be known by the opponent and must be send separately (ECB mode for instance) -
CTR - Counter Introduce some randomness using a counter ✓
High entropy and parallelism ๏ Sensitive to key-reused attack ➡ Popular usage : IPsec (coming soon in this course) -
Stream cipher and block cipher are often used together •
Stream cipher for encrypting large volume of data • Block cipher for encrypting fresh pseudo-random seeds Stream Cipher Block Cipher Approach Encrypt one symbol of plaintext directly into a symbol of ciphertext Encrypt a group of plaintext symbols as one block Pro Fast High diffusion Cons Low diffusion Slow -
How do we agree on the ? The big
challenge with symmetric cryptosystem? E D -
Naive Key Management A1, A2 … A5 want to talk
➡ Each pair needs a key : n (n-1) / 2 keys ➡ Keys must be exchanged physically using a secure channel A1 A2 A3 A4 A5 -
(Better) centralized solution A1, A2 … A5 can talk to
the KDC (Key Distribution Center) ➡ When Ai and Aj want to talk, the KDC can generate a new key and distribute it to them ➡ We still have n keys to distribute somehow ➡ The KDC must be trusted ➡ The KDC is a single point of failure A1 A2 A3 A4 A5 -
Public key approach Each Ai has a pair (Kp, Ks)
and Kp is made public ➡ … details coming later ➡ This is how the web work ! A1 - Ks1 A2 - Ks2 A3 - Ks3 A4 - Ks4 A5 - Ks5 A1 - Kp1 A2 - Kp2 A3 - Kp3 A4 - Kp4 A5 - Kp5 -
Functional Requirements E D ➡ The public key Kp for
encryption ➡ The private key Ks for decryption 1. Dks(Ekp(m))=m for every pair (Kp, Ks) 2. Ekp(m) is easy to compute (either polynomial or linear) 3. Dks(C) is easy to compute (either polynomial or linear) 4. p = Dks(C) finding m is hard without Ks (exponential) 5. Generating a pair (Kp, Ks) is easy to compute (polynomial) 6. Finding a matching key Ks for a given Kp is hard (exponential) Kp Ks -
RSA - Rivest, Shamir and Alderman Key Size 1024 -
4096 Speed ~ factor of 106 cycles / operation Mathematical Foundation Prime number theory -
Number Theory - Prime numbers Prime Numbers • p is
prime if 1 and p are its only divisors e.g 3, 5, 7, 11 … • p and q are relatively prime (a.k.a. coprime) if gcd(p,q) = 1 e.g gcd(4,5) = 1 ➡ There are infinitely many primes Eurler-Fermat Theorem If n = p . q and z = (p-1).(q-1) and a such that a and n are relative primes Then az ≡ 1 (mod n) -
Computational Complexity Easy problems with prime numbers • Generating a
prime number p • Addition, multiplication, exponentiation • inversion, solving linear equations Hard problem with prime numbers • Factoring primes e.g. given n find p and q such that n = p . q -
RSA - generating the key pair 1. Pick p and
q two large prime numbers and calculate n = p . q (see primality tests) 2. Compute z = (p-1).(q-1) 3. Pick a prime number e < z such that e and z are relative primes ➡ (e,n) is the public key 4. Solve the linear equation e * d = 1 ( mod z ) to find d ➡ d is the private key however p and q must be kept secret too -
RSA - encryption and decryption Given Kp = (e, n)
and Ks = d ➡ Encryption : Ekp(m) = me mod n = c ➡ Decryption : Dks(c) = cd mod n = m -
The security of RSA RSA Labs Challenge : factoring primes
set Key length Year Time 140 1999 1 month 155 1999 4 months 160 2003 20 days 200 2005 18 months 768 2009 3 years Challenges are no longer active -
Key length and Key n-bit security • RSA has very
long keys, 1024, 2048 and 4096 are common • Is it more secure than asymmetric crypto with key lengths of 56, 128, 192, 256 ? ➡ Key lengths do not compare ! RSA Key length Effective key length 1,024 80 2,048 112 3,072 128 7,680 192 15,360 256 -
Asymmetric vs Symmetric The best of both worlds ➡ Use
RSA to encrypt a shared key ➡ Use AES to encrypt message E(m) = RSAKp(k), AESk(m) Symmetric Asymmetric pro Fast No key agreement cons Key agreement Very slow