Unit 4: Message integrity and Hash function - Subjective Questions

Message integrity is the assurance that a message has not been altered, inserted, deleted, reordered, or replayed without authorization during transmission or storage.

Confidentiality and integrity provide different security services:

• Confidentiality prevents unauthorized parties from understanding the message.
• Integrity enables the receiver to detect unauthorized modification of the message.
• Encryption alone may hide the contents but does not always prevent an attacker from changing ciphertext bits.
• In some encryption modes, modification of ciphertext can cause predictable changes in the decrypted plaintext.

For example, if an attacker changes an encrypted bank transaction, the receiver may decrypt a modified transaction without knowing that tampering occurred. Therefore, mechanisms such as a Message Authentication Code (MAC), an authenticated-encryption scheme, or a digital signature must be used to provide integrity.

Message authentication provides assurance about the origin of a message and confirms that its contents have not been modified.

The three concepts can be distinguished as follows:

• Message integrity: Detects whether the message was altered.
• Message authentication: Verifies both message integrity and the claimed source of the message.
• Entity authentication: Verifies the identity of a communicating party, generally at the beginning of or during a communication session.

For example, a valid MAC on a message indicates that:

1. The message was generated by an entity possessing the secret key.
2. The message has not been modified after the MAC was computed.

However, message authentication does not automatically guarantee freshness. Timestamps, sequence numbers, or nonces are required to prevent replay of an old but valid authenticated message.

The major techniques are:

• Cryptographic hash function: Produces a fixed-length digest . It detects accidental changes, but by itself it does not authenticate the sender because anyone can recompute the hash.
• Message Authentication Code: Uses a shared secret key, such as . It provides integrity and source authentication between parties sharing .
• Digital signature: The sender signs a message digest using a private key. Anyone with the corresponding public key can verify the signature.

Comparison:

• A plain hash uses no secret key and provides no source authentication.
• A MAC uses a shared secret key, is efficient, and does not provide non-repudiation.
• A digital signature uses an asymmetric key pair, supports public verification, and can provide non-repudiation.

In practice, hashes are building blocks for MACs and signatures, while authenticated-encryption algorithms can provide confidentiality, integrity, and authentication together.

A cryptographic hash function maps a message of arbitrary length to a fixed-length digest:

Its essential properties are:

• Determinism: The same input always produces the same digest.
• Efficient computation: should be easy to calculate for any message.
• Preimage resistance: Given , it should be computationally infeasible to find an such that .
• Second-preimage resistance: Given a particular , it should be infeasible to find such that .
• Collision resistance: It should be infeasible to find any two distinct messages and with the same digest.
• Avalanche effect: A small input change should cause extensive and unpredictable digest changes.
• Uniformity: Digest values should appear uniformly distributed over the output space.

For an ideal -bit hash, preimage attacks require approximately operations, while generic collision attacks require approximately operations.

An iterated hash function divides a padded message into fixed-size blocks and processes them sequentially through a compression function.

Let the padded message be:

The operation is:

Here:

• is the fixed initialization value.
• is the current message block.
• is the previous chaining value.
• is a fixed-input-length compression function.
• is the final message digest.

This approach allows a hash function to process messages of arbitrary length while using a fixed-size internal state. MD5, SHA-1, SHA-256, and SHA-512 use forms of iterative processing. Proper padding and inclusion of the message length are important for avoiding ambiguity between differently sized messages.

The Merkle-Damgård construction builds a variable-input-length hash function from a fixed-input-length collision-resistant compression function.

Its main steps are:

1. Append a single bit to the message.
2. Append enough bits to reach the required block position.
3. Append a fixed-size representation of the original message length.
4. Divide the result into equal-sized blocks.
5. Process each block through the compression function using a chaining value.

This form of padding is often called Merkle-Damgård strengthening.

The length field serves several purposes:

• It makes the encoding of a padded message unambiguous.
• It distinguishes messages that differ only by trailing zeros.
• It supports the security proof that collision resistance of the compression function transfers to the complete construction under appropriate assumptions.

A limitation is that ordinary Merkle-Damgård hashes can permit length-extension attacks when a raw digest is incorrectly used as a MAC.

The three attacks have different goals:

• Preimage attack: Given a digest , find a message such that .
• Second-preimage attack: Given a specific message , find another message such that .
• Collision attack: Find any two distinct messages and such that .

For an ideal -bit hash:

• Preimage resistance is approximately operations.
• Second-preimage resistance is generally approximately operations.
• Collision resistance is approximately operations.

The lower collision complexity follows from the birthday paradox. After generating roughly random digests, the probability that two of them match becomes significant. Thus, a 128-bit digest offers only about 64 bits of generic collision security, whereas a 512-bit digest ideally offers about 256 bits of collision security.

