Introduction to Symmetric Block Cipher Jing Deng Based on Prof. Rick

Introduction to Symmetric Block Cipher Jing Deng Based on Prof. Rick Han’s Lecture Slides Dr. Andreas Steffen’s Security Tutorial

Cryptography plaintext Encryption ciphertext Decryption plaintext Encryption algorithm also called a cipher Cryptography has evolved so that modern encryption and decryption use secret keys Cryptographic algorithms can be openly published Only have to protect the keys plaintext Encryption Key KA ciphertext Decryption Key KB plaintext

Symmetric-Key Cryptography plaintext Encryption Key KA ciphertext Decryption plaintext Key KB KA Secure Key Distribution Both sender and receiver keys are the same: K K A B The keys must be kept secret and securely distributed Thus, also called “Secret Key Cryptography” Data Encryption Standard (DES)

Cryptanalysis Brute force: try every key Ciphertext-only attack: Attacker knows ciphertext of several messages encrypted with same key (but doesn’t know plaintext). Possible to recover plaintext (also possible to deduce key) by looking at frequency of ciphertext letters Known-plaintext attack: Attackers observes pairs of plaintext/ciphertext encrypted with same key. Possible to deduce key and/or devise algorithm to decrypt ciphertext.

Cryptanalysis (2) Chosen-plaintext attack: Attacker can choose the plaintext and look at the paired ciphertext Attacker has more control than known-plaintext attack and may be able to gain more info about key Adaptive Chosen-Plaintext attack: Attacker chooses a series of plaintexts, basing the next plaintext on the result of previous encryption Examples Differential cryptanalysis – DES is resistant it Linear cryptanalysis Cryptanalysis attacks often exploit the redundancy of natural language Lossless compression before encryption removes redundancy

Examples Simple and non-secure ciphers – – – – Shift Cipher – Caesar Cipher Affine Cipher Vigenere Cipher Hill Cipher Information-secure cipher – One-Time Pad

Confusion and Diffusion plaintext Encryption Key KA ciphertext Decryption plaintext Key KB Terms courtesy of Claude Shannon, father of Information Theory “Confusion” Substitution a - b Caesar cipher “Diffusion” Transposition or Permutation abcd - dacb DES

Confusion and Diffusion (2) “Confusion” : a classical Substitution Cipher Courtesy: Andreas Steffen Modern substitution ciphers take in N bits and substitute N bits using lookup table: called S-Boxes

Confusion and Diffusion (3) “Diffusion” : a classical Transposition cipher Courtesy: Andreas Steffen modern Transposition ciphers take in N bits and permute using lookup table : called P-Boxes

Block Cipher Divide input bit stream into n-bit sections, encrypt only that section, no dependency/history between sections Courtesy: Andreas Steffen In a good block cipher, each output bit is a function of all n input bits and all k key bits

Example: DES Data Encryption Standard (DES) Encodes plaintext in 64-bit chunks using a 64-bit key (56 bits 8 bits parity) Uses a combination of diffusion and confusion to achieve security Was cracked in 1997 Parallel attack – exhaustively search key space Decryption in DES – it’s symmetric! Use K again as input and A then the same keys except in reverse order

Example: DES (2) DES 64-bit input is permuted 16 stages of identical operation differ in the 48-bit key extracted from 56-bit key complex R2 R1 is encrypted with K1 and XOR’d with L1 L2 R1, Final inverse permutation stage

Example: DES (3)

Beyond DES Triple-DES: put the output of DES back as input into DES again with a different key, loop again: 3*56 168 bit key Advanced Encryption Standard (AES) – Requirements: shall be designed so that the key length may be increased as needed. block size n 128 bits, key size k 128, 192, 256 bits – Candidates: MARS, twofish, RC6, Serpent, Rijndael – successor (Rijndael)

Encryption Mode (ECB) Electronic Code Book (ECB) mode for block ciphers of a long digital sequence Vulnerable to replay attacks: if an attacker thinks block C corresponds to 2 amount, then substitute another Ck Attacker can also build a codebook of C , guessed P pairs k k

Encryption Mode (CBC) Cipher Block Chaining (CBC) mode for block ciphers Inhibits replay attacks and codebook building: identical input plaintext P i Pk won’t result in same output code due to memory-based chaining IV Initialization Vector – use only once

Stream Cipher Stream ciphers Rather than divide bit stream into discrete blocks, as block ciphers do, XOR each bit of your plaintext continuous stream with a bit from a pseudorandom sequence At receiver, use same symmetric key, XOR again to extract plaintext

Encryption Mode (OFB)