Symmetric Algorithms PDF

Topic 3: Symmetric Ciphers Tin Aung Win [email protected]  At the end of this topic, you will be able to explain: Block and stream symmetric ciphers Learning Block cipher operation modes Outcome Modern symmetric ciphers – DE...

Topic 3: Symmetric Ciphers Tin Aung Win [email protected]  At the end of this topic, you will be able to explain: Block and stream symmetric ciphers Learning Block cipher operation modes Outcome Modern symmetric ciphers – DES and AES The types of Cryptanalysis or attack Symmetric Ciphers Applied Cryptography 2 Symmetric Ciphers Applied Cryptography 3  Symmetric Cipher Types Types of symmetric ciphers Block Stream Ciphers Ciphers Operate on the plaintext in Operate on the plaintext a groups of bits called blocks. single bit or byte at a time. Data must be available before Encrypt as data become the encryption starts. available. eg: Encrypting a file saved on a eg: Encrypt a character typed on storage medium. a keyboard, one at a time. Symmetric Ciphers Applied Cryptography 4 Symmetric Ciphers Applied Cryptography 5  Exclusive OR & Shift Operation on bits – a primer Exclusive Or (XOR) of bits (binary number): ⊕ 1 0 1 0 1 0 1 0 Simple shift operation (such as Caesar or ROT13 cipher) Operation Plaintext bits No. of Shift sequence Ciphertext places Shift Left 0000 1010 3 1. 0001 0100 0101 0000 (Decimal 10, Hex 0A) 2. 0010 1000 (Decimal 80, Hex A0) 3. 0101 0000 Shift right 0101 0000 3 1. 0010 1000 0000 1010 (Decimal 80, Hex A0) 2. 0001 0100 (Decimal 10, Hex 0A) 3. 0000 1010 Symmetric Ciphers Applied Cryptography 6  Stream Ciphers Stream Cipher mode of operation Cryptographic nonce (seed) The stream ciphers use pseudo-random keystream which is generated serially from a random seed value (Key) – such as millisecond of the current time. Key Stream The pseudo-random keystream is XORed with the plaintext in generator a similar fashion to the one-time pad cipher. The original seed value serves as the cryptographic key to regenerate the keystream to decrypt the ciphertext. Key Stream It is most effective in hardware implementation. Key size A stream cipher generally makes use of smaller key sizes such Plaintext ⊕ as 128 bits keys. This differs from a one-time pad, which is more secure. Ciphertext One of the extensively use stream ciphers is RC4. Cryptographic Concepts and Techniques Applied Cryptography 7  Stream Cipher – An example Encryption using XOR ⊕ operation using plaintext and key Plaintext H E L L O ASCII(Binary) 0100 1000 0100 0101 0100 1100 0100 1100 0100 1111 Key (letter A) 0100 0001 0100 0001 0100 0001 0100 0001 0100 0001 Ciphertext = 0000 1001 0000 0100 0000 1101 0000 1101 0000 1110 Plaintext ⊕ Key Decryption using XOR ⊕ operation using plaintext and key Ciphertext 0000 1001 0000 0100 0000 1101 0000 1101 0000 1110 Key (letter A) 0100 0001 0100 0001 0100 0001 0100 0001 0100 0001 Plaintext = 0100 1000 0100 0101 0100 1100 0100 1100 0100 1111 Ciphertext ⊕ Key Plaintext H E L L O To get the plaintext from the ciphertext, just apply XOR again with the same key. Symmetric Ciphers Applied Cryptography 8 Symmetric Ciphers Applied Cryptography 9  Block Ciphers Block ciphers encrypt one block of plaintext after another. The typical block size is 64 or 128 bits. Large enough to preclude analysis, and small enough to be workable. Data to be encrypted must be available beforehand. Eg: Files stored on a disk. Modern block ciphers are product ciphers that use both substitution and transposition methods. Block ciphers are widely used to encrypt large amounts of data. Symmetric Ciphers Applied Cryptography 10  Cipher/Algorithm Modes The cipher (or) algorithm modes below are applicable to different types of block ciphers. Cipher/Algorithm Modes Electronic Cipher Block Cipher Output Codebook Chaining (CBC) Feedback (CFB) Feedback (OFB) (ECB) For the block ciphers only For both block & stream ciphers Symmetric Ciphers Applied Cryptography 11  Encryption and Decryption in ECB Mode Block no. 1 2 n Plaintext (64/128bit) Electronic Codebook Mode (ECB) The plain text is divided into 64/128-bit blocks. Key Block Cipher Example: A 64-bit block of plaintext: DEADLINE Each block is independently encrypted with Ciphertext (64/128bit) the same key. ECB Mode Encryption If plain text blocks repeat, so do the corresponding cipher text blocks. Ciphertext (64/128bit) Patterns in ciphertext may not be well hidden. ECB exhibits weak diffusion. Key Block Cipher ECB was originally designed to encrypt messages that never span more than a single block, such as to encrypt keys to Plaintext (64/128bit) distribute for other operations. ECB Mode Decryption Symmetric Ciphers Applied Cryptography 12  Encryption and Decryption in CBC Mode Plaintext (64/128bit) Cipher Block Chaining Mode (CBC) IV (64/128bit) CBC tries to improve on ECB. Key The encryption of each block is dependent Block Cipher not just on the key but also on the ciphertext of the previous block (except the first block). Ciphertext (64/128bit) The initialisation vector (IV) is introduced to CBC Mode Encryption make each message unique by XORed with the first plaintext block. Ciphertext (64/128bit) IV is a 64-bit block of random bits, also known Key as the cryptographic nonce. Block Cipher An IV is never reused under the same key. IV (64/128bit) Distinct IV produces distinct ciphertexts even if Plaintext the same plaintext is encrypted multiple times. (64/128bit) IV usually does not need to be secret. CBC Mode Decryption Symmetric Ciphers Applied Cryptography 14  Disadvantages of the CBC Mode The encryption in CBC mode cannot be parallelised. CBC mode operates slower than ECB in encryption. Each message includes data from the previous block and hence needs to wait for encryption/decryption of the previous block to be completed first – it is a sequential process. The decryption process however can be mostly parallel. Due to the “chaining” (including previous block data in current block encryption), any error in one block can propagate to the subsequent block. Symmetric Ciphers Applied Cryptography 15  Encryption and Decryption in CFB Mode IV (64/128bit) Cipher Feedback Mode (CFB) CFB mode can be used for both block Key Block Cipher and stream ciphers. Plaintext (64/128bit) The cipher text bits of the current block is fed to the next stage of Ciphertext encryption. (64/128bit) Any error in one block can propagate CFB Mode Encryption to the subsequent block. IV (64/128bit) Encryption process cannot be Key parallelised, but decryption process Block Cipher can. Each block needs to wait for the Ciphertext ciphertext from the previous block to (64/128bit) encrypt. plaintext (64/128bit) CFB Mode Decryption Symmetric Ciphers Applied Cryptography 16  Encryption and Decryption in OFB Mode IV (64/128bit) Output Feedback Mode (OFB) Key Block Cipher OFB mode can be used for both Plaintext (64/128bit) block and stream ciphers. Unlike CFB, only the output bits are Ciphertext (64/128bit) fed to the next stage of encryption. OFB Mode Encryption OFB does not use the previous blocks IV (64/128bit) of plaintext or ciphertext, so error in Key one block does not carry over into the Block Cipher next. Ciphertext (64/128bit) Plaintext (64/128bit) OFB Mode Decryption Symmetric Ciphers Applied Cryptography 17  Padding in Block Ciphers Blocks are fixed sizes in a block cipher, but messages/data come in a variety of lengths. ECB and CBC modes require that the final block be padded before encryption. A simple padding example: 4 2 64 64 64 64 64 A file with size of 3,541 bytes = 28328 bits 0 4 = 442 x 64-bit blocks + 40 bits No of bits to pad = 64-40 = 24 bits 1 2.. 441 442 443 Data blocks Several padding schemes exist: Add null (or 0) bytes to the plaintext to bring its length up to a multiple of the block size, but care must be taken that the original length of the plaintext can be recovered; Padding bits are removed during the decryption process. CBC-specific padding schemes are also used. Append a byte with value 128 (hex 80), followed by as many zero bytes as needed to fill the last block, or Pad the last block with n bytes all with value n. Cryptographic Concepts and Techniques Applied Cryptography 18  Block Cipher VS Stream Cipher Block Cipher Stream Cipher The modes used in block cipher are ECB The algorithm modes used in stream cipher are (Electronic Code Book) and CBC (Cipher Block CFB (Cipher Feedback) and OFB (Output Chaining). Feedback). Uses confusion as well as diffusion. Works on Uses only confusion. Works on substitution transposition techniques like rail-fence, techniques like Caesar cipher, etc. columnar transposition, and etc. Converts the plain text by taking a block at a Converts the text by taking one byte of the plain time. The usual size of the block could be 64 or text at a time. 128-bit. 1 byte (8 bits) at a time is more common. Simple but slow as compared to a Stream Fast but more complex in comparison to block cipher. cipher. Used by nearly all block ciphers. Used for some data-in-transit encryption DES, 3DES, AES, IDEA, Blowfish, RC5 In some TLS suites, RC4 for wireless networks, A5 for cellular networks, etc. Symmetric Ciphers Applied Cryptography 20 Symmetric Ciphers Applied Cryptography 21  Data Encryption Standard (DES) DES is a symmetric block cipher; it encrypts data in 64-bit blocks. In the early 1970s, Horst Feistel from IBM’s "crypto group“ designed a cipher called Lucifer, which later became DES. It was first published as a standard on 15 January 1977. A 64-bit block of plaintext goes in one end of the algorithm, and a 64-bit block of ciphertext comes out the other end. The cipher uses only standard arithmetic and logical operations on numbers of 64-bit blocks. It was broken for the first time under a brute force attack in June 1998. DES key length is 56 bits. It is actually a 64-bit number, but every least-significant bit of 8 bytes is used for error checking and is ignored. DES is a product cipher: confusion + diffusion. 16 rounds of substitution followed by a permutation that is based on the key. All security rests with the key. The cipher is in the public domain. Symmetric Ciphers Applied Cryptography 22  Conceptual View of DES Padding in DES If the message does 64-bit 64-bit 64-bit not end on a block Plain text Plain text Plain text boundary, add one bit, followed by enough zero bits to fill 56-bit Key 56-bit Key 56-bit Key DES DES DES out the block. If the message ends on a block boundary, 64-bit 64-bit 64-bit a whole padding Cipher Cipher Cipher text text text block will be added. Padding bits are Block 1 Block 2 Block n removed during the decryption process. Symmetric Ciphers Applied Cryptography 23  Summary of DES Encryption IP Table 64-bit block (Horst) Feistel network 1 Plain text (64 bits) bit-permutation positions Key Transformation 58 60 50 52 42 44 34 36 26 28 18 20 10 12 2 4 2 Initial Permutation (IP) 62 54 46 38 30 22 14 6 (Diffusion)_ 64 56 48 40 32 24 16 8 Expansion Permutation 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 3 LPT RPT 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 S-Box Substitution 4 16 16 Key Key 40 8 48 16 56 24 64 32 rounds rounds 39 7 47 15 55 23 63 31 P-Box Permutation 38 6 46 14 54 22 62 30 Final Permutation (FP) 37 5 45 13 53 21 61 29 5 (Diffusion) 36 4 44 12 52 20 60 28 XOR and Swap 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 6 Cipher text 33 1 41 9 49 17 57 25 (64 bits) Each round in DES View the animation at: Cryptool -> Indv. Procedure -> Visualization of Algorithm -> DES Symmetric Ciphers Applied Cryptography 24  DES Updates Double DES Perform DES twice with two different keys. It is not widely used. Triple DES or 3DES Uses a "key bundle" that comprises three DES keys, K1, K2, and K3. K1 K2 K3 plaintext ciphertext *6'æéj·g Encrypt Decrypt Encrypt Three-key 3DES version uses three unique keys. K1=K3 in two-key versions, which is less secure. Symmetric Ciphers Applied Cryptography 25  Current status of DES Brute force attack is feasible as DES 56 bits key lengths is too short. The key was found in just 22 hours 15 minutes in January 1999 in DES Challenge III The plaintext was "See you in Rome (second AES Conference, March 22-23, 1999)“ DES is decommissioned by NIST on July 19, 2018. NIST(USA) approved Triple DES through the year 2030 for sensitive government information. Cryptographic Concepts and Techniques Applied Cryptography 27  Advanced Encryption Standard (AES) The Advanced Encryption Standard (AES) (also known by its original name Rijndael) is published as a standard on 26 November 2001 as a DES replacement. AES is a symmetric block cipher. It encrypts data in 128 bit blocks. A 128-bit block of plaintext goes in one end of the algorithm and a 128-bit block of ciphertext comes out the other end. A 128-bit block = 16 bytes (16 character). Example: ENTHUSIASTICALLY AES performed well on a wide variety of hardware, from 8-bit smart cards to high-performance computers. AES key length can be either 128 (most use), 192 or 256 bits. AES is a product cipher: confusion + diffusion. The key size used specifies the number of transformation rounds that convert the plaintext to ciphertext. 10 rounds for 128-bit keys. 12 rounds for 192-bit keys. 14 rounds for 256-bit keys. All security rests with the key. The cipher is in the public domain. Cryptographic Concepts and Techniques Applied Cryptography 28  Advanced Encryption Standard (AES) Unlike DES, AES manipulates bytes instead of bits. S0 S4 S8 S12 It views a 16-byte plaintext as a two-dimensional array of bytes (s = s0, s1,... , s15). S1 S5 S9 S13 AES transforms the bytes, columns, and rows of this array to produce a final value, the ciphertext. S2 S6 S10 S14 Visualise the AES encryption process at https://www.cryptool.org/en/cto/aes-animation S3 S7 S11 S15 Cryptographic Concepts and Techniques Applied Cryptography 29  Advanced Encryption Standard (AES) AES is the most used cipher today. It is yet to be broken. AES is secure because all output bits depend on all input bits in some complex, pseudorandom way. To achieve this, the designers of AES carefully chose each component for a particular reason: Mix Columns: diffusion (transposition) Perform matrix multiplication. Each column is multiplied by a specific matrix. Shift Rows: diffusion (transposition) Each row is shifted a particular number of times. Substitute Bytes: confusion (substitution). Each byte is substituted by another byte. They have shown that this composition protects AES against whole classes of cryptanalytic attacks. Cryptographic Concepts and Techniques Applied Cryptography 30  DES Vs AES DES AES Bit oriented. Byte oriented. 56-bit key length Key lengths can be 128-bits, 192-bits, and 256- bits. Encrypt/decrypt data in 64-bit block size. Encrypt/decrypt data in128-bit block size. The design of the cipher is in the public domain. Design of cipher is in public domain. Uses both confusion and diffusion techniques. Uses both confusion and diffusion techniques. Total 16 rounds of identical operations to encrypt Number of rounds depends on key length: and decrypt 10(128-bits), 12(192-bits), or 14(256-bits) Various known attacks against DES No known crypt-analytical attacks against AES DES can be broken easily as it has known AES is more secure than the DES cipher and is the vulnerabilities. defacto standard. 3DES(Triple DES) is a variation of DES that is secure than the usual DES. Cryptographic Concepts and Techniques Applied Cryptography 31 Symmetric Ciphers Applied Cryptography 32  Cryptanalysis Concepts and Types An attempted cryptanalysis 1. Ciphertext-only attack is also known as an attack. It is assumed that the 2. Known-plaintext attack cryptanalyst/attacker has complete details of the cryptographic algorithm Types of Attacks 3. Chosen-plaintext attack and implementation. Five of the possible types of 4. Chosen-ciphertext attack cryptanalysis or attacks are described here. 5. Rubber-hose attack Cryptographic Concepts and Techniques Applied Cryptography 33  1. Ciphertext-only attack The attacker has the ciphertext of several messages, all of which have been encrypted using the same cipher. The attacker's job is to recover the plaintext of as many messages as possible, or better yet to deduce the key (or keys) used to encrypt the messages, in order to decrypt other messages encrypted with the same keys. ÜÓnclw…¤'!„gGÑÃ# I¾˜ :|ṩ¼51×?7ïô ÜÓnclw…¤'!„gG ¬ö*$ò-â°¢8 ÑÃ#I¾˜ :|á¹ ÜÓnclw…¤'!„gGÑ ©¼51×?7ïô¬ö*$ò Plaintext??? Ã#I¾˜ :|ṩ¼51 -â°¢8 ×?7ïô¬ö* ò-â° 8 Plaintext??? ÜÓnclw…¤'!„ gGÑÃ#I¾˜ :| ṩ¼51×?7ïô Plaintext ¬ö*$ò-â°¢8 ??? Cryptographic Concepts and Techniques Applied Cryptography 34  2. Known-plaintext Attack The attacker has access not only to the ciphertext of several messages, but also to the plaintext of those messages. Her job is to deduce the key (or keys) used to encrypt the messages or an algorithm to decrypt any new messages encrypted with the same key (or keys). ÜÓnclw…¤'!„gGÑÃ# I¾˜ :|ṩ¼51×?7ïô ÜÓnclw…¤'!„gG Plaintext 1 ¬ö*$ò-â°¢8 ÑÃ#I¾˜ :|á¹ ÜÓnclw…¤'!„gGÑ ©¼51×?7ïô¬ö*$ò Ã#I¾˜ :|ṩ¼51 -â°¢8 ×?7ïô¬ö* ò-â° 8 Plaintext 3 ÜÓnclw…¤'!„ Plaintext 2 gGÑÃ#I¾˜ :| ṩ¼51×?7ïô ¬ö*$ò-â°¢8 Cryptographic Concepts and Techniques Applied Cryptography 35  3. Chosen-plaintext Attack ÜÓnclw…¤'!„gGÑÃ# I¾˜ :|ṩ¼51×?7ïô The attacker not only has access to the Plaintext 1 ¬ö*$ò-â°¢8 ÜÓnclw…¤'!„gG ÑÃ#I¾˜ :|á¹ ÜÓnclw…¤'!„ gGÑÃ#I¾˜ :| ciphertext and associated plaintext for several ©¼51×?7ïô¬ö*$ò -â°¢8 ṩ¼51×?7ïô ¬ö*$ò-â°¢8 messages, but he also chooses the plaintext that Plaintext 3 gets encrypted. Plaintext 2 The quick brown ÜÓnclw…¤'!„gGÑ fox jumps over Ã#I¾˜ :|ṩ¼51 the lazy dog. This is more powerful than a known-plaintext ×?7ïô¬ö* ò-â° 8 attack, because the attacker can choose specific plaintext blocks to encrypt, ones that might yield more information about the key. Her job is to deduce the key (or keys) used to encrypt the messages or an algorithm to decrypt any new messages encrypted with the same key (or keys). Cryptographic Concepts and Techniques Applied Cryptography 36  4. Chosen-ciphertext Attack The attacker can choose different ciphertexts to be decrypted and has access to the decrypted plaintext. For example, the cryptanalyst has access to a tamperproof box that does automatic decryption. Her job is to deduce the key. ÜÓnclw…¤'!„ :| gGÑÃ#I¾˜ÜÓnclw…¤'!„ ṩ¼51×?7ïô gGÑÃ#I¾˜ :| ¬ö*$ò-â°¢8 ṩ¼51×?7ïô ¬ö*$ò-â°¢8 The quick brown fox jumps over the lazy dog. ÜÓnclw…¤'!„gGÑÃ# I¾˜ :|ṩ¼51×?7ïô ÜÓnclw…¤'!„gG ¬ö*$ò-â°¢8 ÑÃ#I¾˜ :|á¹ ÜÓnclw…¤'!„gGÑ ©¼51×?7ïô¬ö*$ò Ã#I¾˜ :|ṩ¼51 -â°¢8 ×?7ïô¬ö* ò-â° 8 Cryptographic Concepts and Techniques Applied Cryptography 37  5. Rubber-hose Attack The attacker/cryptanalyst threatens, blackmails, or tortures someone until they give him the key. Bribery is sometimes referred to as a purchase-key attack. These are all very powerful attacks and often the best way to break an algorithm. Cryptographic Concepts and Techniques Applied Cryptography 39  Summary-I Types of symmetric Entire message is available ciphers before the encryption starts. eg: A file stored in disk drive. Message byte (or bit) is DES encrypted when it becomes Block Ciphers Stream Ciphers available. 56 bit key, RC4 64 bit data block Plaintext ⊕ Random bit stream. AES 128/192/256 bit key Algorithm/Cipher Modes 128 bit data block Electronic Cipher Output Cipher Block Code Book Feedback Feedback Chaining (CBC) (ECB) (CFB) (OFB) For the block ciphers only For both block & stream ciphers Padding is required to align the data to the exact block size. Cryptographic Concepts and Techniques Applied Cryptography 40  Summary-II Types of Cryptanalysis (or) Attacks Types of Attacks 1. Ciphertext- 2. Known- 3. Chosen- 4. Chosen- 5. Rubber-hose only attack plaintext attack plaintext attack ciphertext attack cryptanalysis Cryptographic Concepts and Techniques Applied Cryptography 41 Cryptographic Concepts and Techniques Applied Cryptography 42