� � UNIT-4 DATA ENCRYPTION STANDARD

Information Security

Block Cipher Principles

Stream Cipher

• A Stream Cipher is one that encrypts a digital data stream one bit or one byte at a time.
• Examples are autokeyed Vigenere cipher and the Vernam cipher
• For practical reasons, the bit-stream generator must be implemented as an algorithmic procedure, so that the cryptographic bit stream can be produced by both users
• The bit-stream generator is a key controlled algorithm and must produce a bit stream that is cryptographically strong

Block Cipher

• A block cipher is one in which a block of plaintext is treated as a whole and used to produce a cipher text block of equal length
• Typically, a block size of 64 or 128 bits is used
• As with stream cipher, the two users share a symmetric encryption key
• Using some modes of operations, a block cipher can be used to achieve the same effect as the stream cipher

The Fiestel Cipher

• The most general form of block cipher can be used to define any reversible mapping between plaintext and cipher text referred as ideal cipher because it allows for the maximum number of encryption mappings from plaintext block
• Fiestel proposed that we can approximate the ideal block cipher by utilizing the concept of a product cipher, which is the execution of two or more simple ciphers in sequence in such a way that the final result or product is cryptographically stronger than any of the component cipher

​

• The essence is to develop a cipher with a key of length k bits and block length of n bits, allowing 2^k possible transformations
• Here, Fiestel proposed the use of a cipher that alternates substitution and permutations
• Claude Shannon proposed to develop a product cipher that alternates confusion and diffusion

​

​

Confusion and diffusion

• The words are introduced by Claude Shannon to capture two basic building blocks for any cryptographic systems
• The diffusion seeks to make statistics relationship between plaintext and cipher text as complex as possible in order to thwart attempts to deduce the key
• The confusion seeks to make the relationship between the statistics of the cipher text and the value of the encryption key as complex as possible

Fiestel Cipher Structure

• The inputs to the encryption algorithm are a plaintext block of length 2w bits and a key K
• Plaintext block is divided into two halves, L₀ and R₀
• The halves of data pass through n rounds of processing and combine to produce the cipher text block
• Each round i has as inputs L_i-1 and R_i-1 derived from the previous round, as well as a subkey K_i derived from the overall K
• Here 16 rounds are used, although any number of rounds could be implemented
• All rounds have the same structure

​

• A substitution is performed on the left half of data
• This is done by round function F to the right half of the data and then taking the exclusive-OR of the output of that function and left half of the data
• The round function has the same general structure for each round but is parameterize by round subkey K_i
• Following this substitution a permutation is performed that consists of interchange of the two halves of the data

• The exact realization of Fiestel network, depends on the choice of the following parameters and design features:
• Block size: Larger block sizes mean greater security but reduced encryption/decryption speed for a given algorithm. Greater security is achieved by greater diffusion. Traditionally, Block size of 64 bits has been considered a reasonable trade off. The new AES uses a128-bit block size
• Key size: Larger the key size means greater security but decreases encryption/decryption speed Key sizes of 64 bits or less are now widely considered to be inadequate, and 128 bits has become a common size
• Number of Rounds: Multiple rounds offer increasing security
• Subkey generation algorithm: Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis
• Round Function: Greater complexity generally means greater resistance to cryptanalysis

​

• Two other considerations in the design of a Fiestel cipher:
• Fast Software encryption/decryption: In many cases, encryption is embedded in application or utility functions in such a way to produce a hardware implementation. Accordingly the speed of the algorithm becomes a concern
• Ease of analysis: Although we would like to make our algorithm as difficult as possible to analyze, i.e. if the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for vulnerabilities and therefore develop a higher level of assurance as its strength

Fiestel Decryption algorithm

• The process of decryption with the Fiestel cipher is essentially the same as the encryption process
• Use the cipher text as input to the algorithm, but use the subkeys K_i in reverse order i.e. use K_n in the first round, K_n-1 in the second round and so on.

S Box

Example of S box

• Input=010100

​

Step:-

​

​

Answer:-

• Input=100011

​

Step:-

​

​

Answer:-

​

Input=000000

​

​

Output= ?

The Data Encryption Standard(DES)

• The algorithm for DES is called as Data Encryption Algorithm(DEA)
• Here, data are encrypted in 64-bit blocks using 56-bit key
• The algorithm transforms 64-bit input in a series of steps into a 64-bit output
• The same steps ,with the same key, are used to reverse the encryption

​

56

DES Encryption

