Cryptographic Hash Functions Questions

Covers the fundamentals and practical uses of cryptographic hash functions. Topics include what a hash function does, determinism, fixed output size, and one way transformation properties. Key security properties to understand are preimage resistance, second preimage resistance, collision resistance, and the avalanche effect. Candidates should know common algorithms and the evolution of the SHA family including why older algorithms such as MD5 and SHA 1 are considered broken. Practical applications include data integrity verification, file and message checksums, commitment schemes, and the role of hashing in password storage and key derivation. Candidates should also be able to distinguish between general purpose hashing and cryptographic hashing, understand when to use slow key derivation functions or password hashing primitives rather than raw hashes, and recognize common attacks and mitigation strategies.

MediumTechnical

80 practiced

Implement in Python a safe constant-time comparison function for verifying hash digests. Explain why naive byte-by-byte early-return comparisons are dangerous, show your implementation, and state its limitations on different Python runtimes and hardware.

Sample Answer

**Approach (why early-return is dangerous)**

Naive comparisons like `a == b` or byte-by-byte loops that return on first mismatch leak the index of first differing byte via timing. An attacker measuring response time can recover secrets (e.g., HMACs). A constant-time compare accumulates differences without branching on data values.

**Implementation (Python)**

python

# constant-time comparison for bytes-like objects
def const_time_eq(a: bytes, b: bytes) -> bool:
    if not isinstance(a, (bytes, bytearray)) or not isinstance(b, (bytes, bytearray)):
        raise TypeError("bytes-like objects required")
    if len(a) != len(b):
        return False
    result = 0
    for x, y in zip(a, b):
        result |= x ^ y
    return result == 0

**Explanation**

- XOR each pair, OR into an accumulator so every byte is processed.- No data-dependent early exits or branches on byte values (only a final equality check).- Works for fixed-length digests (compare lengths first).

**Limitations**

- Python interpreter optimizations and JIT (PyPy) may introduce micro-timing differences; CPython's bytecode loop tends to be safe enough but not formally constant-time.- Hardware features (speculative execution, caches, CPU frequency scaling) can still leak tiny timing variance.- For highest assurance use library primitives implemented in C with constant-time guarantees (hmac.compare_digest in stdlib), or use crypto libraries exposing constant-time ops.

**Best practice**

Prefer hmac.compare_digest(a, b) for production; use this pattern for simple cases or when stdlib isn't available.

MediumTechnical

71 practiced

Explain how hash functions are used inside proof-of-work systems such as Bitcoin. Describe the desirable hash properties for a PoW algorithm, how difficulty adjustment relates to hash output distribution, and how collision resistance vs preimage resistance matters in this context.

Sample Answer

**Brief answer (cryptographer perspective)**

- Purpose in PoW: miners repeatedly vary a nonce in a block header until the cryptographic hash H(header) meets a network target; verification is cheap (one H) while finding the input is expensive (many trials).

**Desirable hash properties for PoW**- Pseudo‑random, uniform output distribution across n bits (no bias).- Preimage resistance / one‑wayness: given a target value it must be infeasible to find an input that hashes below the target except by brute force.- Fast to compute and verify; deterministic and stable.- Collision resistance is nice for integrity but not required for PoW security.- No structural shortcuts (no easier-than-brute-force partial preimages); this prevents miners from gaining advantage.

**Difficulty adjustment and hash distribution**- Let n = output bits and T = numeric target threshold. The success probability per hash is T / 2^n, so expected trials:

text

expected_attempts = 2^n / T

- The protocol adjusts T so that network-wide hash rate H_rate yields target block interval λ:

text

T_new ≈ T_old * (λ / observed_interval)

- Because outputs are uniform, adjusting T linearly adjusts expected work; uniformity makes difficulty proportional to inverse target.

**Collision vs preimage resistance**- Preimage resistance (and absence of faster than brute‑force partial preimages) is critical: miners must expend ~expected_attempts work.- Collision resistance (finding x≠y with H(x)=H(y)) is orthogonal: collisions don't help meet a numeric threshold unless they give a shortcut to produce low numeric outputs—unlikely. Thus collision breaks integrity (double spends, signatures) but isn't the primary security requirement for PoW.

Result: choose a hash with strong one‑wayness and indistinguishable-from-random outputs; ensure no structural weaknesses that lower the cost below expected_attempts.

MediumTechnical

80 practiced

Design a salt scheme for password storage given the threat model where an attacker obtains a full database dump but not server-side secrets. Discuss salt length, uniqueness, storage format, and how salts protect against rainbow tables and cross-user hash reuse.

MediumTechnical

67 practiced

Compare PBKDF2, bcrypt, scrypt, and Argon2. For each algorithm discuss memory-hardness, GPU/ASIC resistance, speed tuning parameters, and recommended use-cases and parameter choices for a modern web service.

Sample Answer

**Overview — goal:** compare PBKDF2, bcrypt, scrypt, Argon2 on memory-hardness, GPU/ASIC resistance, tunable parameters, and practical parameter choices for a modern web service.

