Unit 6: Cryptographic Protocols - Subjective Questions

A cryptographic hash function is a function that takes an input (message) of arbitrary length and produces a fixed-size output , called the hash value, message digest, or fingerprint.

Key characteristics:

• Deterministic: The same input always produces the same output.
• Fixed output length: Regardless of input size, output is fixed (e.g., 256 bits for SHA-256).
• Efficient: Fast to compute for any given .
• One-way: Computationally infeasible to reverse.

Role in data integrity:

• When data is transmitted or stored, its hash value is computed and kept.
• Later, the hash is recomputed and compared with the stored value.
• If the values match, the data is unaltered; if they differ, the data has been modified (accidentally or maliciously).

For example, software downloads often publish a SHA-256 digest so users can verify the file has not been tampered with. Thus hash functions act as a compact, verifiable summary that detects any change in the underlying data.

A secure cryptographic hash function must satisfy the following three properties:

1. Preimage Resistance (One-wayness):

   • Given a hash value , it should be computationally infeasible to find any message such that .
   • Protects against reversing the digest to recover the input.

2. Second Preimage Resistance (Weak Collision Resistance):

   • Given an input , it should be infeasible to find a different input such that .
   • Prevents substituting a message while keeping the same digest.

3. Collision Resistance (Strong Collision Resistance):

   • It should be infeasible to find any two distinct inputs with .
   • Stronger than second preimage resistance since the attacker is free to choose both messages.

Relationship: Collision resistance implies second preimage resistance, but not vice versa. For an -bit hash, a brute-force preimage attack takes about operations, while a collision can be found in about operations due to the birthday paradox.

The birthday attack is a generic attack that exploits the birthday paradox to find collisions in a hash function faster than brute force.

Birthday paradox intuition:

• In a group of just 23 people, there is a greater than 50% chance that two share a birthday, even though there are 365 possible days.
• This is because the number of pairs grows quadratically.

Applied to hash functions:

• For a hash function with an -bit output, there are possible digests.
• To find a collision by brute force (fixing one message) requires about tries.
• Using the birthday attack, only about randomly chosen messages are needed to find some collision with high probability.

Mathematical estimate: The probability of at least one collision among messages is approximately:

Setting gives .

Impact on output length:

• Because collision search costs only , the output must be twice as long as the desired security level.
• To achieve 128-bit collision security, a hash must produce at least a 256-bit output (e.g., SHA-256).
• This is why modern standards moved away from 128-bit MD5 and 160-bit SHA-1 toward SHA-256 and beyond.

Both are security properties of hash functions but differ in the attacker's freedom and difficulty.

Example of preimage resistance:

• A password system stores . An attacker who steals the digest cannot easily recover the original password.

Example of collision resistance:

• In digital signatures, if an attacker could find two documents (benign) and (malicious) with the same hash, they could get a signature on and reuse it on . Collision resistance prevents this.

Summary: Preimage resistance protects a specific target, while collision resistance protects against any matching pair, making it a stronger and more critical requirement for signatures.

The Merkle–Damgård construction is a method to build a collision-resistant hash function that accepts arbitrary-length input from a fixed-size compression function .

Steps:

1. Padding: The message is padded so its length is a multiple of the block size. The padding usually encodes the original message length (length padding / Merkle–Damgård strengthening).

2. Splitting: The padded message is divided into blocks .

3. Initialization: A fixed initialization vector is set as the initial chaining value: .

4. Iteration: Each block is processed with the compression function:
   

5. Output: The final chaining value (optionally passed through a finalization function) is the hash digest.

Key property:

• Merkle–Damgård theorem: If the compression function is collision resistant, then the overall hash function is also collision resistant.

