Bài giảng Cryptography Basics

Cryptography BasicsObjectivesExplain general cryptography conceptsExplain basic hashing concepts.Basic encryption concepts.Explain and implement protocolsExplain core concepts of public key cryptographyCryptographyCryptography – science of encrypting information.“scrambles” (xáo trộn) data so only authorized parties can “unscramble” and read data using two methodsCan substitute – change one letter with a different letter (thay thế)Can transpose – scramble the order of letters, without actually changing one for another. (chuyển vị)The best cryptosystems both substitute and transpose.Basic IdeaCryptographic TerminologyCryptography - a method of storing and transmitting data in a form only intended for authorized parties to read or process.Cryptanalysis (phân tích mật mã) - science of studying, breaking, and reverse engineering algorithms and keys.Encryption (mã hóa)– the method of transforming data (plaintext) into an unreadable format.Plain text (cleartext): dữ liệu gốc – the format (usually readable) of data before being encryptedCipher text (dữ liệu đã được mã hóa) – the “Scrambled” format of data after being encryptedCryptographic TerminologyDecryption (giải mã) – the method of turning cipher text back into plain text Encryption algorithm – a set or rules or procedures that dictates how to encrypt and decrypt data. Also called an encryption “cipher”Key – (crypto variable) a values used in the encryption process to encrypt and decryptCryptographic TerminologyKey space (không gian khóa) – the range of possible values used to construct keysexample: if a key can be 4 digits (0-9) key space = 10,000 (0000 – 9999)if it can be 6 digitskey space = 1,000,000 (000,000 – 999,999)Key Clustering – Instance when two different keys generate the same cipher text from the same plaintextWork factor – estimated time and resources to break a cryptosystemCác mục tiêu của mã hóaconfidentiality/privacy (Tính bí mật)Integrity (Tính toàn vẹn)Authentication (Tính xác thực)non-repudiation (Tính không chối bỏ)Cryptography HistoryRomans used a shift cipher called a “CEASAR” cipher. Shift Ciphers simply shift characters in an alphabet.ROT13 / shift cipher - Transposition (hoán vị) CipherJumbles up the ordering of characters in a message. The Spartans of Greece used a form of this called the “Scytale” Cipher.Transposition CipherScytaleSteganography (ẩn thông tin)Hiding one message in another“Meet the mini me that ate later.”“Meet me later.”Vigenere CipherThe Vigenère cipher is named for Blaise de Vigenère, although Giovan Battista Bellaso had invented the cipher earlier. Vigenère did invent a stronger autokey cipher.Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution.This cipher is well known because while it is easy to understand and implement, it often appears to beginners to be unbreakable. Vigenere Table (tabula recta)Vigenere CipherFor example, suppose that the plaintext to be encrypted is: ATTACKATDAWNThe person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON": LEMONLEMONLEThe first letter of the plaintext, A, is enciphered using the alphabet in row L, which is the first letter of the key. This is done by looking at the letter in row L and column A of the Vigenère square, namely L. The rest of the plaintext is enciphered in a similar fashion.Plaintext: ATTACKATDAWNKey: LEMONLEMONLECiphertext: LXFOPVEFRNHREncryption Modes – BlockTake the message and break it up into fixed sized blocks, encrypt each block using the given key.Block (ECB encryption)Block Encryption ProblemsSolving Block Encryption ProblemsOften with block encryption, we include a value in addition to the key that changes for each block, so we don’t get repetitive cipher text blocks. This is called Cipher Block Chaining (see next slide)Initialization Vectors are used with the first block in CBCCipher Block Chaining CBC (SSL/TLS)Mã hóaGiải mãXORingXORing is a Boolean mathematical “function” which creates an output bit based on two input bits. It outputs a 1 IF and ONLY if one bit of input is 1 and the other is a 0. INPUT1 INPUT 2 XOR OUTPUT--------------------------------------------------------------------------- 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0Stream Encryption (Mã hóa luồng)The “key” is used as a key stream generator, which creates a series of bits each are is mathematically combined with the bit stream of plaintext to produce cipher text. This is done for small pieces of information, or information not in blocks.Keyboard inputMorse codeAny input that arrives one bit or byte at a timeStream EncryptionPlain Text Bit Keystream Bit Output Bit0 1 1 1 1 0 0 1 1 XOR 1 = 0Cipher text = 0Stream EncryptionPlain Text Bit Keystream Bit Output Bit0 1 1 1 1 0 0 XOR 1 = 1 Cipher text = 0 1 Stream EncryptionPlain Text Bit Keystream Bit Output Bit0 1 1 1 1 XOR 0 = 1 Cipher text = 0 1 1Stream EncryptionPlain Text Bit Keystream Bit Output Bit 0 1 1 XOR 1 = 0 Cipher text = 0 1 1 0Stream EncryptionPlain Text Bit Keystream Bit Output Bit 0 XOR 1 = 1 Cipher text = 0 1 1 0 1One Time Pad1011 – plain text0101 – pad------ XOR1110 – cipher textIn a one time pad you use a different key/pad each time you send a message One Time PadA “perfect cryptosystem” Unbreakable if implemented properlyThe key is a series of bits (0 and 1)The plain text is converted to bitsThe message is XORed with the pad/key to generated the cipher text(more)One Time Pad considerationsThe pad must be used only one timeThe pad must be shared by both sides.The pad must be as long as the messageThe pad must be securely distributedThe pad must be used up of truly random valuesSymmetric Encryption (mã hóa đối xứng)Idea same key is used to BOTH encrypt and decrypt data!Symmetric EncryptionCalled Symmetric or “Private Key encryption”Must securely distribute keys to both parties. Chicken in the egg situation with networksAnyone with the key can either encrypt or decryptVery Fast to encrypt or decryptKey Management is the big issueKey Managementn: number of parties who want to securely communicate# keys = (n*(n-1)) / 25 = (5*4)/2 = 10 keys10 = (10*9)/2 = 45 keys100 = (100*99)/2 = 4950 keys1000 = (1000*999)/2 = 499500 keysSymmetric Algorithms – DESData Encryption Standard (1976)Developed from at NIST request for an encryption standardChosen algorithm was called “Lucifer” from IBMBlock CipherFixed sized blocks of 64 bitsKey size 64 bits, effective size is 56 bits16 rounds of substitution and transpositionDES is no longer considered strong enough, can be broken easily with distributed computing.Triple DESNothing but DES 3 times3DES – EEE33DES – EDE33DES – EEE23DES – EDE2Since it’s 3 x DES, 48 rounds of substitution and transposition.AES (Advanced Encryption Standard) - Tiêu chuẩn mã hóa tiên tiếnDeveloped as a replacement to DES, 1998Actual algorithm is called “Rinjdael”Block cipher128 bit blocksKey sizes of 128,192, 256Rounds depend on key size9: for 128 keys11: for 192 keys13: for 256 bit keysRC5Ronald Rivest , 1994Block cipherBlock size 32, 64, 128Key Size up to 2048 bitsRounds up to 255, minimum of 12 recommendedRC6Ron Rivest, Matt Robshaw, Ray Sidney, Yiqun Lisa Yin, 1998Block cipher based on RC5RC6 proper has a block size of 128 bits and supports key sizes of 128, 192 and 256 bitsSame attributes as RC5Developed to be a AES candidateFaster that RC5RC4Stream cipher – what was that again?Was proprietary, but released on Internet in 1994, “ARC4” is the “open version of RC4”Key length 8 – 2048 bitsUsed in SSL (Secure Sockets Layer) and WEP communicationBlowfishBruce Schneier, 1993Block cipher64 bit blocksKeys 32 - 448 bits16 rounds is the “full version”Free algorithmIDEAInternational Data Encryption Algorithm (Thuật toán Mã hóa Dữ liệu Quốc tế)James Massey, Xuejia Lai, 1991Proposed AES candidateBlock cipher64 bit blocks128 bit keysNot free, Patent expires soon thoughUsed in Pretty Good Privacy (PGP 2.0)SymmetricThat’s Symmetric EncryptionUnderstand the concept (shared keys)Understand it’s strengths (fast for bulk encryption and decryption)Understand it’s weaknesses (key management, non-repudiation)Understand the different algorithm “properties” on the slides.Enter Non-Repudiation (Không thoái thác)Non-Repudiation – being able to definitively prove someone said or wrote something.Proves they actually sent a messageProves the message was not alteredHow do we provide non-repudiation? We’ll see soon after we talk about hashes, and asymmetric encryption.Asymmetric EncryptionUse 2 keys, public key to encrypt a message, private key can decryptAsymmetric EncryptionCalled Public key encryptionRequires 2 related keysPublic key – given to anyonePrivate key – kept secretPublic key is used to encrypt messagePrivate key is used to decrypt messagePrivate key is used to sign messagesPublic key is used to validate signed messagesAsymmetric EncryptionKey exchange is simple!Asymmetric Encryption is SLOW, not suitable for encrypting large amounts of dataWhat is a problem with Asymmetric Encryption and key exchange? (MiM)Can be used to “digitally sign” a message (in a few slides)Provides integrityProvides non-repudiationCan anyone see a use to Asymmetric encryption already?* (very important)Diffie-HellmanWhitfield Diffie , Martin Hellman, 1976The original Asymmetric algorithmUsed with SSL, VPNs, sshUsed ONLY for key exchangeGenerates session keys for secure SYMETRIC encryption communicationsAsymmetric Algorithms – RSARon Rivest, Adi Shamir , Len Adleman, 1977, MITCan be 100 times slower than DESCan be used for encryption, key exchange and digital signaturesSecurity based on difficulty of factoring large numbers.Was patented 1983, 4.405.829, has expired 2000El-GamalTaher Elgamal, 1984Encryption or digital signaturesFreeCan be used for encryption, key exchange and digital signaturesSlowBased on / extended Diffie-HellmanECC - Elliptic Curve CryptographyNeal Koblitz, Victor S. Miller, 1985Encryption, key exchange or digital signaturesSecurity based on analyzing elliptic curves in finite fieldsDoes not require much computing overhead as such used in devices with low resources (PDAs, Cell phones etc)*Asymmetric OverviewUses 2 keys, one for encryption, one for decryptionThis mitigates the key management, key distribution problem (kind of)Is VERY slow (orders of magnitude slower)Can provide integrity and proof of sender (non-repudiation)Often used in a hybrid system (along with private key encryption)Encrypt symmetric keys using asymmetric algorithmsActually do large scale encryption with these asymmetric keys!Hashing - BămHashing is similar to encryption but different.Hashing is a one way operation.Take input messagePut through hashing functionRetrieve fixed length value (hash digest)HashingTry for yourself at hashed, no way to get back the original messageHash digests are fixed, so multiple messages theoretically could produce the same hash digest (collision)HashesHashing can provide integrity (assuming no MiM (next slide))Hashes can be combined with a private key to provide protection against MiM attacks (visualization in a few slides next slide)The more bits in the digest, generally the more secure (less change for collisiongenerally)One Example of a hash that you are probably familiar with is called a “CRC”Normal use of HashHash MiM attack (phase 1)Hash MiM attack (phase 2)HMACHash-based Message Authentication CodeHMACfunction hmac (key, message) if (length(key) > blocksize) then key = hash(key) // keys longer than blocksize are shortened end if if (length(key) < blocksize) then key = key ∥ zeroes(blocksize - length(key)) // keys shorter than blocksize are zero-padded end if o_key_pad = [0x5c * blocksize] ⊕ key // Where blocksize is that of the underlying hash function i_key_pad = [0x36 * blocksize] ⊕ key // Where ⊕ is exclusive or (XOR) return hash(o_key_pad ∥ hash(i_key_pad ∥ message)) // Where ∥ is concatenationend functionHash algorithms – SHASecure Hash AlgorithmDesigned/Published by NIST and NSADesigned for use in the DSSModeled after MD4SHA-1 (SHA-160) – 160 bit digest512 bit blocksSHA-256 – 256 bit digest512 bit blocksSHA-384 – 384 bit digest1024 bit blocksSHA-512 – 512 bit digest1024 bit blocksMD2Developed by Ronald Rivest (of RC and RSA fame)Optimized to run on 8 bit computers128 bit digest128 bit blocksMD4Optimized for 32 bit computers128 bit digestCollisions can be found in under 1 minute on a PC ;(MD5Similar to MD4, but more secureSlower and more secure128 bit digest512 bit blocksWas part of the NTLM authentication protocolCollisions in 8 hours on a PCMoving away from, to SHAHash overviewKnow what a hash isConceptFixed length digestWhat is a hash used forKnow what a collision isKnow it’s susceptible to MiMKnow what HMAC is, and what it tries to accomplishBe familiar with MDx, and SHA-xUnderstand that SHA is considered the best algorithmDigital SignaturesDigital SigningDigital SigningGenerally when I digital sign something.. I don’t encrypt the whole message. Instead Run message through hash algorithm, generated message digestSign the “message digest”Send both the original message and the encrypted message digestDigital SigningProvidesIntegrityNon repudiationNOT confidentialityDigital Signing