Data Integrity: Applications of Cryptographic Hash Functions

Data Integrity: Applications of Cryptographic Hash Functions 05/15/2024 Data Integrity 1

Message Authentication Code (MAC) Cryptographic hash function h(K,M) with two inputs: – Secret key K – Message M Message integrity with MAC – Sequence of messages transmitted over insecure channel – Secret key K shared by sender and recipient – Sender computes MAC c h(K,M) and transmits it along with message M – Receiver recomputes MAC from received message and compares it with received MAC – Attacker cannot compute correct MAC for a forged message – More efficient than signing each message – Secret key can be sent in a separate encrypted and signed message Compute c h(K,M) M c sent message 05/15/2024 Data Integrity M′ c′ received message Compute d h(K,M′) Accept if d c′ 2

HMAC Building a MAC from a cryptographic hash function is not immediate Because of the iterative construction of standard hash functions, the following MAC constructions are insecure: – h(K M) – h(M K) – h(K M K) HMAC provides a secure construction: – h(K A h(K B M)) – A and B are constants – Internet standard used, e.g., in IPSEC – HMAC security is the same as that of the underlying cryptographic hash function 05/15/2024 Data Integrity 3

Securing a Communication Channel Assuring both integrity and confidentiality of messages transmitted over an insecure channel Sign and encrypt – The encrypted pair (message, signature) is transmitted MAC and encrypt – The encrypted pair (message, MAC) is transmitted – Secret key for MAC can be sent in separate message – More efficient than sign and encrypt – MAC is shorter and faster to compute than signature and verification Alternatively, signing or applying MAC could be done on encrypted message M 05/15/2024 encrypted sig M Data Integrity encrypted MAC 4

Hash Chain Repeated cryptographic hashing starting from a random value r – xn r – xi h(xi 1) for i n-1 1 Sequence x1 x2 xn is pseudo-random Applications – One-time passwords – Incremental micropayments (PayWord) Key property for security is preimage resistance of hash function hash x1 x2 x3 x4 x5 x6 reveal 05/15/2024 Data Integrity 5

Validation Chain Validation chain over a sequence of plaintexts p1, p2 , , pn – xn 1 0 – xi h(pi xi 1 ) for i n 1 Incremental stream authentication [Gennaro Rohatgi] – transmit signed x1 – transmit packets (p1, x2), (p2, x3), , (pn-1, xn), (pn, xn 1) – each packet contains the hash of the next packet – the integrity of the first hash implies the integrity of the rest – any prefix of the stream is signed and cannot be repudiated – constant overhead (one hash per plaintext) – one signature (slow), n hash computations (fast) – offline method, requires reliable transmission sig, x1 05/15/2024 p1, x2 p2, x3 p3, x4 Data Integrity p4, x5 p 5, 0 6

Hash Tree Balanced binary tree defining a hierarchical hashing scheme over a set of items – a h(x1, x2) c – b h(x3, x4) – c h(a, b) – The root hash is a hierarchical digest of entire set a x1 b x2 x3 x4 x5 x6 x7 x8 [Merkle] 05/15/2024 Data Integrity 7

Hash Tree Authentication Assumptions g – Collision resistant hash function – Root hash is known Membership proof of an item c – path from the item to the root (L/R sequence) plus hash values of sibling nodes – logarithmic size and verification time Example d a x1 b x2 x3 e x4 x5 f x6 x7 x8 – g h(h(a, h(x3, x4)), d) – The proof of x4 is the sequence [(x3, L), (a , L), (d, R)] 05/15/2024 Data Integrity 8

Stream Authentication with Packet Losses Sequence of plaintexts to be transmitted p1, p2 , , pn Build a hash tree on top of items (i, pi) Transmit the signed root hash For each item pi, transmit packet (i, pi, proof(i,pi)) Logarithmic space overhead and verification time per packet Lost packets do not prevent authentication of future packets Off-line scheme 05/15/2024 Data Integrity 9