Secure Hashing, Digital Signatures, and Secret Sharing Principles

This presentation covers essential concepts of secure hashing, digital signatures, and secret sharing in information security. It discusses the motivation behind using hash functions, properties they must satisfy, examples like HMAC, and the importance of cryptographic hash functions. The content explores the pre-birthday problem and how cryptographic principles apply in scenarios like collision resistance. Learn key aspects from reputable sources like M. Stamp, C. Paar, and J. Pelzl.

• Security
• Cryptography
• Hash Functions
• Digital Signatures
• Information Security

lanthier_j Follow

Uploaded on Feb 21, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Secure Hashing, Digital Signatures, and Secret Sharing Slides Original Source: 1. M. Stamp, Information Security: Principles and Practice, John Wiley 2. C. Paar and J. Pelzl, Understanding Cryptography A Textbook for Students and Practitioners, Springer (www.crypto-textbook.com) 3. B. Forouzan, Cryptography and Network Security, McGraw-Hill 4. Slides from Dr. Sultan Almuhammadi

2. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 2/92

3. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 3/92

4. Hash Function Motivation Suppose Alice signs M o Alice sends M and S = [M]Alice to Bob o Bob verifies that M = {S}Alice o Can Alice just send S? If M is big, [M]Alice costly to compute & send Suppose instead, Alice signs h(M), where h(M) is much smaller than M o Alice sends M and S = [h(M)]Alice to Bob o Bob verifies that h(M) = {S}Alice 4

5. Hash Function Motivation So, Alice signs h(M) o That is, Alice computes S = [h(M)]Alice o Alice then sends (M, S) to Bob o Bob verifies that h(M) = {S}Alice What properties must h(M) satisfy? o Suppose Trudy finds M so that h(M) = h(M ) o Then Trudy can replace (M, S) with (M , S) Does Bob detect this tampering? o No, since h(M ) = h(M) = {S}Alice 5

6. Crypto Hash Function Crypto hash function h(x) must provide o Compression output length is small o Efficiency h(x) easy to compute for any x o One-way given a value y it is infeasible to find an x such that h(x) = y o Weak collision resistance given x and h(x), infeasible to find y x such that h(y) = h(x) o Strong collision resistance infeasible to find anyx and y, with x y such that h(x) = h(y) Lots of collisions exist, but hard to find any 6

7. Pre-Birthday Problem Suppose N people in a room How large must N be before the probability someone has same birthday as me is 1/2 ? o Solve: 1/2 = 1 (364/365)N for N o We find N = 253 7

8. Birthday Problem How many people must be in a room before probability is 1/2 that any two (or more) have same birthday? o 1 365/365 364/365 (365 N+1)/365 o Set equal to 1/2 and solve: N = 23 Surprising? A paradox? Maybe not: Should be about sqrt(365) since we compare all pairsx and y o And there are 365 possible birthdays 8

9. Of Hashes and Birthdays If h(x) is N bits, 2N different hash values are possible So, if you hash about 2N/2 random values then you expect to find a collision o Since sqrt(2N) = 2N/2 Implication: using an exhaustive search attack, a secure L bit symmetric key requires 2L 1 work to break while a secure N bit hash requires 2N/2 work to break o For hashing to have same security (e.g., integrity) as symmetric key 2L 1 = 2N/2 N = 2L 2 2L Hashing requires double the number of bits of symmetric key 9

10. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 10/92

11. Non-crypto Hash (1) Data X = (X0,X1,X2, ,Xn-1), each Xi is a byte Define h(X) =X0+X1+X2+ +Xn-1 Is this a secure cryptographic hash? Example: X = (10101010, 00001111) Hash is h(X) = 10111001 If Y = (00001111, 10101010) then h(X) = h(Y) Easy to find collisions, so notsecure 11

12. Non-crypto Hash (2) Data X = (X0,X1,X2, ,Xn-1) Suppose hash is defined as h(X) = nX0+(n 1)X1+(n 2)X2+ +1 Xn-1 Is this a secure cryptographic hash? Note that h(10101010, 00001111) h(00001111, 10101010) But hash of (00000001, 00001111) is same as hash of (00000000, 00010001) Not secure , but this hash is used in the (non-crypto) application rsync 12

13. Non-crypto Hash (3) Cyclic Redundancy Check (CRC) Essentially, CRC is the remainder in a long division calculation Good for detecting burst errors o Random errors unlikely to yield a collision But easy to construct collisions CRC has been mistakenly used where crypto integrity check is required (e.g., WEP) 13

