Cryptographic Algorithm Implementation Questions

Skills and knowledge for correctly implementing cryptographic algorithms and primitives in code. Candidates should be able to translate algorithm specifications and mathematical definitions into correct implementations, handling binary data layouts, bit operations such as shifts and exclusive or, and large integer arithmetic required for modular operations. Expect to implement core operations and components including Advanced Encryption Standard encryption rounds, Rivest Shamir Adleman modular exponentiation, Secure Hash Algorithm 256 message scheduling, substitution boxes in block ciphers, mixing functions, substitution and permutation operations, and simplified cipher operations for demonstration. Understand appropriate data structure choices and their performance and security implications, including constant time considerations, endianness, padding rules, and proper randomness. Implement and verify against official test vectors and build verification procedures and test harnesses. Emphasize correctness and clear explanation over premature optimization and recognize when to prefer well vetted cryptographic libraries to custom implementations.

HardSystem Design

81 practiced

Design a C library API for symmetric encryption primitives that reduces developer misuse. Define function prototypes for one-shot and streaming use, error handling conventions, an opaque key type with lifecycle functions (allocate/zero/free), and how to advertise constant-time guarantees. Provide an example usage for AES-GCM and HKDF and explain how you would document and test the API.

Sample Answer

**Design goals**- Secure-by-default, minimal footguns, clear lifecycle, constant-time where promised, explicit error model.

**API prototypes (core)**

// Opaque key type
typedef struct sym_key sym_key_t;

// Errors
typedef enum { SE_OK=0, SE_ERR_INVALID, SE_ERR_LEN, SE_ERR_AUTH, SE_ERR_ALLOC, SE_ERR_STATE } se_error_t;

// Key lifecycle
se_error_t sym_key_alloc(sym_key_t **k, size_t bits);   // zeros on alloc
se_error_t sym_key_import(sym_key_t *k, const void *raw, size_t len); // copies
se_error_t sym_key_generate(sym_key_t *k); 
void        sym_key_zero_free(sym_key_t *k);

// One-shot AEAD
se_error_t aead_encrypt_one_shot(const sym_key_t *k,
                                 const uint8_t *nonce, size_t nlen,
                                 const uint8_t *aad, size_t aad_len,
                                 const uint8_t *pt, size_t pt_len,
                                 uint8_t *ct, size_t *ct_len); // ct includes tag

se_error_t aead_decrypt_one_shot(const sym_key_t *k,
                                 const uint8_t *nonce, size_t nlen,
                                 const uint8_t *aad, size_t aad_len,
                                 const uint8_t *ct, size_t ct_len,
                                 uint8_t *pt, size_t *pt_len);

**Streaming API**

typedef struct aead_stream aead_stream_t;
se_error_t aead_stream_init(aead_stream_t **s, const sym_key_t *k, const uint8_t *nonce, size_t nlen);
se_error_t aead_stream_aad(aead_stream_t *s, const void *aad, size_t len);
se_error_t aead_stream_update(aead_stream_t *s, const void *in, size_t in_len, void *out, size_t *out_len);
se_error_t aead_stream_finish(aead_stream_t *s, void *tag, size_t *tag_len);
void        aead_stream_free(aead_stream_t *s);

**Constant-time guarantees**- Export function: const char *se_runtime_properties(void);- Document which primitives are constant-time (e.g., HMAC/HKDF internals constant-time for secret ops; AES-GCM uses AES-NI when available — data-dependent branches avoided in crypto paths). Provide build-time macro SE_ASSUME_CT to assert CT.

**Examples**- AES-GCM one-shot: allocate sym_key, import raw 256-bit key, call aead_encrypt_one_shot with 12-byte nonce, check SE_OK, then zero_free key.- HKDF: provide hkdf_extract / hkdf_expand APIs that accept sym_key_t or raw salt/prk buffers; operations do not expose intermediate secrets and zero-buffer outputs on error.

**Error handling convention**- Return se_error_t; outputs via out-params only when SE_OK. Functions validate lengths and nonce sizes and fail fast.

**Documentation & testing**- Docs: per-function guarantees (memory, thread-safety, CT), required nonce lengths, max message sizes, recommended usage patterns and misuse examples.- Tests: unit tests for edge cases, FIPS test vectors, property tests (nonce reuse detection helpers), fault-injection, valgrind/ASAN checks, constant-time regression tests (frequency/statistical timing, ct-verifier), fuzzing for streaming and boundary conditions, and API misuse tests (double-free, use-after-free).

MediumTechnical

79 practiced

