X

Download Linear Cryptanalysis of TDES PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

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

Linear Cryptanalysis of TDES PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Linear Cryptanalysis of TDES powerpoint presentation easily and in no time. This helps you give your presentation on Linear Cryptanalysis of TDES 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 Linear Cryptanalysis of TDES powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by semchandresh 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

Linear Cryptanalysis of TDES Presentation Transcript

Slide 1 - Linear Cryptanalysis of TDES Part 1  Cryptography 1
Slide 2 - Linear Approx. of Left S-Box TDES left S-box or SboxLeft Part 1  Cryptography 2 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 Notation: y0y1y2y3 = SboxLeft(x0x1x2x3x4x5) For this S-box, y1=x2 and y2=x3 both with probability 3/4 Can we “chain” this thru multiple rounds?
Slide 3 - TDES Linear Relations Recall that the expansion perm is r4r7r2r1r5r7r0r2r6r5r0r3 = expand(r0r1r2r3r4r5r6r7) And y0y1y2y3 = SboxLeft(x0x1x2x3x4x5) with y1=x2 and y2=x3 each with probability 3/4 Also expand(Ri-1)  Ki is Sboxes input at round i Then y1=r2km and y2=r1kn both with prob 3/4 New right half is y0y1y2y3… plus old left half New right bits 1 and 2 are old right bits 2 and 1 plus key bits plus old left bits 1 and 2 (prob 3/4) Bottom line: New right half bits: r1  r2  km  l1 and r2  r1  kn  l2 both with probability 3/4 Part 1  Cryptography 3
Slide 4 - Recall TDES Subkeys Key: K = k0k1k2k3k4k5k6k7k8k9k10k11k12k13k14k15 Subkey K1 = k2k4k5k6k7k1k10k11k12k14k15k8 Subkey K2 = k4k6k7k0k1k3k11k12k13k15k8k9 Subkey K3 = k6k0k1k2k3k5k12k13k14k8k9k10 Subkey K4 = k0k2k3k4k5k7k13k14k15k9k10k11 Part 1  Cryptography 4
Slide 5 - Part 1  Cryptography 5 TDES Linear Cryptanalysis (L0,R0) = (p0…p7,p8…p15) 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) Bit 1, Bit 2 (numbering from 0) p9, p10 p1p10k5, p2p9k6 p1p10k5, p2p9k6 p2k6k7, p1k5k0 p2k6k7, p1k5k0 p10k0k1, p9k7k2 p10k0k1, p9k7k2 probability 1 3/4 3/4 (3/4)2 (3/4)2 (3/4)3 (3/4)3 Known P=p0p1p2…p15 and C=c0c1c2…c15 k0  k1 = c1  p10 (3/4)3 k7  k2 = c2  p9 (3/4)3
Slide 6 - TDES Linear Cryptanalysis Computer program results Use 100 known plaintexts, get ciphertexts. For each, let P=p0p1p2…p15 and let C=c0c1c2…c15 Resulting counts c1  p10 = 0 occurs 38 times c1  p10 = 1 occurs 62 times c2  p9 = 0 occurs 62 times c2  p9 = 1 occurs 38 times Conclusions Since k0  k1 = c1  p10 we have k0  k1 = 1 Since k7  k2 = c2  p9 we have k7  k2 = 0 Actual key is K = 1010 0011 0101 0110 Part 1  Cryptography 6
Slide 7 - To Build a Better Cipher… How can cryptographers make linear and differential attacks more difficult? More rounds --- success probabilities diminish with each round Better confusion (S-boxes) --- reduce success probability on each round Better diffusion (permutations, etc.) --- harder to chain thru multiple rounds Limited mixing and limited nonlinearity, then more rounds required: TEA Strong mixing and nonlinearity, then fewer but more complex rounds: AES Part 1  Cryptography 7
Slide 8 - Side Channel Attack on RSA Part 1  Cryptography 8
Slide 9 - Side Channel Attacks Sometimes possible to recover key without directly attacking the crypto algorithm A side channel consists of “incidental information” Side channels can arise due to The way that a computation is performed Media used, power consumed, unintended emanations, etc. Induced faults can also reveal information Side channel may reveal a crypto key Paul Kocher is the leader in this field Part 1  Cryptography 9
Slide 10 - Side Channels Unintended emanations (EMSEC) Electromagnetic field (EMF) from computer screen can allow screen image to be reconstructed at a distance Smartcards have been attacked via emf emanations Differential power analysis (DPA) Smartcard power usage depends on the computation Differential fault analysis (DFA) Key stored on smartcard in GSM system could be read using a flashbulb to induce faults Timing analysis Different computations take different time RSA keys recovered over a network (openSSL)! Part 1  Cryptography 10
Slide 11 - The Scenario Alice’s public key: (N,e) Alice’s private key: d Trudy wants to find d Trudy can send any message M to Alice and Alice will respond with Md mod N Trudy can precisely time Alice’s computation of Md mod N Part 1  Cryptography 11
Slide 12 - Timing Attack on RSA Consider Md mod N We want to find private key d, where d = d0d1…dn Spse repeated squaring used for Md mod N Suppose, for efficiency mod(x,N) if x >= N x = x % N end if return x Part 1  Cryptography 12 Repeated Squaring x = M for j = 1 to n x = mod(x2,N) if dj == 1 then x = mod(xM,N) end if next j return x
Slide 13 - Timing Attack If dj = 0 then x = mod(x2,N) If dj = 1 then x = mod(x2,N) x = mod(xM,N) Computation time differs in each case Can attacker take advantage of this? Part 1  Cryptography 13 Repeated Squaring x = M for j = 1 to n x = mod(x2,N) if dj == 1 then x = mod(xM,N) end if next j return x mod(x,N) if x >= N x = x % N end if return x
Slide 14 - Timing Attack Choose M with M3 < N Choose M with M2 < N < M3 Let x = M and x = M Consider j = 1 x = mod(x2,N) does no “%” x = mod(xM,N) does no “%” x = mod(x2,N) does no “%” x = mod(xM,N) does “%” only if d1=1 If d1 = 1 then j = 1 step takes longer for M than for M How to make it more robust? Part 1  Cryptography 14 Repeated Squaring x = M for j = 1 to n x = mod(x2,N) if dj == 1 then x = mod(xM,N) end if next j return x mod(x,N) if x >= N x = x % N end if return x
Slide 15 - Timing Attack on RSA “Chosen plaintext” attack Choose M0,M1,…,Mm-1 with Mi3 < N for i=0,1,…,m-1 Let ti be time to compute Mid mod N t = (t0 + t1 + … + tm-1) / m Choose M0,M1,…,Mm-1 with Mi2 < N < Mi3 for i=0,1,…,m-1 Let ti be time to compute Mid mod N t = (t0 + t1 + … + tm-1) / m If t > t then d1 = 1 otherwise d1 = 0 Once d1 is known, similar approach to find d2,d3,… Part 1  Cryptography 15
Slide 16 - Side Channel Attacks If crypto is secure Trudy looks for shortcut What is good crypto? More than mathematical analysis of algorithms required Many other issues (such as side channels) must be considered See Schneier’s article Lesson: Attacker’s don’t play by the rules! Part 1  Cryptography 16
Slide 17 - Knapsack Lattice Reduction Attack Part 1  Cryptography 17
Slide 18 - Background Many combinatorial problems can be reduced to finding a “short” vector in a lattice What is a lattice? Let b1,b2,…,bn be vectors in m The set of all 1b1+2b2+…+nbn, where each i is an integer is a lattice Part 1  Cryptography 18
Slide 19 - Lattice Example Suppose b1=[1,3]T and b2=[2,1]T Then any point in the plane can be written as 1b1+2b2 for some 1,2   Since b1 and b2 are linearly independent We say the plane 2 is spanned by (b1,b2) If 1,2 are restricted to integers, the resulting span is a lattice A lattice is a discrete set of points Part 1  Cryptography 19
Slide 20 - Lattice Example Suppose b1=[1,3]T and b2=[2,1]T The lattice spanned by (b1,b2) is pictured to the right Part 1  Cryptography 20
Slide 21 - Exact Cover Exact Cover --- given a set S and a collection of subsets of S, find a collection of these subsets with each element of S is in exactly one subset Exact Cover is a combinatorial problems that can be solved by finding a “short” vector in lattice Part 1  Cryptography 21
Slide 22 - Exact Cover Exact Cover example Set S = {0,1,2,3,4,5,6} Given subsets (m = 7 elements, n = 13 subsets) Subset: 0 1 2 3 4 5 6 7 8 9 10 11 12 Elements: 013 015 024 025 036 124 126 135 146 1 256 345 346 Want to find a collection of these subsets with each element of S in exactly one subset Could try all 213 possibilities If problem is too big, can try a heuristic search Many different heuristic search techniques Part 1  Cryptography 22
Slide 23 - Exact Cover Solution Exact Cover in matrix form Set S = {0,1,2,3,4,5,6} Subsets (m = 7 elements and n = 13 subsets) Subset: 0 1 2 3 4 5 6 7 8 9 10 11 12 Elements: 013 015 024 025 036 124 126 135 146 1 256 345 346 Part 1  Cryptography 23 Solve: AU = B where ui  {0,1} subsets e l e m e n t s Solution: U = [0001000001001]T m x 1 n x 1 m x n
Slide 24 - Matrix Multiplication Consider AU = B where A is a matrix and U and B are column vectors Let a1,a2,…,an be columns of A and u1,u2,…,un the elements of U Then B = u1a1 + u2a2 + … + unan Part 1  Cryptography 24 3 4 1 5 2 6 = 2 3 1 + 6 4 5 [ [ [ [ ] ] ] ] Example: 30 32 [ ] =
Slide 25 - Example We can restate AU = B as MV = W where Part 1  Cryptography 25 The desired solution is U Columns of M are linearly independent Let c0,c1,c2,…,cn be the columns of M Let v0,v1,v2,…,vn be the elements of V Then W = v0c0 + v1c1 + … + vncn Matrix M Vector W Vector V
Slide 26 - Example Part 1  Cryptography 26 Let L be the lattice spanned by c0,c1,c2,…,cn, the columns of M Recall MV = W Where W =[U,0]T and we want to find U If we can find W, we have solved problem! But W is in the lattice L since all vi are integers and W = v0c0 + v1c1 + … + vncn
Slide 27 - Facts We have W = [u0,u1,…,un-1,0,0,…,0]  L and each ui  {0,1} The length of a vector Y  N is ||Y|| = sqrt(y02+y12+…+yN-12) Then the length of W is ||W|| = sqrt(u02+u12+…+un-12)  sqrt(n) The vector W is a very short vector in L First n entries of W all 0 or 1 Last m elements of W are all 0 Can we use these facts to find U? Part 1  Cryptography 27
Slide 28 - Lattice Reduction If we can find a short vector in L, with first n entries all 0 or 1 and last m entries all 0, then we might have found U LLL lattice reduction algorithm will efficiently find short vectors in a lattice Less than 30 lines of pseudo-code for LLL! No guarantee LLL will find a specific vector But probability of success is good Part 1  Cryptography 28
Slide 29 - Knapsack Example What does lattice reduction have to do with the knapsack cryptosystem? Suppose we have Superincreasing knapsack S = [2,3,7,14,30,57,120,251] Suppose m = 41, n = 491  m-1 = 12 mod n Public knapsack: ti = 41  si mod 491 T = [82,123,287,83,248,373,10,471] Public key: T Private key: (S,m-1,n) Part 1  Cryptography 29
Slide 30 - Knapsack Example Public key: T Private key: (S,m-1,n) S = [2,3,7,14,30,57,120,251] T = [82,123,287,83,248,373,10,471] n = 491, m-1 = 12 Example: 10010110 is encrypted as 82+83+373+10 = 548 Then receiver computes 548  12 = 193 mod 491 and uses S to solve for 10010110 Part 1  Cryptography 30
Slide 31 - Knapsack LLL Attack Attacker knows public key T = [82,123,287,83,248,373,10,471] Attacker knows ciphertext: 548 Attacker wants to find ui  {0,1} s.t. 82u0+123u1+287u2+83u3+248u4+373u5+10u6+471u7=548 This can be written as T  U = 548 Part 1  Cryptography 31
Slide 32 - Knapsack LLL Attack Attacker has: T = [82,123,287,83,248,373,10,471] Wants to solve: T  U = 548 where each ui  {0,1} Same form as AU = B on previous slides! W rewrite problem as MV = W where Part 1  Cryptography 32 LLL gives us short vectors in the lattice spanned by the columns of M
Slide 33 - LLL Result LLL finds short vectors in lattice of M Matrix M’ is result of applying LLL to M Part 1  Cryptography 33  Column marked with “” has the right form Possible solution: U = [1,0,0,1,0,1,1,0]T Easy to verify this is the plaintext!
Slide 34 - Bottom Line Lattice reduction is a surprising method of attack on knapsack A cryptosystem is only secure as long as nobody has found an attack Lesson: Advances in mathematics can break cryptosystems! Part 1  Cryptography 34
 

