Unit 4: Message integrity and Hash function

I. Foundations of Integrity and Hashing

Cryptographic integrity mechanisms detect unauthorized changes to information. They use hash functions, message authentication codes, or digital signatures to convert an arbitrary-length message into a fixed-length value that can be checked by a receiver.

• Core security goals:
  • Integrity: Confirms that message contents have not changed.
  • Data-origin authentication: Confirms that a message came from the claimed source.
  • Non-repudiation: Uses digital signatures to provide evidence that a sender authorized a message.
• Hash-function convention: A cryptographic hash function maps a message (M) of arbitrary finite length to an (n)-bit digest (h).

h = H(M)

• (H) is the hash function.
• (M) is the input message.
• (h) is the fixed-length message digest.
  • Required hash properties:
• Preimage resistance: Given (h), finding any (M) such that (H(M)=h) should require approximately (2^n) work.
• Second-preimage resistance: Given (M), finding (M' \ne M) with the same digest should require approximately (2^n) work.
• Collision resistance: Finding any distinct pair (M,M') such that (H(M)=H(M')) should require approximately (2^{n/2}) work because of the birthday bound.
• Avalanche effect: A one-bit input change should alter roughly half the output bits unpredictably.
  • Operational assumption: Integrity is meaningful only when the expected digest or authentication value reaches the verifier through an authenticated mechanism; an attacker who can replace both a message and its unprotected digest defeats simple hashing.

II. Message Integrity

A. Message Integrity

Message integrity is the assurance that received data is exactly the data sent, without unauthorized insertion, deletion, substitution, or reordering.

• Threat model: An active attacker may modify packets, replay an earlier message, remove fields, or rearrange transactions while data crosses an untrusted network.
• Error detection versus integrity protection:
  1. Non-cryptographic checksums: A CRC detects accidental transmission errors but is not secure against an attacker who can recompute it.
  2. Cryptographic checks: A protected digest, MAC, or signature makes deliberate undetected modification computationally difficult.
• Basic hash comparison: The sender computes (H(M)), and the receiver independently hashes the received message (M_r).

Accept only if H(Mr) = expected_digest

• (M_r) is the received message.
• expected_digest is an authenticated reference value.
  • Scope requirement: Every security-relevant element must be protected, including message body, sender and receiver identifiers, sequence number, timestamp, algorithm identifier, and protocol context.
  • Freshness protection: A valid old message can pass an integrity check, so protocols bind a nonce, sequence number, or timestamp into the protected data.
  • Limitation: An ordinary unkeyed hash provides change detection but not sender authentication because anyone can compute (H(M)) for a replacement message.

B. Applications and Limitations

Integrity checks protect stored files, downloaded software, network packets, database records, and financial transactions.

• File verification: A publisher may distribute a SHA-512 digest through an authenticated channel so users can detect corruption in a downloaded image.
• Protocol use: TLS and IPsec authenticate records or packets while incorporating sequence information to resist modification and replay.
• Canonical representation: Both parties must hash identical byte sequences; differences in encoding, whitespace, or field order produce different digests.
• Endpoint limitation: Cryptography protects data in transit or storage, but it cannot guarantee integrity after a legitimate endpoint has been compromised.

III. Message Authentication

A. Message Authentication

Message authentication establishes both message integrity and the authenticity of its claimed origin, usually through a secret-key MAC or a public-key digital signature.

• Authentication requirements: The receiver must detect content modification, sender impersonation, replay, sequence alteration, and unacceptable delay.
• Message Authentication Code: A MAC algorithm accepts a secret key (K) and message (M), producing a fixed-length tag (T).

T = MAC(K, M)
Accept if Verify(K, M, T) = true

• (K) is a secret shared by authorized parties.
• (M) is the authenticated message.
• (T) is the authentication tag.
  • HMAC construction: HMAC safely combines a cryptographic hash with a secret key.

HMAC(K, M) = H((K' XOR opad) || H((K' XOR ipad) || M))

