Asymmetric Cryptography and Key Exchange Questions

Overview / thesis
Certificate Transparency (CT) is a practical cryptographic accountability layer that deters CA misissuance by forcing public, append-only logging of TLS certificates. It does not prevent misissuance but makes it detectable, enabling remediation.

Merkle tree inclusion proofs & SCTs

• Logs maintain an append-only Merkle tree over entries (certificates). Servers present a Signed Certificate Timestamp (SCT): a log’s signature promising to include the cert within a Maximum Merge Delay (MMD).
• Inclusion proof: a compact set of sibling hashes proving the leaf’s path to the published Merkle root (STH). Verifier checks:

leaf_hash = H(leaf)
root = combine_hashes_along_path(leaf_hash, siblings)
root == STH.merkle_root

Intuition: collision-resistant hash binds leaf to root; signed STH binds root to log state.

Log equivocation threat

• A malicious or compromised log can present different STHs to different clients (equivocation), hiding misissued certs from some observers. Equivocation breaks global auditability.

Monitors and auditors responsibilities

• Monitors: continuously fetch new certificates and STHs, check for unwanted names, and alert domain owners; act as large-scale detectors.
• Auditors: verify inclusion proofs against published STHs and check log append-only consistency proofs. Auditors detect equivocation by comparing logs’ STHs over time and cross-checking with gossip/peers.

Browser integration

• Browsers require either an SCT presented by the server (embedded/OCSP/tls extension) or expect certs to appear in CT logs; some enforce CT for EV/Chrome policies. Browsers perform lightweight auditing/inclusion checks and rely on third-party monitors.

Limitations and attacks against CT operators

• Log compromise/equivocation, operator censorship (refuse or delay entries), targeted withholding, or collusion with malicious CAs.
• Sybil/gossip resistance: without robust cross-client gossip or transparency of STH distribution, equivocation can persist.
• Privacy leakage: logging full precerts can expose domain patterns.
• Operational attacks: DDoS, private-key theft enabling forged SCTs or fake STHs.

Conclusion / cryptographer’s view
CT is strong for detection when combined with diverse, well-audited logs, cross-logging, gossip, and independent monitors. Cryptographic primitives are sound, but system security depends on policy, distribution of trust, and anti-equivocation infrastructure.

Approach overview
Describe chain building as a constrained graph search: certificates are nodes, "issued-by" links are directed edges. Goal: find a path from end-entity to any trusted anchor that satisfies constraints (signatures, validity periods, name constraints, policies). Use backtracking DFS/BFS with pruning, cycle detection, and chain scoring to prioritize.

Algorithm (high level)

• Build index: map SubjectName/SubjectKeyIdentifier -> certs; map AuthorityKeyIdentifier/IssuerName -> certs that can issue.
• Start from EE cert; perform a depth-limited search for candidate issuers until a trust anchor is reached.

function build_paths(ee):
  stack = [(ee, [], initial_state)]
  results = []
  while stack not empty:
    (current, path, state) = pop(stack)
    if current in path: continue   # cycle avoidance
    new_path = path + [current]
    update_state(state, current)  # policies, name-constraints, validity
    if violates(state): continue
    if is_trust_anchor(current): results.append(new_path); continue
    for issuer in find_issuers(current):
      if signature_valid(issuer, current) and time_ok(issuer):
        push(stack, (issuer, new_path, copy(state)))
  return prioritize(results)

Cycle detection

• Track visited certificates in current path (O(1) check via set). Also enforce maximum path length (e.g., 10).

Pruning and validation during search

• Validate each signature and certificate validity period before extending.
• Apply name constraints incrementally: maintain permitted/excluded subtrees state; reject if current cert narrows permitted set to empty or violates excluded set.
• Apply certificate policies: maintain acceptable policy set per RFC 5280 policy processing — intersect policy OIDs; support policy mappings and anyPolicy; mark path invalid if final policy set doesn’t include required policy unless explicit policy mapping allows it.

Prioritization

• Score chains by:
  • Shorter length (fewer intermediates)
  • Stronger crypto (sig alg strength, key size)
  • Matching EKUs/policies and name constraints (higher score)
  • Anchor trust level (local anchor > less-trusted)
• Return highest-scoring valid path(s).

Trade-offs & notes

• BFS finds shortest path but DFS with heuristics may find cryptographically better chains sooner.
• Cache signature/verifier results for performance.
• Follow RFC 5280 rules exactly for policy processing and name-constraints; treat cross-signatures as multiple issuance edges (same subject with different issuers).

Approach / summary

ECDH replaces the modular-exponentiation group of classic (finite-field) DH with scalar multiplication on an elliptic-curve group. That change drives differences in operations, key size, and per‑bit security.

Operations

• DH (finite field): single-party operation is modular exponentiation g^x mod p (cost: modular multiplications and modular reductions; complexity dominated by repeated squaring/multiplication).
• ECDH: scalar multiplication k·P on curve (cost: point additions and point doublings; uses field arithmetic — multiplications, squarings, inversions — but far fewer group operations for equivalent security).

Key size & security per bit

• Security per bit: ECC offers much higher security per bit. Rough mapping: 2048-bit DH ≈ 112 bits security, while a 256-bit elliptic curve (e.g., secp256r1/Curve25519) ≈ 128 bits security.
• Result: ECDH keys are an order of magnitude smaller (128–521 bit curves vs 1024–15360 bit DH) for comparable security.

