Distributed Systems Security and Cryptography Concepts 95-702 Distributed Systems 195-702 Distributed Systems 2 Assumptions and Guidelines • Interfaces are exposed – How? • Networks are insecure – How? • Algorithms are available to attackers. – We assume they understand RSA, DES, etc. – Why not keep them secret? • Attackers may have have large resources. – Why? • Limit the lifetime and scope of secrets. • Minimize the trusted base.95-702 Distributed Systems 3 Julius Caesar (shift) cipher • Pick a key (a number) • Shift the letters of the plaintext by the key to create the ciphertext. • E.g. – Plaintext: Yellow cake – Key: 3 – Ciphertext: Bhoorz fdnh Source: http://en.wikipedia.org/wiki/File:Caesar3.svg95-702 Distributed Systems 4 Basic Crypto Terminology: • Is this secret-key or public-key algorithm? • Is this a symmetric or asymmetric algorithm? • Is it vulnerable to brute-force attack? • Is it a block-cipher?95-702 Distributed Systems 5 Block cipher How could you make it a block-cipher? • E.g. Two characters, Key: 1 • cake • 0011000110110011 • 001100101011010095-702 Distributed Systems 6 Block cipher chaining How could you use block-cipher chaining? • Key: 1 • cake • 0011000110110101 • 01000101 - xor • 01000110 - encrypt • 010001101101 - xor • 010001101110 - encrypt95-702 Distributed Systems 7 Block cipher How could you use block-cipher chaining? • Key: 1 • cake • 0011000110110101 • 01000101 - xor • 01000110 - encrypt • 010001101101 - xor • 010001101110 - encrypt • Do the last letter95-702 Distributed Systems 8 Block cipher How could you use block-cipher chaining? • Key: 1 • cake • 0011000110110101 • 01000101 - xor • 01000110 - encrypt • 010001101101 - xor • 010001101110 - encrypt • 0100011011101011 - xor • 0100011011101100 - encryptAdvanced Encryption Standard • Very complex chaining block cipher • Symmetric algorithm • Adopted by US National Institute of Standards – Replaced DES • It is what most browsers use: – https://www.fortify.net/cgi/ssl_2.pl 95-702 Distributed Systems 995-702 Distributed Systems 10 Asymmetric algorithms • Symmetric algorithms require Alice and Bob to share a secret (the key). – Both can encrypt and decrypt messages • Asymmetric algorithms allow for not sharing a secret. – Alice can encode a message for Bob – She cannot decode messages already encoded for Bob95-702 Distributed Systems 11 Symmetric Secret Key Secret Key95-702 Distributed Systems 12 Asymmetric Public Key Private Key Private Key Public Key95-702 Distributed Systems 13 Public Key • Uses asymmetric keys • Single public key – Let the world see • Single private key – You keep secret • Public can: – Encrypt a message for you using the public key – Decrypt a message encrypted with your private key using your public key.95-702 Distributed Systems 14 What doesn’t work • No one can decrypt a message encrypted with your public key with your public key – Only with the private key • You can’t decrypt a message that you encrypted with your private key with your private key – Only with your public key – (You should not be needing to do this)95-702 Distributed Systems 15 Symmetric vs Asymmetric algorithms • Symmetric – Fast – Difficult to distribute keys and and keep them secure • Asymmetric – 100 to 1000 times slower – Can allow for public keys • Best of both worlds, which we will discuss more later: – Use asymmetric keys to exchange symmetric keys at the beginning of a conversation – Symmetric keys will have the lifespan of that conversation – E.g.: SSL, PGP95-702 Distributed Systems 16 Scenario • I want President Obama to be able to send me confidential email messages: – I publish my public key on my web site – He encrypts his email with my public key – Sends it to me • What can Eve see? – Only I can decrypt his email with my private key95-702 Distributed Systems 17 But who sent it? • How do I know the message came from President Obama? • How do I know it wasn’t that sneaky Mallory, pretending to be the President? • How can I be sure that the message is coming from the President?95-702 Distributed Systems 18 Solution • President Obama puts his public key on his web site • He encrypts his message with his private key • He encrypts that encrypted message with my public key • He sends it to me. • What does Eve see? • What do I do? • How do I know it is from President Obama? • If he encrypted it with his private key, why did he need to use my public key? • Could Mallory fake it?RSA • RSA is a commonly used for public key encryption 95-702 Distributed Systems 19The RSA Public-Key Cryptosystem • Developed by Rivest, Shamir, and Aldeman in 1977 95-702 Distributed Systems 20The RSA Public-Key Cryptosystem 1. Select at random two large prime numbers p and q. – These numbers would normally be about 500 digits 2. Compute n by the equation n = pq. 3. Compute φ(n) = (p –1)(q –1) 4. Select a small odd integer e that is relatively prime to φ(n) 95-702 Distributed Systems 2195-702 Distributed Systems 22 φ(n) = (p –1)(q –1) • Called Euler's totient function – (not important here) • What’s interesting is its range: – Equals the number of positive integers less than or equal to n that are coprime to n – E.g. φ(15) = 8 • {1, 2, 4, 7, 8, 11, 13, 14} – So when using big prime numbers, it will also be very big.The RSA Public-Key Cryptosystem 1. Select at random two large prime numbers p and q. – These numbers would normally be about 500 digits 2. Compute n by the equation n = pq. 3. Compute φ(n) = (p –1)(q –1) 4. Select a small odd integer e that is relatively prime to φ(n) 95-702 Distributed Systems 2395-702 Distributed Systems 24 Why small odd integer? • The public key will be – {that integer, n} • Your private key will be – {another integer, n} • The range of your private integer is dependent on φ(n), which is quite large
View Full Document
Unlocking...