• There are two inputs to the encryption function:
• The plaintext to be encrypted
• The key
• Here, plaintext must be 64-bits in length and the key is 56-bits in length
• In left-hand side of the figure, 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 permuted input
• This is followed by a phase consisting of sixteen rounds of same function, which involves both permutation and substitution functions
• The output of the last round(16^th) consists of 64 bits that are a function of the input plaintext and the key. The left and right halves are swapped to produce preoutput
• Finally, the preoutput is passed through a permutation [IP^-1] that is the inverse of the initial permutation, to produce the 64-bit cipher text

​

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

​

Single Round of DES

• The figure shows the internal structure of a single round
• On the left-hand side, the left and right halves are treated as separate 32-bit quantities, labeled L and R
• As in any classical Fiestel cipher, the overall processing at each round can be summarize in the following formulas:
• Li=Ri-1
• R=Li-1(XOR) F(Ri-1,Ki)
• The round key K_i is 48 bits
• The R input is 32 bits. It is first expanded to 48-bits by using a table that defines a permutation plus an expansion that involves duplication of 16 of the result R bits
• The result passes through a substitution function that produces a 32-bit output and then it is permuted

​

​

The role of S-Boxes

• The role of S-boxes in the function F is illustrated in the figure
• The substitution consists of a set of eight S-boxes, each of which accepts 6 bits as input and produces 4 bits as output
• The transformation is defined as:
• The first and last bits of the input to box Si form a 2-bit binary number to select one of four substitutions defined by the four rows in the table for Si
• The middle four bits select one of the sixteen columns
• For example, in S1, for input 011001, row is 01(row1)
• And the column is 1100(column 12). So the value is 9, i.e. 1001

The Avalanche Effect

• A desirable property of encryption algorithm is that a small change in either the plaintext or the key should produce a significant change in the cipher text
• In particular, a change in one bit of the plaintext or one bit of the key should produce a change in many bits of the cipher text
• This is referred to avalanche effect

The Strength of DES

• The use of 56-bit keys
• With a key of 56 bits, there are 2⁵⁶ possible keys, which is approximately 7.2*10¹⁶ keys
• So a brute-force attack appears impractical
• Assuming that, 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 years to break the cipher
• The nature of DES algorithm
• Another concern is the possibility that cryptanalysis is possible by exploiting characteristics of the DES algorithm
• The focus of concern has been on eight substitution tables, or S-boxes

• They were not made public
• The boxes were constructed in such a way that cryptanalysis is possible for an opponent who knows the weakness in the S-boxes
• And no one has so far succeeded in discovering the weaknesses in the S-boxes
• Timing attacks
• A timing attack is one in which information about the key or the plaintext is obtained by observing how long it takes a given implementation to perform descriptions on various cipher texts
• The authors conclude that DES appears to be fairly resistant to a successful timing attack

​

Differential Cryptanalysis attack

• One of the most significant advances in cryptanalysis in recent years
• The rationale behind this is to observe the behavior of pairs of text blocks evolving along each round of cipher , instead of observing the evolution of single text block
• This method looks at pairs of cipher text whose plaintexts have particular differences
• The technique analyses the progress of differences as the plaintexts travel through the various rounds of DES
• The idea is to choose pairs of plaintext with fixed differences
• The two plaintexts can be chosen at random, as long as they satisfy the specific difference conditions
• Using the differences in the resulting cipher text pairs, assign likelihood to different keys
• As more and more cipher text pairs are analyzed, the correct key emerges

Linear Cryptanalysis

• A statistical known plaintext attack
• Correlation among pt, ct, key bits are exploited:
• Find a binary equation of pt, ct, key bits (“linear approximation”) which shows a non-trivial correlation among them (“bias”).
• Collect a large pt-ct sample.
• Try all key values with the collected pt-ct in the eq.�(hence, relatively few key bits must be involved.)
• Take the key that maximizes the bias as the right key.
• The remaining key bits can be found by brute force or by another LC attack.

​

Block Cipher design principles

• DES Design Criteria
• Number of Rounds
• Design of Function F

DES Design Criteria

• Design Criteria mainly focuses on the design of the S-boxes and P function taking output of the S-boxes
• Criteria for the S-boxes are as follows:
• No output bit of any S-box should be too close a linear function of the input bits
• Each row of an S-box should include all 16 possible output combinations
• If two inputs to an S-box differ in exactly one bit, the outputs must be differ in at least two bits

​

