An Introduction to Cryptography - courses.cs.washington.edu

An Introduction to Cryptography - courses.cs.washington.edu

University of Washington CSEP 590TU Practical Aspects of Modern Cryptography Instructors: Josh Benaloh, Brian LaMacchia, John Manferdelli Tuesdays: 6:30-9:30, Allen Center 305 Webpage: http://www.cs.washington.edu/education/courses/csep590/06wi/ Recommended texts: Stinson, Cryptography, Theory and Practice. 2nd Edition, CRC Press, 2002. Menezes, vanOrtshot, Vanstone. Handbook of Applied Cryptography. Ferguson and Schneier, Practical Cryptography. JLM 20060107 22:16 1 New Lecture Schedule Date Topic Lecturer 1 1/3 Practical Aspects of Cryptography Josh 2

1/10 Symmetric Key Ciphers and Hashes John 3 1/17 Public Key Ciphers Josh 4 1/24 Cryptographic Protocols I Brian 5 1/31 Cryptographic Protocols II Brian 6

2/7 Security of Block Ciphers John 7 2/14 AES and Cryptographic Hashes John 8 2/21 Trust, PKI, Key Management [Last HW Assignment) Brian 9 3/1 Random Numbers/Elliptic Curve Crypto Josh 10

3/8 Three topics: Elections, ITAR/Politics, Side Channels/Timing Attacks, DRM, BigNum Implementation All JLM 20060107 22:16 2 Symmetric Key Cryptography and Cryptographic Hashes - I John Manferdelli [email protected] [email protected] Portions 2004-2005, John Manferdelli. This material is provided without warranty of any kind including, without limitation, warranty of non-infringement or suitability for any purpose. This material is not guaranteed to be error free and is intended for instructional use only. JLM 20060107 22:16 3 Communications Engineers Coat of Arms The Source Sender: Alice Compress Plaintext

(P) Noisy insecure channel (to save space) Noisy insecure channel Encode Encrypt (for confidentiality) (to correct errors) The Sink Receiver:Bob Decode (to correct errors) JLM 20060107 22:16 Decrypt (for confidentiality) Decompress (to save space) Plaintext (P)

4 Symmetric Encryption Plaintext (P) Key (k) Encrypt Ek(P) Ciphertext (C) Ciphertext (C) Key (k) Decrypt Dk(P) Plaintext (P) Symmetric Key cryptographic algorithms use a secret known to the authorized parties called a key. Encryption and Decryption use the same key. The transformations are simple and fast enough for practical use and implementation. Keyspace large enough to protect against exhaustive search. The encryption algorithm must be efficiently invertible. Two major types: Stream ciphers and Block ciphers JLM 20060107 22:16 5 Why go Ugly? Algorithm

Speed RSA-1024 Encrypt .32 ms/op (128B), 384 KB/sec RSA-1024 Decrypt 10.32 ms/op (128B), 13 KB/sec AES-128 .53 s/op (16B), 30MB/sec RC4 .016 s/op (1B), 63 MB/sec DES .622 s/op (8B), 12.87 MB/sec RSA implementation uses CRT, Karasuba and Montgomery. Timings do not include setup. All results are for an 850MHz x86. JLM 20060107 22:16 6 Ugly II Algorithm Speed

SHA-1 48.46 MB/sec SHA-256 24.75 MB/sec SHA-512 8.25 MB/sec Timings do not include setup. All results are for an 850MHz x86. JLM 20060107 22:16 7 Ugly III Symmetric Key Size RSA/DH Key Size Elliptic Curve Key Size 80 1024 160

112 2048 224 128 3072 256 192 8192 384 256 15360 521 JLM 20060107 22:16 8 Suite B - Computation Cost Symmetric Key Size JLM 20060107 22:16

Ratio RSA/DH:EC 80 3:1 112 6:1 128 10:1 192 32:1 256 64:1 9 Adversaries and their Discontents Wiretap Adversary Bob Eve Alice Plaintext (P)

Decrypt Encrypt Channel Plaintext (P) Man in the Middle Adversary Alice Plaintext (P) Bob Encrypt Mallory Decrypt Plaintext (P) Channel JLM 20060107 22:16 10 Adversaries Cryptography is computing/communicating in the presence of an Adversary An Adversarys strength is characterized by:

Computational resources available to the adversary: Exponential time/memory Polynomial time/memory Nature of access to cryptographically protected data: Probable plaintext attacks Known plaintext/ciphertext attacks Chosen plaintext attacks Adaptive interactive chosen plaintext attacks (oracle model) Physical Access Outsider threat Insider Threat (Timing, side channels) Trusted Insider Threat (Some key access) JLM 20060107 22:16 11 Cipher Requirements WW II Universally available (simple, light instrumentation) - interoperability Compact , rugged: Easy for people to use Security in key only: We assume that the attacker knows the complete details of the cryptographic algorithm and implementation Adversary has access to some corresponding plain and ciphertext Now

Adversary has access to unlimited ciphertext and lots of chosen text Implementation in digital devices (power/speed) paramount Easy for computers to use Resistant to ridiculous amount of computing power JLM 20060107 22:16 12 Practical Attacks Exhaustive Search of Key space Exhaustive Search of Keyspace Restricted by poor practice. For example non random key generation Exploiting bad key Management/Storage Bribing Keyholder Side Channel/Timing Exploiting encryption Errors Spoofing (ATM PIN) Leaking due to size, position, language choice, repetition, frequency, intersymbol transitions

JLM 20060107 22:16 13 Some Formal Attack Requirements Indistinguishability: Given two messages and the encryption of one of the messages (the target ciphertext), it is hard to determine which message is encrypted Related to Semantic Security Non-Malleability : Given a target ciphertext y, it is hard to find another ciphertext y such that the corresponding plaintexts are meaningfully related JLM 20060107 22:16 RSA Slide --- Key Management 14 Security In Practice Balances risk of loss, usability and operational efficiency against costs Risk assessed against known threat and absolute computing model. (e.g.- Linear cryptanalysis in 243 steps rather that O(f(n))). This requires an intelligent assessment of each problem case and computing/communication environment. The greatest threat to good security is the insistence on perfect security.

JLM 20060107 22:16 15 Block Cipher In a block cipher, plaintext is encrypted in blocks of m elements of the alphabet. In the binary block case, m is the block length in bits and Ek: P C where P=C= {0,1,, 2m-1}. Since Ek is invertible, Ek SN, the permutations on N = 2m elements. Thus Ek: k SN. Think of k as selecting an element from SN , which is enormous. | SN| = N! (2 N) (N/e)N. For example, in DES, the keyspace has N=256 elements, SN has more than (264)N elements which is way, way more than the number of elementary particles in the universe JLM 20060107 22:16 16 Block Ciphers: Modes ECB : ci= Ek(pi)

Same plaintext gets same ciphertext anywhere in stream Not semantically secure All other modes safer for long communications. CBC: c0 = IV, ci= Ek(pi+ci-1) Errors propagate two blocks Cant use parrallel HW or pre-processing, slower OFB: z0 = IV, zi= Ek(zi-1), ci= pi + zi Limited error propagation CFB: c0 = IV, zi= Ek(ci-1), ci= pi + zi Error propagates for a few blocks but self-synchronizing CTR: zi= Ek(nonce || i), ci= pi + zi Never reuse nonce key combination Current favorite: fast, random access, allows preprocessing, similar security to CBC JLM 20060107 22:16 17 Stream Cipher Definition and Example A Stream Cipher takes an arbitrary sequence of elements from the (plaintext) input alphabet to the (ciphertext) output alphabet. Example for the binary alphabet: Let mt represents the bits of the plaintext, t =1,2, Let kt be bits selected from a random source, t =1,2,

