Cryptography Fundamentals Questions

Direct answer

Salting adds a random, unique-per-user value to a password before hashing so that identical
passwords never produce identical stored hashes; key stretching deliberately makes each
hashing attempt slow (or memory-hungry) so an attacker who steals the hash dump still has to
pay a real per-guess cost. Together they turn "crack the whole database at once with a
precomputed table" into "crack each password individually, slowly."

Structured elaboration

• Generating and storing salts: generate a fresh, random salt (commonly 16 bytes) from a
  CSPRNG per user, and store it alongside the hash. The salt is not secret, it can sit in
  plaintext in the same database row; its job is uniqueness, not confidentiality.
• Why unique salts defeat precomputation: a rainbow table (a precomputed map from common
  passwords to their hashes) is only useful because it lets an attacker look up a hash instead
  of computing one. A unique salt per user means the same password produces a different hash
  for every user, so an attacker would need a separate precomputed table per salt value, which
  is infeasible at any real user-base size.
• How key stretching increases attacker work: an iterated hash (many rounds of a hash
  function) or a memory-hard function (Argon2id, scrypt) makes each individual guess
  expensive in CPU time, memory, or both. This does not slow down a legitimate login (one
  verification per attempt is cheap in absolute terms) but multiplies the cost of trying
  billions of candidate passwords offline by the same factor.

Worked example

Suppose 5,000 users in a leaked database chose the password "password123". With a plain,
unsalted hash, all 5,000 rows show the identical hash value, so cracking it once (via a
rainbow table lookup or a single guess) reveals all 5,000 accounts simultaneously. With unique
per-user salts, those same 5,000 users produce 5,000 different hash values, and an attacker
must run the guess-and-check process separately against each one; a rainbow table built for
the unsalted case is useless here since it was never built for any of these specific salts.

Trade-offs & pitfalls (remaining risks needing additional controls)

• Salting and stretching only make offline cracking (against a stolen hash) expensive; they
  do nothing against online guessing at the login endpoint, which still needs rate limiting
  and account lockout/backoff.
• A short or common password remains crackable even when properly salted and stretched,
  because the search space itself is small; this is why NIST SP 800-63B and similar guidance
  push for password length and breach-list checking rather than relying on hashing alone.
• Choosing stretching parameters too low (to save server CPU) narrows the gap between "safe"
  and "fast enough to crack anyway"; parameters need periodic revisiting as hardware gets
  cheaper.

Direct answer

A padding oracle attack against Cipher Block Chaining (CBC) mode lets an attacker decrypt
ciphertext without ever learning the key, by abusing a server that reveals, one bit of
information at a time, whether decrypted padding was valid. The fix is to stop that leak entirely:
authenticate the ciphertext before you ever act on decrypted padding, ideally by switching to
authenticated encryption so the question "was the padding valid" never becomes observable.

Structured elaboration

CBC decrypts block $i$ as:

so every byte of plaintext depends on both the ciphertext block and the previous ciphertext
block, byte for byte. If an attacker can flip bits in $C_{i-1}$ and ask an oracle "did this decrypt
to validly-padded plaintext (PKCS#7: the last byte states how many padding bytes there are, and
they must all equal that value)", the oracle's yes/no answer reveals one byte of the intermediate
decryption value $D_k(C_i)$ at a time, working backward from the last byte of the block. Once the
attacker has that intermediate value, XOR-ing it with the real previous ciphertext byte recovers
the real plaintext byte, no key required.

Worked example

Say the attacker wants byte 15 (the last byte) of a block. Let $I = D_k(C_i)[15]$ be the true
intermediate value (unknown to the attacker) and $c = C_{i-1}[15] = 0x3C$ be the real ciphertext
byte actually on the wire. The real plaintext byte is $p = I \oplus c$.

1. The attacker tries every candidate byte $c' \in [0, 255]$ in place of $c$ and resubmits the
   ciphertext, watching for the server's padding-valid response.
2. Padding is valid for the last byte exactly when $I \oplus c' = 0x01$ (a single valid padding
   byte). Suppose that happens at $c' = 0x58$.
