--title Introduction to Cryptographic Systems --date today --author Tim Laurence --newpage What is Cryptography? --header --header What is Cryptography? --- --boldon Dictionary.com --boldoff The science or study of the techniques of secret writing, especially code and cipher systems, methods, and the like. --- It is the application of technologies that allow one to control information. - --newpage Why I am qualified? --header --header Why I am qualified? --- * I am not! --- * I use it a lot --- * I will talking about parts in general, not specifics --- * The goal in not to teach you how to build systems with crypto components, it is to understand systems with crypto components - --newpage What I am going to cover --header --header What I am going to cover Background Material Digests Encryption Historic Symmetric Public Key Signatures - --newpage Background Material --header --header Background Material - --newpage Introducing our cast of characters --header --header Introducing our cast of characters Alice Bob --- Eve - Eavesdropper Mallory - Malicious attacker Trent - Trusted party - --newpage Terms --header --header Terms * (K)ey - AKA password * (P)laintext - AKA our message * (C)iphertext * Random * Pseudo random number generator - --newpage exclusive or, XOR --header --header exclusive or, XOR --- A easily reversible way of mixing two things, such as a plaintext and key --- 1 XOR 1 = 0 0 XOR 1 = 1 1 XOR 0 = 1 0 XOR 0 = 0 --- key stream XOR message = ciphertext --newpage exclusive XOR with something else --header --header exclusive XOR K P C K P C 1 XOR 1 = 0 1 XOR ? = 0 0 XOR 1 = 1 -> 0 XOR ? = 1 1 XOR 0 = 1 1 XOR ? = 1 0 XOR 0 = 0 0 XOR ? = 0 --- K C ? K C P 1 XOR 0 = ? 1 XOR 0 = 1 0 XOR 1 = ? -> 0 XOR 1 = 1 1 XOR 1 = ? 1 XOR 1 = 0 0 XOR 0 = ? 0 XOR 0 = 0 key stream XOR ciphertext = plaintext - --newpage What are digests? --header --header Digests What are digests? --- Constant output size - --newpage Checksums --header --header Checksums --- * Detect changes in data * Alice -> Bob, did it arrive undamaged/unchanged? - --newpage Simple checksum example --header --header Simple checksum example Add digits together and only keep remainder (A + ...N) % 10 % = modulo operator --- (1 + 9) % 10 = 0 (1 + 2 + 4 + 8) % 10 = 5 (1 + 4 + 2 + 8) % 10 = 5 --- Oh no, the messages are not the same ad = da - --newpage --header --header Fancier checksums Positionally dependent checksums come to the rescue! (1^1 + 2^2 + 4^3 + 8^4) = 4165 % 10 = 5 (1^1 + 4^2 + 2^3 + 8^4) = 4121 % 10 = 1 - --newpage Checksum Analysis --header --header Checksum Analysis Pros: Cheap and easy way to confirm data is not corrupted Cons: Checksums increase the amount of data you need to communicate --- Checksums are everywhere ---- CRC or CRC32, Cyclic redundancy check ---- IP packet headers & TCP data and headers ---- Credit cards - Luhn formula checksum ---- SIN - --newpage --header --header Hashes What are hashes --- * Checksums optimized to use a full data-space --- * Data can be clumpy. Look at your phone book --- * The small sections are easy to search but the large sections are expensive to search --- * Hashes spread the data out more evenly so you can search more quickly --- Why do we care? - --newpage --header --header Cryptographic Hashes --- * Large data-space --- * One way function, difficult to create desired output (aka collision) --- * Data-space is very uniformly used - --newpage --header --header Example of Cryptographic Hashes $ echo 1 | md5sum b026324c6904b2a9cb4b88d6d61c81d1 - $ echo 2 | md5sum 26ab0db90d72e28ad0ba1e22ee510510 - $ cat /usr/share/dict/words | md5sum c6b99275b5bbcd737714f9fb5c854e31 - $ - --newpage Real world hash example, how UNIX passwords are stored --header --header Real world hash example, how UNIX passwords are stored H(password)=hash --- People are bad at choosing good passwords! --- Rainbow tables --- Add salt H(password . salt) = hash shadow file entry = salt . hash - --newpage Another example, HMACsto someone --header --header Another example, HMACs What if you want to prove you sent a message? Hashed Message Authentication Code, HMAC --- It mixes a hash with a password H( (K XOR leftPad) . H((K XOR rightPad) . P) ) - --newpage Another example --header --header Another example Alice and Bob share a lot in common including a key Alice writes a letter to Bob asking "Will you marry me" She worries Bob's son, Mallory, hates her and wants to set Bob against her At the end of the letter she calculates a hash of the letter mixing in their shared key, making a HMAC When Bob receives the letter he verifies he gets the same HMAC If not, the letter has been changed - --newpage Cryptographic Hash Analysis --header --header Cryptographic Hash Analysis Pros: Bob and Alice can be sure that Mallory didn't change the message Alice and Bob can confirm they are looking at the same letter without having to transmit the whole letter Cons: Mallory can still read the letter Mallory could change the letter, this would cause a HMAC failure. This would prevent Alice and Bob from communicating With HMACs Alice and Bob still have to find a way to come up with a shared key --- You may have seen SHA1, SHA256, MD5 - --newpage Let's talk about encryption --header --header Let's talk about encryption Combine a method, plaintext, with a key Results in Ciphertext E(P,K) = C D(C,K) = P --- Historic Ciphers - --newpage Caesar Cipher --header --header Caesar Cipher --- Rotate letters --- Key is the number of spaces to rotate --- Caesar(ABC , 1) = BCD Caesar(ABC , 2) = CDE Caesar(ABC , 13) = NOP, also know as ROT13 --- ABCDEFGHIJKLMNOPQRSTUVWXYZ NOPQRSTUVWXYZABCDEFGHIJKLM HI -> UV UV -> HI - --newpage Caesar Weaknesses --header --header Caesar Weaknesses Frequency Analysis ETAON --- Known text Dear Bob --- Brute force guessing - --newpage --header --header One Time Pad Mix randomness with the plaintext --- Encryption: 1 2 3 4 5 6 7 8 9 0<-plaintext ROT 1 1 8 5 7 3 0 0 3 9<-key = 2 3 1 9 2 9 7 8 2 9<-ciphertext --- Decryption: 1 1 8 5 7 3 0 0 3 9<-key ROT 2 3 1 9 2 9 7 8 2 9<-ciphertext = 1 2 3 4 5 6 7 8 9 0<-plaintext - --newpage --header --header OTP guessing Encryption: ROT 1 1 8 5 7 3 0 0 3 9<-key 1 2 3 4 5 6 7 8 9 0<-plaintext = 2 3 1 9 2 9 7 8 2 9<-ciphertext Decryption: 2 3 1 9 2 9 7 8 2 9<-ciphertext ROT 2 4 3 2 6 4 3 5 0 8<-guessed key = 0 9 8 7 6 5 4 3 2 1<-guessed plaintext - --newpage OTP Analysis --header --header OTP Analysis Pros: Perfect encryption No way for attacker to prove they know the key Cons: Key must be perfectly random Key must be as long as message Key may not be reused - --newpage Modern Symmetric Ciphers --header --header Modern Symmetric Ciphers Stream and Block Cheap and fast to perform - --newpage --header --header Stream Ciphers Pseudo random number generator F(Position,K) = key stream Simulates a OTP - --newpage --header --header Example of a Stream Cipher F(1,K)=2, F(2,K)=8, F(3,K)=3 ,F(4,K)=4 XOR 2 8 3 4 A B C D = s z p p --- XOR 2 8 3 4 = A B C D - --newpage --header --header Block Ciphers There is a static size work unit, or block, they operate on Input is padded up to next work unit size They perform operations that reorder bit and change bits Very complex relationship between plaintext and ciphertext - --newpage --header --header Symmetric Cipher Analysis Pros: They are very easy to implement They are very fast Cons: Repeated plaintext blocks in block ciphers results in repeated ciphertext blocks - --newpage --header --header Block Encryption modes of operation Electronic Code Book, ECB E(P block, K) = Block of C --- Identical Blocks return identical results - --newpage --header --header Chain Block Cipher mode, CBC Every block of plaintext is mixed with the previous block of ciphertext E(P block XOR previous C block, K) = Block of Ciphertext --- Can't decrypt anything after a missing block - --newpage --header --header Cipher Feedback mode, CFB Every block is mixed with encrypted previous block Can perform RANDOM access E(previous C block, K) XOR P block = Block of Ciphertext - --newpage --header --header Output Feedback mode Create a stream by performing CBC on F(previous F(),K) Mix this with P to make C E(previous F(), K) XOR P block = Block of Ciphertext No random access Acts like a stream cipher - --newpage --header --header Counter mode, CTR E(counter,K) XOR P = C Can be done in parallel Acts like a Stream Cipher Random access Requires a strong block cipher --- $ echo 1 | openssl aes-256-ecb -K abc | hexdump -C 00000000 98 2b 58 79 17 83 02 ce a5 0f 23 79 19 e6 4c 88 |.+Xy......#y..L.| 00000010 $ echo 2 | openssl aes-256-ecb -K abc | hexdump -C 00000000 25 5e ca ce 59 0a d3 fe 6f 27 aa 87 e0 95 22 26 |%^..Y...o'...."&| 00000010 - --newpage --header --header Public Key Crypto E(P,K1) = C D(C,K1) != P D(C,K2) = P E(P,K2) = C D(C,K1) = P --- private key public key - --newpage Public keys in the real world --header --header Public keys in the real world Alice and Bob again want to communicate. Alice and Bob exchange public keys in a secure manner Alice encrypts her plaintext with Bob's public key. Alice sends the ciphertext to Bob Bob decrypts the ciphertext with his private key to recover plaintext --- What prevents Mallory from sending a message as Bob? --- Alice encrypts her plaintext with Bob's public key. Alice then encrypts that ciphertext with her private key Alice sends the double encrypted ciphertext to Bob Bob decrypts the ciphertext with Alice's public key Bob decrypts the ciphertext with his private key to recover plaintext - --newpage Public Key Analysis --header --header Public Key Analysis --- Public key is very slow to perform --- There are mathematical relationships between the keys Keys need to be much larger since they only sparsely populate their data space --- Alice and Bob still need to exchange keys. What keeps Mallory from performing mischief --- Introduce Trent --- They both trust Trent and have his public key They send their public key to Trent Now they both can Trent for the others' public key - --newpage --header --header This is my message! I want to make sure no-one can claim I wrote something I want to make sure I can prove I wrote something Signatures --- Now digital signatures Hash the plain text, encrypt the result with your private key, and append to plaintext Creating: E( H(P) , Private K) Verifying: D( Signature, Public K) = H(P) - --newpage Let's bring all together --header --header Let's bring all together Secure Sockets Layer, SSL Actually it is called Transport Layer Security, TLS, now - --newpage First things first, we need some public keys --header --header First things first, we need some public keys Remember Trent? We now call him Certificate authority, CA. Verisign, Thawte, DigiCert, GoDaddy, etc All of these organizations have "root" certificates in your computer What is a certificate? Public key Identification information Date constraints Now we know the CA's public key. We can verify the CA trusts someone else I am glossing over lots of options and details here - --newpage --header --header Negotiation phase: * A client sends a ClientHello message The highest TLS protocol version it supports A random number A list of encryption algorithms it supports The compression methods it supports. * The server responds with a ServerHello message Chosen protocol version A random number Chosen encryption algorithm Chosen compression method A session ID. * The server sends its Certificate * The server sends a ServerHelloDone message - --newpage --header --header Key Exchange phase: * The client sends a ClientKeyExchange message PreMasterSecret which is encrypted using the public key of the server --- * The client and server then use the random numbers and PreMasterSecret to compute the "master secret". ---- * The client now sends a ChangeCipherSpec record telling the server Everything I tell you from now on will be authenticated and encrypted. --- * The client sends an encrypted Finished message, containing a hash of all previous messages. --- * The server decrypts the client's message and verifies the hash --- * Finally, the server sends a ChangeCipherSpec Everything I tell you from now on will be authenticated and encrypted. --- * The server sends its authenticated and encrypted Finished message. --- * The client performs the same decryption and verification. - --newpage Application phase --header --header Application phase Headers Data Packets Control packets - --newpage Conclusion --header --header Conclusion There is much more to learn Wikipedia has a lot of very good pages These are tools Care must be taken to use the right tool in the right way Secuity is formed through review and concensus Good luck, have fun, but leave the designing to the experts - --header --header Questions?