Let ct represent the ciphertext bits. ct= mt kt defines a self-reciprocal (self inverting) stream cipher called a one-time pad. You cant beat one time pads for security (can you spot why they are seldom used?) JLM 20060107 22:16 18 The Manual Ciphers Simple Transposition: Grilles, columnar transpositions. Monoalphabetic Substitution: Caesar, simple substitution Polyalphabetic substitution: Vigeniere Polygraphic substitution Hill, Playfair Additional Reference : Army cryptanalysis manual, http://www.umich.edu/~umich/fm-34-40-2/ JLM 20060107 22:16 19

Group Theory in Cryptography - 1 Groups are sets of elements that have a binary operation with the following properties: 1. 2. 3. If x,y,z G, xy G and (xy)z=x(yz). It is not always true xy=yx. There is an identity element 1 G and 1x=x1=x for all x in G For all, x in G there is an element x-1 G and x x-1 =1= x-1 x One very important group is the group of all bijective maps from a set of n elements to itself denoted Sn or n. These are called the permutations of n elements. The binary operation is the composition of mappings. The identity element leaves every element alone. The inverse of a mapping, x, undoes what x does. If Sn and the image of x is y we can write this two ways: y= (x); this is the usual functional notation your used to where mappings are applied from the left. When mappings are applied from the left and and are elements of Sn denotes the mapping obtained by applying first and then - i.e. y= (x)). Some people apply mappings from the right. They would write y=(x) For them, denotes the mapping obtained by applying