Usage: MD5, SHA-1, and SHA-2 are based on this construction. A known weakness is the length-extension attack, which newer designs (e.g., SHA-3's sponge construction) avoid.

A Message Authentication Code (MAC) is a short piece of information (a tag) generated from a message and a secret key, used to verify both the integrity and the authenticity of the message.

Formal description:

• Generation: where is a shared secret key and is the message.
• Verification: The receiver recomputes and checks whether .

How it provides security:

• Integrity: Any change to (or ) causes the recomputed tag to differ, revealing tampering.
• Authenticity: Since the key is shared only between sender and receiver, only a party holding could have generated a valid tag. This proves the message came from a legitimate holder of the key.

Key points:

• MACs use symmetric (shared) keys, unlike digital signatures which use asymmetric keys.
• A MAC cannot provide non-repudiation because both parties know the same key — either could have produced the tag.
• Common constructions: HMAC (hash-based) and CMAC (cipher-based).

HMAC (Hash-based Message Authentication Code) is a widely used MAC construction that securely combines a cryptographic hash function with a secret key.

HMAC definition:

where:

• is the key padded (or hashed then padded) to the hash block size.
• = inner pad (byte 0x36 repeated).
• = outer pad (byte 0x5c repeated).
• denotes concatenation, denotes XOR.

Why the naive is insecure:

• For hash functions built with the Merkle–Damgård construction (MD5, SHA-1, SHA-256), is vulnerable to a length-extension attack.
• An attacker who knows and the length of can compute for an appended message without knowing the key .
• This lets the attacker forge a valid tag for an extended message.

Why HMAC is safe:

• The nested (double) hashing with two different key-derived pads prevents the length-extension attack.
• HMAC's security has been formally proven under the assumption that the underlying compression function behaves like a pseudorandom function.

Both MACs and digital signatures authenticate messages and ensure integrity, but they differ fundamentally in their key model and properties.

Key distinctions:

• Non-repudiation: A digital signature binds the message to a unique private key, so the signer cannot later deny signing. A MAC uses a shared key, so either party could have created the tag — no non-repudiation.
• Scalability: MACs require a shared key between each pair of communicating parties; signatures rely on published public keys, easing key management across many parties.
• Performance: MACs are far faster, so they are preferred for high-volume symmetric-key communication, while signatures suit open, multi-party settings.

A digital signature is a cryptographic mechanism that lets a signer bind their identity to a message using a private key, allowing anyone with the corresponding public key to verify authenticity.

Components of a signature scheme:

• Key Generation: Produces a key pair — a public key and a private (secret) key .
• Signing algorithm: .
• Verification algorithm: .

Typical process (hash-then-sign):

1. The signer computes the hash of the message: .
2. The signer encrypts/transforms the hash with their private key to produce the signature .
3. The signer sends to the receiver.
4. The verifier computes from the received message.
5. The verifier uses the public key on to recover/compare the hash and checks .
6. If they match, the signature is valid.

Security services provided:

• Authentication: Confirms the message came from the holder of .
• Integrity: Any change to invalidates the signature.
• Non-repudiation: The signer cannot deny having signed, since only they possess .

Why hash first? Signing the fixed-size hash instead of the whole message improves efficiency and, with a collision-resistant hash, preserves security.

The RSA signature scheme uses the RSA trapdoor function in reverse: signing with the private key and verifying with the public key.

Key Generation:

• Choose two large primes and ; compute .
• Compute Euler's totient: .
• Choose public exponent with .
• Compute private exponent such that .
• Public key: ; Private key: .

Signing (using hash-then-sign):

1. Compute the message digest .
2. Compute the signature:
   
3. Send .

Verification:

1. Compute from the received message.
2. Recover the hash from the signature:
   
3. Accept the signature if .

Correctness: Since (because ), verification succeeds for genuine signatures.

Security basis: Relies on the difficulty of factoring and computing without the primes. In practice, padding schemes such as RSA-PSS are used to prevent forgery attacks on textbook RSA.

A secure digital signature scheme must satisfy several requirements to be trustworthy:

1. Authenticity:

   • The signature must verifiably prove that the message originated from the claimed signer.

2. Integrity:

   • Any alteration of the signed message must invalidate the signature, ensuring the message has not been changed.

3. Non-repudiation:

   • The signer must not be able to deny having signed the message later, since only they hold the private key.

4. Unforgeability:

   • It must be computationally infeasible for an attacker to create a valid signature for any message without the private key. The strongest notion is Existential Unforgeability under Chosen Message Attack (EUF-CMA).

5. Non-reusability:

   • A signature must be tied to a specific message and cannot be detached and reattached to a different message.

6. Signer authentication / key binding:

   • The public key must be reliably bound to the signer's identity (usually via a certificate from a trusted CA).

These requirements ensure the scheme resists impersonation, tampering, and repudiation, forming the foundation of trust in electronic transactions.

EUF-CMA stands for Existential Unforgeability under Chosen Message Attack, the standard security definition for digital signature schemes.

The security game:

1. The challenger generates a key pair and gives the public key to the adversary.
2. The adversary may adaptively request signatures on messages of its choice (the chosen message attack / signing oracle access).
3. The adversary outputs a message-signature pair .

Winning condition:

• The adversary wins if and was never queried to the signing oracle.

Security definition:

• A scheme is EUF-CMA secure if for every efficient (probabilistic polynomial-time) adversary, the probability of winning this game is negligible.

Interpretation:

• Existential forgery means the attacker only needs to forge a signature on some message (not a chosen meaningful one).
• Chosen message attack gives the attacker strong power — access to legitimate signatures on messages of its choosing.
• Because this model grants the attacker great freedom yet still demands security, a scheme meeting EUF-CMA is considered robust for real-world use.

A length-extension attack exploits the internal structure of certain hash functions to append data to a message and compute a valid hash without knowing the original message.

How it works:

• For a Merkle–Damgård hash, the final output equals the internal chaining state after processing all blocks.
• Given and the length of (but not itself), an attacker can:
  1. Treat as the intermediate chaining state.
  2. Continue the hashing process with additional data .
  3. Produce a valid .

Why it matters:

• If a MAC is naively built as , an attacker can forge tags for extended messages, breaking authentication.

Vulnerable constructions:

• MD5, SHA-1, SHA-256, SHA-512 — all based on the Merkle–Damgård construction.

Resistant constructions:

• SHA-3 (Keccak) — uses the sponge construction, which does not expose the full internal state.
• HMAC — its nested structure defeats the attack.
• SHA-512/256 and truncated variants also resist it because the full state is not revealed.

Mitigation: Use HMAC for keyed hashing, or use hash functions/modes designed to resist length extension.

Hash functions are used to store passwords securely so that the plaintext password is never kept on the server.

Basic approach:

• Instead of storing the password , the system stores .
• At login, the entered password is hashed and compared to the stored digest.
• Due to preimage resistance, an attacker who steals the database cannot easily recover the original passwords.

Why plain hashing is insufficient:

1. Precomputed / Rainbow table attacks: Attackers precompute hashes of common passwords. If two users share a password, they get identical hashes.
2. Fast hashing: General-purpose hashes (SHA-256) are fast, enabling billions of guesses per second in brute-force/dictionary attacks.

Recommended defenses:

• Salting: Add a unique random salt to each password before hashing: . This defeats rainbow tables and ensures identical passwords have different stored digests.
• Slow / memory-hard functions: Use dedicated password hashing functions like bcrypt, scrypt, Argon2, or PBKDF2 which are deliberately slow and resource-intensive, drastically increasing attack cost.
• Pepper: An additional secret value stored separately from the database can add another layer.

Conclusion: Secure password storage combines a salt, optionally a pepper, and a slow adaptive hashing algorithm rather than a plain fast cryptographic hash.

Non-repudiation is the security property that prevents a party from denying the authenticity of their actions, such as sending or signing a message.

How digital signatures provide non-repudiation:

• Signatures use an asymmetric key pair .
• Only the signer possesses the private key used to create the signature.
• Anyone can verify the signature with the public key .
• Since only the signer could have produced a valid signature, they cannot credibly deny having created it — providing legally meaningful proof of origin.

Why MACs cannot provide non-repudiation:

• MACs use a shared symmetric key known to both the sender and receiver.
• Because both parties hold the same key, either could have generated a valid tag.
• If a dispute arises, a receiver could have forged the MAC just as easily as the sender, so the tag proves nothing about which party created it.

Summary:

• Signatures: private key is unique to the signer → non-repudiation achieved.
• MACs: key is shared → only integrity and authenticity between trusting parties, no non-repudiation.

This distinction is why digital signatures are required for contracts, legal documents, and financial transactions where accountability matters.

Security of cryptographic primitives can be evaluated under two different models:

1. Unconditional (Information-Theoretic) Security:

• Security holds even against an adversary with unlimited computing power.
• Based on probability theory, not on the hardness of computational problems.
• Example: A one-time MAC based on universal hashing (e.g., using pairwise independent functions) can be provably secure for a single message.
• Limitation: Usually requires keys as long as the message and cannot be reused, making it impractical for many messages.

2. Computational Security:

• Security holds only against adversaries with bounded (polynomial-time) resources.
• Based on assumptions that certain problems are computationally infeasible (e.g., finding hash collisions, factoring large integers).
• Example: HMAC is computationally secure assuming the compression function is a pseudorandom function.
• Advantage: Practical — short reusable keys, efficient operations.

Comparison:

Conclusion: Real-world hash functions and MACs (SHA-256, HMAC) rely on computational security, since information-theoretic security is impractical for general use.

The Digital Signature Algorithm (DSA) is a federal standard (FIPS 186) based on the difficulty of the discrete logarithm problem.

Domain parameters:

• : a large prime.
• : a prime divisor of .
• : a generator of order modulo , i.e., .

Key generation:

• Private key: random with .
• Public key: .

Signing message (with hash ):

1. Choose a random per-message secret , with .
2. Compute .
3. Compute .
4. The signature is the pair . (If or , choose a new .)

Verification of on :

1. Compute .
2. Compute and .
3. Compute .
4. Accept the signature if .

Important note: The random value must be unique and secret for each signature. Reusing or leaking allows recovery of the private key . This is why deterministic nonce generation (RFC 6979) is often used.

The hash-then-sign paradigm means that a signer first computes the hash of the message and then applies the signing operation to rather than to the full message .

Reasons for hash-then-sign:

1. Efficiency: Public-key signing operations are slow. Signing a short fixed-size digest (e.g., 256 bits) is far faster than signing a large message.

2. Handling arbitrary message lengths: Signature algorithms like RSA operate on inputs bounded by the modulus size. Hashing maps any length message to a fixed short value that fits.

3. Security structure: It cleanly separates the compression (hash) from the signing (public-key) operation.

Critical hash property — Collision Resistance:

• If the hash function is not collision resistant, an attacker could find two messages with .
• The attacker could then get a legitimate signature on and present it as a valid signature on , since both share the same digest.
• This would break the scheme's unforgeability.

Therefore: Collision resistance is the essential property. This is also why the collision attacks on MD5 and SHA-1 forced their retirement from signature use, in favor of SHA-256 and stronger hashes.

Both CBC-MAC and HMAC are widely used MAC constructions but are built on different primitives.

CBC-MAC (Cipher Block Chaining MAC):

• Built from a block cipher (e.g., AES) operating in CBC mode.
• The message is split into blocks; each block is XORed with the previous ciphertext output and encrypted.
• The final ciphertext block becomes the MAC tag.
• , tag .

HMAC (Hash-based MAC):

• Built from a cryptographic hash function (e.g., SHA-256).
• Uses nested hashing with inner and outer key pads:
  

Comparison:

Key points:

• Plain CBC-MAC is insecure for variable-length messages — an attacker can forge tags by concatenating messages. This is fixed in CMAC by using derived subkeys on the last block.
• HMAC is provably secure and naturally handles arbitrary lengths, making it the more common general-purpose choice.

Conclusion: Choose CMAC when a block cipher is already available (e.g., in constrained/hardware environments), and HMAC when a strong hash function is preferred and variable-length security is needed out of the box.

The avalanche effect is a desirable property of cryptographic hash functions (and block ciphers) whereby a small change in the input produces a drastic, unpredictable change in the output.

Definition:

• Ideally, flipping a single input bit should flip each output bit with probability .
• On average, about half of the output bits change for any single-bit input change.

Example:

• Consider hashing two nearly identical strings:
  • H("hello") and H("hellp")
• Even though the inputs differ by one letter, their digests will look completely unrelated, with roughly 50% of bits differing.

Why it matters for data integrity:

1. Tamper detection: Any minor modification of the data — even a single bit flip — produces a completely different hash, making tampering easy to detect.

2. Unpredictability: An attacker cannot make controlled small changes to the output by making small input changes, which helps resist manipulation.

3. Supports collision resistance: Strong diffusion makes it hard to engineer two inputs that map to the same output.

Conclusion: The avalanche effect ensures that hash outputs are highly sensitive to input changes, which is fundamental to using hashes as reliable integrity fingerprints.