Cryptography Fundamentals Questions

Direct answer

A cryptographic hash function must be preimage resistant (given an output, you cannot find
an input that produces it), second-preimage resistant (given one input, you cannot find a
different input with the same output), and collision resistant (you cannot find any two
distinct inputs that share an output at all). Common algorithms today are SHA-256 and SHA-3;
MD5 and SHA-1 are broken for collision resistance and should not be used where that property
matters.

Structured elaboration

• Preimage resistance: given H(m) = h, it should be computationally infeasible to find
  any m that produces h. This is what makes a hash "one-way."
• Second-preimage resistance: given a specific m1, it should be infeasible to find a
  different m2 with H(m1) = H(m2).
• Collision resistance: it should be infeasible to find any pair m1 != m2 with
  H(m1) = H(m2), without fixing either input in advance. This is the property MD5 and SHA-1
  have both practically broken (real collision attacks have been demonstrated for both).
• Where a hash is the right tool: integrity checks (comparing a downloaded file's hash
  against a published one to detect corruption or tampering), content-addressing (Git commit
  hashes, package registries keying content by its digest so identical content always maps to
  the same address), and as the digest step inside a digital signature: signing algorithms
  sign a fixed-size hash of a message rather than the message itself, since asymmetric
  operations are expensive on large inputs.
• Where it is not the right tool: storing passwords with a bare, unsalted hash. Hash
  functions are deliberately fast, which is exactly wrong for password storage: an attacker
  with a stolen hash dump can try billions of guesses per second on commodity GPUs. Password
  storage needs a slow, memory-hard key derivation function (Argon2id, scrypt, bcrypt), not a
  general-purpose hash used directly.

Worked example

To see why collision resistance is the strongest property, compare a real hash to a toy,
clearly-broken one: H(x) = x mod 97. Take m1 = 5 and m2 = 102. 102 mod 97 = 5, so
H(5) = H(102) = 5: a collision found by inspection, with no search at all. That is exactly
what "not collision resistant" looks like. A real hash like SHA-256 produces a 256-bit output,
so the best known way to find any colliding pair is a generic birthday-bound search of roughly
2^128 attempts (the square root of 2^256 possible outputs), which is computationally out
of reach with current or foreseeable hardware. The mod-97 toy fails instantly because its
output space is only 97 values; a cryptographic hash needs both a large output space and no
structural shortcut into it.

Trade-offs & pitfalls

• Collision resistance and preimage resistance are different properties; a function can lose
  one without immediately losing the other, which is why "MD5 has collisions" does not
  automatically mean "MD5 leaks passwords," but it does mean you should not trust MD5 for
  anything where an attacker choosing two colliding inputs would matter (like forging a signed
  document).
• "Hashing" and "encryption" are often confused: hashing is one-way and not meant to be
  reversed at all, encryption is two-way and meant to be reversed with the right key. A hash
  cannot be "decrypted" back to the original input, by design.

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

Public Key Infrastructure (PKI) is the system of certificates, certificate authorities, and
trust chains that lets a stranger's public key be trusted without meeting them first. A
certificate authority (CA) signs a certificate binding a public key to an identity; anyone who
already trusts that CA can then trust the certificate, and by extension the key inside it.

Structured elaboration

flowchart TD
    Root["Root CA (trust anchor, pre-installed in OS/browser)"]
    Inter["Intermediate CA (signed by Root)"]
    Leaf["Server certificate (signed by Intermediate)"]
    Root -->|signs| Inter
    Inter -->|signs| Leaf
    Leaf -->|presented during TLS handshake| Client["Client validates the whole chain"]

• Certificate: a data structure containing a public key, an identity (like a domain
  name), a validity window, and a signature from whoever issued it.
• Certificate authority (CA): a party trusted to verify identity claims before signing a
  certificate. Trust in a CA is not proven cryptographically from scratch each time, it comes
  from the CA's root certificate being pre-installed as a trust anchor in operating systems
  and browsers.
• Certificate chains: in practice, a root CA rarely signs end-entity (leaf) certificates
  directly; it signs intermediate CAs, which sign the leaf certificates servers actually
  present. Validating a certificate means walking this chain, checking each signature, until
  reaching a root the client already trusts.
