Cryptography - 02 Cryptography PDF

02 Cryptography Definition of Cryptography The term cryptography meant originally hidden writing old greek κρυπτός: hidden, γράφειν: write) Nowadays, encryption renders the contents of a message unaccessible for outsiders DEPARTMENT...

02 Cryptography Definition of Cryptography The term cryptography meant originally hidden writing old greek κρυπτός: hidden, γράφειν: write) Nowadays, encryption renders the contents of a message unaccessible for outsiders DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 3 Basics Plaintext M Ciphertext C Key k DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 4 Basics plaintext M ciphertext C Hi Bob! Hi Bob! UnyybObo! Alice Bob key k DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 5 Goals of Cryptography Cryptography has three main goals confidentiality when communicating over an insecure medium, e.g. the internet integrity of messages authentication of communication partners DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 6 Kerckhoffs' Principle A cryptographic system has to be...... indecipherable... secure, even if everything about it, except for the secret key k, is publicly known !! Do not rely on security through obscurity !! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 7 Algorithms Cryptography Classic Modern Characters → ← Bits / Ciphers Ciphers Numbers Transposition Substitution- Symmetric Asymmetric Ciphers Ciphers Ciphers Ciphers ↑ ↑ ↑ ↑ Reordering of Replacement of Same Key for Different Keys for Characters Characters Encryption and Encryption and Decryption Decryption DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 8 Transposition Ciphers: Skytale M : Leather strip wrapped around the wooden staff C : Leather strip without the staff k: Wooden staff with specific diameter DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 9 Substitution Ciphers Two different types of substitution ciphers exist monoalphabetic substitution ciphers polyalphabetic substitution ciphers DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 10 Substitution Ciphers: Caesar Cipher The Caesar Cipher is a monoalphabetic substitution cipher Plaintext and ciphertext use the latin alphabet Both alphabets are shifted against each other Example: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z J K L M N O P Q R S T U V W X Y Z A B C D E F G H I HELLO becomes QNUUX DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 11 Substitution Ciphers: Vigenère Cipher The Vigenère Cipher is a polyalphabetic substitution cipher Based on the latin alphabet A keyword determines the ciphertext alphabets Example: Keyword: UM A B C D E F G H I J K L M N O P Q R S T U V W X Y Z U V W X Y Z A B C D E F G H I J K L M N O P Q R S T M N O P Q R S T U V W X Y Z A B C D E F G H I J K L HELLO becomes BQFXI DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 12 Symmetric Ciphers Symmetric Ciphers use the same key for encryption and decryption Distinction between block ciphers and stream ciphers Low computational costs How to transport the symmetric key? DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 13 Symmetric Ciphers Alice Bob writes reads Hello Bob, how are you? This is my secret know Hello Bob, how are you? This is my secret message: message: … … … … … … encrypts decrypts ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL@K$HA OIW&*FYA)JHRLAIHF(A@YAGFIAGFKAJSFKAU insecure ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL@K$HA OIW&*FYA)JHRLAIHF(A@YAGFIAGFKAJSFKAU GSFASKJGFKAJSGFKAJSGFAKSGFKAJSGF*(@ GIA@UFBAI&@FGA medium GSFASKJGFKAJSGFKAJSGFAKSGFKAJSGF*(@ GIA@UFBAI&@FGA DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 14 Symmetric Ciphers Two Types of symmetric ciphers exist... Block Ciphers The plaintext is chunked into blocks of equal size, possibly filling the last block with zeros Each block is encrypted using the same key Stream Ciphers The plaintext is encrypted bitwise, using a key stream The key stream has the same length as the plaintext DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 15 Symmetric Ciphers: Block Ciphers Several modes of operation for block ciphers available, e.g. EBC and CBC. Electronic Codebook Mode (ECB) Every block is handled separately ci = mi ⊙ k Easy to attack, as same blocks of the plaintext are encrypted identically Cipher Block Chaining (CBC) Every block is linked to the previous block ci = (mi ⊕ ci−1 ) ⊙ k, c0 = r Harder to attack, as blocks cannot be treated separately anymore DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 16 Symmetric Ciphers: Block Ciphers Example: ECB vs. CBC Original ECB CBC DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 17 Diffie-Hellman Key Exchange Invented by Whitfield Diffie and Martin Hellman in 1976 Alice choses a prime p, a generator g of Zp , and a random value x Alice computes A = g mod p and sends Bob (p, g, A) x Bob choses a random value y, computes B = g mod p, and sends Alice y (B) (x∗y) Alice computes K = B mod p = g x mod p (y∗x) Bob computes K = A mod p = g y mod p DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 18 Diffie-Hellman Key Exchange Example Alice choses p = 13, g = 2, and x = 5 5 Alice computes A = 2 mod 13 = 6 and sends Bob (13, 2, 6) 8 Bob choses y = 8, computes B = 2 mod 13 = 9, and sends Alice (9) 5 Alice computes K = 9 mod 13 = 3 8 Bob computes K = 6 mod 13 = 3 DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 19 Diffie-Hellman Key Exchange Does the Diffie-Hellman Key Exchange solve the key distribution problem? 2 Still need to create n keys for n people Computations over groups can be expensive Vulnerable to a Man-in-the-Middle attack DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 20 Asymmetric Ciphers Asymmetric Ciphers use different keys for encryption and decryption Two keys make up a key pair, consisting of...... a private key for decryption... a public key for encryption High computational costs Key distributions is easy DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 21 Asymmetric Ciphers Alice Bob writes publishes knows reads Hello Bob, how are you? This is my secret Hello Bob, how are you? This is my secret message: message: … … public private … … … … encrypts decrypts iInsecure ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL @K$HAOIW&*FYA)JHRLAIHF(A@YAGFI @K$HAOIW&*FYA)JHRLAIHF(A@YAGFI AGFKAJSFKAUGSFASKJGFKAJSGFKAJ AGFKAJSFKAUGSFASKJGFKAJSGFKAJ SGFAKSGFKAJSGF*(@GIA@UFBAI&@F GA Medium SGFAKSGFKAJSGF*(@GIA@UFBAI&@F GA DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 22 Asymmetric Ciphers: RSA The most commonly used asymmetric cipher is the RSA algorithm Invented in 1977 at MIT by Ron Rivest, Adi Shamir and Leonard Adleman Based on the factorization of large primes DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 23 Asymmetric Ciphers: RSA Key Pair Private Key: (d, N) Public Key: (e, N) Encryption: C = M mod N, M < N e Decryption: M = C mod N d DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 24 Asymmetric Ciphers: RSA Key Generation Alice chooses two prime numbers p and q such that p ≠q Alice computes N = p ∗ q and φ(N) = (p − 1) ∗ (q − 1) Alice chooses e such that e is coprime to φ(N) and 1 < e < φ(N) Alice computes d such that e ∗ d ≡ 1 (mod φ(N)) Alice publishes (e, N) and keeps (d, N) secret at all costs DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 25 Asymmetric Ciphers: RSA Key Generation: Example Alice chooses p = 11 and q = 13 = 11 ∗ 13 = 143 and Alice computes N φ(143) = (11 − 1) ∗ (13 − 1) = 120 Alice chooses e = 23 Alice computes d = 47 (23 ∗ 47 − 9 ∗ 120 = 1) Alice publishes (23, 143) and keeps (47, 143) secret DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 26 Asymmetric Ciphers: RSA Encryption and Decryption: Example Encryption Given: (e, N) = (23, 143), M = 97 (a) 23 Compute: C = M mod N = 97 e mod 143 = 102 Decryption Given: (d, N) = (47, 143), C = 102 (a) 47 Compute: M = C mod N = 102 d mod 143 = 97 DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 27 Asymmetric Ciphers: RSA Why does it work? (1 / 3) Euler's Theorem states that a φ(N) ≡ 1 (mod N) if a and N are coprime (without proof) Combining encryption and decryption gives M mod N = M e∗d mod N Since e ∗ d ≡ 1 mod φ(N), a k must exists such that k ∗ φ(N) + 1 = e ∗ d Thus, it holds that M e∗d mod N = M k∗φ(N)+1 mod N DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 28 Asymmetric Ciphers: RSA Why does it work? (2 / 3) Applying the rules of modular arithmetic gives k M k∗φ(N)+1 mod N = M ∗ M φ(N) mod N If M and N are coprime, Euler's Theorem gives φ(N )k M ∗M mod N = M ∗ 1 mod N k If M and N are not coprime (only the case if either p or q is a divisor of M ), it can be shown that the equation still holds DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 29 Asymmetric Ciphers: RSA Why does it work? (3 / 3) Assume w.o.l.g. that p ∣ M and q ∤ M Then, M ∗ (M ) q−1 k∗(p−1) ≡ M (mod q) Generally, if a ≡ b mod k, then k ∣ (a − b) Thus, q ∣ M ∗ (M ) q−1 k∗(p−1) −M Since p ∣ M , also p ∗ q ∣ M ∗ (M ) q−1 k∗(p−1) − M holds Thus, M ∗ (M ) q−1 k∗(p−1) ≡ M (mod p ∗ oq) DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 30 Digital Signatures A digital signature can be used to verify the...... sender of the message... integrity of the message DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 31 Digital Signatures Requirements to a digital signature: Only the real sender of the message can create a digital signature The signature can be verified by the recipient of the message A digital signature belongs to exactly one message and is only valid for that message DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 32 Message Digests Message digests compress the input to an ouput of fixed length No keys are involved Properties of a message digest: one-wayness: its hard to find the input for a given output collision resistance: finding two inputs that lead to the same output is difficult DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 33 Message Authentication Codes Workflows Signature Alice computes a message digest for her plaintext Alice encrypts the digest with her private key Verification Bob decrypts the digest using Alice's public key Bob computes a message digest for the plaintext using the same algorithm as Alice Bob compares the decrypted digest and the digest he computed himself DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 34 Message Authentication Codes Alice Bob reads writes Hello Bob, how are you? This is my secret Hello Bob, how are you? This is my secret message: message: … … … … public … … private hashes hashes FA03141C compares FA03141C FA03141C encrypts insecure decrypts ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL medium ASDIQ@$LANLSD)(@I$ALSAYS(D*UQL @K$HAOIW&*FYA)JHRLAIHF(A@YAGFI @K$HAOIW&*FYA)JHRLAIHF(A@YAGFI AGFKAJSFKAUGSFASKJGFKAJSGFKAJ AGFKAJSFKAUGSFASKJGFKAJSGFKAJ SGFAKSGFKAJSGF*(@GIA@UFBAI&@F SGFAKSGFKAJSGF*(@GIA@UFBAI&@F GA GA DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 35 Hybrid Ciphers Hybrid ciphers are a combination of symmetric and asymmetric ciphers The rather short key of a symmetric cipher is encrypted using an asymmetric cipher The following communication is encrypted symmetrically Examples: HTTPS (SSL / TLS) Mail encryption... DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 36 Hybrid Ciphers: SSL DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 37 Cryptography in Practice In general, using cryptography is easy! A lot of crypto libraries are available: Java: JCA, Bouncy Castle C/C++: Botan, Crypto++, OpenSSL C#: SSC, Bouncy Castle... However... DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 38 Cryptography in Practice Examples for obsolete cryptography: Symmetric Ciphers DES: Broken, don't use! Blowfish: Broken, don't use! Message Digests MD5: Broken, don't use! SHA-1: Broken, don't use! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 42 Cryptography in Practice Instead, use the following: AES as a symmetric cipher RSA as an asymmetric cipher SHA-3 as a message digest DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 43 Cryptography in Practice Use a good source for randomness! Built-in generators /dev/random /dev/urandom java.security.SecureRandom Use generators from libraries! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 45 Theory of Cryptography In general, secure means that an attacker can not derive any information about the plaintext when a ciphertext is known. DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 49 Theory of Cryptography Consider the following cryptographic game: (Alice generates a public key ka and sends it to Bob, so that Bob can encrypt plaintexts himself) Bob sends two messages m0 and m1 to Alice Alice picks a random bit b, computes cb = E(mb , ka ) and sends cb to Bob Bob tries to guess b while knowing cb If Bob has an advantage in this game by knowing cb (and ka ), the used cipher is not semantically secure DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 50 Theory of Cryptography Please Note: !! No deterministic asymmetric cryptographic system is semantically secure !! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 51 Theory of Cryptography In general, four types of attacks can be distinguished: Ciphertext-only: Only ciphertexts are known Known-plaintext: Pairs of plaintext and ciphertext are known Chosen-plaintext: Similar to known-plaintext, but the attacker can chose which plaintexts are encrypted Chosen-ciphertext: Similar to chosen-plaintext, but the attacker can retrieve the plaintext to arbitrary ciphertexts DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 52 Theory of Cryptography Generally, a cryptographic system is semantically secure if it has a property called IND-CPA IND-CPA: indistinguishability under chosen plaintext attack The equivalence of IND-CPA and semantic security was proposed by Shafi Goldwasser and Silvio Micali in 1982 DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 53 Final Remarks Does cryptography even exist? Actually, we don't know! Cryptography implies P ≠ NP , but P ≠ NP should not imply crypto! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 54 Basics of Elliptic Curves An elliptic curve is NOT a mathematical function, but a set of points satisfying 2 3 a certain equation, e.g. y = x + ax + b It looks as follows: Simple Elliptic Curve : https://commons.wikimedia.org/wiki/File:Elliptic_curve_simple.svg DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 56 Basics of Elliptic Curves More generally, an elliptic curve is...... a set of points satisfying an equation with two variables (x, y) where x has degree three and y has degree two... symmetric to the X-axis... cut by a non-horizontal line exactly one or three times DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 57 Computations on Elliptic Curves An operation ⊕ can be defined on an elliptic curve as follows: 1. Draw a straight line through two points A and B. This line will intersect the ′ curve at exactly one more point C ′ 2. At point C draw a vertical line. It will hit the curve at exactly one other point C 3. It holds that A ⊕ B =C DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 58 Computations on Elliptic Curves A visual example: B A Operation ⊕ on an Elliptic Curve DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 59 Computations on Elliptic Curves A visual example: C' B A Operation ⊕ on an Elliptic Curve DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 60 Computations on Elliptic Curves A visual example: C' B A C Operation ⊕ on an Elliptic Curve DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 61 Computations on Elliptic Curves There are a few more things to know about computations on elliptic curves: For a point P = (xp , yp ) its negative −P is defined as −P = (xp , −yp ) The neutral element O of ⊕ is called point at infinity and the following equations hold: O+O = O P +O = P P + (−P ) = O DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 62 Computations on Elliptic Curves The operation P ⊕ Q = R can be defined mathematically as follows: y q −y p λ= xq −xp 2 xr = λ − xp − xq yr = λ(xp − xr ) − yp DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 63 Computations on Elliptic Curves 2 Doubling a point (computing P ⊕ P = P ) works in the same manner with a slight modification to λ: 3∗ +a 2 xp λ= 2 ∗ yo DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 64 Security of Elliptic Curves It turns out that computing P n = C is rather easy, but finding n when only P and C are known is hard. This is basically the same as computing a discrete logarithm over an elliptic curve. That can be used in different ciphers, e.g. the ElGamal cryptosystem. DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 65