Why ECDH for constrained devices

• Smaller keys → less storage, bandwidth, and certificate size.
• Scalar mult on properly chosen curves is faster and uses less memory/CPU than equivalent-strength modular exponentiation.
• Lower power consumption and shorter latency for key agreement.

Curve properties that influence performance

• Field type: prime fields GF(p) (e.g., P-256, Curve25519) vs binary fields GF(2^m). Prime fields are usually faster and easier to implement constant‑time on CPUs; binary fields can be efficient in hardware but are less common.
• Curve form: Montgomery or Edwards forms (Curve25519, Ed25519) allow faster, simpler, and more constant‑time ladder-based scalar multiply than short Weierstrass.
• Coordinate representation: affine needs inversions (costly); projective/Jacobian avoid inversions at expense of more multiplications — typically faster overall. Montgomery ladder uses x‑only arithmetic and is side‑channel resistant.
• Optimizations: windowed methods, precomputation, and endomorphisms (GLV) can speed scalar mult but add implementation complexity and potential side‑channel vectors.

Trade-offs / security notes

• ECC relies on ECDLP assumptions; avoid curves with known weaknesses (anomalous, small cofactor, special structure). Prefer standardized, well-studied curves (Curve25519, P-256 with caution on implementation).
• Implement constant‑time arithmetic and validate points to prevent invalid‑curve and side‑channel attacks.

This explanation shows why ECDH is preferred on constrained devices and which curve choices most affect performance and safety.

Definition (brief)

Key confirmation is a protocol property by which one or both parties obtain cryptographic assurance that the other party actually possesses the established session key K. It complements key agreement (which establishes K) by proving possession and binding K to the intended peer and session.

Two mechanisms for mutual key confirmation

1. MAC over the transcript using the derived key

• Each party computes MAC_K( transcript || role_id ) and sends it to the other.
• Verification ensures the sender knows K and that the transcript (nonces, pubkeys) is bound to the MAC.
• Example: Alice computes T_A = MAC_K("Alice" || session_transcript) and Bob verifies.

2. Explicit signature over key material

• Each party signs a message that includes the session key material or a key-derivation output: SIG_skA( "confirm" || K || transcript ).
• Signatures provide non-repudiation and tie long-term identity to the specific key.

How confirmation prevents active and reflection attacks

• Active MitM: An attacker who tampers with the handshake cannot forge the MAC or signature without K or the long-term signing key; mismatched transcript or incorrect K causes verification failure, preventing the attacker from convincing parties they share the same key.
• Reflection attacks: Including role identifiers and the full transcript in MACs/signatures prevents replaying the other side’s message as one’s own. Reflection would require producing a valid MAC/signature for the same role and transcript which leaks role binding and is infeasible without the key or signing key.

Including nonces/session identifiers, role tags, and binding to the full transcript is critical to avoid subtle attacks (e.g., key-compromise impersonation or cross-protocol replay).

Approach (brief)

Use a random r with 1 < r < N, gcd(r,N)=1. Blind message M by M' = M * r^e mod N, compute S' = (M')^d mod N (in constant-time), then unblind S = S' * r^{-1} mod N. For CRT, blind separately or use a single r lifted to p,q. Add verification by checking S^e ≡ M (mod N) and fallback on non-CRT safe path if mismatch.

Pseudocode

# Inputs: M, private key (N, d, p, q, dp, dq, qinv), public e
function RSA_sign_blinded(M):
  repeat:
    r = random_in_range(2, N-1)
  until gcd(r, N) == 1

  # compute r^e mod N in constant-time exp
  r_e = modexp_consttime(r, e, N)
  M_blind = (M * r_e) mod N

  # Perform exponentiation; prefer CRT version below
  S_blind = modexp_crt_consttime(M_blind, key)   # see CRT section

  r_inv = modinv_consttime(r, N)
  S = (S_blind * r_inv) mod N

  # Verification (constant-time compare)
  if not consttime_equal(modexp_consttime(S, e, N), M):
    # optional: retry or compute safe non-CRT full modexp
    S = modexp_consttime(M, d, N)
  return S

CRT adaptation

• Choose r such that gcd(r,p)=gcd(r,q)=1 (same check suffices).
• Either blind M as above then use CRT-safe exponentiation: compute m1 = M_blind mod p, m2 = M_blind mod q; s1 = m1^{dp} mod p, s2 = m2^{dq} mod q (use constant-time modular multiply/add routines); recombine with CRT.
• Alternatively pick rp = r mod p, rq = r mod q and blind per-prime: m1 = (M mod p) * rp^{e mod (p-1)} mod p, similar for q — this avoids cross-mod reductions.

Constant-time precautions

• Use constant-time modular exponentiation and multiplication (fixed-window with dummy operations).
• Ensure random r length is uniformly distributed (no bias leaks).
• Avoid branches based on secret data; use constant-time gcd/modinv implementations or compute modinv via precomputed exponent if safe.
• Limit retries on verification; use safe full-modexp fallback to avoid leaking CRT info.

Verification

• Check S^e mod N == M (constant-time). If fails, fallback to single-limb full modexp without CRT and log/handle per policy.