X

OR
X

Iframe embed code :

Presentation url :

X

Description :

Hash functions ppt presentation.

Tags :

cryptocurrency | crypto | bitcoin | elon musk | cryptanalysis | hash functions

Home / Computers & Web / Computers & Web Presentations / Hash Functions PowerPoint Presentation

# Hash Functions PowerPoint Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Hash Functions powerpoint presentation easily and in no time. This helps you give your presentation on Hash Functions 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 Hash Functions powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by freelancepresenter in Computers & Web ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

## Hash Functions Presentation Transcript

 Slide 1 - Hash Functions Part 1  Cryptography 1
 Slide 2 - Hash Function Motivation Part 1  Cryptography 2 Suppose Alice signs M Alice sends M and S = [M]Alice to Bob Bob verifies that M = {S}Alice Aside: Is it OK to just send S? If M is big, [M]Alice is costly to compute Suppose instead, Alice signs h(M), where h(M) is much smaller than M Alice sends M and S = [h(M)]Alice to Bob Bob verifies that h(M) = {S}Alice
 Slide 3 - Crypto Hash Function Part 1  Cryptography 3 Crypto hash function h(x) must provide Compression --- output length is small Efficiency --- h(x) easy to computer for any x One-way --- given a value y it is infeasible to find an x such that h(x) = y Weak collision resistance --- given x and h(x), infeasible to find y  x such that h(y) = h(x) Strong collision resistance --- infeasible to find any x and y, with x  y such that h(x) = h(y) Lots of collisions exist --- but hard to find
 Slide 4 - Pre-Birthday Problem Part 1  Cryptography 4 Suppose N people in a room How large must N be before the probability someone has same birthday as me is  1/2 Solve: 1/2 = 1 - (364/365)N for N Find N = 253
 Slide 5 - Birthday Problem Part 1  Cryptography 5 How many people must be in a room before probability is  1/2 that two or more have same birthday? 1  365/365  364/365   (365N+1)/365 Set equal to 1/2 and solve: N = 23 Surprising? A paradox? Maybe not: “Should be” about sqrt(365) since we compare all pairs x and y
 Slide 6 - Of Hashes and Birthdays Part 1  Cryptography 6 If h(x) is N bits, then 2N different hash values are possible sqrt(2N) = 2N/2 Therefore, hash about 2N/2 random values and you expect to find a collision Implication: secure N bit symmetric key requires 2N1 work to “break” while secure N bit hash requires 2N/2 work to “break”
 Slide 7 - Non-crypto Hash (1) Part 1  Cryptography 7 Data X = (X0,X1,X2,…,Xn-1), each Xi is a byte Spse hash(X) = X0+X1+X2+…+Xn-1 Is this secure? Example: X = (10101010,00001111) Hash is 10111001 But so is hash of Y = (00001111,10101010) Easy to find collisions, so not secure…
 Slide 8 - Non-crypto Hash (2) Part 1  Cryptography 8 Data X = (X0,X1,X2,…,Xn-1) Suppose hash is h(X) = nX0+(n-1)X1+(n-2)X2+…+1Xn-1 Is this hash secure? At least h(10101010,00001111)h(00001111,10101010) But hash of (00000001,00001111) is same as hash of (00000000,00010001) Not one-way, but this hash is used in the (non-crypto) application rsync
 Slide 9 - Non-crypto Hash (3) Part 1  Cryptography 9 Cyclic Redundancy Check (CRC) Essentially, CRC is the remainder in a long division problem Good for detecting burst errors But easy to construct collisions CRC sometimes mistakenly used in crypto applications (WEP)
 Slide 10 - Popular Crypto Hashes Part 1  Cryptography 10 MD5 --- invented by Rivest 128 bit output Note: MD5 collision recently found SHA-1 --- A US government standard (similar to MD5) 180 bit output Many others hashes, but MD5 and SHA-1 most widely used Hashes work by hashing message in blocks
 Slide 11 - Crypto Hash Design Part 1  Cryptography 11 Desired property: avalanche effect Change to 1 bit of input should affect about half of output bits Crypto hash functions consist of some number of rounds Want security and speed Avalanche effect after few rounds But simple rounds Analogous to design of block ciphers
 Slide 12 - Tiger Hash Part 1  Cryptography 12 “Fast and strong” Designed by Ross Anderson and Eli Biham --- leading cryptographers Design criteria Secure Optimized for 64-bit processors Easy replacement for MD5 or SHA-1
 Slide 13 - Tiger Hash Part 1  Cryptography 13 Like MD5/SHA-1, input divided into 512 bit blocks (padded) Unlike MD5/SHA-1, output is 192 bits (three 64-bit words) Truncate output if replacing MD5 or SHA-1 Intermediate rounds are all 192 bits 4 S-boxes, each maps 8 bits to 64 bits A “key schedule” is used
 Slide 14 - Tiger Outer Round Part 1  Cryptography 14 Input is X X = (X0,X1,…,Xn-1) X is padded Each Xi is 512 bits There are n iterations of diagram at left One for each input block Initial (a,b,c) constants Final (a,b,c) is hash Looks like block cipher! F7 F9  W   c a b c a b F5 key schedule key schedule c a b W W Xi
 Slide 15 - Tiger Inner Rounds Part 1  Cryptography 15 Each Fm consists of precisely 8 rounds 512 bit input W to Fm W=(w0,w1,…,w7) W is one of the input blocks Xi All lines are 64 bits The fm,i depend on the S-boxes (next slide) fm,0 fm.1 fm,2 fm,7 w0 w1 w2 w7 c a b c a b
 Slide 16 - Tiger Hash: One Round Part 1  Cryptography 16 Each fm,i is a function of a,b,c,wi and m Input values of a,b,c from previous round And wi is 64-bit block of 512 bit W Subscript m is multiplier And c = (c0,c1,…,c7) Output of fm,i is c = c  wi a = a  (S0[c0]  S1[c2]  S2[c4]  S3[c6]) b = b + (S3[c1]  S2[c3]  S1[c5]  S0[c7]) b = b  m Each Si is S-box: 8 bits mapped to 64 bits
 Slide 17 - Tiger Hash Key Schedule Part 1  Cryptography 17 Input is X X=(x0,x1,…,x7) Small change in X will produce large change in key schedule output x0 = x0  (x7  0xA5A5A5A5A5A5A5A5) x1 = x1  x0 x2 = x2  x1 x3 = x3  (x2  ((~x1) << 19)) x4 = x4  x3 x5 = x5 +x4 x6 = x6  (x5  ((~x4) >> 23)) x7 = x7  x6 x0 = x0 +x7 x1 = x1  (x0  ((~x7) << 19)) x2 = x2  x1 x3 = x3 +x2 x4 = x4  (x3  ((~x2) >> 23)) x5 = x5  x4 x6 = x6 +x5 x7 = x7 (x6  0x0123456789ABCDEF)
 Slide 18 - Tiger Hash Summary (1) Part 1  Cryptography 18 Hash and intermediate values are 192 bits 24 rounds S-boxes: Claimed that each input bit affects a, b and c after 3 rounds Key schedule: Small change in message affects many bits of intermediate hash values Multiply: Designed to insure that input to S-box in one round mixed into many S-boxes in next S-boxes, key schedule and multiply together designed to insure strong avalanche effect
 Slide 19 - Tiger Hash Summary (2) Part 1  Cryptography 19 Uses lots of ideas from block ciphers S-boxes Multiple rounds Mixed mode arithmetic At a higher level, Tiger employs Confusion Diffusion
 Slide 20 - HMAC Part 1  Cryptography 20 Can compute a MAC of M with key K using a “hashed MAC” or HMAC HMAC is a keyed hash Why do we need a key? How to compute HMAC? Two obvious choices h(K,M) h(M,K)
 Slide 21 - HMAC Part 1  Cryptography 21 Should we compute HMAC as h(K,M) ? Hashes computed in blocks h(B1,B2) = F(F(A,B1),B2) for some F and constant A Then h(B1,B2) = F(h(B1),B2) Let M’ = (M,X) Then h(K,M’) = F(h(K,M),X) Attacker can compute HMAC of M’ without K Is h(M,K) better? Yes, but… if h(M’) = h(M) then we might have h(M,K)=F(h(M),K)=F(h(M’),K)=h(M’,K)
 Slide 22 - The Right Way to HMAC Part 1  Cryptography 22 Described in RFC 2104 Let B be the block length of hash, in bytes B = 64 for MD5 and SHA-1 and Tiger ipad = 0x36 repeated B times opad = 0x5C repeated B times Then HMAC(M,K) = H(K  opad, H(K  ipad, M))
 Slide 23 - Hash Uses Part 1  Cryptography 23 Authentication (HMAC) Message integrity (HMAC) Message fingerprint Data corruption detection Digital signature efficiency Anything you can do with symmetric crypto
 Slide 24 - Online Auction Part 1  Cryptography 24 Suppose Alice, Bob and Charlie are bidders Alice plans to bid A, Bob B and Charlie C They don’t trust that bids will stay secret Solution? Alice, Bob, Charlie submit hashes h(A), h(B), h(C) All hashes received and posted online Then bids A, B and C revealed Hashes don’t reveal bids (one way) Can’t change bid after hash sent (collision)
 Slide 25 - Spam Reduction Part 1  Cryptography 25 Spam reduction Before I accept an email from you, I want proof that you spent “effort” (e.g., CPU cycles) to create the email Limit amount of email that can be sent Make spam much more costly to send
 Slide 26 - Spam Reduction Part 1  Cryptography 26 Let M = email message Let R = value to be determined Let T = current time Sender must find R such that hash(M,R,T) = (00…0,X), where N initial bits of hash are all zero Sender then sends (M,R,T) Recipient accepts email, provided hash(M,R,T) begins with N zeros
 Slide 27 - Spam Reduction Part 1  Cryptography 27 Sender: hash(M,R,T) begins with N zeros Recipient: verify that hash(M,R,T) begins with N zeros Work for sender: about 2N hashes Work for recipient: 1 hash Sender’s work increases exponentially in N Same work for recipient regardless of N Choose N so that Work acceptable for normal email users Work unacceptably high for spammers!
 Slide 28 - Secret Sharing Part 1  Cryptography 28
 Slide 29 - Shamir’s Secret Sharing Part 1  Cryptography 29 (X0,Y0) (X1,Y1) (0,S) Two points determine a line Give (X0,Y0) to Alice Give (X1,Y1) to Bob Then Alice and Bob must cooperate to find secret S Also works in discrete case Easy to make “m out of n” scheme for any m  n X Y 2 out of 2
 Slide 30 - Shamir’s Secret Sharing Part 1  Cryptography 30 (X0,Y0) (X1,Y1) (0,S) Give (X0,Y0) to Alice Give (X1,Y1) to Bob Give (X2,Y2) to Charlie Then any two of Alice, Bob and Charlie can cooperate to find secret S But no one can find secret S A “2 out of 3” scheme X Y (X2,Y2) 2 out of 3
 Slide 31 - Shamir’s Secret Sharing Part 1  Cryptography 31 (X0,Y0) (X1,Y1) (0,S) Give (X0,Y0) to Alice Give (X1,Y1) to Bob Give (X2,Y2) to Charlie 3 points determine a parabola Alice, Bob and Charlie must cooperate to find secret S A “3 out of 3” scheme Can you make a “3 out of 4”? X Y (X2,Y2) 3 out of 3
 Slide 32 - Secret Sharing Example Part 1  Cryptography 32 Key escrow --- required that your key be stored somewhere Key can be used with court order But you don’t trust FBI to store keys We can use secret sharing Say, three different government agencies Two must cooperate to recover the key
 Slide 33 - Secret Sharing Example Part 1  Cryptography 33 (X0,Y0) (X1,Y1) (0,K) Your symmetric key is K Point (X0,Y0) to FBI Point (X1,Y1) to DoJ Point (X2,Y2) to DoC To recover your key K, two of the three agencies must cooperate No one agency can get K X Y (X2,Y2)