The Message Digest (MD) family, designed mainly by Ronald Rivest, includes MD2, MD4, and MD5.

• MD2: Designed for 8-bit systems, processes 128-bit blocks and produces a 128-bit digest. It is obsolete and cryptographically broken.
• MD4: Designed for high-speed software implementation on 32-bit processors. It uses a 128-bit state, produces a 128-bit digest, and performs three rounds. Serious collisions can be generated efficiently.
• MD5: A strengthened successor to MD4. It processes 512-bit blocks, maintains a 128-bit state, and uses four rounds containing 64 operations. Practical collision attacks make it unsuitable for security-sensitive applications.

The MD family strongly influenced later hash functions, particularly SHA-1 and the SHA-2 design style. Its members commonly use:

• Iterated compression
• Little-endian word processing
• Boolean functions
• Modular addition
• Circular left rotations

Today, MD4 and MD5 must not be used for collision-resistant applications such as certificates or digital signatures.

MD5 accepts an arbitrary-length message and produces a 128-bit digest.

Processing steps:

1. Append a bit to the message.
2. Append bits until the length is congruent to .
3. Append the original message length as a 64-bit little-endian value.
4. Divide the padded message into 512-bit blocks.
5. Initialize four 32-bit chaining variables , , , and .
6. Process each block through four rounds, with 16 operations per round.

The four Boolean functions are:

Each operation uses a message word, a constant, modular addition modulo , and a circular left rotation. The final values of , , , and are concatenated to produce the digest.

MD4 and MD5 comparison:

• Both process 512-bit message blocks and produce a 128-bit digest.
• Both use four 32-bit chaining variables and operations such as Boolean functions, modular addition, and circular rotation.
• MD4 has three rounds containing 48 operations.
• MD5 has four rounds containing 64 operations.
• MD5 uses more constants, different message-word orders, and additional transformations to reduce weaknesses found in MD4.
• MD4 is generally faster because it performs fewer operations.
• MD5 is slower than MD4 but was originally intended to provide a higher security margin.

However, both algorithms are now insecure:

• MD4 collisions can be generated extremely efficiently.
• MD5 is vulnerable to practical collision and chosen-prefix collision attacks.
• Their 128-bit output also limits generic collision security to approximately operations.

Neither should be selected for modern digital signatures, certificates, file-authenticity systems, or adversarial integrity protection.

A length-extension attack allows an attacker who knows and the length of to compute a valid digest for a message of the form:

where is the original hash padding and is attacker-chosen data, without knowing the complete original message in some applications.

The attack occurs because, in a Merkle-Damgård hash, the final digest exposes the final chaining state. The attacker can use that digest as the starting state and continue processing additional blocks.

It becomes dangerous when a system constructs a MAC as:

An attacker may extend the message and generate a matching digest without learning .

Prevention methods:

• Use HMAC, which applies the hash in a nested keyed construction.
• Use a standardized MAC such as CMAC or KMAC.
• Use authenticated encryption when confidentiality is also required.
• Do not treat an unkeyed hash or a naive secret-prefix hash as a secure MAC.

Length extension does not directly reveal the original message or produce an arbitrary collision.

SHA-512 produces a 512-bit digest and processes messages in 1024-bit blocks.

Padding:

• Append one bit to the message.
• Append zero bits so that:

• Append the original length as a 128-bit unsigned integer.

Thus, the padded message length becomes a multiple of 1024 bits.

Parsing:

• Divide the padded message into 1024-bit blocks.
• Each block is interpreted as sixteen 64-bit words.

Initialization:

SHA-512 uses eight predefined 64-bit initial hash values:

For each message block, these values initialize eight working variables, commonly denoted . After 80 rounds, the working variables are added to the previous hash state modulo . After the final block, the eight 64-bit state words are concatenated to produce the 512-bit digest.

For each 1024-bit message block, SHA-512 constructs eighty 64-bit schedule words through .

For the first sixteen words:

For the remaining words:

The eight working variables are initialized from the current chaining state. In round :

The registers are shifted and updated, including:

After 80 rounds, each working variable is added modulo to its corresponding chaining word. This combination of schedule expansion, Boolean functions, rotations, constants, and modular addition provides diffusion and nonlinearity.

SHA-512 uses six important logical functions over 64-bit words.

Choice function:

It chooses bits from or according to the corresponding bits of .

Majority function:

Each output bit is the majority value of the corresponding input bits.

Uppercase sigma functions:

Lowercase sigma functions:

The uppercase functions are used in round processing, while the lowercase functions are used to expand the message schedule.

SHA-512 is a member of the SHA-2 family and produces a 512-bit message digest.

Expected ideal security:

• Preimage resistance: approximately operations.
• Second-preimage resistance: approximately operations for ordinary messages.
• Collision resistance: approximately operations because of the birthday bound.