• Use in TLS: during the handshake, the server presents its certificate (and usually the
  intermediate chain); the client verifies the signature chain up to a trusted root, checks
  the domain name matches, and checks the validity window, before it will trust the public
  key for the key exchange.

Worked example

A browser connecting to example.com receives a leaf certificate for example.com signed by
"Intermediate CA X," which is itself signed by "Root CA R." The browser already has Root CA
R's certificate baked into its trust store. It verifies Intermediate CA X's signature using
Root CA R's public key, then verifies the leaf certificate's signature using Intermediate CA
X's public key. Only after both signatures check out, the domain name matches, and the
current date falls inside the leaf certificate's validity window does the browser proceed to
trust that public key for the handshake.

Trade-offs & pitfalls

• Certificate expiration: every certificate in the chain has a validity window; if the
  leaf certificate's window ends and it is not renewed, clients will refuse the connection (or
  warn loudly) even though nothing about the underlying keys has actually changed. This is a
  frequent, entirely avoidable cause of production outages, which is why certificate expiry is
  tracked as an operational alert, not just a one-time setup step.
• Self-signed certificates skip the CA entirely (the certificate signs itself), which is fine
  for internal testing but provides no independent identity verification for anyone who
  hasn't been told in advance to trust that specific certificate.

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

Elliptic curve cryptography (ECC) does the same job as RSA, public-key encryption and
signatures, using the algebraic structure of points on an elliptic curve instead of large
integer factorization. It reaches the same security level as RSA with much smaller keys,
because the best known attack against the underlying elliptic-curve discrete-log problem has
no sub-exponential shortcut, unlike RSA's factorization problem.

Structured elaboration

• Key sizes: a 256-bit elliptic-curve key (P-256) provides roughly the same security as a
  3072-bit RSA key; a 384-bit curve (P-384) roughly matches a 7680-bit RSA key. The gap widens
  as the target security level rises.
• Computational cost: ECC signing and key-generation operations are cheap compared to RSA
  at an equivalent security level, since RSA's cost grows faster than ECC's as key size
  increases. RSA public-key verification is actually cheap in absolute terms (a small public
  exponent keeps that operation fast), but RSA's private-key operations and key generation get
  noticeably expensive at 3072+ bits.
• Bandwidth: ECC keys and signatures are dramatically smaller, a P-256 ECDSA signature is
  roughly 64 bytes versus roughly 256 to 384 bytes for an RSA-2048/3072 signature. This matters
  directly for TLS handshake size, mobile bandwidth, and embedded/IoT devices with tight memory
  budgets.
• Use cases: ECDSA for digital signatures, ECDH (and its ephemeral form, ECDHE) for key
  exchange, both filling the same roles RSA and classic Diffie-Hellman fill, just cheaper.
• Named curves: P-256 (also called secp256r1, a NIST-standardized curve) is the most
  widely deployed; Curve25519 (used for X25519 key exchange) and Ed25519 (its signature
  counterpart) are increasingly preferred, in part because their parameters were generated
  through a fully documented, deterministic process, addressing concerns some practitioners
  raised about the opacity of how certain NIST curve constants were originally chosen.

Worked example

A mobile app performs 1,000,000 TLS handshakes a day against its API. Each handshake carries
one server certificate signature. An RSA-3072 signature runs roughly 384 bytes; a P-256 ECDSA
signature runs roughly 64 bytes, a saving of 320 bytes per handshake. Across a day:
1,000,000 x 320 bytes = 320,000,000 bytes, that is, about 320 MB of signature bytes saved
daily just from the certificate switch, before counting any of the other handshake fields ECC
also shrinks. For a bandwidth-constrained mobile client population, that is a real, measurable
reason to prefer ECDSA over RSA beyond the abstract "smaller keys" framing.

Trade-offs & pitfalls

• ECC implementations are more delicate than RSA's: incorrect point validation, timing
  side-channels during scalar multiplication, and "invalid curve" attacks are all
  ECC-specific implementation pitfalls that a naive from-scratch implementation is likely to
  get wrong. "Don't roll your own crypto" applies even more strongly to ECC than to RSA.
• Choice of curve matters beyond raw key size: Curve25519/Ed25519 are designed to make
  several classes of implementation mistakes (like weak point validation) structurally harder
  to make than the older NIST curves do.