Implement HMAC-SHA256 in Python assuming a provided sha256(data: bytes) -> bytes function. Implement hmac_sha256(key: bytes, message: bytes) -> bytes using the 64-byte block size. Handle keys longer than the block and keys shorter than the block according to the HMAC spec and explain why HMAC resists length-extension attacks.

Sample Answer

**Approach**- Follow RFC 2104/HMAC spec with SHA-256 and 64-byte block size.- If key length > 64, replace key with sha256(key). If < 64, pad with zero bytes to 64.- Compute inner = sha256((key ^ 0x36) || message), outer = sha256((key ^ 0x5c) || inner).

python

def hmac_sha256(key: bytes, message: bytes) -> bytes:
    BLOCK_SIZE = 64  # bytes for SHA-256

    # Step 1: normalize key
    if len(key) > BLOCK_SIZE:
        key = sha256(key)               # reduce long keys
    if len(key) < BLOCK_SIZE:
        key = key + b'\x00' * (BLOCK_SIZE - len(key))  # pad short keys

    # Step 2: create inner and outer padded keys
    ipad = bytes((b ^ 0x36) for b in key)
    opad = bytes((b ^ 0x5c) for b in key)

    # Step 3: compute HMAC
    inner_hash = sha256(ipad + message)
    return sha256(opad + inner_hash)

Explanation and reasoning- Hashing long keys ensures a fixed-length secret; padding enforces block-aligned input for the XOR pads.- The double-hash structure (inner then outer) prevents length-extension attacks: length-extension allows forging H(message || suffix) when attacker knows H and message length for Merkle–Damgård hashes. HMAC prevents that because the attacker does not know the secret-derived ipad value and the outer hash inputs are opad || inner_hash (fixed-length hash output), so they cannot produce a valid outer hash for an extended message without the key.

Complexity and edge cases- Time: O(|key| + |message|) dominated by two SHA-256 calls over those inputs.- Edge cases handled: empty key, empty message, key exactly block size, key longer than block reduced by sha256.

EasyTechnical

78 practiced

Implement the AES AddRoundKey operation: a C function that XORs a 16-byte state with a 16-byte round key in-place. Show at least two implementation variants (byte-wise and word-wise using 64-bit XORs) and discuss alignment and SIMD/AES-NI optimizations you might apply for production code.

Sample Answer

**Brief approach**Implement AddRoundKey by XORing each byte of a 16-byte AES state with corresponding byte of a 16-byte round key. Provide a simple byte-wise loop and a faster 64-bit word-wise XOR. Discuss alignment, endianness, and further SIMD/AES-NI optimizations.

**Byte-wise implementation**

#include <stdint.h>
void add_round_key_bytes(uint8_t state[16], const uint8_t rk[16]) {
    for (int i = 0; i < 16; ++i) {
        state[i] ^= rk[i];
    }
}

**Word-wise (64-bit) implementation**

#include <stdint.h>
#include <string.h> // for memcpy if unaligned

void add_round_key_u64(uint8_t state[16], const uint8_t rk[16]) {
    // Use 64-bit XORs; handle possible unaligned pointers portably via memcpy
    uint64_t s0, s1, k0, k1;
    memcpy(&s0, state + 0, 8);
    memcpy(&s1, state + 8, 8);
    memcpy(&k0, rk + 0, 8);
    memcpy(&k1, rk + 8, 8);
    s0 ^= k0;
    s1 ^= k1;
    memcpy(state + 0, &s0, 8);
    memcpy(state + 8, &s1, 8);
}

**Alignment & endianness**- Using memcpy avoids undefined behavior for unaligned access and preserves portability.- XOR is bytewise-equivalent regardless of endianness when using memcpy into integer words; do not reinterpret_cast pointers on platforms where alignment matters.- If you rely on direct uint64_t pointer dereference for performance, ensure state and rk are 8-byte aligned (posix_memalign, aligned_alloc) and document ABI.

**SIMD / AES-NI optimizations**- For high throughput use: - AES-NI: use AESKEYGENASSIST and AESENC instructions for rounds; AddRoundKey becomes a single pxor on XMM/YMM/ZMM registers. - SSE2/AVX2: load 128-bit state and key into __m128i and use _mm_xor_si128. Example: _mm_storeu_si128(state, _mm_xor_si128(_mm_loadu_si128(state), _mm_loadu_si128(rk))).- Consider branchless, constant-time code and ensure sensitive data cleansing and no compiler reordering.

**Complexity**- Time: O(1) (fixed 16 bytes). Space: O(1) in-place.