3. The attacker now knows $I = c' \oplus 0x01 = 0x58 \oplus 0x01 = 0x59$.
4. Recover the real byte: $p = I \oplus c = 0x59 \oplus 0x3C = 0x65$, which is the ASCII letter
   e.

Running that exact arithmetic (verified, not asserted) reproduces it: with $I = 0x59$ fixed as
ground truth, the search over $c'$ finds the valid byte at $0x58$, and $0x59 \oplus 0x3C$ does
equal $0x65$. Repeating this per byte, and then per block, decrypts the whole message. In the
worst case this costs up to 256 oracle queries per byte and up to $256 \times 16 = 4096$ queries
per 16-byte block, no cryptanalysis of the cipher itself needed, only a working oracle.

Trade-offs & pitfalls

• Use authenticated encryption with associated data (AEAD), such as AES in Galois/Counter Mode
  (AES-GCM) or ChaCha20-Poly1305, which authenticates the ciphertext as one atomic operation and
  never exposes a separate "was the padding valid" signal.
• If you are stuck with CBC, verify a Message Authentication Code (MAC) computed over the
  ciphertext (encrypt-then-MAC) before attempting to unpad, and reject on MAC failure with one
  uniform, generic error, before any padding logic runs at all.
• Never let padding errors, MAC errors, and format errors produce distinguishable responses,
  status codes, or timings. Rate-limit and log repeated malformed-ciphertext submissions, since a
  real attack needs thousands of requests per byte.
• Common wrong turn: fixing only the error message while leaving a timing difference between
  "padding check failed fast" and "padding check passed, MAC check failed later". Timing is itself
  an oracle.

Direct answer

The Elliptic Curve Digital Signature Algorithm (ECDSA) signs a message by picking a random
per-signature value, turning it into a curve point, and combining that with the message hash and
the private key to produce a pair of numbers, $(r, s)$. Those signatures can be malleable, meaning
a different valid signature can be produced for the same message without the private key,
because for every valid $(r, s)$ the pair $(r, n - s)$, where $n$ is the curve's group order, is
also valid. Distributed systems must enforce a canonical form on ingestion or that second, forged
signature can be mistaken for a distinct, unrelated event.

Structured elaboration

• How it works, at a high level. Hash the message, generate a fresh random nonce $k$, compute
  the curve point $k \cdot G$ and take its x-coordinate mod the group order $n$ as $r$, then
  compute:

where $d$ is the private key. Verification recomputes a point from $(r, s, H(m), \text{public key})$ and checks that its x-coordinate matches $r$.

• Why malleability exists. The verification equation is symmetric under negating $s$: both $s$
  and $n - s$ satisfy it for the same $(r, H(m), \text{public key})$. Different byte encodings
  (raw $r \| s$ versus Distinguished Encoding Rules, DER) add a second, unrelated source of
  malleability, since a non-canonical Abstract Syntax Notation One (ASN.1) encoding can represent
  the identical logical signature as more than one byte string.
• Real-world impact. This is not theoretical: Bitcoin's original protocol computed a
  transaction's identifier from its raw serialized bytes, signature included, so anyone could flip
  $s \to n - s$ on an unconfirmed transaction and change its identifier without invalidating it,
  a bug generally referred to as transaction malleability, later addressed by enforcing low-$s$
  signatures and, more completely, by Segregated Witness.

Worked example

This is directly demonstrable, not just asserted, by generating a real key pair, signing once, and
checking that both the original and the flipped signature verify:

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature, encode_dss_signature
from cryptography.hazmat.primitives import hashes
from cryptography.exceptions import InvalidSignature

private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551  # NIST P-256 group order

message = b"transfer 100 units to account 42"
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))
r, s = decode_dss_signature(signature)

s_flipped = (n - s) % n
flipped_signature = encode_dss_signature(r, s_flipped)