• (K') is the key adjusted to one hash-block length.
• ipad and opad are fixed inner and outer padding constants.
• XOR is bitwise exclusive OR; (||) denotes concatenation.
  • MAC versus digital signature:
    1. MAC: Both parties know (K), so verification is fast, but either party could have generated the tag.
    2. Digital signature: The sender signs with a private key and others verify with the public key, supporting public verification and non-repudiation.
  • Tag security: For a uniformly distributed (t)-bit tag, blind forgery succeeds with probability approximately (2^{-t}) per attempt.
  • Verification discipline: Implementations compare tags in constant time and reject messages before processing unauthenticated content.

B. Applications and Limitations

The appropriate mechanism depends on whether verification is private or public.

• Shared systems: HMAC is suitable for API requests, protocol records, and communication between servers sharing a key.
• Public evidence: Digital signatures are suitable for software releases, certificates, and documents that many independent parties must verify.
• Key management: A strong MAC fails if the shared key is disclosed, reused carelessly, or generated with insufficient entropy.
• Replay limitation: A MAC authenticates supplied bytes but does not independently prove freshness; counters or nonces must be included.

IV. Iterated Hash Function

A. Iterated Hash Function

An iterated hash function processes a padded message block by block, repeatedly applying a fixed-size compression function to update an internal chaining value.

• Merkle-Damgård structure: After padding, split the message into blocks (M_1,\ldots,M_N), and begin with a fixed initial value (H_0=IV).

Hi = f(Hi-1, Mi), for i = 1, 2, ..., N
digest = HN

• (IV) is the public initialization value.
• (M_i) is message block (i).
• (f) is the compression function.
• (H_i) is the chaining value after block (i).
  • Padding role: Padding makes the message length a multiple of the block size and commonly encodes the original bit length, separating messages that otherwise share padded forms.
  • Compression principle: A large input consisting of one chaining value and one message block is reduced to a new fixed-size chaining value.
  • Security inheritance: Proper Merkle-Damgård strengthening allows collision resistance of the full hash to be related to collision resistance of its compression function.
  • Length extension: For several classic iterated hashes, knowing (H(M)) and the length of (M) permits computation of a hash for (M || padding || X) without knowing (M); therefore, a raw construction such as (H(K||M)) is unsafe as a general MAC.
  • Countermeasure: HMAC uses nested keyed hashing so the exposed digest is not a reusable internal chaining state.

B. Significance and Limitations

Iteration permits messages of almost any practical length to be processed with fixed memory.

• Streaming: Each block can be processed as it arrives, so the entire file need not remain in memory.
• Parallelism limitation: A basic chain makes (Hi) depend on (H{i-1}), restricting parallel processing within one message.
• Structural attacks: Multicollision and length-extension properties arise from the construction even when the compression function has no obvious implementation defect.

V. Whirlpool

A. Whirlpool

Whirlpool is a 512-bit cryptographic hash function designed by Vincent Rijmen and Paulo Barreto, using an AES-like block-cipher structure and the Miyaguchi-Preneel compression scheme.

• Parameters: Whirlpool processes 512-bit message blocks, maintains a 512-bit chaining state, and produces a 512-bit digest.
• Padding: A 1 bit and sufficient 0 bits are followed by a 256-bit representation of the original message length, making the total length divisible by 512.
• Block-cipher basis: Its internal transformation operates on an (8 \times 8) array of bytes and performs 10 rounds.
• Round operations:
  • SubBytes: Replaces each byte through a nonlinear S-box.
  • ShiftColumns: Cyclically shifts bytes to distribute local changes.
  • MixRows: Applies a diffusion matrix over the finite field (GF(2^8)).
  • AddRoundKey: XORs the state with the current round key.
• Compression rule: For chaining value (H_{i-1}) and block (M_i), Whirlpool uses:

Hi = EHi-1(Mi) XOR Mi XOR Hi-1

• (E{H{i-1}}(M_i)) is encryption of (Mi) using (H{i-1}) as the block-cipher key.
• (H_i) is the resulting chaining value.
  • Security scale: An ideal 512-bit digest offers about (2^{256}) collision resistance and (2^{512}) preimage resistance.

B. Applications and Limitations

Whirlpool is suitable where a wide digest and conservative collision-security margin are desired.

• Application: It can verify file integrity and serve as a component in cryptographic systems that explicitly standardize Whirlpool.
• Implementation cost: Its 512-bit state and table-based transformations may be less convenient than SHA-2 on platforms with optimized SHA instructions.
• Compatibility: Protocol participants must agree on the exact Whirlpool version and byte representation because earlier revisions used different internal details.

VI. SHA512

A. SHA512

SHA-512 is a SHA-2 family hash standardized by NIST; it processes 1024-bit blocks using 64-bit operations and returns a 512-bit digest.

• Padding: Append a 1 bit, then 0 bits, then the original message length as a 128-bit integer so the final size is a multiple of 1024 bits.
• Initial state: Eight specified 64-bit words (H_0,\ldots,H_7) form the initial 512-bit chaining value.
• Message schedule: Sixteen 64-bit block words are expanded to 80 words (W0,\ldots,W{79}) using rotations, shifts, and modular addition.
• Round processing: Each of 80 rounds updates working words (a,b,c,d,e,f,g,h) using a schedule word (W_t) and fixed constant (K_t).

T1 = h + Σ1(e) + Ch(e,f,g) + Kt + Wt
T2 = Σ0(a) + Maj(a,b,c)

• Addition is modulo (2^{64}).
• (Ch) selects bits from (f) or (g) according to (e).
• (Maj) outputs the majority bit of (a,b,c).
• (\Sigma_0) and (\Sigma_1) combine fixed rotations.
  • Finalization: The working words are added to the previous state; after the final block, the eight state words are concatenated.
  • Security: SHA-512 is designed for approximately 256-bit collision security and 512-bit preimage security, subject to ideal-hash assumptions.
  • Variants: SHA-512/224 and SHA-512/256 use distinct initial values and truncate output to 224 or 256 bits; they are not merely arbitrary truncations of standard SHA-512.

B. Applications and Limitations

SHA-512 performs especially well on processors designed for efficient 64-bit arithmetic.

• Applications: It supports file hashing, digital-signature preprocessing, HMAC-SHA-512, and integrity verification.
• Password limitation: Fast hashing is undesirable for password storage; a salted password-hashing function such as Argon2, scrypt, bcrypt, or PBKDF2 is required.
• Authentication limitation: SHA-512 alone is unkeyed and therefore does not authenticate a sender.

VII. Description of MD Hash Family

A. Description of MD Hash Family

The Message Digest family consists of early cryptographic hash algorithms, principally MD2, MD4, and MD5, developed by Ronald Rivest.

• MD2: Designed for 8-bit processors, MD2 processes 128-bit blocks, uses byte substitutions and a checksum, and outputs 128 bits; practical collisions make it obsolete.
• MD4: MD4 processes 512-bit blocks through three rounds of 32-bit operations and outputs 128 bits; its speed-oriented design led to serious collision weaknesses.
• MD5: MD5 strengthened MD4 with four rounds totaling 64 steps, four 32-bit state words, nonlinear Boolean functions, constants, additions modulo (2^{32}), and left rotations.
• MD5 iteration: Each 512-bit block updates a 128-bit state conventionally denoted (A,B,C,D); the final digest concatenates those four 32-bit words.
• Padding pattern: MD4 and MD5 append a 1 bit, zeros, and a 64-bit encoding of the original message length, producing a multiple of 512 bits.
• Security failure: MD5 collisions can be deliberately generated, including chosen-prefix collisions where attackers select two different prefixes and construct suffixes that yield the same digest.
• Current status: MD2, MD4, and MD5 must not be used for collision-sensitive security tasks such as certificates, digital signatures, or software authenticity.

B. Historical Significance and Limitations

The MD family established design patterns that influenced later iterated hashes, including SHA-1 and SHA-2.

• Historical contribution: Its compression-based iteration, modular arithmetic, Boolean functions, and bit rotations became common hash-design components.
• Residual non-security use: MD5 may identify accidental duplicate files, but only when adversarial manipulation is impossible.
• Migration requirement: Security systems should use approved modern hashes such as SHA-256, SHA-512, SHA-3, or another algorithm required by the applicable standard.
• General lesson: A 128-bit digest provides at most about (2^{64}) generic collision resistance, and cryptanalytic weaknesses can reduce the practical effort far below that bound.