14. Popular Crypto Hashes MD5 invented by Rivest o 128 bit output o Note: MD5 collisions easy to find SHA-1 A U.S. government standard, inner workings similar to MD5 o 160 bit output Many other hashes, but MD5 and SHA-1 are the most widely used Hashes work by hashing message in blocks 14

15. Crypto Hash Design Desired property: avalanche effect o 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 o Avalanche effect after few rounds o But simple rounds Analogous to design of block ciphers 15

16. Tiger Hash Fast and strong Designed by Ross Anderson and Eli Biham leading cryptographers Design criteria o Secure o Optimized for 64-bit processors o Easy replacement for MD5 or SHA-1 16

17. Tiger Hash Like MD5/SHA-1, input divided into 512 bit blocks (padded) Unlike MD5/SHA-1, output is 192 bits (three 64-bit words) o 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 17

18. Tiger Outer Round a b c Xi Input is X o X = (X0,X1, ,Xn-1) o X is padded o Each Xi is 512 bits There are n iterations of diagram at left o One for each input block Initial (a,b,c) constants Final (a,b,c) is hash Looks like block cipher! F5 W key schedule W F7 key schedule W F9 a + c b a b c 18

19. Tiger Inner Rounds a b c Each Fm consists of precisely 8 rounds 512 bit input W to Fm o W=(w0,w1, ,w7) o W is one of the input blocks Xi All lines are 64 bits The fm,i depends on the S-boxes (next slide) w0 fm,0 w1 fm.1 w2 fm,2 w7 fm,7 a b c 19

20. Tiger Hash: One Round Each fm,i is a function of a,b,c,wi and m o Input values of a,b,c from previous round o And wi is 64-bit block of 512 bit W 512/64 = 8 wi s (i.e., 8 rounds per Fm) o Subscript m is multiplier o And c = (c0,c1, ,c7) Output of fm,i is o c = c wi o a = a (S0[c0] S1[c2] S2[c4] S3[c6]) o b = b + (S3[c1] S2[c3] S1[c5] S0[c7]) o b = b m Each Si is S-box: 8 bits mapped to 64 bits 20

21. Tiger Hash Key Schedule 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) Input is X o X=(x0,x1, ,x7) Small change in X will produce large change in key schedule output 21

22. Tiger Hash Summary (1) Hash and intermediate values are 192 bits 24 (inner) rounds o S-boxes: Claimed that each input bit affects a, b and c after 3 rounds o Key schedule: Small change in message affects many bits of intermediate hash values o Multiply: Designed to ensure that input to S-box in one round mixed into many S-boxes in next S-boxes, key schedule and multiply together designed to ensure strong avalanche effect 22

23. Tiger Hash Summary (2) Uses lots of ideas from block ciphers o S-boxes o Multiple rounds o Mixed mode arithmetic At a higher level, Tiger employs o Confusion o Diffusion 23

24. Security of MD5 & SHA-x Source: https://en.wikipedia.org/wiki/SHA-3 24

25. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 25/92

26. HMAC Can compute a MAC of the message M with key Kusing a hashed MAC or HMAC HMAC is a keyed hash o Why would we need a key? How to compute HMAC? Two obvious choices: h(K,M) and h(M,K) Which is better? 26

27. HMAC Should we compute HMAC as h(K,M) ? Hashes computed in blocks o h(B1,B2) = F(F(A,B1),B2) for some F and constant A o Then h(B1,B2) = F(h(B1),B2) Let M = (M,X) o Then h(K,M ) = F(h(K,M),X) o Attacker can compute HMAC of M without K Is h(M,K) better? o 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) 27

28. The Right Way to HMAC Described in RFC 2104 Let B be the block length of hash, in bytes o 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)) 28

29. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 29/92

30. Hash Uses Authentication (HMAC) Message integrity (HMAC) Message fingerprint Data corruption detection Digital signature efficiency Anything you can do with symmetric crypto Also, many, many clever/surprising uses 30

31. Online Bids 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 A possible solution? o Alice, Bob, Charlie submit hashesh(A), h(B), h(C) o All hashes received and posted online o Then bids A, B, and C submitted and revealed Hashes don t reveal bids (one way) Can t change bid after hash sent (collision) But there is a flaw here 31