MediumTechnical

76 practiced

Implement modular exponentiation pow_mod(base, exponent, modulus) in Python without using the built-in pow(base, exponent, modulus). Use the binary (square-and-multiply) method, ensure you reduce intermediate values to control growth, and discuss complexity and when you would prefer Montgomery or other accelerated multiplication schemes.

Sample Answer

**Approach (brief)** Use binary square-and-multiply: scan exponent bits L->R (or R->L) squaring current result and multiplying when bit=1. Reduce after each multiply/square to keep intermediates small. This is standard for RSA-sized bigints.

**Code (Python)**

python

def pow_mod(base: int, exponent: int, modulus: int) -> int:
    """Compute base^exponent % modulus using square-and-multiply."""
    if modulus == 1:
        return 0
    base %= modulus
    result = 1
    e = exponent
    while e > 0:
        if e & 1:
            result = (result * base) % modulus  # reduce immediately
        base = (base * base) % modulus          # reduce after squaring
        e >>= 1
    return result

**Key points / reasoning**- Reducing after every multiplication or square bounds size to < modulus^2 then modulo brings back to < modulus, preventing growth.- Use bit operations for speed; loop runs O(log exponent) multiplications.

**Complexity**- Time: O(k) modular multiplications where k = number of bits in exponent = O(log exponent). Each multiplication for n-bit numbers is M(n) cost (schoolbook M(n)=O(n^2), FFT-based faster).- Space: O(1) extra.

**When to use Montgomery or accelerated multiplication**- For large moduli (RSA 2048+), many modular multiplications—Montgomery reduces cost by replacing divisions with shifts and additions and enabling windowing/binary exponentiation with faster modular reductions.- Use Montgomery when modulus is odd and you precompute R and R^-1; combine with sliding-window exponentiation and fast big-int mul (Karatsuba/Toom- Cook/FFT) for best throughput.- For single small exponentiations, plain square-and-multiply is fine; for repeated ops (TLS handshakes, crypto libraries), use Montgomery or specialized assembly-optimized routines.

EasyTechnical

123 practiced

Implement a constant-time function in C that compares two byte arrays of equal length and returns 1 if they are equal and 0 otherwise. Provide the function signature, a complete implementation that avoids secret-dependent branches and early returns, and a short explanation of why your implementation is constant-time. Describe how you would test this implementation for timing leakage and what pitfalls compilers might introduce.

Sample Answer

**Function signature and implementation**

#include <stddef.h>
#include <stdint.h>

/* Returns 1 if a and b are equal (len bytes), 0 otherwise.
   Constant-time: no secret-dependent branches or early returns. */
int ct_compare(const void *a, const void *b, size_t len) {
    const unsigned char *x = (const unsigned char *)a;
    const unsigned char *y = (const unsigned char *)b;
    unsigned int diff = 0;
    size_t i;

    for (i = 0; i < len; i++) {
        /* XOR each byte and OR into accumulator */
        diff |= (unsigned int)(x[i] ^ y[i]);
    }

    /* diff == 0 -> equal. Map to 1/0 without branching. */
    return (int)((diff | -diff) >> (sizeof(diff)*8 - 1)) ^ 1;
}

Explanation why this is constant-time- The loop iterates exactly len times, performs identical memory loads and bitwise ops for every index, and has no secret-dependent branches or early returns.- The final reduction maps zero/non-zero to 1/0 using bitwise arithmetic instead of branching, avoiding data-dependent control flow.

Testing for timing leakage- Microbenchmark: run many (millions) comparisons with fixed public inputs and with secret-dependent differences at varying positions; record per-call latencies and compare distributions statistically (t-test, KS test).- Control environment: pin to a CPU core, disable turbo/C-state scaling, disable other background tasks, use high-resolution timers (rdtsc with serialization).- Use side-channel tools: perf, Cachegrind, or hardware performance counters to detect differing instruction/memory patterns.- Test with different alignments, lengths, and values to ensure no position-dependent timing.

Compiler pitfalls and mitigations- Compiler optimizations may vectorize, reorder, or introduce conditional moves/early-outs. They might transform code into calls to memcmp or eliminate work if it thinks inputs are unused.- Mitigations: mark pointers as volatile if necessary, or use portable compiler barriers / inline assembly to prevent undesired transformations. Prefer reviewing generated asm (objdump/clang -S) and test compiled binaries for timing. Use well-reviewed constant-time primitives from cryptographic libraries when available.

Unlock Full Question Bank

Get access to hundreds of Cryptographic Algorithm Implementation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.