Asymmetric Cryptography PDF

Asymmetric Cryptography SIO João Paulo Barraca Asymmetric (Block) Ciphers Use key pairs ꟷ One private key: personal, not transmittable ꟷ One public key: available to all Allow ꟷ Confidentiality without any previous exchange of secrets ꟷ Authentication Of contents (...

Asymmetric Cryptography SIO João Paulo Barraca Asymmetric (Block) Ciphers Use key pairs ꟷ One private key: personal, not transmittable ꟷ One public key: available to all Allow ꟷ Confidentiality without any previous exchange of secrets ꟷ Authentication Of contents (data integrity) Of the data origin (source authentication, or digital signature) João Paulo Barraca, André Zúquete SIO 2 Operations of an asymmetric cipher Confidentiality Authenticity plaintext plaintext key key pair pair decrypt(private key) encrypt(public key) decrypt(public key) encrypt(private key) ciphertext ciphertext João Paulo Barraca, André Zúquete REVERSE ENGINEERING 3 Use cases: confidential communication Secure communication with a target (Bob) ꟷ Alice encrypts plaintext P with Bob’s public key Kpub_Bob Alice: C = {P}Kpub_Bob ꟷ Bob decrypts cyphertext C with his private key Kprv_Bob Bob: P’= {C}Kprv_Bob ꟷ P' should be equal to P (requires checking using integrity control) ꟷ Kpub_Bob needs to be known by Alice Kpub_Bob Kprv_Bob Alice Bob plaintext encryption ciphertext decryption plaintext João Paulo Barraca, André Zúquete SIO 4 Use cases: authenticated communication Authenticate the communication from Alice ꟷ Alice encrypts plaintext P with her private key Kprv_Alice Alice: C = {P}Kprv_Alice ꟷ Anyone can decrypt cyphertext C with Alices’ Public key Kpub_Alice Anyone: P’= {C}Kpub_Alice ꟷ If P’ = P, then C is Alice’s signature of P ꟷ Kpub_Alice needs to be known by the message verifiers Kprv_Alice Kpub_Alice Alice Anyone plaintext encryption ciphertext decryption plaintext João Paulo Barraca, André Zúquete SIO 5 Asymmetric ciphers Issues Advantages ─ They are a fundamental authentication mechanism ─ They allow to explore features that are not possible with asymmetric ciphers Disadvantages ─ Performance: 2 or 3 orders of magnitude over AES ─ Very inefficient and memory consuming: Large keys Problems ─ Trustworthy distribution of public keys: how to know if the public key is the correct one? ─ Lifetime of key pairs: How to make sure that we can deal with lost/deprecated/leaked keys? João Paulo Barraca, André Zúquete SIO 6 Asymmetric ciphers Overview Approaches: complex mathematic problems ─ Discrete logarithms of large numbers ─ Integer factorization of large numbers Most common algorithms ─ RSA ─ ElGamal ─ Elliptic curves (ECC) Other techniques with asymmetric key pairs ─ Diffie-Hellman (key agreement) João Paulo Barraca, André Zúquete SIO 7 RSA Rivest, Shamir, Adelman, 1978 Keys: Private: (d, n) Public: (e, n) Public key encryption (confidentiality) of P ─ C = Pe mod n ─ P = Cd mod n Private key encryption (authenticity) of P ─ C = Pd mod n P, C are numbers! Message is converted to/from numbers ─ P = Ce mod n 0 ≤ P, C < n João Paulo Barraca, André Zúquete SIO 8 RSA Rivest, Shamir, Adelman, 1978 Computational complexity: Discrete logarithm and Integer factoring Key selection ─ Large n (hundreds or thousands of bits) coprime → gcd(a, b) = 1 ─ n = p × q with p and q being large (secret) prime numbers × → multiplication ─ Chose an e co-prime with (p-1) × (q-1) mod → modulo operation ─ Compute d such that e × d  1 (mod (p-1) × (q-1))  → modular congruence ─ Discard p and q ─ The value of d cannot be computed out of e and n a  b mod n iff rem(a,n) = rem(b,n) Only from p and q João Paulo Barraca, André Zúquete SIO 9 Playing with RSA p=5 q = 11 (prime numbers) ꟷ n = p x q = 55 ꟷ (p-1) x (q-1) = 40 e=3 (public key = e, n) ꟷ Coprime of 40 d = 27 (private key = d, n) ꟷ e x d  1 (mod 40) -> d x e mod 40 = 1 -> (27 x 3) mod 40 = 1 For a message to encrypt, P = 26 (notice that P, C  [0, n-1]) ꟷ C = Pe mod n = 263 mod 55 = 31 ꟷ P = Cd mod n = 3127 mod 55 = 26 João Paulo Barraca, André Zúquete SIO 10 Hybrid Encryption Combines symmetric with asymmetric cryptography ꟷ Use the best of both worlds, while avoiding problems ꟷ Asymmetric cipher: Uses public keys (but it is slow) ꟷ Symmetric cipher: Fast (but with weak key exchange methods) Method: ꟷ Obtain Kpub from the receiver ꟷ Generate a random Ksym ꟷ Calculate C1 = Esym( Ksym, P ) ꟷ Calculate C2 = Easym( Kpub, Ksym ) ꟷ Send C1 + C2 C1 = Text encrypted with symmetric key C2 = Symmetric key encrypted with the receiver public key May also contain the IV João Paulo Barraca, André Zúquete SIO 11 Randomization of asymmetric encryptions RSA is a deterministic algorithm: equal messages result in equal outputs What we need: Non-deterministic result of asymmetric encryptions ꟷ N encryptions of the same value, with the same key, should yield N different results ꟷ Goal: prevent the trial & error discovery of encrypted values Approaches ꟷ Concatenation of value to encrypt with two values ꟷ A fixed one (for integrity control) ꟷ A random one (for randomization) João Paulo Barraca, André Zúquete SIO 12 Randomization of asymmetric encryptions OAEP (Optimal Asymmetric Encryption Padding) iHash: digest over Label seed: random value PS: zeros M: plaintext MGF: Mask Generation Function ─ Similar to Hash, but with variable size João Paulo Barraca, André Zúquete SIO 13 Diffie-Hellman Key Agreement (1976) q (large prime) α (primitive root mod q) a = random b = random Ya = αa mod q Yb = αb mod q Kab = Yba mod q Kba = Yab mod q Kab = Kba Information and Organizational Security 14 João Paulo Barraca, André Zúquete SIO 14 Diffie-Hellman Key Agreement (1976) a = random c = random b = random Ya = αa mod q Yc = αc mod q Ya Yb Yb = αb mod q Yc Yc Kca = Yac mod q Kac = Yca mod q Kcb = Yb mod q c Kbc = Ycb mod q Information and Organizational Security 15 João Paulo Barraca, André Zúquete SIO 15 Elliptic Curve Cryptography (ECC) Elliptic curves are specific functions ꟷ They have a generator (G) ꟷ A private key Kprv is an integer with a maximum of bits allowed by the curve ꟷ A public key Kpub is a point (x,y) = Kprv × G ꟷ Given Kpub, it should be hard to guess Kprv Curves ꟷ NIST curves (15) Other curves P-192, P-224, P-256, P-384, P-521 ◦ Curve25519 (256 bits) B-163, B-233, B-283, B-409, B-571 ◦ Curve448 (448 bits) K-163, K-233, K-283, K-409, K-571 João Paulo Barraca, André Zúquete SIO 16 ECDH: DH with ECC ECC curve → G a = random b = random Ya = a G Yb = b G Kab = a Yb Kba = b Ya Kab = Kba João Paulo Barraca, André Zúquete SIO 17 ECC public key encryption Combines hybrid encryption with ECDH Obtain Kpub_recv from the receiver Generate a random Kprv_send and the corresponding Kpub_send Calculate Ksym = Kprv_send Kpub_recv C = E( P, Ksym ) Send C + Kpub_send Receiver calculates Ksym = Kpub_send Kprv_recv P = D( C, Ksym ) João Paulo Barraca, André Zúquete SIO 18 Digital signatures Encrypt/Decrypt (RSA) Sign/Verify (ElGamal, EC) data data key key pair pair decrypt(public key) encrypt(private key) verify(public key) sign(private key) signature signature João Paulo Barraca, André Zúquete REVERSE ENGINEERING 19 Operations with Private Keys Authenticate the contents of a document ꟷ Ensure its integrity (it was not changed) Authenticate its author ꟷ Ensure the identity of the creator/originator Prevent repudiation of the encrypted payload ꟷ Non-repudiation ꟷ Genuine authors cannot deny authorship Only the identified author could have generated a given payload Because only the author has the private key João Paulo Barraca, André Zúquete SIO 20 Digital signatures Authenticate the contents of a document ꟷ Ensure its integrity (it was not changed) Authenticate its author ꟷ Ensure the identity of the creator/originator Prevent repudiation of signatures ꟷ Non-repudiation property ꟷ Genuine authors cannot deny authorship Only the identified author could have generated a given signature João Paulo Barraca, André Zúquete SIO 21 Practical Considerations Encryption with private key is vital for authentication ꟷ Only the author can make it, everyone can verify it But… sending secure authenticated texts will require two (slow) encryptions ꟷ Remember: Asymmetric ciphers are slow and inefficient Preferred Approach: Encrypt Hash(T), creating Digital Signatures João Paulo Barraca, André Zúquete SIO 22 Digital Signatures Approaches ꟷ Digest function of the Text (only for performance) ꟷ Asymmetric encryption/decryption or signature/verification Signing: Ax(doc) = info + E(Kx-1, digest(doc + info)) Ax(doc) = info + S(Kx-1, digest(doc + info)) info = signing context, signer identity, Kx Verification: D(Kx, Ax(doc))  digest(doc + info) V(Kx, Ax(doc), doc, info) → True / False João Paulo Barraca, André Zúquete SIO 23 Encryption / decryption signatures João Paulo Barraca, André Zúquete wikipedia, http://en.wikipedia.org/wiki/Digital_signature SIO 24  wikipedia, http://en.wikipedia.org/wiki/Digital_signature Encryption / decryption signatures © André Zúquete, João Paulo Barraca Information and Organizational Security 25 SIO Digital Signature on a mail message Multipart content, signature w/ certificate From - Fri Oct 02 15:37:14 2009 […] Date: Fri, 02 Oct 2009 15:35:55 +0100 From: User A MIME-Version: 1.0 To: User B Subject: Teste Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=sha1; boundary="------------ms050405070101010502050101" This is a cryptographically signed message in MIME format. --------------ms050405070101010502050101 Content-Type: multipart/mixed; boundary="------------060802050708070409030504" This is a multi-part message in MIME format. --------------060802050708070409030504 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Corpo do mail --------------060802050708070409030504— --------------ms050405070101010502050101 Content-Type: application/x-pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" Content-Description: S/MIME Cryptographic Signature MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIamTCCBUkwggSyoAMCAQICBAcnIaEwDQYJKoZIhvcNAQEFBQAwdTELMAkGA1UEBhMCVVMxGDAWBgNV […] KoZIhvcNAQEBBQAEgYCofks852BV77NVuww53vSxO1XtI2JhC1CDlu+tcTPoMD1wq5dc5v40Tgsaw0N8dqgVLk8aC/CdGMbRBu+J1LKrcVZa+khnjjtB66HhDRLrjmEGDNttrEjbqvpd2QO2 vxB3iPTlU+vCGXo47e6GyRydqTpbq0r49Zqmx+IJ6Z7iigAAAAAAAA== --------------ms050405070101010502050101-- João Paulo Barraca, André Zúquete SIO 26 Digital Signatures at kernel.org João Paulo Barraca, André Zúquete SIO 27