Advantages:

• No practical collision attack is known against full SHA-512.
• Its large digest provides a high security margin.
• It is standardized and widely supported.
• It performs efficiently on many 64-bit processors.
• It is suitable as a component of HMAC and digital-signature schemes.

Limitations:

• Its 512-bit output may consume more storage and bandwidth than required.
• It may be slower on small 32-bit processors than SHA-256.
• As a Merkle-Damgård-style hash, it should not be used in naive secret-prefix MAC constructions because of length extension.
• A plain SHA-512 digest does not authenticate the sender.

SHA-512/256 may be used when a shorter digest and 256-bit output are preferred.

Whirlpool is a cryptographic hash function designed by Vincent Rijmen and Paulo Barreto. It produces a 512-bit digest and processes 512-bit message blocks.

Its design is based on a dedicated 512-bit block cipher called , which follows a substitution-permutation network influenced by the AES design strategy.

Main features:

• 512-bit internal state
• 512-bit message blocks
• 512-bit output digest
• Ten rounds in the internal block-cipher transformation
• Byte substitution, permutation, diffusion, key addition, and round constants

Whirlpool uses the Miyaguchi-Preneel compression structure. If is the previous chaining value and is the current block, the update can be represented as:

where denotes the internal block-cipher transformation.

The message is padded, divided into blocks, and processed iteratively. The feed-forward of both the message and previous state helps bind the compression output to its inputs.

Whirlpool represents its 512-bit state as an matrix of bytes. Each of its ten rounds applies several transformations:

• SubBytes: Each byte is replaced through a nonlinear substitution box. This provides confusion and resistance against linear and differential attacks.
• ShiftColumns: Bytes are cyclically shifted by different offsets, distributing bytes across columns.
• MixRows: Each row is transformed through matrix multiplication over the finite field . This provides strong diffusion.
• AddRoundKey: The state is combined with the current round key using bitwise XOR.
• Round constants: Constants are incorporated into the key schedule to break symmetry between rounds.

The round keys are generated using transformations related to those used on the data state. After ten rounds, the block-cipher output is combined with the input block and previous chaining value through the Miyaguchi-Preneel feed-forward operation.

Together, substitution supplies nonlinearity, while shifting and mixing cause each input byte to influence many output bytes.

SHA-512 and Whirlpool comparison:

• Both produce a 512-bit digest.
• SHA-512 processes 1024-bit message blocks, whereas Whirlpool processes 512-bit message blocks.
• SHA-512 maintains eight 64-bit state words and performs 80 rounds for each block.
• Whirlpool uses a 512-bit state arranged as an byte matrix and applies 10 block-cipher-like rounds.
• SHA-512 uses modular addition, rotations, shifts, Boolean functions, message scheduling, and fixed constants.
• Whirlpool uses byte substitution, permutation, finite-field diffusion, round-key addition, and a block-cipher-based compression structure.
• SHA-512 belongs to the SHA-2 family and follows an MD-style iterative design.
• Whirlpool uses the Miyaguchi-Preneel construction based on a dedicated block cipher.

For an ideal 512-bit digest, both target about preimage security and collision security. SHA-512 is more widely standardized and deployed, while Whirlpool provides a structurally different alternative with strong diffusion.

HMAC, or Hash-based Message Authentication Code, combines a cryptographic hash function with a secret key.

Its construction is:

where:

• is the key adjusted to the hash block size.
• is the inner padding constant.
• is the outer padding constant.
• is the message.

Operation:

1. Combine the adjusted key with the inner pad.
2. Hash that value together with the message.
3. Combine the key with the outer pad.
4. Hash the outer value together with the inner digest.

HMAC provides integrity and source authentication because only parties possessing the secret key can generate the correct tag. The nested construction prevents the ordinary length-extension problem associated with naive constructions such as . The receiver recomputes the tag and compares it in constant time with the received tag.

A suitable procedure can use HMAC with a sequence number or nonce.

Sender procedure:

1. Establish a strong shared secret key through a secure key-establishment mechanism.
2. Assign a unique sequence number to each message.
3. Form the authenticated data:

4. Compute:

5. Transmit .

Receiver procedure:

1. Check that is fresh and has not been processed previously.
2. Reconstruct using the sender and receiver identities.
3. Recompute .
4. Compare and using a constant-time comparison.
5. Accept the message only if the tag is valid and the freshness check succeeds.

Justification:

• HMAC detects message modification.
• The secret key authenticates the source to another key holder.
• Identities prevent substitution between communication contexts.
• The sequence number or nonce prevents replay.
• Clear, unambiguous encoding prevents field-concatenation ambiguity.

If confidentiality is also needed, an authenticated-encryption scheme such as AES-GCM or ChaCha20-Poly1305 should be used.