Hash Functions & Merkle Structures Checkpoint

Collision/preimage resistance, Merkle-Damgard, length extension, and Merkle proofs.

1. Collision resistance for a b-bit hash is about:

2^(b/2) work 2^b work b work b^2 work

2. Preimage resistance for a b-bit hash is about:

2^b work 2^(b/2) work b work log b work

3. Merkle-Damgard hashing processes messages by:

Iterating a compression function over fixed-size blocks Encrypting each block independently Sorting blocks before hashing Using a stream cipher

4. Length extension attacks apply to:

Merkle-Damgard hashes when used as naive MACs AEAD modes HMAC One-time pads

5. HMAC prevents length extension primarily because:

It hashes with a secret key on both inner and outer layers It uses a longer hash output It uses randomness every time It is encrypted

6. A Merkle proof size for N leaves is:

O(log N) O(N) O(1) O(sqrt N)

7. If a hash is collision resistant, then a commitment using hash(nonce || message) is:

Computationally binding (assuming nonce is fixed at commit time) Information-theoretically binding Always hiding without a nonce Equivalent to encryption

8. Why is domain separation important in hash-based designs?

It prevents cross-protocol collisions between different contexts It makes hashes longer It removes the need for padding It guarantees information-theoretic security

9. Given a Merkle tree, duplicating the last leaf when a level has an odd count:

Keeps the tree balanced and deterministic Changes proof size to O(N) Breaks collision resistance Is required for preimage resistance

10. True/False: Collision resistance implies preimage resistance.

Auto-advance on pass