32. Spam Reduction Spam reduction Before accept email, want proof that sender spent effort to create email o Here, effort == CPU cycles Goal is to limit the amount of email that can be sent o This approach will not eliminate spam o Instead, make spam more costly to send 32

33. Spam Reduction Let M = email message R = value to be determined T = current time Sender must find R so that h(M,R,T) = (00 0,X), where N initial bits of hash value are all zero Sender then sends (M,R,T) Recipient accepts email, provided that h(M,R,T) begins with N zeros 33

34. Spam Reduction Sender: h(M,R,T) begins with N zeros Recipient: verify that h(M,R,T) begins with N zeros Work for sender: about 2Nhashes Work for recipient: always 1 hash Sender s work increases exponentially in N Small work for recipient regardless of N Choose N so that o Work acceptable for normal email users o Work is too high for spammers 34

35. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 35/92

36. Digital Signature Standard (DSS) Proposed by the National Institute of Standards and Technology (NIST) in 1991 DSS uses a digital signature algorithm (DSA): Designed to provide only the digital signature function Cannot be used for encryption or key exchange Must be a public-key technique (publicly verifiable) Use the SHA algorithm for hashing the message Example of digital signature approaches: RSA Approach DSS Approach

37. Digital Signature Approaches (DSS vs. RSA) b a PRi : Private key of user i PUi : Public key of user i d

38. Digital Signature Algorithm (DSA) NIST adopted DSA based on ElGamal digital signature with the following parameters: Prime p of length 512-1024 bits 160-bit prime q such that q | (p 1) (i.e., q divides p 1) Compute g h(p-1)/q mod p, where h < (p 1) and g > 1 Compute y gd mod p, for random d, where 0 < d < q Private key: d Public key: (p, q, g, y) The signature s = (a, b) is generated as follows: a (gr mod p) mod q, for random r, where 0 < r < q b (r-1 (SHA(M) + d a)) mod q The length of the signature s = (a, b) = (2 160) bits

39. DSA Signature Verification Given message M, signature s = (a, b), public key (p, q, g, y) 1. Compute auxiliary value w b-1 mod q 2. Compute auxiliary value u1 (w SHA(M))mod q 3. Compute auxiliary value u2 (w a) mod q 4. Compute v (gu1 yu2mod p) mod q If v a mod q signature is valid If v a mod q signature is invalid

40. DSA Example Let p = 59, q = 29, g = 3 (i.e., h = 11), and d = 7 y gd mod p 37 mod 59 4 Public key: (p, q, g, y) = (59, 29, 3, 4) Private key: d = 7 Let message M be such that SHA(M) = 26, and choose r = 10 a (gr mod p) mod q (310 mod 59) mod 29 20, and b (r-1 (SHA(M) + d a)) mod q (3 (26 + 7 20)) mod 29 5 Verify: Assume that received M generates SHA(M) = 26 w = b-1 mod q 5-1 mod 29 6 u1 w SHA(M)mod q (6 26) mod 29 11 u2 w a mod q (6 20) mod 29 4 v (gu1 yu2mod p) mod q ((311 44) mod 59) mod 29 20 Since v a mod q signature is valid Exercise: Assume receiver gets M* M (e.g., SHA(M*) = 25), show that signature is not valid

41. Outline Crypto Hash Functions Motivation and Desired Properties Examples HMAC Uses of Crypto Hash Functions Digital Signatures Secret Sharing 41/92

42. Shamirs Secret Sharing Y 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 (X1,Y1) (X0,Y0) (0,S) X 2 out of 2 42

43. Shamirs Secret Sharing Y Give (X0,Y0) to Alice Give (X1,Y1) to Bob Give (X2,Y2) to Charlie Then any two can cooperate to find secret S But one can t find secret S A 2 out of 3 scheme (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 2 out of 3 43

44. Shamirs Secret Sharing Give (X0,Y0) to Alice Give (X1,Y1) to Bob Give (X2,Y2) to Charlie 3 pts determine parabola Alice, Bob, and Charlie must cooperate to find S A 3 out of 3 scheme What about 3 out of 4 ? Y (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 3 out of 3 44

45. Secret Sharing Example Key escrow suppose it s required that your key be stored somewhere Key can be recovered with court order But you don t trust FBI to store your keys We can use secret sharing o Say, three different government agencies o Two must cooperate to recover the key 45

46. Secret Sharing Example Y 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 (X0,Y0) (X1,Y1) (X2,Y2) (0,K) X 46