first and then - i.e. y= ((x). JLM 20060107 22:16 20 Group Theory in Cryptography - 2 The smallest k such that k=1 is called the order of . G is finite if it has a finite number of elements. In a finite group, all elements have finite order and the order of each element divides the number of elements of G (Lagranges Theorem). Example. Let G= S4. = 12, 23, 34, 41, = 13, 24, 31, 42. = 14, 21, 32, 43 Applying mappings from the left, = 14, 21,32,43. Sometimes is written like this: = 1 2 3 4 2 3 4 1 Sometimes permutations are written as products of cycles: =(1234)and (13)(24). JLM 20060107 22:16 21 Transpositions Grilles B U L L W I N K L E I S A D O P E

BWLAEUINEDLNIOLKSP ci= pS(i) where S=(1)(2,5,17,16,12,11,7,6)(3,9,14,4,13,15,8,10) JLM 20060107 22:16 22 Breaking Completely filled Columnar Transposition Message (from Sinkov) EOEYE GTRNP SECEH HETYH SNGND DDDET OCRAE RAEMH TECSE USIAR WKDRI RNYAR ABUEY ICNTT CEIET US Procedure 1. Determine rectangle dimensions (l,w) by noting that message length=m = l x w. Here m=77, so l=7, w=11 or l=11, w=7 2. Anagram to obtain relative column positions Note a transposition is easy to spot since letter frequency is the same as regular English. JLM 20060107 22:16 23 Anagramming Look for words, digraphs, etc. Note: Everything is very easy in corresponding plain/ciphertext attack

1 E O E Y E G T R N P S 2 E C E H H E T Y H S N 3 G N D D D D

E T O C R 4 A E R A E M H T E C S 5 E U S I A R W K D R I JLM 20060107 22:16

6 R N Y A R A N U E Y I 7 C N T T C E I E T U S 3 G N D

D D D E T O C R 6 R N Y A R A N U E Y I 1 E O E Y E G T R N P

S 5 E U S I A R W K D R I 7 C N T T C E I E T U S 2 E C E H

H E T Y H S N 4 A E R A E M H T E C S 24 Alphabetic Substitution A monoalphabetic cipher maps each occurrence of a plaintext character to one ciphertext character A polyalphabetic cipher maps each occurrence of a plaintext character to more than one ciphertext character A polygraphic cipher maps more than one plaintext character at a time Groups of plaintext characters are replaced by assigned groups of ciphertext characters JLM 20060107 22:16

25 Et Tu Brute?: Substitutions Caeser Cipher B U L L W I N K L E I S A D O P E D W N N Y K P M N G K U C F Q S G c= pCk, C= (ABCDEFGHIJKLMNOPQRSTUVWXYZ), k= 2 here k=3 for classical Caeser JLM 20060107 22:16 26 Attacks on Monoalphabetic Substitution Letter Frequency A E I M Q U Y .0651738 .1041442 .0558094 .0202124 .0008606 .0225134 .0145984

B F J N R V Z .0124248 .0197881 .0009033 .0564513 .0497563 .0082903 .0007836 C G K O S W sp .0217339 .0158610 .0050529 .0596302 .0515760 .0171272 .1918182 D

H L P T X .0349835 .0492888 .0331490 .0137645 .0729357 .0013692 Probable word. Corresponding plain/cipher text makes this trivial. JLM 20060107 22:16 27 Polygraphic Frequencies Bigraphs EN ON ST ND RE IN ED TO ER TE

NE SE NT AN VE AT TH OR ES TI ION FOR AND OUR ING THI IVE ONE OF THAT AS BE YOU AND IS

WITH NOT WHICH TO I WAS BY ARE A IT HIS BUT ON Trigraphs ENT TIO Words THE IN FOR HE HAVE JLM 20060107 22:16 28 Letter Frequency Bar Graph

JLM 20060107 22:16 29 Letter Frequency Bar Graph Letter Frequency a b 60 c d e f 50 g h i 40 j C ou nt k l m

30 n o p 20 q r s 10 t u v w 0 1 Letter x y z JLM 20060107 22:16 30 Shifted Letter Frequency Bar Graph

JLM 20060107 22:16 31 Vigenere Multialphabetic Cipher 6 Alphabet Direct Standard Example (Keyword: SYMBOL) ABCDEFGHIJKLMNOPQRSTUVWXYZ -------------------------STUVWXYZABCDEFGHIJKLMNOPQR YZABCDEFGHIJKLMNOPQRSTUVWX MNOPQRSTUVWXYZABCDEFGHIJKL BCDEFGHIJKLMNOPQRSTUVWXYZA OPQRSTUVWXYZABCDEFGHIJKLMN LMNOPQRSTUVWXYZABCDEFGHIJK JLM 20060107 22:16 PLAIN: KEY: CIPHER: GET OUT NOW SYM BOL SYM YCF PIE FMI 32 Constructing Vig Alphabets Direct Standard: ABCDEFGHIJKLMNOPQRSTUVWXYZ Reverse Standard: ZYXWVUTSRQPONMLKJIHGFEDCBA Keyword Direct (Keyword: NEW YORK CITY): NEWYORKCITABDFGHJLMPQRSUVZ

Keyword Transposed (Keyword: CHICAGO): CHIAGO BDEFJK LMNPQR STUVWX YZ CBLSYHDMTZIENUAFPVGJQWOKRX JLM 20060107 22:16 33 Solving Vigenere 1. Determine Number of Alphabets Repeated runs yield interval differences. Number of alphabets is the gcd of these. (Kasiski) Statistics: Index of coincidence 2. Determine Plaintext Alphabet 3. Determine Ciphertext Alphabets JLM 20060107 22:16 34 Statistical Tests for Alphabet Identification Index of coincidence for letter frequency Can choose same letters fi choose 2 ways

IC i fi(fi-1)/(n(n-1)), so IC i pi2 For English Text IC .07 For Random Text IC= 1/26=.038 IC is useful for determining number of alphabets (key length) and aligning alphabets. For n letters enciphered with m alphabets: IC(n,m)= 1/m (n-m)/(n-1) (.07) + (m-1)/m n/(n-1) (.038) Other Statistics Vowel Consonant pairing Digraph, trigraph frequency JLM 20060107 22:16 35 Review of Attacks on Polyalphabet Letter Frequency, multigram frequencies, transition probabilities Index of Coincidence Alphabet Chaining Sliding Probable Text Limited Keyspace search

Long repeated sequences in ciphertext Markoff like contact processes Decimation of sequences Log weights Generatrix Direct and indirect symmetries JLM 20060107 22:16 36 Polygraphic Substitution PlayFair Digraphic Substitution OHNMA FERDL IBCGK PQSTU VWXYZ JLM 20060107 22:16 TH QM 37 Hill Cipher The Hill cipher is a block cipher with block size is 2 over the normal alphabet. Assign each letter a number between 0 and 25 (inclusive) For example, a = 0, b = 1, . . ., z = 25 (z is used as space) Let p1p2 be two successive plaintext letters. c1c2 are the ciphertext output where c1 = k11p1 + k12p2 (mod 26)

c2 = k21p1 + k22p2 (mod 26) Apply the inverse of the key matrix [k11 k12 | k21 k22] to transform ciphertext into plaintext Works better if we add space (27=33 letters) or throw out a letter (25=52) JLM 20060107 22:16 38 Breaking Hill The Hill cipher is resistant to a ciphertext only attack with limited ciphertext. Increasing the block size increases the resistance. It is trivial to break using a known plaintext attack. The process is much like the method used to break an affine cipher. Corresponding plaintext/ciphertext are used to set up a system of equations whose solutions are the key bits. JLM 20060107 22:16 39 Information Theory Motivation How much information is in a binary string? Game: I have a value between 0 and 2n-1 (inclusive), find it by asking the minimum number of yes/no questions.

Write the number as [bn-1bn-2b0]2 . Questions: Is bn-1 1?, Is bn-2 1? , , Is b0 1? So, what is the amount of information in a number between 0 and 2n-1? Answer: n bits The same question: Let X be a probability distribution taking on values between 0 and 2n-1 with equal probability. What is the information content of a observation? There is a mathematical function that measures the information in an observation from a probability distribution. Its demoted H(X). H(X)= i pilg(pi) JLM 20060107 22:16 40 Information Theory

The definition of H(X), which is called entropy, has two desireable properties Doubling the storage (the bits your familiar with) doubles the information content H(1/2, 1/3, 1/6)= H(1/2, 1/2) + H(2/3,1/3) It was originally developed to study how efficiently one can reliably transmit information over noisy channel. Applied by Shannon to Cryptography (Communication Theory of Secrecy Systems. BTSJ, 1949) Entropy which measures amount of uncertainty that is represented in a sample drawn from a stochastic distribution Thus information learned about Y by observing X is I(Y,X)= H(Y)-H(Y| X). Can be used to estimate requirements for cryptanalysis of a cipher. JLM 20060107 22:16 41 Information Theory in Cryptography Studying key search

Distribution A: 2 bit key each key equally likely Distribution B: 4 bit key each key equally likely Distribution C: n bit key each key equally likely Distribution A: 2 bit key selected from distribution (1/2, 1/6, 1/6, 1/6) Distribution B: 4 bit key selected from distribution (1/2, 1/30, 1/30, , 1/30) Distribution C: n bit key selected from distribution (1/2, 1/(2 n-1), , 1/(2n-1)) JLM 20060107 22:16 42 Information Theory in Cryptography How much information is there in a key drawn from a random variable X Distribution A: H(X)= lg(4) + lg(4) + lg(4) +1/4 lg(4) = 2 bits Distribution B: H(X)= 16 x (1/16 lg(16))= 4 bits Distribution C: H(X)= 2n x (1/2n) lg(2n) = n bits Distribution A: H(X) = lg(2) + 3 x(1/6 lg(6))= 1.79 bits Distribution B: H(X) = lg(2) + 15 x(1/30 lg(30))= 2.95 bits

Distribution C: H(X) = lg(2) + 1/2 2n-1 x(1/(2n-1) lg(2n-1)) n/2+1 bits JLM 20060107 22:16 43 Information Theory in Cryptography What is the expected number of keys that must be tried to determine a key drawn from a random variable X Distribution A: E(X)= (1+2+3) = 1.5 trials Distribution B: E(X)= 1/16 (1+2++15)=7.5 trials Distribution C: E(X)= 1/2n (1+2+ +2n) = (2n-1)/2 trials Distribution A: E(X) = x 1 + 1/6(2+3)= 4/3 trials Distribution B: E(X) = X1 + 1/30 (2+3++15)= 125/12 trials Distribution C: E(X) = X1 + 1/(2n-1)(2+3++2n-1)= + 1/(2n-1) (2n-1)(2n+1)trials JLM 20060107 22:16 44 Equivocation and Bayes Theorem

HE= Lim n (x[1],,x[n]) (1/n)Pr(X=(x[1],,x[n])) lg(Pr(X=(x[1], ,x[n]))) For random stream of letters HR= i(1/26)lg(26)=4.7004 For English HEnglish = 1.2-1.5 (so English is about 75% redundant) There are approximately T(n)= 2nH n symbol messages that can be drawn from the meaningful English sample space. H(X,Y)= H(Y)+H(X|Y) Bayes: P(x|y) P(y)= P(x)P(y|x) X and Y are independent if P(X,Y)= P(X)P(Y) JLM 20060107 22:16 45 Some Information Theory Theorems H(K|C)= H(M|C)+ H(K|M,C) Proof: H(K|C)= H(K,C)-H(C), H(K|M,C)= H(M, K, C)-H(M,C). H(M|C)= H(M,C) H(C). Thus, H(K|C)= H(K,C)-H(M,C)+H(M|C). H(M|K,C)= H(M,K,C)- H(K,C), but H(M|K,C)= 0 since there is no uncertainty in the message given the ciphertext and the key. H(K| M,C)= H(M,K,C)- H(M,C). So H(K|M,C)= H(K,C)- H(M,C). Thus H(K|C)= H(K|M,C)+H(M|C). Perfect Security: P(C|M)=P(C) JLM 20060107 22:16 46

Unicity and Random Ciphers Question: How many messages do I need to trial decode so that the expected number of false keys for which all m messages land in the meaningless subset is less than 1? Answer: The unicity point. Nice application of Information Theory. Theorem: Let H be the entropy of the source (say English) and let be the alphabet. Let K be the set of (equiprobable) keys. Then u= lg(|K|)/(lg(|)-H). JLM 20060107 22:16 47 Unicity for Random Ciphers Meaningful Messages 2Hn Cipher Messages ||n Non-Meaningful Messages Decoding with correct key Decoding with incorrect key JLM 20060107 22:16 48 Unicity Distance for Monoalphabet HCaeserKey= Hrandom = lg(26)= 4.7004

HEnglish 1.2. For Caeser, u lg(26)/(4.7-1.2) 4 symbols, for ciphertext only attack. For known plaintext/ciphertext, only 1 corresponding plain/cipher symbol is required for unique decode. For arbitrary substitution, u lg(26!)/(4.7-1.2) 25 symbols for ciphertext only attack. For corresponding plain/ciphertext attack, about 8-10 symbols are required. Both estimates are remarkably close to actual experience. JLM 20060107 22:16 49 Application: One Time Pads are unbreakable M, C, K are n bits long P(M=x|C=y)=P(M=x and C=y)/P(C=y). P(M=x and C=y) =P(M=x and K=x y)=P(M=x)P(K=x y)=P(M=x)2-n P(C=y)= xP(M=x and C=y)= xP(M=x)2-n=2-n So P(M=x|C=y)= P(M=x) 2-n/2-n=P(M=x) JLM 20060107 22:16 50 Information Theoretic Estimates to break monoalphabet Cipher Type of Attack Information

Resources Computational Resources Caeser Ciphertext only U= 4.7/1.2=4 letters 26 computations Caeser Known plaintext 1 corresponding plain/cipher pair 1 Substitution Ciphertext only ~30 letters O(1) Substitution

Known plaintext ~10 letters O(1) JLM 20060107 22:16 51 Mixing cryptographic elements to produce strong cipher Diffusion transposition Using group theory, the action of a transposition on a1 a2 ak could be written as a(1) a(2) a(k) . Confusion substitution Using group theory, the action of a substitution on a1 a2 ak could be written as (a1) (a2) (ak) . Transpositions and substitutions may depend on keys. Keyed permutations may be written as k(x). Incidentially, a block cipher on b bits is nothing more than a keyed permutation on 2b symbols. Iterative Ciphers key dependant staged iteration of combination of basic elements is very effective way to construct cipher. (DES, AES) JLM 20060107 22:16 52 The Machine Ciphers Simple Manual Wheels Wheatstone Jefferson

Rotor Enigma Heburn SIGABA TYPEX Stepping switches Purple Mechanical Lug and cage M209 JLM 20060107 22:16 53 Jefferson Cipher JLM 20060107 22:16 54 Enigma JLM 20060107 22:16 55

Group Theory for Rotors Theorem: If =(a11 a12 a1i) (a11 a1j) (a11 a1k)then 1= (a 11 a12 a1i) (a11 a1j) (a11 a1k). When permutations are written as products of cycles, it is very easy to calculate their order. (It is the LCM of the length of the cycles). Writing cryptographic processes as group operation can be very useful. For example, if R denotes the mapping of a rotor and C=(1,2,,26), the mapping of the rotor turned one position is CRC -1. Reference: Rotman, Group Theory. Lang, Algebra. Hall, Group Theory. Chelsea. JLM 20060107 22:16 56 Diagrammatic Enigma Structure U L M N S Lamps Keyboard Message flows right to left

U: Umkehrwalze (reversing drum) N,M,L: First (fastest), second third rotors S: Stecker (plugboard) L B Diagram courtesy of Carl Ellison JLM 20060107 22:16 57 Military Enigma Encryption Equation c= (p) PiNP-i PjMP-j PkLP-k U PkL-1P-k PjM-1P-j PiN-1P-i K: Keyboard P=(ABCDEFGHIJKLMNOPQRSTUVWXYZ) N: First Rotor M: Second Rotor L: Third Rotor U: Reflector. Note: U=U-1. i,j,k: Number of rotations of first, second and third rotors respectively. Later military models added plug-board (S) and additional rotor (not included). The equation with Plugboard is: c=(p)S PiNP-i PjMP-j PkLP-k U PkL-1P-k PjM-1P-j PiN-1P-i S-1 JLM 20060107 22:16 58 Enigma Data

Rotors Input Rotor Rotor Rotor Rotor Rotor Rotor Rotor I II III IV V VI VII ABCDEFGHIJKLMNOPQRSTUVWXYZ EKMFLGDQVZNTOWYHXUSPAIBRCJ AJDKSIRUXBLHWTMCQGZNPYFVOE BDFHJLCPRTXVZNYEIWGAKMUSQO ESOVPZJAYQUIRHXLNFTGKDCMWB VZBRGITYUPSDNHLXAWMJQOFECK JPGVOUMFYQBENHZRDKASXLICTW NZJHGRCXMYSWBOUFAIVLPEKQDT Reflector B Reflector C JLM 20060107 22:16 (AY)

(JX) (AF) (LZ) (BR) (KN) (BV) (MX) (CU) (MO) (CP) (NW) (DH) (TZ) (DJ) (TQ) Ring Turnover Rotor I Rotor II Rotor III Rotor IV Rotor V Rotors VI R F W K A A/N

(EQ) (FS) (GL) (IP) (VW) (EI) (GO) (HY) (KR) (SU) 59 Military Enigma Key Length Key Length (rotor order, rotor positions, plugboard) 60 rotor orders. lg(60)= 5.9 bits. 26*26*26 = 17576 initial rotor positions. lg(17576)= 14.1 bits of key 10 exchanging steckers were specified yielding C(26,2) C(24,2) C(8,2)/10! = 150,738,274,937,250. lg(150,738,274,937,250)= 47.1 bits as used Bits of key: 5.9 + 14.1 + 47.1 = 67.1 bits Note: plugboard triples entropy of key! Rotor Wiring State lg(26!) = 88.4 bits/rotor. Total Key including rotor wiring: 67.1 bits + 3 x 88.4 bits = 312.3 bits JLM 20060107 22:16 60 Method of Batons Applies to Enigma Without plugboard With fast rotor ordering known and only the fast rotor moving With a crib Let N be the fast rotor and Z the combined effect of the other apparatus, then N-1ZN(p)=c.

Since ZN(p)=N(c), we know the wiring of N and a crib, we can play the crib against each of the 26 possible positions of N for the plaintext and the ciphertext. In the correct position, there will be no scritches or contradictions in repeated letters. This method was used to analyze the early Enigma variants used in the Spanish Civil War and is the reason the Germans added the plugboard. Countermeasure: Move fast rotor next to reflector. JLM 20060107 22:16 61 German Key Management before 5/40 Daily keys were distributed on paper monthly and distributed by courier. Each daily key consisted of a line specifying: (date, rotor order, ring settings, plug settings -10) For each message 1. 2. 3. 4. Operator chooses a 3-letter sequences, the indicator and the text Operator set rotor positions to indicator and encrypted text twice.

Machine rotor positions were reset to text positions and the message encrypted. Operator prepended indicator and twice encrypted rotor order text to transmitted message. This was done to avoid starting rotors in the same position for each message without enormous key lists. Good motivation. Bad idea. JLM 20060107 22:16 62 Changes German use of Enigma 1. 2. 3. 4. 5. Plugboard added 6/30 Key setting method 1/38 Rotors IV and V 12/38 More plugs - 1/39 End of message key pair encipherment 5/40 JLM 20060107 22:16 63

Polish (Rejewski) Attack Rejewski exploited weakness in German keying procedure to determine rotor wiring Rejewski had ciphertext for several months but no German Enigma. Rejewski had Stecker settings for 2 months (from a German spy via the French in 12/32), leaving 265.2 bits of key (the wirings) to be found. He did. Poles determine the daily keys Rejewski catalogued the characteristics of rotor settings to detect daily settings. He did this with two connected Enigmas offset by 3 positions (the cyclotometer). In 9/38, when the message key was no longer selected from standard setting (the Enigma operator to choose a different encipherment start called the indicator), Rejewskis characteristics stopped working. Zygalski developed a new characteristic and computation device (Zygalski sheets) to catalog characteristics which appeared when 1st/4th, 2nd/5th,3rd/6th ciphertext letters in encrypted message keys (Females) were the same. JLM 20060107 22:16 64

How Rejewski did it Recall c=(p)S PiNP-i PjMP-j PkLP-k U PkL-1P-k PjM-1P-j PiN-1P-I S-1 Let Q= MLUL-1M-1=Q-1 Then the first 6 permutations (used to encrypt settings twice) are: A=A-1= SP1NP-1QP1N-1P-1S-1, B=B-1= SP2NP-2QP2N-1P-2S-1 C=C-1= SP3NP-3QP3N-1P-3S-1, D=D-1= SP4NP-4QP4N-1P-4S-1 E=E-1= SP5NP-5QP5N-1P-5S-1, F=F-1= SP6NP-6QP6N-1P-6S-1 Their products and what they reveal about encrypted settings (c1c2c3c4c5c6): AD= SP1NP-1QP1N-1P3NP-4QP4N-1P-4S-1. (c1)AD= c4. BE= SP2NP-2QP2N-1P3NP-5QP5N-1P-5S-1. (c2)BE= c5. CF= SP3NP-3QP3N-1P3NP-6QP6N-1P-6S-1. (c3)CF= c6. So we can find AD, BE and CF after about 80 messages. JLM 20060107 22:16 65 How Rejewski did it (continued) We dont know S, N or Q. Suppose

AD= (dvpfkxgzyo)(eijmunqlht)(bc)(rw)(a)(s) BE= (blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k) CF= (abviktjgfcqny)(duzrehlxwpsmo) Now the following two simple Group Theory Theorems help: 1. The product of two permutations of the same degree consisting of products of disjoint transpositions has an even number of cycles of the same length and the each element of a transposition ends up in different cycles of the same length. 2. Two permutations in Sn are conjugate () iff they have the same cycle structure. JLM 20060107 22:16 66 How Rejewski did it (conclusion) Using the first theorem, the expression for CF gives 13 possibilities for C and F, 27(=3x9) possibilities for B and E and 20(=2x10) possibilities for A and D. Histograms of the enciphered message keys showed spikes. Rejewski deduced, correctly, that these were often for plaintext keys AAA, BBB, CCC, etc. --- that allowed him to line up cycles between the three Enigma pairs. This determines A,B,C,D,E and F. Rejewski was given 2 months of key sheets, carrying the Stecker settings. From them he removed the Stecker and solved the equations for the fast rotor. For example:

S-1AS= P1NP-1QP1N-1P-1 with S-1AS and P, known. This leaves only two permutations Q and N (the fast rotor) unknown and Q is in precisely the right form to apply the second group theory result. Thus we can obtain both Q and N (see postscript). Since all the rotors are in the fast position at some time, we (as Rejewski) can obtain all the wirings. JLM 20060107 22:16 67 How Rejewski did it (postscript) A=SP1NP-1QP1N-1P-1S-1 A=S-1P-1AP1S= NP-1QP1N-1 B=SP2NP-2QP2N-1P-2S-1 B=S-1P-2BP2S= NP-2QP2N-1 So, AB=NP-1QP1QP2N-1 Similarly, CD= NP-2QP1QP3N-1 So CD= NP-1N-1 AB NPN-1 JLM 20060107 22:16 68 Digital Block Ciphers Complicated keyed invertible functions constructed from

iterated elementary rounds. Confusion: non-linear functions (ROM lookup) Diffusion: permute round output bits Key mixing: xor key schedule at beginning of round Characteristics: Fast Data encrypted in fixed block sizes (64,128,256 bit blocks are common). Key and message bits non-linearly mixed in ciphertext DES (1974) design was watershed in public symmetric key crypto. JLM 20060107 22:16 69 Data Encryption Standard Federal History 1972 study RFP: 5/73, 8/74 NSA: S-Box influence, key size reduction Published in Federal Register: 3/75 FIPS 46: January, 1976. IBM Descendant of Feistels Lucifer Designers: Horst Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman Brute Force Cracking EFS DES Cracker: $250K, 1998. 1,536 custom chips. Can brute force a DES key in days Deep Crack and distributed.net break a DES key in 22.25 hours.

JLM 20060107 22:16 70 Horst Feistel: Lucifer Early 1970s: First serious needs for civilian encryption (in electronic banking) IBMs response: Lucifer, an iterated SP cipher Lucifer (v0): x Two fixed, 4x4 s-boxes, S0 & S1 S0 S1 S0 S1 S0 S1 A fixed permutation P P Key bits determine S0 S1 S0 S1 S0 S1 which s-box is to be used at each position 8 x 64/4 = 128 key bits S0 S1 S0 S1 S0 S1 (for 64-bit block, 8 rounds) .... ... .... ....

P Graphic by [email protected] JLM 20060107 22:16 EK(x) 71 From Lucifer to DES 8 fixed, 6x4 s-boxes (non-invertible) expansion E (simple duplication of 16 bits) round keys are used only for xor with the input 56-bit key size 16 x 48 round key bits are selected from the 56-bit master key by the key schedule. JLM 20060107 22:16 x 32 bits E 48 S1 S2

.... ki S8 32 P f(x, ki) 72 Iterated Feistel Cipher Key Key Schedule Plaintext k1 k2 r Feistel Rounds kr Ciphertext JLM 20060107 22:16 73 Feistel Round Graphic courtesy of Josh Benaloh

f ki F(K,X)= non-linear function Note: If i(L,R)= (Lf(E(R) ki) ,R) and (L,R)= (R,L), this round is i(L,R). To invert: swap halves and apply same transform with same key: ii(L,R)=(L,R). JLM 20060107 22:16 74 DES Round Function 32 bits Sub-key 48 bits 6/4-bit substitutions 32-bit permutation Slide courtesy of Josh Benaloh JLM 20060107 22:16 75 Chaining Feistel Rounds f

f JLM 20060107 22:16 ki ki+1 76 Feistel Ciphers defeat simple attacks After 2 to 4 rounds to get flat statistics. Parallel system attack Solve for key bits or constrain key bits ki(1)= a11(K)p1 c1 + a12(K)p2 c1 ++ a1N(K)pncn ki(m)= am1(K)p1 c1 + am2(K)p2 c1 ++ amN(K)pncn Solving Linear equations for coefficients determining cipher c1= f11(K)p1+ f12(K)p2++ f1n(K)pn c2= f21(K)p1+ f22(K)p2++ f2n(K)pn

cm= fm1(K)p1+ fm2(K)p2++ fmn(K)pn Even a weak round function can yield a strong Feistel cipher if iterated sufficiently. Provided its non-linear JLM 20060107 22:16 77 DES 64-bit Plaintext k2 k1 (48 bits) 56-bit Key 16 Feistel Rounds k16 64-bit Ciphertext JLM 20060107 22:16 78 DES Round L (32 bits) R (32 bits)

ki (48 bits) f L (32 bits) R (32 bits) F(K,X)= non-linear function JLM 20060107 22:16 79 JLM 20060107 22:16 80 JLM 20060107 22:16 81 JLM 20060107 22:16 82 DES Described Algebraically i(L,R)= (Lf(E(R) ki) ,R) ki is 48 bit sub-key for round i and f(x)= P(S1S2S3 S8(x)). Here, each S box operates on 6 bit quantities and outputs 4 bit quantities. P permutes the resulting 32 output bits.

(L,R)= (R,L). Each round (except last) is i. Note that i i= i2. Full DES is: DESK(x)= IP-1 16 3 2 1 IP(x) So its inverse is DESK-1(x)= IP-1 1 14 15 16 IP(x) JLM 20060107 22:16 83 DES Key Schedule C0D0= PC1(K) Ci+1 = LeftShift(Shifti, Ci), Di+1 = LeftShift(Shifti, Di), Ki= PC2(Ci ||Di) Shifti= <1,2,2,2,2,2,2,1,2,2,2,2,2,2,1,1> Note: Irregular Key schedule protects against related key attacks. [Biham, New Types of Cryptanalytic Attacks using Related Keys, TR-753, Technion] JLM 20060107 22:16 84 DES Key Schedule pc1[64] 57 49 59 51 31 23 29 21 41 43 15

13 33 35 07 05 25 27 62 28 17 19 54 20 09 11 46 12 01 03 38 04 58 60 30 00 50

52 22 00 42 44 14 00 34 36 06 00 26 63 61 00 18 55 53 00 10 47 45 00 02 39 37 00

pc2[48] 14 17 11 24 01 05 03 28 15 06 21 10 23 19 12 04 26 08 16 07 27 20 13 02 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 JLM 20060107 22:16 85 DES Key Schedule Key schedule round 1 10 51 34 60 49 17 33 57 1 36 27 18 41 22 28 39 54 37 4 47 30 14 13 62 55 31 2 9 19 42 3 35 26 25 44 58 59 5 53 23 29 61 21 38 63 15 20 45 Key schedule round 2 2 43 26 52 41 9 25 49 59 1 11 34 60 27 18 17 36 50 51 58 57 19 10 33 14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55 7 12 37 6 5 54 47 23 JLM 20060107 22:16

86 DES Data S4 (hex) 7 d e d 8 b a 6 9 3 f 0 3 5 0 6 0 6 c a 6 f b 1 9 0 7 d a 3 d 8

1 4 f 9 2 7 1 4 8 2 3 5 5 c e b b 1 5 c c a 2 7 4 e

8 2 f 9 4 e S5 (hex) 2 c 4 e b 2 4 2 1 b 8 c 1 c b 7 7 4 a 1 a 7 d e b d 7 2

6 1 8 d 8 5 f 6 5 0 9 f 3 f c 0 f a 5 9 d 3 6 a 0 9

3 4 e 8 0 5 9 6 e 3 S6 (hex) c 1 a a f 4 9 e f 4 3 2 f 2 5 c 9 7 2 9 2 c 8 5

6 9 c f 8 5 3 a 0 6 7 b d 1 0 e 3 d 4 1 4 e a 7 e 0

1 6 7 b d 0 5 3 b 8 b 8 6 d JLM 20060107 22:16 87 DES Data E S7 (hex) 4 b 2 d 0 b 1 4 b 6 b d e 7

d 8 f 4 c 1 0 9 3 4 8 1 7 a d a e 7 3 e a 9 c 3 f 5

9 5 6 0 7 c 8 f 5 2 0 e a f 5 2 6 8 9 3 1 6 2 c S8 (hex) d 2 8 1 f d

7 b 4 2 1 e 4 8 1 7 6 a 9 4 f 3 c a b 7 e 8 1 4 2 d a c 0 f

9 5 6 c 3 6 a 9 e b d 0 5 0 f 3 0 e 3 5 c 9 5 6 7 2 8

b 32 4 8 12 16 20 24 28 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15

19 23 27 31 4 8 12 16 20 24 28 32 5 9 13 17 21 25 29 1 Note: DES can be made more secure against linear attacks by changing the order of the S-Boxes: Matsui, On Correlation between the order of S-Boxes and the Strength of DES. Eurocrypt,94. JLM 20060107 22:16 88

S Boxes as Polynomials over GF(2) 1,1: 56+4+35+2+26+25+246+245+236+2356+16+15+156+14+146+145+13+135+134+1346+1 345+13456+125+1256+1245+123+12356+1234+12346 1,2: C+6+5+4+45+456+36+35+34+346+26+25+24+246+2456+23+236+235+234+2346+1+15+ 156+134+13456+12+126+1256+124+1246+1245+12456+123+1236+1235+12356+ 1234+12346 1,3: C+6+56+46+45+3+35+356+346+3456+2+26+24+246+245+236+16+15+145+13+1356+13 4+13456+12+126+125+12456+123+1236+1235+12356+1234+12346 1,4: C+6+5+456+3+34+346+345+2+23+234+1+15+14+146+135+134+1346+1345+1256+ 124+1246+1245+123+12356+1234+12346 JLM 20060107 22:16 89 DES Data 1 16 2 7 3 20 4 21 5 29

6 12 17 2 18 8 19 24 20 14 21 32 22 27 7 28 23 3 8 17 24 9 9

1 P 10 15 11 23 12 26 13 5 14 18 15 31 16 10 25 19 26 13 27 30

28 6 29 22 30 11 31 4 32 25 Note on applying permutations: For permutations of bit positions, like P above, the table entries consisting of two rows, the top row of which is in order means the following. If t is above b, the bit at b is moved into position t in the permuted bit string. For example, after applying P, above, the most significant bit of the output string was at position 16 of the input string. JLM 20060107 22:16 90 Homework Review DES description by reading http://www.aci.net/kalliste/des.htm or http://www.itl.nist.gov/fipspubs/fip46-2.htm You need to know DES well for a future class as well as for problem number 5.

JLM 20060107 22:16 91 DES Data S1 (hex) e 4 d 0 f 7 4 1 e f c 8 1 4 8 2 2 e d 4 f 2 6 9 b d 2 1 8 1

b 7 3 a f 5 a 6 c b 6 c 9 3 c b 7 e 5 9 3 a 9 5 a 0

0 3 5 6 7 8 0 d S2 (hex) f 1 8 3 d 4 0 e 7 d 8 a e 7 b 1 6 f a 3 b 2 4 f 3 8

d 4 4 e 1 2 9 c 5 b 7 0 8 6 2 1 c 7 d a 6 c c 6 9 0

0 9 3 5 5 b 2 e a 5 f 9 S3 (hex) a 0 9 d 7 0 d 6 4 1 a d e 9 9 0 6 3 8 6 3 4

f 9 f 6 3 8 5 a 0 7 1 2 b 4 d 8 1 f c 5 2 e 7 e c 3

b c 5 b 4 b a 5 2 f e 2 8 1 7 c JLM 20060107 22:16 92 Cryptographic Hashes A cryptographic hash (CH) is a one way function, h, from all binary strings (of arbitrary length) into a fixed block of size n (called the size of the hash) with the following properties: 1. Given y=h(x) it is infeasible to calculate a x x such that y=h(x). (One way, non-invertibility or pre-image resistance). Functions satisfying this condition are called One Way Hash Functions (OWHF) 2.

Given u, it is infeasible to find w such that h(u)=h(w). (weak collision resistance, 2nd pre-image resistance). 3. It is infeasible to find u, w such that h(u)=h(w). (strong collision resistance). Note 32. Functions satisfying this condition are called Collision Resistant Functions (CRFs). Just like Symmetric ciphers ratio of work factor for computation of hash vs work factor to break hash should be very high. Adversary has complete information on computing hash and (obviously) can compute as many hashes from the target as she wants. JLM 20060107 22:16 93 Observations on Cryptographic Hashes Hashes are a strong checksum OWHF and CRF conditions make CHs satisfy many of the properties of random functions Small changes should create large changes (otherwise the preimage of near neighbors are near neighbors making collisions easy to find) Small input changes should be statistically unrelated (uncorrelated) to changes in a subset of the hash bits Analysis of CHs very similar to Symmetric Cipher techniques

Popular practical cryptographic hashes MD4, MD5 (now broken) SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 (last 4 are SHA-2) RIPEMD JLM 20060107 22:16 94 Observations Collision Resistance 2nd pre-image resistance Let f(x)= x2-1 (mod p). f(x) acts like a random function but is not a OWHF since square roots are easy to calculate mod p. Let f(x)= x2 (mod pq). f(x) is a OWHF but is neither collision nor 2nd pre-image resistant If either h1(x) or h2(x) is a CRHF so is h(x)= h1(x) || h2(x) MDC+signature & MAC+unknown Key require all three properties

Ideal Work Factors: Type Work Property OWHF 2n Pre-image 2nd Pre-image CRHF 2n/2 Collision MAC 2t Key recovery, computational resistance JLM 20060107 22:16 95 What are Hash Functions Good for? Modification Detection Codes (MDCs): This is a strong checksum (integrity check). Sometimes called unkeyed

hashes. Message Authentication Code (MACs): If shared secret is part of the hash, two parties can determine authenticated integrity with CHs. Called keyed hashes. Message Digests (MDs): Encrypting (with private key) the CH of a message (its MD) acts as a certification that the message was approved by possessor of private key. This is called a Digital Signature. [Note: you could sign the whole message rather than the hash but this would take oodles of time by comparison.] JLM 20060107 22:16 96 What are Hash Functions Good for? Uniquely and securely identifies bit streams like programs. Hash is strong name for program. Entropy mixing: Since CHs are random functions into fixed size blocks with the properties of random functions, they are often used to mix biased input to produce a seed for a psuedo-random number generator. Password Protection: Store salted hash of password instead of password (Needham). Bit Committment JLM 20060107 22:16 97 One-Way Functions Hashes come from two basic classes of one-way functions Mathematical Multiplication: Z=XY

Modular Exponentiation: Z = YX (mod n) (Chaum vP Hash) Ad-hoc (Symmetric cipher-like constructions) Custom Hash functions (MD4, SHA, MD5, RIPEMD) JLM 20060107 22:16 98 Chaum-vanHeijst-Pfitzmann Compression Function Suppose p is prime, q=(p-1)/2 is prime, a is a primitive root in F p, b is random. g: {1,2,,q-1}2 {1,2,,p-1}, q=(p-1)/2 by: g(s, t) = as bt (mod p) Not used in practice: too slow. Reduction to discrete log: Suppose g(s, t)= g(u, v) can be found. Then as bt (mod p)= au bv (mod p). So as-u (mod p)= bv-t (mod p). Let b= ax (mod p). Then (s-u)=x(y-t) (mod p-1). But p-1= 2q so we can solve for x, thus determining the discrete log of b. JLM 20060107 22:16 99 Merkle/Damgard Construction Hi-1 Padded n bit blocks Compression Function (f)

Input: x=x1||||xt Input is usually padded H0= IV Hi= f(Hi-1, xi) h(x)= g(ht) Hash Value Graphic by Josh Benaloh JLM 20060107 22:16 100 A Cryptographic Hash: SHA-1 160 bits of state 512-bit input Compression Function 160-bit state JLM 20060107 22:16 Slide by Josh Benaloh 101 A Cryptographic Hash: SHA-1 Picture from Wikipedia

JLM 20060107 22:16 102 Padding Standard technique Let last message block have k bits. If k=n, make a new block and set k= 0. Append a 1 to last block leaving r=n-k-1 remaining bits in block. If r>=64, append r-64 0s then append bit length of input expressed as 64 bit unsigned integer If r<64, append n-r 0s (to fill out block), append n-64 0s at beginning of next block then append bit length of input expressed as 64 bit unsigned integer JLM 20060107 22:16 103 Technique for CHs from Block Ciphers Let input be x= x1 || x2 || || xt where each xi is n bits long. Let g be a function taking an n bit input to an m bit input. Let E(k, x) be a block cipher with m bit keyspace and n bit block. Let H 0= IV. Construction 1 Hi= E(g(Hi-1), xi) Hi-1 Construction 2 Hi= E(xi, Hi-1) Hi-1 Construction 3 Hi= E(g(Hi-1), xi) xi Hi-1 Note: Because of collisions n should be >64. Ideally, m=n and g= id. DES with n= 64 is too small. AES with n=m=128 is better. JLM 20060107 22:16

104 Birthday Attacks Probability of collision determined by Birthday Paradox calculation: (1-1/n) (1-2/n) (1-(k-1)/n)= (n!/k!)/nk Probability of collision is >.5 when k2 > n. Need 280 blocks for SHA. 1+x ex, i=1i=k (1-i/n) e-k(k-1)/(2n) JLM 20060107 22:16 105 Attacks on Cryptographic Hashes Berson (1992) using differential cryptanalysis on 1 round MD-5. Boer and Bosselaers (1993), Pseudo collision in MD5. Dobbertin (1996), Collisions in compression function. Attacks inspired RIPEMD proposal. Biham and Chen (2004), Collisions in SHA-0. Chabaud and Joux (2004), Collisions in SHA-0 . Wang, Feng, Lai, Yu, (2004), MD4, MD5, RIPEMD Wang et al, (2004, 2005), SHA-1

SHA-1 has stood up best: best known theoretical attack (11/05) requires 263 operations. JLM 20060107 22:16 106 MACs using Hashes Prefix and suffix attacks Hash(k1, Hash(k2, m)) HMACK(x)= SHA-1(Kopad || SHA-1(K ipad )||x) Hash(k|p|m|k) JLM 20060107 22:16 107 Winnowing and Chaffing (Rivest) Want to send 1001. Pick random stream (mi) and embed message at positions (say) 3, 7, 8 14 MAC each packet (mmi).

Make sure MAC is correct only in message positions JLM 20060107 22:16 108 Homework 1-Question 1 Encrypt the following message using a Vigeniere cipher with direct standard alphabets. Key: JOSH. All persons born or naturalized in the United States, and subject to the jurisdiction thereof, are citizens of the United States and of the state wherein they reside. No state shall make or enforce any law which shall abridge the privileges or immunities of citizens of the United States; nor shall any state deprive any person of life, liberty, or property, without due process of law; nor deny to any person within its jurisdiction the equal protection of the laws. Upper case only! Turn plain and cipher text into 5 letter groups. Calculate the index of coincidence of the plaintext and ciphertext. Break the ciphertext into 4 columns. What is the index of coincidence of each column? JLM 20060107 22:16 109 Homework 1-Question 1 (addendum) ALLPE OTHEJ FTHES

AWWHI FTHEU IBERT NWITH RSONS URISD TATEW CHSHA NITED YORPR INITS BORNO ICTIO HEREI LLABR STATE OPERT JURIS JLM 20060107 22:16 RNATU NTHER NTHEY IDGET SNORS YWITH DICTI RALIZ EOFAR

RESID HEPRI HALLA OUTDU ONTHE EDINT ECITI ENOST VILEG NYSTA EPROC EQUAL HEUNI ZENSO ATESH ESORI TEDEP ESSOF PROTE TEDST FTHEU ALLMA MMUNI RIVEA LAWNO CTION ATESA NITED KEORE

TIESO NYPER RDENY OFTHE NDSUB STATE NFORC FCITI SONOF TOANY LAWS JECTT SANDO EANYL ZENSO LIFEL PERSO 110 Homework 1-Question 2 Break the Vigeniere based ciphertext below. Plaintext and ciphertext alphabets are direct standard. What is the key length? What is the key? If the key length is k, how long a corresponding plain, ciphertext sequence be given to solve? Can you give an upper bound on the pure ciphertext length needed? IGDLK UERXY DIGIY

HCLSP MWKGF PUSXF MJSGC EEYHE DCSRR ZCDLC UCFIY MJVRY FMGEP UTOWS AZSRB NYDXJ ZBMLC FGYRQ JLM 20060107 22:16 PLYRC ERYWC GNDLC QYXHD DGCLY IGDLA QRRIP ZYDMM APRMQ VSCXY TYBMR

UERXJ ZQGSS IGNSU ZBVEQ KDYVY QREWQ ZBCXM MLNLG FGXKN XJGMR FPSZC OYBID EMBTF QYMIY TDSVK ALDSD APRMK MLDSB YMXKM ZCCWG ULSWF IFYWF AYVPU GPCIJ ZRRIP FFOAM MJVLY TGMLK

HCCEL 111 Homework 1-Question 3 Consider a message source M(x) with the following distribution: M: P(x=0)= p M: P(x=1)= q, with p+q=1 and a one time pad selected from distribution P(x) P: P(x=0)= P: P(x=1)= Consider the ciphertext formed by xoring the message m with the pad p, so that c= mp What is the ciphertext distribution C? Calculate H(M), H(P), H(C). Calculate: I(M|C)= H(M)-H(M|C) Suppose, P: P(x=0)=3/4 and P(x=1)=1/4. What is the ciphertext distribution and H(M), H(P), H(C) and I(M|C) now. JLM 20060107 22:16 112 Homework 1-Question 4 Calculate the output of the first two rounds of DES with input message 0x3132333435363738 and key 0x00abcdefabcdef89. The input to round 1 (after initial permutation) and the first 2 round keys are given below. For fixed key, DES is a permutation on 264 letters. Approximately how many such permutations are there? (Hint: Use Stirlings approximation.)

Compare this to the size of the key space for DES. Round 01 Key: Round 02 Key: 01001111 01010111 00000111 10111001 01011100 10101011 00101111 00100111 01101001 00111011 01111111 00100100 Input to DES: 00110100 00111000 00000000 00000000 Round 1 Input: JLM 20060107 22:16 00110011 00110111 11111111 11111111 00110010 00110110 11100001 00010000 00110001 00110101 10101010 01100110 113

Homework 1-Question 5 (Extra Credit) Given a one rotor machine, M, depicted below with equation Ci R-1 C-i U C-i R Ci (p)=c with C, U, R below. R: ABCDEFGHIJKLMNOPQRSTUVWXYZ EKMFLGDQVZNTOWYHXUSPAIBRCJ U: ABCDEFGHIJKLMNOPQRSTUVWXYZ YRUHQSLDPXNGOKMIEBFZCWVJAT C: The cyclic permutation AB, BC, etc Lamps U R Keyboard JLM 20060107 22:16 114 Homework 1-Question 5 (cont) Calculate the ciphertext derived from the plaintext: HELLOWORLD What do you think the index of coincidence of the ciphertext from a 50 letter message is? If the key was the starting position, i, of M, how many letters of corresponding plain/cipher text would you need to find the key? How many ciphertext only letters? The following may be helpful: R-1 ABCDEFGHIJKLMNOPQRSTUVWXYZ UWYGADFPVZBECKMTHXSLRINQOJ

JLM 20060107 22:16 115 General Modern References Blake, Seroussi, and Smart, Elliptic Curves in Cryptography, Cambridge Bressoud and Wagon, Computational Number Theory. Key Press. Bach and Shallit, Algorithmic Number Theory. Berlekamp, Algebraic Coding Theory. Reprinted by Aegean Park Press. Biham and Shamir, Differential Cryptanalysis of DES. Springer. Boneh, Twenty Years of attacks on RSA. Notices AMS. Buchmann, Introduction to Cryptography. Springer. Cohen, A Course in Computational Algebraic Number Theory. Springer. Damgard, Lectures on Data Security. Springer. Golumb, Shift Register Sequences. Reprinted by Aegean Park Press. Koblitz, A Course in Number Theory and Cryptography. Springer. Koblitz, Algebraic Aspects of Cryptography. Springer. Konheim, Cryptography: A Primer. Wiley. JLM 20060107 22:16 116 General Modern References Landau, DES, AES, Survey article. Notices AMS. MacWilliams et. al., Theory of Error Correcting Codes. North Holland. Menezes, van Oorshot, Vanstone, Handbook of Applied Cryptography. (Online: http://www.cacr.math.uwaterloo.ca/hac ). CRC Press. Rhee, Cryptography and Secure Communications. Rivest, Class notes on Security and Crypto online. (web.mit.edu). Schneier, Applied Cryptography. Wiley. Simovits, The DES: Documentation and Evaluation. Aegean Park Press. Stinson, Cryptography: Theory and Practice. CRC Press. Welch, Codes and Cryptography. Oxford.

/ Web sites: www.rsa.com, www.counterpane.com, www.iacr.org has loads of preprints. JLM 20060107 22:16 117 End Paper Done JLM 20060107 22:16 118

Recently Viewed Presentations

  • The Knee Joint - Eiu

    The Knee Joint - Eiu

    THE KNEE JOINT BONES OF THE KNEE FEMUR Lateral condyle (6 left) Medial condyle (8 left) Intercondylar fossa (7 left) FEMUR FEMUR TIBIA Medial condyle Lateral condyle Tibial Tuberosicty Medial Malleolus TIBIA TIBIA Gerdy's tubercle IT band insertion FIBULA No...
  • Enzyme Regulation I - كلية الطب

    Enzyme Regulation I - كلية الطب

    Enzyme Regulation I. Enzyme Regulation Mechanisms. 1. Allosterism. 2. Covalent Modification. 3. Control of Synthesis. 4. Availability of Substrate. Control of Enzyme Activity. Substrate Does Not Change Enzyme. Binding of Substrate. Substrate Does Change Enzyme.
  • P2  Science Friday 15th June 2018 Key Revision

    P2 Science Friday 15th June 2018 Key Revision

    P2 - ScienceFriday 15th June 2018. Key Revision Points. Triple Science. Forces & Weight. Vector magnitude and direction (i) displacement (ii) ... Moments & Gears (Triple Only) Examples of forces causing rotation. Write down the equation that links distance, force...
  • Programmazione ad alto livello con Python

    Programmazione ad alto livello con Python

    Modules. If youquit from the Python interpreter and enteritagain, the definitionsyouhave made (code and variables) are lost. Therefore, ifyouwant to write a somewhatlongerprogram, you are better off using a text editor to prepare the input for the interpreter and runningit...
  • Exchange Rates and the Balance of Payments

    Exchange Rates and the Balance of Payments

    Exchange Rates and the Trade Balance ... you buy a case of French wine for $1,000. You pay for the wine with cash The French wine maker uses the $1,000 to buy a computer from Dell - Net exports equals...
  • OWASP Plan - Strawman

    OWASP Plan - Strawman

    * Logic in Flash * Logic can be built in to Flash applications with ACTIONSCRIPT Actionscript is the programming language for Flash applications This is what powers your favorite flash game. ActionScript 3.0 is the latest version. We will talk...
  • Presentation main title can go over three or four lines if ...

    Presentation main title can go over three or four lines if ...

    Problems facing schools . Today, because of rapid economic and social change, schools have to prepare students for jobs that have not yet been created, technologies that have not yet been invented and problems that we don't yet know will...
  • Mosquito Assessment and Control Unmanned Aerial Systems (MAC-UAS)

    Mosquito Assessment and Control Unmanned Aerial Systems (MAC-UAS)

    Purpose: Document change of a particular site over time with regard to standing water or other land use relevant to mosquito management. Aerial Photographic Monitoring (March 8, 2017) (August 10, 2017) Visual Assessment of Mosquito Habitat.