**PBKDF2**- Memory-hardness: None (CPU-bound only).- GPU/ASIC resistance: Poor; efficient on GPUs/ASICs.- Tunables: iteration count.- Use-case: legacy compatibility, key derivation when memory-hardness not required.- Recommended params: use HMAC-SHA256 with iterations ≥ 600k (adjust to target ~100–500 ms on server), but prefer a memory-hard function for password hashing.

**bcrypt**- Memory-hardness: Minimal; small fixed S-box table (~4 KB).- GPU/ASIC resistance: Better than PBKDF2 historically, but modern GPUs/ASICs still effective.- Tunables: cost factor (2^cost rounds).- Use-case: still acceptable for legacy systems.- Recommended params: cost 12–14 depending on hardware to target ~100–300 ms.

**scrypt**- Memory-hardness: Yes — parameterizable (N, r, p) to force large RAM usage per instance.- GPU/ASIC resistance: Stronger than bcrypt/PBKDF2 when N and r large; still possible specialized hardware but costlier.- Tunables: N (cpu/memory cost), r (blocksize), p (parallelization).- Use-case: good where memory-hardness is required and libraries available.- Recommended params: N=2^14..2^20, r=8, p=1 (tune to 100–500 ms and desired memory per hash e.g. 16–64 MB).

**Argon2 (Argon2id preferred)**- Memory-hardness: Designed for memory-hardness with proven trade-offs.- GPU/ASIC resistance: Best practical resistance when configured with high memory and multiple passes; Argon2id mitigates side-channel attacks.- Tunables: memory (KB), time (passes), parallelism (lanes).- Use-case: modern recommended password hashing.- Recommended params: Argon2id with memory = 64–256 MB, time = 2–4, parallelism = number of CPU cores (but limit to 1–4 in web contexts) tuned to ~200–500 ms.

**Trade-offs & deployment notes**- Balance target latency (100–500 ms) vs throughput/DoS risk.- Use unique salts, high-entropy secrets (pepper) stored separately if desired.- Prefer Argon2id for new systems; scrypt acceptable; bcrypt only if Argon2 unavailable; retire PBKDF2 for passwords unless interoperability required.- Monitor and re-evaluate parameters periodically as hardware evolves.

MediumTechnical

71 practiced

Compare Merkle–Damgård and sponge constructions in terms of resistance to length-extension, support for extendable-output functions, internal state handling, and performance trade-offs for software and hardware implementations.

Sample Answer

**Direct answer — high level comparison**

- Resistance to length-extension - Merkle–Damgård (MD): vulnerable. Given H(m) and len(m) an attacker can compute H(m || pad || m') for many MD-based hashes (SHA-1, SHA-2) because the internal chaining value is exposed as the output. - Sponge: resistant by design. Squeeze output is derived from the full internal state after absorbing; the output does not expose the internal chaining value in a way that enables simple continuation, so standard sponge hashes (Keccak/SHA‑3) avoid length-extension.

- Support for extendable-output functions (XOF) - MD: not natively an XOF. You can truncate or iterate the compression in ad-hoc ways, but that often reintroduces weaknesses. MD constructions require additional scaffolding to safely produce XOF semantics. - Sponge: native XOF support. The squeeze phase can produce arbitrary-length output (e.g., SHAKE128/256) without structural changes.

- Internal state handling and security parameters - MD: state = chaining value sized typically equal to output length (n). Security bounds relate to compression function properties; length-extension stems from exposing the chaining value as the output. - Sponge: state = b = r + c (rate r, capacity c). Security against collisions/preimage depends on capacity c (rough rule: c ≈ 2·desired security bits). The separation r/c allows tuning throughput (r) versus security margin (c). Internal permutation is the primitive, not a compression function.

- Performance trade-offs (software vs hardware) - Software: MD-based (SHA-2) often faster on general-purpose CPUs with native 32/64-bit arithmetic and optimized instruction sequences; simpler block-wise compression lends to fast pipeline and existing SIMD optimizations. Keccak/SHA‑3 can be competitive but needs tuned bit-sliced or vectorized implementations; its permutation operates on large bit-state which can be heavier without specific instructions. - Hardware/ASIC/Firmware: sponge (Keccak) tends to excel—compact permutation, good diffusion, and efficient bit-level parallelism give high throughput and low gate count in hardware; also natural for side-channel countermeasures via masking. MD variants can be implemented efficiently too, but usually need more logic for arithmetic-heavy operations. - Implementation notes: sponge's large internal state increases memory and register pressure in constrained environments; MD's incremental updates and smaller chaining value reduce memory overhead.

Practical implications for a cryptographer- Choose MD families when compatibility and fast CPU software is paramount and length-extension can be mitigated (e.g., HMAC).- Choose sponge/Keccak when you need XOF, strong resistance to length-extension, flexible security/throughput tuning, or hardware-favorable designs (e.g., lightweight protocols, hardware tokens).- Always set capacity/padding/usage according to security proofs (c >= 2·security bits), and prefer standardized constructions (HMAC for MD; SHAKE for sponge XOF).

Unlock Full Question Bank

Get access to hundreds of Cryptographic Hash Functions interview questions and detailed answers.

Join thousands of developers preparing for their dream job.