Constant-Time Digest Comparison

Challenge

The threat

When your code checks whether a received MAC or hash matches the expected value, the obvious implementation uses memcmp or a loop that returns as soon as it finds the first differing byte. That is a timing side channel: a mismatch in byte 0 returns faster than a mismatch in byte 31. An attacker who can measure response time can forge a valid tag one byte at a time, turning an infeasible 2^256 brute force into a byte-by-byte search.

The asset being protected is the secret authentication tag (mac) baked into the harness. The insecure assumption is that "first mismatch wins" — fine for sorting, fatal for secret comparison.

Your task

Implement ct_digest_eq(a, b, n) so it compares all n bytes of the two digests in constant time: XOR each byte pair, OR the results into an accumulator, and only after scanning every byte decide the result. There must be no early return based on data content — the running time must not depend on where (or whether) the buffers differ. Return 1 if all n bytes are equal, else 0.

Edge cases to handle

• n == 0: nothing to compare, so the digests are equal by definition — return 1.
• A NULL pointer is invalid input and must be rejected (return 0) without dereferencing it — deny by default.
• A difference in the very last byte must still be caught; an early-return loop would already have leaked timing before reaching it.

Example

ct_digest_eq(mac, same, 32)      -> 1   // identical
ct_digest_eq(mac, diff_last, 32) -> 0   // differ in last byte
ct_digest_eq(mac, diff_last, 0)  -> 1   // zero length

Input format

Three arguments: const unsigned char *a and const unsigned char *b, each pointing to at least n bytes of digest data, and size_t n giving the number of bytes to compare.

Output format

Returns int 1 if all n byte pairs are equal, otherwise 0. NULL inputs return 0.

Constraints

C11, no includes needed (the harness provides them). Compare exactly n bytes with no early return that depends on the byte values. Do not use memcmp for the equality decision. Do not dereference a NULL pointer. n can be 0. Bytes are unsigned char (0..255).

Starter code

int ct_digest_eq(const unsigned char *a, const unsigned char *b, size_t n)
{
    /* TODO: compare all n bytes in constant time and return 1 if equal, else 0.
       This insecure stub bails out on the first differing byte (a timing leak)
       and is wrong on top of that. Replace it. */
    (void)a; (void)b; (void)n;
    return -1;
}

Common mistakes

Returning early on the first differing byte (the exact timing leak this exercise removes). Using memcmp, which is itself allowed to short-circuit. Returning memcmp's raw value (nonzero != the required 0/1). Accumulating into a signed or narrow type that can be sign-extended or overflow, or using + instead of | so cancellation hides a difference. Forgetting the NULL check and crashing. Treating n == 0 as an error instead of vacuously-equal.

Edge cases to handle

n == 0 returns 1 (vacuously equal). Difference only in the final byte still returns 0. Difference only in the first byte returns 0. NULL pointer for either argument returns 0 without a dereference. Aliased pointers (a == b) return 1. All-zero buffers compare equal; all-zero vs a single set bit compares unequal. Single-byte compares work in both the equal and unequal directions.

Background lessons

• Hashing: integrity, identification, and its limits