Symmetric Key Encryption Lecture Notes PDF

Lec 7 – BNIF 711 Winter 2024 Symmetric Key Encryption Dr. Aya Salama Outlines Introduction to Symmetric Key Encryption Common Symmetric Key Algorithms Block Cipher Operation Modes 2 Alternative nam...

Lec 7 – BNIF 711 Winter 2024 Symmetric Key Encryption Dr. Aya Salama Outlines Introduction to Symmetric Key Encryption Common Symmetric Key Algorithms Block Cipher Operation Modes 2 Alternative names: private-key, single-key or secret-key cryptography. Oscar (bad guy) Unsecure channel (e.g. Internet) Alice Bob (good) x x (good) Problem Statement: 1) Alice and Bob would like to communicate via an unsecure channel (e.g., WLAN or Internet). 2) A malicious third party Oscar (the bad guy) has channel access but should not be able to understand the communication.  Oscar Solution: Encryption with symmetric cipher. (bad guy)  Oscar obtains only ciphertext y, that looks Unsecure like random bits channel y (e.g. Internet) Alice Encryption Decryption Bob (good) x e( ) y d( ) x (good) K K Key Generator Secure Channel x is the. plaintext y is the ciphertext K is the key Set of all keys {K1, K2,...,Kn} is the key space  Encryption equation y = eK(x) Decryption equation x = dK(y) Encryption and decryption are inverse operations if the same key K is used on both sides: dK(y) = dK(eK(x)) = x Important: The key must be transmitted via a secure channel between Alice and Bob. The secure channel can be realized. However, the system is only secure if an attacker does not learn the key K!  The problem of secure communication is reduced to secure transmission and storage of the key K.  Confusion and Diffusion Cipher needs to completely obscure statistical properties of original message A one-time pad does this More practically Shannon suggested combining S & P elements to obtain: Diffusion – dissipates statistical structure of plaintext over bulk of cipher text Confusion – makes relationship between ciphertext and key as complex as possible Data Encryption Standard (DES) ▪ Data Encryption Standard (DES) was the first modern and standardized symmetric-key encryption scheme ▪ Originally developed by IBM DES became the most widely used block cipher in the world. DES encrypts 64-bit data using a 56-bit key. ▪ DES proved insecure in July 1998 (brute-force attack) ▪ 56 bit long encryption keys too short! ▪ However, no other fatal weaknesses reported so far ▪ Has been superseded by AES 7  Strength of DES 56-bit keys have 256 = 7.2 x 1016 values, which means brute force attack to guess the key looks hard. In 1997, it was possible to discover the key in a few months using an executive search. In 1998 on, dedicated hardware created by Electronic Frontier Foundation with $220,000 cost in could break DES in a few days In 1999, a study showed that DES could be broken in 22 hours. 8  Triple DES Made part of DES in 1999 Uses 3 keys and 3 DES executions Using 3 keys 3DES has an effective key length of 168 bits (3*56) What about Double DES? 9  National Institute of Standards and Technology (NIST) is a U.S. federal agency within the Department of Commerce. Its primary mission is to promote innovation and industrial competitiveness by advancing measurement science, standards, and technology. Advanced Encryption Standard (AES) ▪ In 1997, US NIST issued a call for a new Advanced Encryption Standard with requirements ▪ Security strength better than 3DES ▪ Significantly more efficient ▪ Increased block length (128 bits) ▪ Support key sizes of 128, 192, and 256 bits 11  Advanced Encryption Standard (AES) Requirements Evaluation Criteria private key symmetric block cipher Initial criteria: 128-bit data, 128/192/256-bit keys security – effort for practical cryptanalysis cost – in terms of computational efficiency stronger & faster than Triple-DES algorithm & implementation characteristics active life of 20-30 years (+ archival use) Final criteria: provide full specification & design general security details ease of software & hardware implementation both C & Java implementations implementation attacks NIST have released all submissions & flexibility (in en/decrypt, keying, other factors) unclassified analyses AdvancedEncryptionStandard The Short Listed Algorithms with their scores were: Rijndael: 86 positive, 10 negative Serpent: 59 positive, 7 negative Twofish: 31 positive, 21 negative RC6: 23 positive, 37 negative MARS: 13 positive, 84 negative NIST selected Rijndael as the proposed AES algorithm Designers were two cryptographers from Belgium: Dr. Joan Daemen and Dr. Vincent Rijmen. 13  Advanced Encryption Standard (AES) - Rijndael Designed by Rijmen-Daemen in Belgium ❑ Designed to be: ⚫ resistant against known attacks has 128/192/256 bit keys, 128 bit data ⚫ speed and code compactness on many CPUs an iterative rather than Feistel cipher ⚫ design simplicity processes data as block of 4 columns of 4 bytes operates on entire data block in every round  The AES Cipher - Rijndael →data block of → 4 columns of 4 bytes→ is state → key is expanded→ to array of words processes data as 4 groups of 4 bytes (state) Each round is built from four basic steps/Operations: 1. byte substitution (1 S-box used on every byte) 2. shift rows (permute bytes between groups/columns) 3. Mix-Columns step: a matrix multiplication step 4. Add Round Key step: an XOR step with a round key derived from the 128-bit encryption key  Block Cipher andPadding Block ciphers require the length n of the plaintext to be a multiple of the block size b. If the length of the plaintext is not multiple of the block size b, then we need to pad the last block. When the block size and plaintext length are a multiple of 8, a common padding method (PKCS5) is a sequence of identical bytes, each indicating the padding's length (in bytes). 16  Padding Example Let's assume we want to encrypt the word "ciphertext" with a block size of length 8 bytes (64-bits) c i p h e r t e x t Block 1: 8 bytes c i p h e r t e Block 2: 8 bytes x t 6 6 6 6 6 6 17 S-Box A good S-box will have the property that changing one input bit will change about half of the output bits. A good S-box will have the property that each output bit will depend on every input bit. 18 S-Box and P-Box P-boxes permute or rearrange bits across S-box inputs. (S-P) networks comprise several rounds, each round being a substitution, a permutation, and the addition of key material. 19  (S-P) Network The four keys (k1, k2, k3, and k4) are derived from a single key. This series of keys is called a key schedule the derived keys are called round keys. In each round we perform both substitution and permutation operations 20  Byte Substitution A simple substitution of each byte uses one table of 16x16 bytes containing a permutation of all 256 8-bit values each byte of state is replaced by byte indexed by row (left 4-bits) & column (right 4-bits) eg. byte {95} is replaced by byte in row 9 column 5 which has value {2A} S-box constructed using defined transformation of values designed to be resistant to all known attacks  Shift Rows a circular byte shift 1st row is unchanged 2nd row does 1 byte circular shift to left 3rd row does 2 byte circular shift to left 4th row does 3 byte circular shift to left decrypt inverts using shifts to right  Mix Columns Each byte is replaced by a value dependent on all 4 bytes in the column Matrix multiplication  Mix Columns Can express each col as 4 equations to derive each new byte in col Decryption requires use of inverse matrix with larger coefficients, hence a little harder  Add Round Key XOR state with 128-bits of the round key Again processed by column (though effectively a series of byte operations) Inverse for decryption identical since XOR own inverse, with reversed keys Designed to be as simple as possible a form of Vernam cipher on expanded key requires other stages for complexity / security AES Round  AES Key Expansion takes 128-bit (16-byte) key and expands into array of 44/52/60 32-bit words start by copying key into first 4 words → then loop creating words that depend on values in previous 4 places back ⚫ in 3 of 4 cases just XOR these together ⚫ 1st word in 4 has rotate + S-box + XOR round constant on previous, before XOR 4th back  Key Expansion Rationale Designed to resist known attacks Design criteria included ⚫ knowing part key insufficient to find many more ⚫ invertible transformation ⚫ fast on wide range of CPU’s ⚫ use round constants to break symmetry ⚫ diffuse key bits into round keys ⚫ enough non-linearity to hinder analysis ⚫ simplicity of description  AES Decryption AES decryption is not identical to encryption since steps done in reverse But can define an equivalent inverse cipher with steps as for encryption but using inverses of each step with a different key schedule Works since result is unchanged when swap byte substitution & shift rows swap mix columns & add (tweaked) round key  Feistel Cipher Horst Feistel develops Feistel Cipher at IBM It implements Shannon's substitution- permutation network concept. Most symmetric block ciphers are based on a Feistel Cipher Structure 31  Feistel Cipher How does it work? →Partitions input block into two halves which are processed through multiple rounds. In every round: Perform a substitution on the left data half based on a round function of the right half & subkey Then have permutation-swapping halves 32  Feistel Cipher Design elements of Feistel cipher include: Block size: increasing size improves security but slows the cipher Key size: increasing size improves security, makes exhaustive key searching harder, but may slow the cipher Subkey generation: greater complexity can make analysis harder but slows the cipher Round function: greater complexity can make analysis harder but the slows cipher  Feistel Cipher Decryption The Feistel structure ensures that the decryption process mirrors the encryption process, allowing for simple key management. Round Keys: The keys used for decryption are the same as those used for encryption, but they are applied in reverse order.  Feistel Cipher Security Security: The design provides security through diffusion and confusion, ensuring that small changes in input result in significant changes in output. This structure is the foundation for many well- known ciphers, such as DES (Data Encryption Standard).  IDEA Algorithm The International Data Encryption Standard (IDEA) Developed in Switzerland 1991 It uses 128-bit key, 64-bit block size, 8 rounds The algorithm is quite different than DES, ○ Doesn't use S-boxes ○ It uses binary addition rather than exclusive-or It is used in Pretty Good Privacy (PGP) 36 Pretty Good Privacy (PGP) It is a data encryption and decryption software library that provides cryptographic privacy and authentication for data communication. PGP is an open-source software typically includes a key management component, which allows users to create, modify, and revoke digital certificates and manage the public and private keys associated with them. PGP also includes a certificate validation component, which allows users to verify the authenticity of digital certificates. It was created by Phil Zimmermann in 1991, stable release (2018) 37 Blowfish Proposed by Bruce Schneier in 1993 A popular alternative to DES Variable length keys - 128 bits but up to 448 bits Variable number of rounds up to 16 rounds It uses a 64-bit block size Used in many commercial software packages Initially was not free, but now it is Studies showed that Blowfish is a much faster algorithm than IDEA and DES. 38  Twofish The Twofish algorithm developed by Bruce Schneier (also the creator of Blowfish) It was one of the AES finalists. Like Rijndael, Twofish is a block cipher. It operates on 128-bit blocks of data and is capable of using cryptographic keys up to 256 bit in length. It uses two techniques not found in other algorithms: pre-whitening and post-whitening. In cryptography, re-whitening and post-whitening are techniques used to protect against known plaintext attacks. 39 SkipjackAlgorithm Was approved for use by the US government in Federal Information Processing Standard (FIPS) 185 as part of the Escrowed Encryption Standard (EES) Skipjack operates on 64-bit blocks of text. It uses an 80-bit key Skipjack has an added twist—it supports the escrow of encryption keys. Two government agencies, the National Institute of Standards and Technology (NIST) and the Department of the Treasury, hold a portion of the information required to reconstruct a Skipjack key. 40 Stop here