X

Download Overview of Linear Cryptanalysis PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

Home / Business & Management / Business & Management Presentations / Overview of Linear Cryptanalysis PowerPoint Presentation

Overview of Linear Cryptanalysis PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Overview of Linear Cryptanalysis powerpoint presentation easily and in no time. This helps you give your presentation on Overview of Linear Cryptanalysis in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this Overview of Linear Cryptanalysis powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by slidefu in Business & Management ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

Overview of Linear Cryptanalysis Presentation Transcript

Slide 1 - Overview of Linear Cryptanalysis Part 1  Cryptography 1
Slide 2 - Linear Cryptanalysis Like differential cryptanalysis, we target the nonlinear part of the cipher But instead of differences, we approximate the nonlinearity with linear equations For DES (or TDES) we would like to approximate S-boxes by linear functions How well can we do this? Part 1  Cryptography 2
Slide 3 - S-box Linear Analysis Part 1  Cryptography 3 column row 00 01 10 11 0 10 01 11 00 1 00 10 01 11 output y0 y1 y0y1 0 4 4 4 i x0 4 4 4 n x1 4 6 2 p x2 4 4 4 u x0x1 4 2 2 t x0x2 0 4 4 x1x2 4 6 6 x0x1x2 4 6 2 Input x0x1x2 where x0 is row and x1x2 is column Output y0y1 Counts: 0 and 8 (4 is unbiased) Either 0 or 8 is best for attacker
Slide 4 - Linear Analysis Part 1  Cryptography 4 column row 00 01 10 11 0 10 01 11 00 1 00 10 01 11 output y0 y1 y0y1 0 4 4 4 i x0 4 4 4 n x1 4 6 2 p x2 4 4 4 u x0x1 4 2 2 t x0x2 0 4 4 x1x2 4 6 6 x0x1x2 4 6 2 For example, y1 = x1 with prob. 3/4 And y0 = x0x21 with prob. 1 And y0y1=x1x2 with prob. 3/4
Slide 5 - Linear Cryptanalysis Consider a single DES S-box Let Y = Sbox(X) Suppose y3 = x2  x5 with high probability This is a linear approximation to output y3 Can we extend this so that we can solve linear equations for the key? As in differential cryptanalysis, we need to “chain” thru multiple rounds Part 1  Cryptography 5
Slide 6 - Linear Cryptanalysis of DES DES is linear except for S-boxes How well can we approximate S-boxes with linear functions? DES S-boxes designed so there are no good linear approximations to any one output bit But there are linear combinations of output bits that can be approximated by linear combinations of input bits Part 1  Cryptography 6
Slide 7 - Tiny DES Part 1  Cryptography 7
Slide 8 - Tiny DES (TDES) A much simplified version of DES 16 bit block 16 bit key 4 rounds 2 S-boxes, each maps 6 bits to 4 bits 12 bit subkey each round Plaintext = (L0,R0) Ciphertext = (L4,R4) No useless junk Part 1  Cryptography 8
Slide 9 - Part 1  Cryptography 9 L R expand shift shift key key SboxLeft XOR XOR compress L R 8 8 8 8 8 8 12 8 12 6 4 8 8 8 One Round of TDES SboxRight 6 4 Ki
Slide 10 - TDES Fun Facts TDES is a Feistel Cipher (L0,R0) = plaintext For i = 1 to 4 Li = Ri-1 Ri = Li-1  F(Ri-1,Ki) Ciphertext = (L4,R4) F(R, K) = Sboxes(expand(R)  K) where Sboxes(x0x1x2…x11) = (SboxLeft(x0x1…x5),SboxRight(x6x7…x11)) Part 1  Cryptography 10
Slide 11 - TDES Key Schedule Key: K = k0k1k2k3k4k5k6k7k8k9k10k11k12k13k14k15 Subkey Left: k0k1…k7 rotate left 2, select 0,2,3,4,5,7 Right: k8k9…k15 rotate left 1, select 9,10,11,13,14,15 Subkey K1 = k2k4k5k6k7k1k10k11k12k14k15k8 Subkey K2 = k4k6k7k0k1k3k11k12k13k15k8k9 Subkey K3 = k6k0k1k2k3k5k12k13k14k8k9k10 Subkey K4 = k0k2k3k4k5k7k13k14k15k9k10k11 Part 1  Cryptography 11
Slide 12 - TDES expansion perm Expansion permutation: 8 bits to 12 bits Part 1  Cryptography 12 r0r1r2r3r4r5r6r7 r4r7r2r1r5r7r0r2r6r5r0r3 We can write this as expand(r0r1r2r3r4r5r6r7) = r4r7r2r1r5r7r0r2r6r5r0r3
Slide 13 - TDES S-boxes Right S-box SboxRight Part 1  Cryptography 13 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 C 5 0 A E 7 2 8 D 4 3 9 6 F 1 B 1 1 C 9 6 3 E B 2 F 8 4 5 D A 0 7 2 F A E 6 D 8 2 4 1 7 9 0 3 5 B C 3 0 A 3 C 8 2 1 E 9 7 F 6 B 5 D 4 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 6 9 A 3 4 D 7 8 E 1 2 B 5 C F 0 1 9 E B A 4 5 0 7 8 6 3 2 C D 1 F 2 8 1 C 2 D 3 E F 0 9 5 A 4 B 6 7 3 9 0 2 5 A D 6 E 1 8 B C 3 4 7 F Left S-box SboxLeft
Slide 14 - Differential Cryptanalysis of TDES Part 1  Cryptography 14
Slide 15 - TDES TDES SboxRight Part 1  Cryptography 15 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 C 5 0 A E 7 2 8 D 4 3 9 6 F 1 B 1 1 C 9 6 3 E B 2 F 8 4 5 D A 0 7 2 F A E 6 D 8 2 4 1 7 9 0 3 5 B C 3 0 A 3 C 8 2 1 E 9 7 F 6 B 5 D 4 For X and X suppose X  X = 001000 Then SboxRight(X)  SboxRight(X) = 0010 with probability 3/4
Slide 16 - Differential Crypt. of TDES The plan… Select P and P so that P  P = 0000 0000 0000 0010 = 0x0002 Then P and P differ in exactly 1 bit Let’s carefully analyze what happens as these plaintexts are encrypted with TDES Part 1  Cryptography 16
Slide 17 - TDES If Y  Y = 001000 then with probability 3/4 SboxRight(Y)  SboxRight(Y) = 0010 YY = 001000  (YK)(YK) = 001000 If Y  Y = 000000 then for any S-box, Sbox(Y)  Sbox(Y) = 0000 Difference of (0000 0010) is expanded by expansion perm to diff of (000000 001000) The bottom line: If X  X = 00000010 then F(X,K)  F(X,K) = 00000010 with prob. 3/4 Part 1  Cryptography 17
Slide 18 - TDES Suppose R  R = 0000 0010 Suppose K is unknown key Then with probability 3/4 F(R,K)  F(R,K) = 0000 0010 Input to next round looks like input to current round Maybe we can chain this thru multiple rounds! Part 1  Cryptography 18
Slide 19 - TDES Differential Attack Select P and P with P  P = 0x0002 Part 1  Cryptography 19 (L0,R0) = P L1 = R0 R1 = L0  F(R0,K1) L2 = R1 R2 = L1  F(R1,K2) L3 = R2 R3 = L2  F(R2,K3) L4 = R3 R4 = L3  F(R3,K4) C = (L4,R4) (L0,R0) = P L1 = R0 R1 = L0  F(R0,K1) L2 = R1 R2 = L1  F(R1,K2) L3 = R2 R3 = L2  F(R2,K3) L4 = R3 R4 = L3  F(R3,K4) C = (L4,R4) P  P = 0x0002 With probability 3/4 (L1,R1)  (L1,R1) = 0x0202 With probability (3/4)2 (L2,R2)  (L2,R2) = 0x0200 With probability (3/4)2 (L3,R3)  (L3,R3) = 0x0002 With probability (3/4)3 (L4,R4)  (L4,R4) = 0x0202 C  C = 0x0202
Slide 20 - TDES Differential Attack Choose P and P with P  P = 0x0002 If C  C = 0x0202 then R4 = L3  F(R3,K4) R4 = L3  F(R3,K4) R4 = L3  F(L4,K4) R4 = L3  F(L4,K4) and (L3,R3)  (L3,R3) = 0x0002 And L3 = L3 and C=(L4,R4) and C=(L4,R4) are all known and L3 = R4  F(L4,K4) L3 = R4  F(L4,K4) Then for the correct subkey K4 we have R4  F(L4,K4) = R4  F(L4,K4) Part 1  Cryptography 20
Slide 21 - TDES Differential Attack Choose P and P with P  P = 0x0002 If C  C = (L4, R4)  (L4, R4) = 0x0202 Then for the correct subkey K4 R4  F(L4,K4) = R4  F(L4,K4) which we rewrite as R4  R4 = F(L4,K4)  F(L4,K4) Expanding, we find 0010 = SBoxRight( l0l2l6l5l0l3  k13k14k15k9k10k11)  SBoxRight( l0l2l6l5l0l3  k13k14k15k9k10k11) where L4 = l0l1l2l3l4l5l6l7 Inputs to SBoxLeft are identical, so we gain no information on other bits of K4 Part 1  Cryptography 21
Slide 22 - TDES Differential Attack Algorithm to find right 6 bits of subkey K4 count[i] = 0, for i=0,1,. . .,63 for i = 1 to iterations Choose P and P with P  P = 0x0002 Given corresponding C and C if C  C = 0x0202 for K = 0 to 63 if 0010 == (SBoxRight( l0l2l6l5l0l3 K)SBoxRight( l0l2l6l5l0l3 K)) increment count[K] end if next K end if next i All K with max count[K] are possible (partial) K4 Part 1  Cryptography 22
Slide 23 - TDES Differential Attack Choose 100 pairs P and P with P P= 0x0002 Found 47 of these give C  C = 0x0202 Tabulate counts for these 47 Counts of 47 for each K  {000001,001001,110000,111000} No other count exceeds 39 Implies that K4 is one of 4 values, that is, k13k14k15k9k10k11 {000001,001001,110000,111000} Actual key is K=1010 1001 1000 0111 Part 1  Cryptography 23