4. If two inputs to an S-box differ in the two middle bits exactly, the outputs must differ in at least two bits
5. If two inputs to an S-box differ in their first two bits and are identical in their last two bits, the two outputs must not be the same
6. For any nonzero 6-bit difference between inputs, no more than eight of the 32 pairs of inputs exhibiting that difference may result in the same output difference
7. This is a criterion similar to the previous one, but the case of three S-boxes

• The criteria for permutation P are as follows
• The four output bits from each S-box at round I are distributed so that two of them affect “middle bits” of round (i+1) and the other two bits affect end bits
• The four output bits from each S-box affect six different S-boxes on the next round, and no two affect the same S-box
• For two S-boxes j,k, if an output bit from Sj affects a middle bit of Sk, on the next round, then an output bit from Sk cannot affect a middle bit of Sj

Double DES and Triple DES

Double DES and Triple DES

• In Double DES, there would be two keys for encryption and decryption K1 and K2
• For a plaintext P, the cipher text is generated as

C = E(K2, E(K1,P))

• Decryption requires that the keys be applied in reverse order

P = D(K1, D(K2,C))

• For DES, this scheme apparently involves a key length of 56*2=112 bits, resulting in a dramatic increase in cryptographic change

Triple DES with two keys

• An obvious counter to the meet-in-the-middle attack is to use three stages of encryption with three different keys
• This raises the cost of the meet-in-the-middle attack to 2¹¹²
• It has the drawback of requiring a key length of 56*3=168 bits, which may be somewhat unwieldy
• As an alternative, Tuchman proposed a triple encryption method that uses only two keys
• The function follows encrypt-decrypt-encrypt(EDE) sequence

• C = E(K1, D(K2,E(K1,P)))
• P = D(K1,E(K2,D(K1,C)))
• There is no special meaning attached to the second step of decryption
• Its only significance is that it allows Triple DES to work with two, rather than three keys
• Currently, there are no practical cryptanalytic attacks on 3DES
• The cost of a brute-force key search on 3DES is on the order of 2¹¹² and estimates that the cost of differential cryptanalysis suffers an exponential growth, compared to single DES, exceeding 10⁵²

Modes of Operations

• Electronic Codebook(ECB)
• Cipher Block Chaining(CBC)
• Cipher Feedback(CFB)
• Output Feedback(OFB)
• Counter(CTR)

Electric Codebook Mode(ECB)

• Simplest mode of operation
• Incoming plaintext message is divided into blocks of 64 bits each and encrypted independently of other blocks
• For all blocks in a message, the same key is used for encryption
• At the receiver’s end, the incoming data is divided into 64-bits and by using the same key as was used for encryption, each block is decrypted to produce the corresponding output
• As the same key is used for all the messages, if the plaintext block repeats in the original message, the corresponding cipher text message will also repeat in the encrypted message
• Suitable for small messages

​

Cipher Block Chaining Mode(CBC)

• In ECB, if a plaintext block more than once in the input, the corresponding cipher text will also occur more than once in the output, providing some clues to the cryptanalyst
• CBC mode ensures that even if a block of plain text repeats in the input, these two identical blocks yield totally different cipher text blocks in the output
• It uses feedback mechanisms
• Here, the results of the encryption of the previous block are fed into the encryption of the current block
• Thus each block of cipher text is dependent on the corresponding current input plaintext block, as well as the previous plaintext blocks
• Here IV is simply used to make message unique
• It is randomly generated

Cipher Feedback Mode(CFB)

• It also uses 64-bit IV that is kept in a shift register. It is encrypted in the first step to produce a corresponding 64-bit IV cipher text
• Now the leftmost j bits of the encrypted IV are XORed with the first j bits of the plain text which produces first portion of the cipher text
• Now the contents of the shift register are shifted left by j positions. Thus the rightmost j positions of the shift register now contain unpredictable data. These rightmost bits are filled by C. this is repeated until all the plaintext units are encrypted

​

Output Feedback Mode(OFB)

• This mode is extremely same as CFB mode
• The difference is that in the case of CFB, the cipher text is fed into the next stage of the encryption process
• But in the case of OFB, the output of the IV or nonce is fed into the next stage of the encryption process
• The advantage is that it do not propagate the error, i.e. if any error occurs in any cipher text block Ci, it will not affect the other blocks
• The drawback is that an attacker can make necessary changes to the cipher text

Counter Mode(CTR)

• This mode is quite similar to the OFB mode, with one variation
• It uses sequence numbers as counters as inputs to the algorithm
• After each block is encrypted, to fill the register, the next counter value is used
• Usually, a constant is used as the initial counter value and it is incremented for every iteration
• The size of the counter block would be same as the plaintext block