CSC 316 Chapter 2b, Fall 2007

Chapter 2 Basic Encryption and Decryption (part B) Transpositions (Permutations) • P.52 • Transposition: an encryption in which the letters of the message are rearranged • Also known as permutations • Compare the goals: – Substitution  confusion – Transposition  diffusion Confusion vs Diffusion • Confusion: making it difficult to determine how a message and key were transformed into ciphertext. • Diffusion: spreading the information from the message or the key out widely across the ciphertext • See p.62 for more discussions. Columnar Transpositions • A rearrangement of the plaintext characters into columns. • The ciphertext is generated from the columns. • Example: p.53 Complexity of Columnar Transpositions • Time: proportional to the length of the message, that is, O(n) or at the order of function n. • Space: depends on the length of the message. • Output cannot be produced until all characters of the message have been read. • Initial delay varies, depending on the length of the message. C.f., constant initial delay in the previous (substitution) algorithms. Digrams, Trigrams, & Other Patterns • Digrams: groups of two letters • Trigrams: groups of three letters • Table 2-2 (p.54): Most Frequent digrams an Trigrams Note: not counting digrams that consist of the last letter of one word and the first letter of the next word. Cryptanalysis by Digram Analysis 1. To compute the letter frequencies o Clue: The fact that all letters appear with their normal frequencies implies that a transposition has been performed. o (Same IC as monoalphabrtic 0.068 same distribution graph as plaintext English) 2. To find where in the ciphertext a pair of adjacent columns lies (that is, to determine the width of a row in the original table used for encryption) o The ‘moving window’ method: Fig. 2-5 (p.56) The ‘moving window’ method 1. Pick a window size, say n. 2. Compare every Ci, 1  i  n ,in the window to Ci+n and determine if the two form a common digram by checking their frequency. 3. Do most of the digrams look reasonable? Compute their mean and std. deviation The ‘moving window’ method Double transposition (P.51) • Involves two columnar transpositions • An example of product ciphers, in which one encryption is applied to the result of another C = E2 (E1 (P) ) Fractionated Morse • A keyed monoalphabetic cipher • Uses Morse code as its base • Double encodings (P  Morse code  P’) • 3 steps: 1. Convert P to Morse code, using separator(s) between letters and words. 2. Divide the Morse code messages into blocks of 3 symbols. 3. Each block of symbols is encoded as the letter corresponding to that 3-symbol pattern Stream versus Block Ciphers • Stream ciphers: The plaintext characters are encoded by the sender letter-by-letter as sent to the receiver. – Example: substitution ciphers • Block ciphers: Blocks of plaintext are encoded into ciphertext before being sent. – Example: columnar transposition Stream Ciphers + Fast + Little storage space + Low error propagation, meaning that encoding errors affect just one character in the ciphertext - low diffusion, meaning that individual characters in the ciphertext can be analyzed using frequency distribution, digram analysis, IC and the Kasiski method - Susceptibility to malicious insertions and modifications Block Ciphers - Slow - Require more storage space - Error propagation + High diffusion + High immunity to insertions 4 cryptanalysis cases & 5 approaches 1. Ciphertext only Ciphertext-only attack 2. Full or partial plaintext Known plaintext attack Probable plaintext analysis 3. Ciphertext of any plaintext Chosen plaintext attack 4. Algorithm + Ciphertext Chosen ciphertext attack Complete listing of examples of cryptanalysis methods • Brute Force • Known Plaintext • Chosen Plaintext • Adaptive Chosen Plaintext • Ciphertext only • Chosen Ciphertext • Adaptive Chosen Ciphertext • Meet in the Middle • Differential Cryptanalysis • Linear Cryptanalysis • Differential Linear Cryptanalysis • Factoring • Statistical Data Encryption Standard (DES) • 1976: officially adopted as a U.S. federal standard • Was authorized for use on all public and private sector unclassified communication • Later became an international standard by the ISO • The strength of DES comes from repeated application of the two encryption techniques, substitution and permutation, one on top of the other, for a total of 16 cycles. • Product cipher: C = E2 ( E1(P) ) • A secret key method Chronology • 1976 DES is approved as a standard • 1977 DES is published as a FIPS standard FIPS PUB 46 • 1992 Biham and Shamir report the first theoretical attack with less complexity than brute force (differential cryptanalysis). However, it requires an unrealistic 247 chosen plaintexts. • 1993 DES is reaffirmed for the third time as FIPS 46-2 • June1997 The DESCHALL Project breaks a message encrypted with DES for the first time in public. • July1998 The EFF's DES cracker (Deep Crack) breaks a DES key in 56 hours. • January1999 DES key in 22 hours and 15 minutes.25 October • 1999 DES is reaffirmed for the fourth time as FIPS 46-3, which specifies the preferred use of Triple DES, with single DES permitted only in legacy systems. • 2001 The Advanced Encryption Standard is published in FIPS 197 • 2002 The AES standard becomes effective • 2004 The withdrawal of FIPS 46-3 (and a couple of related standards) is proposed in the Federal Register [2]19 May2005NIST withdraws FIPS 46-315 March • 2007 The FPGA based parallel machine of the University of Bochum and Kiel, Germany, breaks DES in 6.4 days at $10,000 hardware cost Data Encryption Standard (DES) • 16 cycles of substitutions and permutations: Fig.10-7 (p.647) • Steps in a single cycle: Fig. 647, Fig. 10-9 Operates on blocks of data: 64 bits per block Splits a data block in half: left half, right half (32 bits) Scrambles each half independently: shifted left, permuted Combines the key with the right half: the result is then combined with the left half Swaps the two halves: T = right half; right half += key; right half += left half; left half = T. Data Encryption Standard (DES) (1 CYCLE) Key Transformation • 64-bit key, but only 56 of the bits are used (bits 8, 16, 24, 32, 40, 48, 56, 64 are parity bits) • At each step, the key is split into two 28-bit halves. • The halves are shifted by a specified number of digits (Table 10-2, p.651), pasted together again, and then 48 of these 56 bits are permuted as a key during this step (choice permutation: Table 10-3 P. 651). • How to combine a 32-bit right half with a 56-bit key? p.649: Fig. 10-11 Expansion permutation: The 32-bit half is expanded to 48 bits by repeating certain bits See Table 10-1 p.649 Permuted choices: The 56-bit key is reduced to 48 bits by choosing only certain bits • Fig. 10-11: a detailed single cycle Data Encryption Standard (DES) Substitutions and S-boxes • An S-box is a table in which 6 bits of data are replaced by 4 bits. • The 48-bit input is divided into eight 6-bit blocks  8 S-boxes for substitutions (Table 10-4, p.652) • Substitutions by S-boxes S-box substitutions • Use Table 10-4 • Input: Bj = 6 bits (b1 b2 b3 b4 b5 b6) • Output: a 4-bit binary number • Process: 1. r = b1 b6 2. c = b2 b3 b4 b5 3. result = the value at (r, c) of the S-box j (Sj) of Table 3- 6. 4. Convert the result to a binary number. S-box substitutions • Example: p.650 Input = Bj = B7 = 010011b r = 01b = 1 c = 1001b = 9 result = (r, c) = (1, 9) in S7 = 3 = 0011b • Suppose the Input = B4 = 101010b. What’s the output of the substitution? P-box permutations • Permutations: Initial permutation Permutation in each cycle Final inverse permutation • inverse & final permutations: Table 3-8, 3-9, p.110 • Per-cycle permutation: p.653: Table 10-5 Examples Bit 1  bit 9 Bit 23 bit 11 Bit 19  ? Bit 27  ? Summary of DES Encryption • Input = (64-bit data block, 64-bit key) • process 64-bit key  56 bits Initial permutation 16 cycles: Key transformation (split, shift, permuted) Data blocks substitution & permutation Lj = Rj-1 ; Rj = Lj-1 XOR f(Rj-1, kj) S-boxes, P-boxes Final permutation • Output = 64-bit ciphertext DES Decryption • Encryption: (Lj-1 , Rj-1)  (Lj , Rj) Lj = Rj-1 ; Rj = Lj-1 XOR f(Rj-1, kj) • Decryption: (Lj , Rj)  (Lj-1 , Rj-1) Rj-1 = Lj Lj-1 = Rj XOR f(Lj, kj) • Reverse key transformation