Block Cipher Principles: Stream Ciphers, Feistel Cipher, DES, AES
Module 3 – Block Cipher Principles – Stream Ciphers and Block Ciphers, Feistel Cipher, Feistel Decryption algorithm, The Data Encryption Standard, DES Decryption – Avalanche effect, The AES Cipher, substitute bytes transformation, Shift row transformation, Mix Column Transformation
Stream Ciphers and Block Ciphers: A stream cipher encrypts a digital data stream one bit or one byte at a time. ★ Examples of classical stream ciphers are the auto keyed Vigenère cipher and the Vernam cipher. A block cipher treats a block of plaintext as a whole and produces a ciphertext block of equal length. Typically, a block size of 64 or 128 bits is used
Block Cipher: There are a vast number of block cipher schemes in use. Many of them are publicly known. Most popular and prominent block ciphers are listed below. Digital Encryption Standard (DES) – The popular block cipher of the 1990s. It is now considered as a ‘broken’ block cipher, due primarily to its small key size. Advanced Encryption Standard (AES) – It is a relatively new block cipher based on the encryption algorithm Rijndael that won the AES design competition.
Feistel Cipher Feistel Cipher is not a specific scheme of block cipher. ➢ It is a design model from which many different block ciphers are derived. ➢ DES is just one example of a Feistel Cipher. ➢ A cryptographic system based on Feistel cipher structure uses the same algorithm for both encryption and decryption
Encryption Process The encryption process uses the Feistel structure consisting of multiple rounds of processing of the plaintext, each round consisting of a “substitution” step followed by a “permutation” step ,the input block to each round is divided into two halves that can be denoted as L and R for the left half and the right half ❖ In each round, the right half of the block, R, goes through unchanged. But the left half, L, goes through an operation that depends on R and the encryption key. ❖ First, we apply an encrypting function ‘f’ that takes two inputs − the key K and R. The function produces the output f(R,K). Then, we XOR the output of the mathematical function with L. ❖ In real implementation of the Feistel Cipher, such as DES, instead of using the whole encryption key during each round, a round-dependent key (a subkey) is derived from the encryption key. This means that each round uses a different key, although all these subkeys are related to the original key. ❖ The permutation step at the end of each round swaps the modified L and unmodified R. Therefore, the L for the next round would be R of the current round. And R for the next round will be the output L of the current round. ❖ Above substitution and permutation steps form a ‘round’. The number of rounds are specified by the algorithm design.❖ Once the last round is completed then the two sub blocks, ‘R’ and ‘L’ are concatenated in this order to form the ciphertext block
Decryption Process ★ The process of decryption in Feistel cipher is almost similar. Instead of starting with a block of plaintext, the ciphertext block is fed into the start of the Feistel structure and then the process thereafter is exactly the same as described in the given illustration. ★ The process is said to be almost similar and not exactly the same. In the case of decryption, the only difference is that the subkeys used in encryption are used in the reverse order. ★ The final swapping of ‘L’ and ‘R’ in the last step of the Feistel Cipher is essential. If these are not swapped then the resulting ciphertext could not be decrypted using the same algorithm.
Data Encryption Standard (DES Encryption & Decryption) ★ The algorithm is designed to encipher and decipher blocks of data consisting of 64 bits under control of a 64-bit key ★ A block to be enciphered is subjected to an initial permutation IP and then to a complex key-dependent computation and finally to a permutation which is the inverse of the initial permutation IP-1 ★ First, the 64-bit plaintext passes through an initial permutation(IP) that rearranges the bits to produce the permuted output. ★ This is followed by a phase consisting of 16 rounds of the same function, which involves both permutation and substitution function. ★ The output of the last round consists of 64 bits that are a function of the input plain text and the key. ★ The left and right halves of the output are swapped to produce the pre output. ★ Finally, the pre output is passed through a permutation that is inverse of the initial permutation function,to produce the 64-bit cipher text. ★ The right hand portion of the figure 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 different subkeys are produced because of the repeated shifts of the key bits.
Avalanche effect DES Analysis, The DES satisfies both the desired properties of block cipher. These two properties make cipher very strong. ❖Avalanche effect − A small change in plaintext results in a very great change in the ciphertext. ❖Completeness − Each bit of ciphertext depends on many bits of plaintext. ❖Avalanche effect ❖A small change in plaintext results in a very great change in the ciphertext. ❖it quantifies the effect on the cipher-text with respect to the small change made in plain text or the key Eg : Plain Text : 0000 0000 0000 0000 Cipher Text: 34A2 05DC A34B C32A ★ If a cryptographic algorithm does not exhibit the avalanche effect, then a cryptanalyst can analyze the ciphertext and make predictions about the plaintext. ★ The avalanche effect is significant to prevent cryptanalysts from making predictions about the input partially or entirely. AES (Advanced Encryption Standard): ★ AES is a symmetric block cipher ★ designed by Rijmen-Daemen in Belgium ★ has 128/192/256 bit keys, 128 bit data ★an iterative rather than feistel cipher ★ treats data in 4 groups of 4 bytes ★ operates an entire block in every round
The four stages are as follows: AddRoundKey •Each round uses four different words from the expanded key array. •Each column in the state matrix is XORed with a different word. •The heart of encryption. All other functions’ properties are permanent and known to all.InvAddRoundKey :•Key is used in reverse order Substitution Byte (Subbyte) :★ It is a bytewise lookup process that returns a 4-byte word in which each byte is the result of applying the Rijndael S-box. ★ Simple substitution of each byte using one table of 16×16 bytes containing a permutation of all 256 8-bit values ★ each byte of state is replaced by byte in row (left 4-bits) & column (right 4-bits) ★ eg. byte {95} is replaced by row 9 col 5 byte which is the value {2A} Shift Rows :•a circular byte shift in each row –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 does shifts to right •since state is processed by columns, this step permutes bytes between the columns Mix Columns ❖ This stage (known as MixColumn) is basically a substitution but it makes use of arithmetic of GF(2^8). ❖ Each column is operated on individually. Each byte of a column is mapped into a new value that is a function of all four bytes in the column. ❖ The transformation can be determined by the following matrix multiplication on state 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 
•Each of the 16 rounds consists of, key transformation Expansion Permutation S- box substitution P- box permutation XOR and Swap
1.Key transformation •The initial 64-bit key is transformed into a 56- bit key by discarding every 8th bit of the initial key. • From this 56 key, a different 48-bit sub key is generated during each round using the process called key transformation. •For this, the 56 key is divided into two halves, each of 28 bits. These halves are circularly shifted left by one or two positions, depending on the round 2. Expansion Permutation After initial permutation,we had two 32 bit plain text areas, Left Plain Text and Right Plain Text. During Expansion permutation, the RPT is expanded from 32 bits to 48 bits, the bits are permuted as well. 1. The 32 bit RPT is divided into 8 blocks, with each block consisting of 4 bits. 2. Each 4 bit block of the previous step is expanded to a corresponding 6 bit block. 3. S- box substitution It is a process that accepts the 48 bit input from the XOR operation involving the compressed key and expanded RPT and produces a 32 bit output using the substitution technique. The substitution is performed by eight substitution boxes (s boxes). Each of the eight S boxes has 6 bit input and a 4 bit output. The 48 bit input block is divided into 8 sub blocks and each such sub block is given to an S box . P- box permutation The output of the S- box consists of 32 bits. These 32 bits are permuted using a P- box. A 16 in the first block indicates that the bit at the position 16 of the original input moves to bit at position 1 in the output. XOR and SWAP ● The left half portion of the initial 64 bit plain text block is KMEA ENGINEERING COLLEGE XORed with the output produced by P- box permutation.The result of this XOR operation becomes the new right half. ● The old right half becomes the new left half, in a process of swapping.Final Permutation:●At the end of the 16 rounds, the final permutation is performed. ● This is simple transposition, the 40th input bit takes the position of the 1st output bit and so on DES Decryption : The same algorithm used for encryption in DES also works for decryption. ●The values of the various tables and the operations as well as the sequence are carefully chosen so that the algorithm is reversible. ●The only difference between the encryption and decryption process is the reversal of key portions. ●If the original key K was divided into K1, K2….K16 for the 16 encryption rounds, then for decryption, the key should be used as K16, K15…K1.
Module 5: Message Authentication and Hash Function Authentication requirements, Authentication functions- Message Encryption, Public Key Encryption, Message Authentication Code, Hash function Message authentication is a mechanism or service used to verify the integrity of a message. Message authentication assures that data received are exactly as sent by (i.e., contain no modification, insertion, deletion, or replay) and that the purported identity of the sender is valid. 1. Authentication requirements Authentication Requirements In the context of communications across a network, the following attacks can be identified: 1. Disclosure: Release of message contents to any person or process not possessing the appropriate cryptographic key. 2. Traffic analysis: Discovery of the pattern of traffic between parties. 3. Masquerade: Insertion of messages into the network from a fraudulent source. 4. Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and modification. 5. Sequence modification: Any modification to a sequence of messages between parties, including insertion, deletion, and reordering.6. Timing modification: Delay or replay of messages. 7. Source repudiation: Denial of transmission of message by source. 8. Destination repudiation: Denial of receipt of message by destination.2. Message Authentication Functions there must be some sort of function that produces an authenticator: a value to be used to authenticate a message. message authentication is concerned with: ❖protecting the integrity of a message ❖validating identity of originator ❖non-repudiation of origin .three functions used: 1. message encryption : The ciphertext of the entire message serves as its authenticator 2. message authentication code (MAC): A function of the message and a secret key that produces a fixed-length value that serves as the authenticator 3. hash function: A function that maps a message of any length into a fixed-length hash value, which serves as the authenticator 1. Message Encryption ➔message encryption by itself also provides a measure of authentication a)symmetric encryption➔if symmetric encryption is used then: • receiver know sender must have created it • since only sender and receiver now key used • So, content cannot of been altered • Provides both: sender authentication and message authenticity.b)public-key encryption
➔if public-key encryption is used: ● encryption provides no confidence of sender ● since anyone potentially knows public-key ➔however if ◆ sender signs message using his private-key ◆ then encrypts with recipients public key ◆ have both secrecy and authentication. Consider the straightforward use of symmetric encryption (Figure 11.1a). A message M transmitted from source A to destination B is encrypted using a secret key K shared by A and B. If no other party knows the key, then confidentiality is provided: No other party can recover the plaintext of the message.
it provides confidentiality but not authentication. The source (A) uses the public key PUb of the destination (B) to encrypt M. Because only B has the corresponding private key PRb, only B can decrypt the message. This scheme provides no authentication because any opponent could also use B’s public key to encrypt a message, claiming to be A. To provide authentication, A uses its private key to encrypt the message, and B uses A’s public key to decrypt (Figure 11.1c). This provides authentication using the same type of reasoning as in the symmetric encryption case: The message must have come from A because A is the only party that possesses PRa and therefore the only party with the information necessary to construct ciphertext that can be decrypted with PUa. To provide both confidentiality and authentication, A can encrypt M first using its private key, which provides the digital signature, and then using B’s public key, which provides confidentiality Message Authentication Code (MAC) a small fixed-sized block of data: ○ depends on both message and a secret key ○ like encryption though need not be reversible ○ appended to message as a signature • receiver performs same computation on message and checks it matches the MAC • provides assurance that message is unaltered and comes from sender Message Authentication Code This technique assumes that two communicating parties, say A and B, share a common secret key K. When A has a message to send to B, it calculates the MAC as a function of the message and the key MAC = C(K,M), where M= input message C=MAC function K= shared secret key • MAC provides authentication • Message can be encrypted for secrecy generally use separate keys for each can compute MAC either before or after encryption. Requirements for MACS MAC needs to satisfy the following: 1. knowing a message and MAC, is infeasible to find another message with same MAC 2. MACS should be uniformly distributed 3. MAC should depend equally on all bits of the message .Hash Functions A hash function is like a MAC ★ hash value h is generated by a function H of the form h = H (M) M is a variable-length message and H(M) is the fixed-length hash value. ➔usually assume that the hash function is public and not keyed ➔note that a MAC is keyed ● hash used to detect changes to message ● can use in various ways with message ● most often to create a digital signature Hash Functions & Digital Signatures Only the hash code is encrypted, using public-key encryption and using the sender’s private key. As with (b), this provides authentication. It also provides a digital signature. a. The message plus concatenated hash code is encrypted using symmetric encryption. Because only A and B share the secret key, the message must have come from A and has not been altered. The hash code provides the structure or redundancy required to achieve authentication. Because encryption is applied to the entire message plus hash code, confidentiality is also provided.
b. Only the hash code is encrypted, using symmetric encryption. This reduces the processing burden for those applications that do not require confidentiality. E(K, H(M)) is a function of a variable-length message M and a secret key K, and it produces a fixed-size output that is secure against an opponent who does not know the secret key. c. Only the hash code is encrypted, using public-key encryption and using the sender’s private key. As with (b), this provides authentication. It also provides a digital signature, because only the sender could have produced the encrypted hash code. In fact, this is the essence of the digital signature technique. d. If confidentiality as well as a digital signature is desired, then the message plus the private-key- encrypted hash code can be encrypted using a symmetric secret key. This is a common technique. e. It is possible to use a hash function but no encryption for message authentication. f. Confidentiality can be added to the approach of (e) by encrypting the entire message plus the hash code
Requirements for Hash Functions 1. can be applied to any size message M 2. produces a fixed-length output h 3. easy to compute h=H (M) for any message M 4. given h is infeasible to find x s.t. H (x)=h 5. given x is infeasible to find y s.t. H(y)=H(x) 6. is infeasible to find any x, y s.t. H(y)=H
Module 2 Groups A group G, sometimes denoted by {G, ·} is a set of elements with a binary operation, denoted by · ,that associates to each ordered pair (a, b) of elements in G an element (a · b) in G, such that the following axioms are obeyed:
(A1) Closure: If a and b belong to G, then a · b is also in G. (A2) Associative: a · (b · c) = (a · b) · c for all a, b, c in G. (A3) Identity element: There is an element e in G such that a · e = e · a = a for all a in G. (A4) Inverse element: For each a in G there is an element a’ in G such that a · a’ = a’ · a = e. A group is said to be abelian if it satisfies the following additional condition: (A5) Commutative: a · b = b · a for all a, b in G. Rings :A ring R, sometimes denoted by {R, +, x}, is a set of elements with two binary operations, called addition and multiplication, such that for all a, b, c in R the following axioms are obeyed: (A1-A5) R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. (M1) Closure under multiplication: If a and b belong to R, then ab is also in R. (M2) Associativity of multiplication: a(bc) = (ab)c for all a, b, c in R. (M3) Distributive laws: a(b + c) = ab + ac for all a, b, c in R. (a + b)c = ac + bc for all a, b, c in R. A ring is said to be commutative if it satisfies the following additional condition: (M4) Commutativity of multiplication: ab = ba for all a, b in R. A ring is said to be integral domain, which is a commutative ring that obeys the following axioms: (M5) Multiplicative identity: There is an element 1 in R such that a1 = 1a = a for all a in R. (M6) No zero divisors: If a, b in R and ab = 0, then either a = 0 or b = 0. Fields : A field F, sometimes denoted by {F, +, x}, is a set of elements with two binary operations, called addition and multiplication, such that for all a, b, c in F the following axioms are obeyed: (A1-M6) F is an integral domain; that is, F satisfies axioms A1 through A5 and M1 through M6. (M7) Multiplicative inverse: For each a in F, except 0, there is an element a -1 in F such that aa -1 = (a -1 )a = 1.
Module 4: RSA ALGORITHM :RSA algorithm is a public key encryption technique and is considered as the most secure way of encryption. It was invented by Rivest, Shamir and Adleman in year 1978 and hence name RSA algorithm. 1. Select two prime numbers, p = 17 and q = 11. 2. Calculate n = pq = 17 x 11 = 187. 3. Calculate φ(n) = (p – 1)(q – 1) = 16 x 10 = 160. 4. Select e such that e is relatively prime to φ(n) = 160 and less than φ(n) we choose e = 7. 5. Determine d such that de = 1 (mod 160) and d Euler’s theorem Euler’s theorem states that for every a and n that are relatively prime {gcd(a,n) = 1}: a φ(n) ≡ 1 (mod n) Fermat’s theorem: Fermat’s theorem states the following: If p is prime and a is a positive integer not divisible by p, then 1. a P-1 ≡ 1 (mod p) a P-1 (mod p) = 1 2. a P ≡ a (mod p) a P (mod p) = a