def verifies(sig):
    try:
        public_key.verify(sig, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

print("original signature verifies:      ", verifies(signature))
print("(r, n - s) signature also verifies:", verifies(flipped_signature))
print("exactly one of {s, n-s} is low-S (<= n/2):", (s <= n // 2) != (s_flipped <= n // 2))

original signature verifies:       True
(r, n - s) signature also verifies: True
exactly one of {s, n-s} is low-S (<= n/2): True

That third line is the useful, always-true invariant across runs (the nonce is random, so which of
the two happens to be "original" varies, but exactly one member of every $\{s, n-s\}$ pair is
always $\le n/2$), and it is exactly what the low-S rule below relies on.

Trade-offs & pitfalls

• Enforce canonical form on ingestion. Require strict DER parsing (reject non-minimal
  encodings), and enforce the low-S rule, only accept signatures where $s \le n/2$, canonicalizing
  or rejecting the high-S alternative. Reject $r = 0$ or $s = 0$ outright.
• Verify the public key, not just the signature. Confirm the public key actually lies on the
  curve and is not the point at infinity before using it, and prefer deterministic nonce generation
  (RFC 6979) over a naive random nonce, since a reused or biased nonce leaks the private key
  entirely, a different and more severe failure than signature malleability.
• Storage and audit. Store signatures immutably alongside signer key identifier, algorithm,
  timestamp, and canonicalization status, so a non-canonical or unexpected encoding is itself a
  signal worth alerting on, not just silently rejecting.
• Common wrong turn: deriving an event's identity or deduplication key from the raw signature
  bytes instead of from the signed message content; that is precisely the design flaw malleability
  exploits.

Direct answer

Use a MAC (like HMAC or CMAC) when both sides already share a secret key and you only need to
prove the message wasn't tampered with between two mutually-trusting parties. Use a digital
signature when you need non-repudiation, proof that a specific party and no one else produced
it, or when many independent parties need to verify without ever holding a shared secret.

Structured elaboration

• Non-repudiation: a MAC is computed with a shared key, so either party who holds that
  key could have produced it; the receiver themselves is technically capable of forging a
  valid MAC, which means a MAC can never prove who specifically created a message, even to
  itself. A digital signature is produced with a private key only the signer holds; anyone
  with the public key can verify it came from that specific private key, giving genuine
  non-repudiation, the signer cannot credibly deny having signed it.
• Key management: a MAC needs the same secret key securely distributed to every party who
  must verify, which does not scale well once there are many independent verifiers. A
  signature scheme needs one private key held by the signer and an openly distributable public
  key; any number of parties can verify without any of them holding a secret at all, which is
  why signatures fit enterprise settings with many downstream consumers (software distribution,
  document signing across organizations, certificate chains).
• Performance: HMAC (built from a hash function) and CMAC (built from a block cipher) are
  both fast, symmetric-key operations. Signing with RSA or ECDSA costs more than computing a
  MAC (it involves genuine asymmetric-key math), though ECDSA signing is considerably cheaper
  than RSA signing at an equivalent security level; verification is typically the cheaper
  half of a signature scheme.

Worked example

Two microservices inside the same trust boundary, sharing a secret deployed via the same
secrets manager, want to confirm requests between them are unmodified: HMAC is the right
choice, since both sides already trust each other and share the key, and no outside party
ever needs to verify these requests. A software vendor shipping an update that thousands of
independent customer machines must verify came from that vendor, and no one else, needs a
digital signature: there is no shared secret between the vendor and every customer, and only
the vendor's private key should be able to produce a valid signature.

Trade-offs & pitfalls

• Using a MAC where verification needs to happen outside the trusted pair (say, a
  third-party auditor) quietly breaks the "who could have produced this" guarantee that the
  scenario actually needed.
• Using a signature purely for internal service-to-service integrity checks works but pays an
  unnecessary performance and key-management cost when a shared-key MAC would have been
  sufficient.

Direct answer

PKCS#7 padding (defined in RFC 2315, and reused unchanged in modern standards for block ciphers)
fills the last block of a message so its length becomes a multiple of the cipher's block size: the
value of every padding byte equals the count of padding bytes added, from 1 up to the block
size. Unpadding must check that consistently and reject anything else, but it must do that check
without leaking, through timing, which specific byte was wrong, since that leak is exactly what a
padding oracle attack exploits.

Structured elaboration

• Approach. pad computes how many bytes are missing to reach a multiple of block_size
  (always between 1 and block_size, even when the input is already a multiple, since padding
  must always be present so unpad can find it) and appends that many bytes, each holding that
  count as its value.
• Approach. unpad first checks the length is a nonzero multiple of block_size, reads the
  last byte as the claimed padding count, and rejects it outright if it is 0 or bigger than
  block_size. Only then does it verify every one of the claimed padding bytes actually holds
  that value.
• Avoiding a padding oracle. The verification loop below never returns as soon as it finds a
  mismatch; it OR's every byte's difference into an accumulator and checks it once at the end, so
  the number of comparisons performed does not depend on where the first bad byte was. That
  alone does not make the surrounding system safe: the real defense is to authenticate the
  ciphertext (via an AEAD cipher, authenticated encryption with associated data, or a Message
  Authentication Code, MAC, such as HMAC, computed over the ciphertext) before this function
  is ever called during decryption, so a tampered ciphertext is rejected before its padding is
  inspected at all.

Worked example

class PaddingError(ValueError):
    pass

def pad(data: bytes, block_size: int) -> bytes:
    if not (1 <= block_size <= 255):
        raise ValueError("block_size must be between 1 and 255")
    pad_len = block_size - (len(data) % block_size)
    return data + bytes([pad_len]) * pad_len

def unpad(data: bytes, block_size: int) -> bytes:
    if not data or len(data) % block_size != 0:
        raise PaddingError("invalid padding length")
    pad_len = data[-1]
    if pad_len < 1 or pad_len > block_size:
        raise PaddingError("invalid padding value")
    # Constant-time check: touch every candidate padding byte instead of
    # returning on the first mismatch, so timing does not reveal *which*
    # byte was wrong.
    diff = 0
    for b in data[-pad_len:]:
        diff |= b ^ pad_len
    if diff != 0:
        raise PaddingError("invalid padding bytes")
    return data[:-pad_len]

block_size = 16
msg = b"attack at dawn!!"  # 16 bytes, exactly one block

padded_short = pad(b"hi", block_size)
padded_exact = pad(msg, block_size)

print("pad(b'hi', 16)         =", padded_short, "len:", len(padded_short))
print("pad(16-byte msg, 16)   =", padded_exact, "len:", len(padded_exact))
print("unpad round-trips 'hi'  :", unpad(padded_short, block_size) == b"hi")
print("unpad round-trips full  :", unpad(padded_exact, block_size) == msg)

tampered = bytearray(padded_short)
tampered[-1] ^= 0xFF
try:
    unpad(bytes(tampered), block_size)
    print("tampered padding accepted (BUG)")
except PaddingError as e:
    print("tampered padding rejected:", e)

Output (deterministic, this exact run reproduces it):

pad(b'hi', 16)         = b'hi\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e' len: 16
pad(16-byte msg, 16)   = b'attack at dawn!!\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10' len: 32
unpad round-trips 'hi'  : True
unpad round-trips full  : True
tampered padding rejected: invalid padding value

Trade-offs & pitfalls

• Complexity: both functions are O(n) in the input length; the constant-time scan adds no
  asymptotic cost since it is bounded by block_size (at most 255 byte comparisons).
• Edge cases: an already-block-aligned input still gets a full extra block of padding (a common
  point of confusion, PKCS#7 never leaves zero padding bytes); an empty ciphertext; a pad_len of
  0 or greater than block_size, both invalid and must be rejected before the byte-by-byte check
  runs; a ciphertext whose length is not a multiple of block_size at all, which is a format error
  distinct from a padding error but should still surface a single generic exception.
• A constant-time comparison inside unpad reduces one class of timing leak, but if this function
  is called on attacker-controlled ciphertext before a MAC or AEAD tag has been checked, the
  system is still exploitable: the attacker does not need a timing side-channel if the application
  simply returns a different HTTP status or error string for "bad padding" versus "bad MAC".
  Encrypt-then-MAC (or AEAD outright) removes the padding oracle at the protocol level; this
  function alone only removes it at the instruction level.