Frequently Asked Questions

> About SlidesFinder?

Slidesfinder is a website that allows users to upload and share their PowerPoint presentations online. It provides a platform for individuals and businesses to share their ideas and knowledge through presentations, and for others to view and download these presentations for educational or professional purposes.
Slidesfinder offers a wide range of presentation topics and categories, including business, education, science, technology, health, and more. Users can also search for presentations using keywords, tags, or by category. The website provides tools to create professional presentations with rich media, animations, and graphics.



One of the key features of Slidesfinder is its user-friendly interface, which allows users to easily upload, view, and share presentations. Users can also embed their presentations in their websites or blogs using the website's embed code feature.
Slidesfinder also offers premium services, such as the ability to create private presentations and to download presentations in high-quality formats. However, the basic features of Slidesfinder are free to use, making it accessible to anyone who wants to share their ideas and knowledge through presentations.

> How do I register with SlidesFinder?

Go to registration page (you can see signup link on top of website page) https://www.slidesfinder.com/signup . If you have facebook/gmail account them just click on SIGN IN WITH FACEBOOK OR SIGN IN WITH GOOGLE button, by this you will be a registered member of slidesfinder without filling any form, required detail automatically will be fatch from your account. If you do not a Facebook account, then click on "Signup". Fill all required fields and you will be a registered member of slidesfinder.

