Symmetric Encryption Principles�

​

• Symmetric Cryptography (DES, Triple DES, AES, Key distribution)
• Chiper Lock Mode(Electronic Codebook Mode ,

​

​

​

Symmetric Encryption Principles

• Symmetric Cipher Model
• Plaintext
• Encryption Algorithm
• Secret Key (known to sender and receiver)
• Ciphertext
• Decryption Algorithm

Plaintext

Message

Encryption

Algorithm

Secret

Key

Plaintext

Message

Decryption

Algorithm

Secret

Key

Transmitted Ciphertext

Symmetric encryption

Symmetric encryption is a form of cryptosystem in which encryption and decryption are performed using the same key. It is also known as conventional encryption.

● Symmetric encryption transforms plaintext into ciphertext using a secret key and an encryption algorithm. Using the same key and a decryption algorithm, the plaintext is recovered from the ciphertext.

​

​

Figure :Symmetric encryption and decription

Traditional symmetric ciphers use substitution and/or transposition techniques.

●Rotor machines are sophisticated precomputer hardware devices that use substitution techniques.

​

Symmetric Cryptography�

chapter-3rd

7

Symmetric key

• A common secret that all parties must know
• Difficult to distribute key securely
• Used by DES, 3DES, AES, Twofish, Blowfish, IDEA, RC5

chapter-3rd

8

Fig. Symmetric cryptography

Attributes of Strong Encryption

• Confusion
• Change key values each round
• Performed through substitution
• Complicates plaintext/key relationship
• Interceptor should not be able to predict how ciphertext will change by changing one character
• Diffusion
• Change location of plaintext in ciphertext
• Done through transposition
• Cipher should spread information from plaintext over cipher text

​

​

chapter-3rd

9

Types of Encryption

• Block cipher

Encrypts blocks of data, often 128 bits

• Stream cipher

Operates on a continuous stream of data

Block Chiper

A block cipher is an encryption/decryption scheme in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length.

● Many block ciphers have a Feistel structure. Such a structure consists of a number of identical rounds of processing. In each round, a substitution is performed on one half of the data being processed, followed by a permutation that interchanges the

two halves. The original key is expanded so that a different key is used for each round.

● The Data Encryption Standard (DES) has been the most widely used encryption algorithm until recently. It exhibits the classic Feistel structure. DES uses a 64-bit block and a 56-bit key.

Feistel Cipher

• A Feistel block cipher operates on a plaintext block of n bits to produce a ciphertext block of n bits. There are 2^n possible different plaintext blocks and, for the encryption to be reversible (i.e., for decryption to be possible), each must produce a unique ciphertext block. Such a transformation is called reversible, or nonsingular.

Feistel Network Structure

chapter-3rd

13

Encrypt

Decrypt

CIPHERTEXT

PLAINTEXT

Decryption of Fiestel cipher

• The process of decryption with a Feistel cipher is essentially the same as the encryption process. The rule is as follows: Use the ciphertext as input to the algorithm, but use the subkeys Ki in reverse order.
• That is, use Kn in the first round, Kn-1 in the second round, and so on until K1 is used in the last round.This is a nice feature because it means we need not implement two different algorithms, one for encryption and one for decryption.

Data Encryption Standard (DES)

• The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST).
• In 1973, NIST published a request for proposals for a national symmetric-key cryptosystem. A proposal from IBM, a modification of a project called Lucifer, was accepted as DES. DES was published in the Federal Register in March 1975 as a draft of the Federal Information Processing Standard (FIPS).
• There has been considerable controversy over the design, particularly in the choice of a 56-bit key.

​

​

​

​

​

chapter-3rd

15

Symmetric Encryption

• Uses same “secret key” to encipher and decipher message
• Encryption methods can be extremely efficient, requiring minimal processing
• Both sender and receiver must possess encryption key
• If either copy of key is compromised, an intermediate can decrypt and read messages
• Key distribution problem

chapter-3rd

16

Modern Block Ciphers

• Block ciphers are among the most widely used types of cryptographic algorithms
• Provide secrecy and/or authentication services
• In particular will introduce DES (Data Encryption Standard)

chapter-3rd

17

Block Cipher Principles

• Most symmetric block ciphers are based on a Feistel Cipher Structure
• Needed since must be able to decrypt ciphertext to recover messages efficiently
• Block ciphers look like an extremely large substitution
• Would need table of 2⁶⁴ entries for a 64-bit block
• Instead create from smaller building blocks

​

​

chapter-3rd

18

chapter-3rd

19

Figure 8-5 Example of Symmetric Encryption

Symmetric Encryption (cont’d.)

• Data Encryption Standard (DES): one of most popular symmetric encryption cryptosystems
• 64-bit block size; 56-bit key
• Adopted by NIST in 1976 as federal standard for encrypting non-classified information
• Triple DES (3DES): created to provide security far beyond DES
• Advanced Encryption Standard (AES): developed to replace both DES and 3DES

chapter-3rd

20

DES

• A block cipher:
• encrypts blocks of 64 bits using a 56 bit key
• outputs 64 bits of ciphertext
• A product cipher
• basic unit is the bit
• performs both substitution (S-box) and transposition (permutation) (P-box) on the bits
• Cipher consists of 16 rounds (iterations) of processing
• From the original 56-bit key, 16 subkeys are generated (2⁵⁶ )

​

​

chapter-3rd

21

DES - Basics

• Fundamentally DES performs only two operations on its input, bit shifting (permutation), and bit substitution.
• The key controls exactly how this process works.
• By doing these operations repeatedly and in a non-linear manner you end up with a result which can not be used to retrieve the original without the key.
• By applying relatively simple operations repeatedly a system can achieve a state of near total randomness.

chapter-3rd

22

DES

• As with any encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in length and the key is 56 bits in length.

Looking at the left-hand side of the figure, we can see that the processing of the plaintext proceeds in three phases. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits to produce the permuted input. This is followed by a phase consisting of 16 rounds of the same function, which involves both permutation and substitution functions. The output of the last (sixteenth) round consists of 64 bits that are a function of the input plaintext and the key. The left and right halves of the output are swapped to produce the preoutput. Finally, the preoutput is passed through a permutation (IP-1) that is the inverse of the initial permutation function, to produce the 64-bit ciphertext. With the exception of the initial and final permutations, DES has the exact structure of a Feistel cipher.

The right-hand portion of shows the way in which the 56-bit key is used. Initially, the key is passed through a permutation function. Then, for each of the 16 rounds, a subkey (Ki) is produced by the combination of a left circular shift and a permutation. The permutation function is the same for each round, but a different subkey is produced because of the repeated shifts of the key bits.

DES Overview

chapter-3rd

27

Figure Encryption and decryption with DES

DES Structure

• The encryption process is made of two permutations (P-boxes), which we call initial and final permutations, and sixteen rounds of complex key dependent calculation.

​

​

chapter-3rd

28

DES uses 16 rounds. Each round of DES is a Feistel cipher

• .

chapter-3rd

29

The heart of DES is the DES function. The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output. �

• .

chapter-3rd

30

Expansion P-box

• Since R_I−1 is a 32-bit input and K_I is a 48-bit key, we first need to expand R_I−1 to 48 bits.

​

chapter-3rd

31

chapter-3rd

32

S-Boxes

The S-boxes do the real mixing (confusion). DES uses 8 S-boxes, each with a 6-bit input and a 4-bit output. See Figure 6.7.

Continue

Figure 6.7 S-boxes

chapter-3rd

33

Continue

Figure 6.8 S-box rule

Feistel Network Structure

chapter-3rd

34

Encrypt

Decrypt

CIPHERTEXT

PLAINTEXT

Each Iteration Use of a Different Sub-key

• DES works on 64 bits of data at a time. Each 64 bits of data is iterated on from 1 to 16 times (16 is the DES standard).
• For each iteration a 48 bit subset of the 56 bit key is fed into the encryption block
• Decryption is the inverse of the encryption process.

chapter-3rd

35

DES Key Processing

• The key is usually stored as a 64-bit number, where every eighth bit is a parity bit.
• The parity bits are pitched during the algorithm, and the 56-bit key is used to create 16 different 48-bit subkeys - one for each round.
• Subkeys Generation
• First, the key is loaded according to the PC-1 and then halved.
• Then each half is rotated by 2 bits in every round except the first, second, 9th and last rounds.
• The reason for this is that it makes it secure against related-key cryptanalysis.
• Then 48 of the 56 bits are chosen according to a compression permutation.

​

​

​

chapter-3rd

36

The Key Schedule

• The subkeys used by the 16 rounds are formed by the key schedule which consists of:
• An initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves
• 16 stages consisting of
• selecting 24-bits from each half and permuting them by PC2 for use in function f,
• rotating each half either 1 or 2 places depending on the key rotation schedule

chapter-3rd

37

DES Decryption

Decrypt must unwind steps of data computation

With Feistel design, do encryption steps again

Using subkeys in reverse order (SK16 … SK1)