> Is slidesfinder account confirmation is mandatory?

Yes it is mandetory to active your account to login.

> Do I need to signup/login on SlidesFinder before uploading a PowerPoint presentation?

Yes, you need to login with your account before uploading presentation. Your username will be displayed on your uploaded presentation. Your registered email id is needed for sending your stats of uploaded presentation.

Slidesfinder is a sharing website for PowerPoint presentations search and share. Find your interest in the form of powerpoint presentations on slidesfinder and save your valuable time . On Slidesfinder you get presentations from our huge library of professional ppt presentations. We believe in making your search INFORMATIVE and FUN. Find your best ppt presentation from a pool of PowerPoint presentations stacked under important industry categories like business & management, heath & Wellness,eduction & training etc. We provide unique informative PowerPoint presentation for marketers, presenters and educationists. These professional PowerPoint presentations are uploaded by professionals from across numerous industry segments.These ppt presentations are available for FREE download.

Not just finding your interest, but facilitate you broadcast your interest. We have created this platform for easy sharing of PowerPoint presentations, ensuring that these presentations get maximum exposure. Create your slidesfinder account and upload PowerPoint presentations for free, share on social media platforms and BUILD YOUR CROWD WITH PRESENTATION !!

The Great Buddha says, "Share your knowledge.It’s a way to achieve immortality"! So, start sharing knowledge and we are here to make that immortal !!

© 2013-2024 SlidesFinder. All rights reserved.

Re-productivity of content are not allowed. Without prior written permission from author, commercial use of any content is illegal.