Note that IP undoes final FP step of encryption

1st round with SK16 undoes 16th encrypt round

….

16th round with SK1 undoes 1st encrypt round

then final FP undoes initial encryption IP

thus recovering original data value

chapter-3rd

38

Strength of DES – Key Size

• 56-bit keys have 2⁵⁶ = 7.2 x 10¹⁶ values
• Brute force search looks hard
• Assuming on average half the key space has to be searched, a single machine performing one DES encryption per microsecond would take more than a thousand year to break the cipher
• Still must be able to recognize plaintext
• Now considering alternatives to DES

chapter-3rd

39

Strength of DES – Timing Attacks

• Attacks actual implementation of cipher
• Use knowledge of consequences of implementation to derive knowledge of some/all subkey bits
• Specifically use fact that calculations can take varying times depending on the value of the inputs to it
• Particularly problematic on smartcards

chapter-3rd

40

Strength of DES – Analytic Attacks

• Now have several analytic attacks on DES
• These utilize some deep structure of the cipher
• by gathering information about encryptions
• can eventually recover some/all of the sub-key bits
• if necessary then exhaustively search for the rest
• generally these are statistical attacks
• include
• differential cryptanalysis
• linear cryptanalysis
• related key attacks

​

chapter-3rd

41

Security of DES

• DES, as the first important block cipher, has gone through much scrutiny. Among the attempted attacks, three are of interest:
1. Brute-Force Attack
2. Differential Cryptanalysis
3. Linear Cryptanalysis

​

​

chapter-3rd

6.42

Attack Methods

• Brute-Force Attack
• the most basic method of attack is brute force — trying every possible key in turn.
• Combining the weakness of short cipher key with the key complement weakness, it is clear that DES can be broken using 2⁵⁵ encryptions.
• Differential Cryptanalysis
• In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output.
• To break the full 16 rounds, differential cryptanalysis requires 2⁴⁷ chosen plaintexts.
• It has been revealed that the designers of DES already knew about this type of attack and designed S-boxes and chose 16 as the number of rounds to make DES specifically resistant to this type of attack.

chapter-3rd

43

6.5.1

Attack Methods-II

• Linear cryptanalysis
• Linear cryptanalysis is newer than differential cryptanalysis.
• Linear cryptanalysis tries to take advantage of high probability occurrences of linear expressions involving plaintext bits, "ciphertext" bits, and subkey bits.
• Linear cryptanalysis is a known plaintext attack and uses a linear approximation to describe the behavior of the block cipher. Given sufficient pairs of plaintext and corresponding ciphertext, bits of information about the key can be obtained and increased amounts of data will usually give a higher probability of success.
• DES is more vulnerable to linear cryptanalysis than to differential cryptanalysis. S-boxes are not very resistant to linear cryptanalysis.
• It has been shown that DES can be broken using 2⁴³ pairs of known plaintexts. However, from the practical point of view, finding so many pairs is very unlikely.

​

chapter-3rd

44

DES- Current State

• Currently DES is no longer certified for US federal use.
• The availability of faster hardware, and access to large distributed systems meant that 56-bit DES keys could be recovered by brute force searches in an unreasonably short time (days or even hours).
• DES should almost certainly not be used in any new product, and should not be used in existing products to protect information with a lifetime of more than a few minutes.

chapter-3rd

45

3DES or Triple-DES

• Triple-DES is a block cipher, which applies the Data Encryption Standard (DES) cipher algorithm three times to each data block.
• DES used a single 56-bit key.
• 3DES uses three 56-bit keys (often just referred to as a 3DES key), and performs three rounds of DES operations on the data.
• The result is that DES technology could be used until long term solution (the Advanced Encryption Standard) is found.

chapter-3rd

46

Triple DES - More Secure

chapter-3rd

47

3DES

• A typical application of 3DES is known as EDE (Encrypt-Decrypt-Encrypt).
• In this case, the first and third keys are equal, so the effective key length is 112-bits.
• In the first operation, the plaintext is encrypted with the first DES key, K₁.

chapter-3rd

48

3DES

• In the second step, the results of the first step, C₁, is decrypted using the second key, K₂
• Since K₂ ≠ K₁, this does not result in the original plaintext message.

chapter-3rd

49

3DES

• In the final step, the results of the second step, C₂, is encrypted using the third key, K₃
• The output ciphertext C₃ is the final encrypted message.
• Recall that K₃ = K₁ in this case, so even though there are three 56-bit keys, the effective key length is only 112-bits.

chapter-3rd

50

3DES or Triple-DES

• Decryption in this case follows the reverse of the encryption process, as shown below.

chapter-3rd

51

3DES or Triple-DES

• Although the length of the key has doubled, there are 2⁵⁶ (= 72,057,594,037,927,936) times as many keys.
• Therefore a brute force search for a 3DES-EDE key would take 2⁵⁶ times longer on the same hardware than a brute force search for a DES key.
• There are some approaches that can recover 3DES keys more quickly than brute force searches, but for many kinds of data 3DES is still an acceptable encryption method.

chapter-3rd

52

Triple DES

• (a) Triple encryption using DES. (b) Decryption.

AES – The Advanced Encryption Standard

• Rules for AES proposals
• The algorithm must be a symmetric block cipher.
• The full design must be public.
• Key lengths of 128, 192, and 256 bits supported.
• Both software and hardware implementations required
• The algorithm must be public or licensed on nondiscriminatory terms.

AES (2)

• An outline of Rijndael.

AES (3)

• Creating of the state and rk arrays.

AES

• DES is near end of useful life
• NIST has begun process to look for successor to DES
• The Advanced Encryption Standard (AES) was the result of an open international search organized by NIST for a replacement for DES.
• AES Process:
• Proposals submitted 3/98
• AES Workshop - 8/98
• 15 proposals selected
• Key sizes of 128, 192, and 256 bits

​

chapter-3rd

57

AES

• Rules:
• Unclassified
• Royalty-free
• Worldwide
• Public domain
• Significantly More Efficient than 3DES
• Symmetric Block Cipher

​

• AES Timeline:
• Public comment through April 1999
• Candidate Conference, March 22-23, 1999, Rome
• Finalists selected summer 1999
• AES3 conference, April 13 -14, 2000, New York

​

chapter-3rd

58

AES

• Algorithms were submitted, and five finalists were selected.
• Finalists for the AES standard are:
• MARS (IBM - USA)
• RC6 (RSA Labs - USA)
• Rijndael (Daemen and Rijmen - Belgium)
• SERPENT (Anderson, Biham, and Knudsen - UK, Israel, Norway)
• TWOFISH (Schneier, Kelsey, et al. - USA)

​

​

chapter-3rd

59

AES

• The finalists were subjected to open review by the cryptographic community.
• The entire process took over 3 years to complete.
• The Rijndael algorithm was declared by NIST to be the eventual winner, and is now generally referred to as AES.
• http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
• Rijndael was developed and submitted by two European cryptographers, Joan Daemen and Vincent Rijmen.

chapter-3rd

60

Evaluation Criteria for �AES Proposals

• Security
• Computational Efficiency
• Memory Requirements
• Hardware and Software Suitability
• Flexibility

chapter-3rd

61

Symmetric Key Encryption- Strength

• The strengths of modern symmetric key encryption algorithms include:
• Fairly fast encryption/decryption process (in comparison to public key techniques, for example)
• Several well known, well tested algorithms are available, including 3DES and AES.
• Library implementations of symmetric key algorithms are commonly available for many programming languages.

chapter-3rd

62

AES Algorithm – High Level

• KeyExpansion—round keys are derived from the cipher key using Rijndael's key schedule
• Initial Round
• AddRoundKey—each byte of the state is combined with the round key using bitwise xor
• Rounds
• SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
• ShiftRows—a transposition step where each row of the state is shifted cyclically a certain number of steps.
• MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
• AddRoundKey
• Final Round (no MixColumns)
• SubBytes
• ShiftRows
• AddRoundKey

​

chapter-3rd

63

chapter-3rd

64

The State and Key Schedule

• Input is a 128 bit block (16 bytes) that is placed in the state array
• The key is entered in a block and divided into key schedule words of 4 bytes/word.
• The key schedule is an expansion of the key—eg, a 128 bit key is expanded into 44 key schedule words.
• A square matrix of bytes is used by the standard to describe the state.

chapter-3rd

65

Rounds and Transformation Stages

• The encryption process executes a round function, Nr times, with the number of rounds (Nr) being dependent on key size.
• The round function consists of four transformation stages.
• SubBytes()
• ShiftRows()
• MixColumns()
• AddRoundKey()

chapter-3rd

66

Rounds and Transformation Stages

• The cipher begins with an AddRoundKey().
• All rounds then execute each of the transformations except the last round.
• The MixColumns( ) transformation is not executed in the final round.
• For a 128 bit key, there are 10 rounds.
• 12 and 14 rounds are used with keys of 192 and 256.

​

​

chapter-3rd

67