Cryptographic Hashing and Digital Signatures Questions

Approach summary

Construct the combiner so that any collision on the combined function implies a collision on at least one primitive you trust. The simplest provable combiner is output concatenation with domain separation and independent parameters:

• Define H(x) = H1(0 || x) || H2(1 || x) (or H1_s1(x)||H2_s2(x) with independent salts).

Why this helps (formal guarantee sketch)

• If there exists x ≠ x' with H(x) = H(x'), then both H1(0||x)=H1(0||x') and H2(1||x)=H2(1||x'). Thus a collision in H yields collisions in H1 and in H2.
• Therefore, if at least one of H1 or H2 is collision-resistant, then producing a collision for H is at least as hard as producing a collision for that primitive. Formally: a PPT adversary that breaks H yields a PPT adversary that breaks H_i by projecting the collision to H_i.

Limitations and caveats

• Concatenation preserves collision-resistance but increases output length. It does not automatically improve second-preimage or preimage resistance beyond the stronger primitive.
• If H1 and H2 share design flaws (same internal state, related keys, or correlated randomness), combiners may fail; enforce independent implementations/parameterization.
• XOR combiners (H = H1 xor H2) lack the same provable guarantee: an adversary can often manipulate inputs to cancel outputs; security requires stronger assumptions (e.g., both modeled as random or keyed ideal primitives) and gives weaker reductions.
• Practical concerns: performance, output length, and the need for domain separation to prevent cross-collisions.

Recommendations

• Use concatenation with independent salts/domain separation for a provable “at least as strong as one” guarantee.
• Prefer keyed constructions (HMAC or hashing with independent keys) when adversarial chosen-inputs or related-key attacks are realistic.
• Document assumptions in any reduction (which primitive is assumed CR, independence, salt secrecy).

Brief answer summary
ECDSA and EdDSA differ significantly in side-channel resilience, nonce handling, curve form, and operational suitability. For a high-security CA I recommend Ed25519ph (or Ed448 with careful ops). For resource-constrained IoT, recommend X25519 for KEM/KA and Ed25519 for signatures or compact variants with hardware protections.

Side‑channel resistance

• EdDSA (Edwards, e.g., Ed25519/Ed448): designed for constant-time implementations; uses simple, regular group ops (twisted Edwards) that map well to constant-time code and scalar multiplication techniques reducing SCA leakage.
• ECDSA (Weierstrass, e.g., P-256): traditional w/ variable-time inversion and nonce-dependent branching; more prone to timing and power attacks unless hardened (double-and-add always, projective coords, blinding).

Nonce handling

• ECDSA: requires fresh unpredictable nonce per signature; bad RNG -> private key compromise (famously catastrophic). Mitigations: deterministic RFC 6979 or robust RNG + nonce blinding.
• EdDSA: deterministic by design (hash-derived nonces), eliminating RNG dependence for nonce. Deterministic mode improves security against RNG failures; optional randomized pre-hashing exists for extra entropy.

Curve formats

• Weierstrass (P-256, secp256k1): less regular group law; more implementation pitfalls for SCA.
• Edwards (Curve25519/Ed25519, Ed448): unified and complete formulas reduce exceptional cases and make constant-time implementations easier.

Suitability—long-lived server keys vs ephemeral client keys

• Long-lived server CA keys: prefer deterministic, SCA-resistant algorithms with conservative curves and strong margins. Ed448 for highest security or Ed25519 with hardware-protected HSMs. Deterministic nonces reduce RNG risk.
• Client-side ephemeral keys/IoT: prefer compact, fast algorithms with small code and low RAM. X25519 for ECDH; Ed25519 for signatures. If device lacks side‑channel protections, use protocols that minimize secret exposure (ephemeral keys, post-quantum hybrids).

Final recommendations

• High-security CA: Ed448 (or Ed25519 if operational constraints), implemented in HSMs with audited constant-time libs and key management policies.
• Constrained IoT: X25519 for key agreement, Ed25519 for signatures; use deterministic EdDSA to avoid RNG failure, enable firmware mitigations for SCA (masking, simple blinding), and consider hardware-backed keys where possible.

Situation & goal
Protect a legacy API that accepts RSA PKCS#1 v1.5 + SHA-1 signatures from Bleichenbacher-style padding oracles and chosen-prefix collision attacks (SHA-1).

Detection (concrete)

• Instrument verification paths for timing variance and error-message divergence; log verification time histogram per client IP and endpoint.
• Detect anomalous repeated malformatted signatures (high error rate, structured bytes) using IDS rules.
• Use fuzzing (e.g., boofuzz) across signature inputs and monitor oracle-like behavior.

Mitigations — code-level

• Enforce strict ASN.1 + EMSA-PKCS1-v1_5 encoding checks; do NOT accept truncated/lenient encodings.
• Make verification constant-time and unify error paths/responses.

Example (Python, conceptual):

# constant-time check sketch using cryptography library
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives import hashes
def verify(pubkey, signature, message):
    # always perform full-length operations and return same-class errors
    try:
        pubkey.verify(
            signature,
            message,
            padding.PKCS1v15(),
            hashes.SHA256()  # migrate to SHA-2
        )
    except Exception:
        # map all exceptions to a single opaque error and constant-time sleep
        constant_time_sleep()
        raise VerificationFailed

Runtime mitigations

• Rate-limit signature verification attempts per principal.
• Add jitter/constant delay to verification to reduce timing channels.
• Reject signatures that use SHA-1 immediately (policy flag) while allowing verification logging for forensics.

Library & infra updates

• Upgrade crypto libs to latest (OpenSSL >=1.1.1+ / 3.x) with constant-time RSA and hardened ASN.1 parsers.
• Prefer RSA-PSS with SHA-256 for new keys; enable hardware HSMs to perform verifications if available.

Emergency policy

• Immediate: Reject any certificates/signatures signed with SHA-1 (HTTP 403) for high-risk endpoints (auth, payment, code signing). Add monitoring rule & incident response runbook.
• 48–72h: Deploy constant-time verification + uniform errors + rate limiting.
• 1 week: Library upgrade in staging with RSA-PSS support; enable enforcement flag off-by-default.
• 30 days: Turn on enforcement for all internal high-risk endpoints; rotate keys for critical clients.
• 90 days: Full retirement of PKCS#1 v1.5+SHA-1; require RSA-PSS or ECDSA with SHA-2.

Migration timeline & prioritization

1. Day 0: High-risk endpoints — auth, session tokens, payment, code signing — immediate SHA-1 rejection + logging.
2. Days 1–7: Deploy runtime mitigations (constant delays, rate-limiting), upgrade libs in staging.
3. Days 7–30: Migrate clients: offer compatibility endpoints; issue new credentials using RSA-PSS/SHA-256.
4. Days 30–90: Cutover, revoke legacy trust; rotate keys; full deprecation of PKCS#1 v1.5 with SHA-1.

Trade-offs & rationale

• Immediate strict rejection reduces availability for legacy clients but prevents catastrophic oracle exploitation.
• Constant-time + uniform errors mitigate Bleichenbacher; moving away from SHA-1 prevents chosen-prefix collisions.

Metrics & validation

• Monitor reduction in malformed attempts, timing-variance sigma, and successful signature verifications.
• Post-migration: run adaptive whitebox/blackbox tests and formal verification of padding checks.

Clarify requirements & goals

• Integrity/authenticity across versions, content-addressed, resistant to collisions/second-preimage even if algorithms evolve; support mixed-era objects and an auditable migration path.

High-level design

• Use Merkle DAG like Git, but every object header includes: (1) algorithm id, (2) domain-separator tag, (3) canonical serialization version, (4) timestamp and signer meta. Object ID = H_alg( domain || type || serialization || payload ).

Domain separation

• Domain prefix explicit per object type and purpose, e.g. "git:blob:v1", "git:tree:v1", "git:migration:v1". This prevents type-collision and cross-protocol preimage attacks.

Hash algorithm versioning

• Include algorithm identifier (e.g. IETF-style: alg = {name, params, version}) inside object header and in references. References store (alg_id, digest). Verify by recomputing with stated alg.

Storing mixed-era objects

• DAG nodes may reference digests computed with different algs. Store reference tuples (alg_id || digest). Verification traverses DAG using each referenced alg to recompute.

Migration path if hash broken

1. Detect and announce deprecation (timestamped signed statement).
2. Add chained rehash objects: for every stored object O with old digest d_old, create a migration wrapper M = {alg_new_id, old_alg_id, old_digest=d_old, payload = canonical_serial(O)} and compute d_new = H_new(domain || "migration" || M). Store M under d_new; update refs in newer commits to point to d_new.
3. Keep signed provenance: sign migration manifests with repository key to prove mapping from d_old→d_new.
4. Provide an incremental utility that re-writes commits to point to new digests, preserving history by layering (old refs remain immutable). Verifiers accept either original chain if still secure or follow signed migration manifests to validate via chained hashes.

Integrity & auditability

• All migration manifests and deprecation statements are themselves content-addressed and signed; verification checks chain of signatures and rehash mappings. Clients must verify both canonical serialization and alg identifiers before accepting migrated references.

Trade-offs

• Storage blow-up vs. auditability: migration wrappers duplicate objects; use deduplication of canonical payloads.
• Complexity: verifier must support multiple algs and signature verification.

This design preserves versioned authenticity, resists cross-type and cross-era collisions, and provides an auditable, incremental migration path.

Scope & objectives

• Replace SHA-1 signatures across PKI to SHA-256 while preserving service continuity and verifiability for legacy clients.
• Minimize windows of exposure to collision attacks; maintain code-signing and OTA trust semantics (timestamps, archived signatures).

Inventory & risk assessment

• Catalog all certs (roots, intermediates, leaf), CRLs/OCSP responders, code-signing keys, signed artifacts, timestamping servers, devices with legacy stacks.
• Prioritize by risk/impact: Internet-facing TLS, firmware OTA, code-signing, then internal services and archives.
• Threat note: SHA-1 collision practical for high-value targets — accelerate high-risk replacements.

Phased migration plan

1. Preparation
   • Generate new RSA/ECDSA keys and new CA certs signed with SHA-256 (or stronger hashes).
   • Publish policy/expiry: shorten validity for transitional certs.
2. Cross-signing / dual-path trust
   • Issue new intermediates signed by new root (SHA-256) and cross-sign those intermediates with existing SHA-1 root to create dual-validation paths. This preserves legacy client trust while enabling modern clients to prefer SHA-256.
   • For extremely constrained devices, provide vendor-specific cross-signed intermediates.
3. Reissue leaf certs
   • Reissue high-priority leaf certs immediately under SHA-256 chain; stagger bulk reissues.
4. Client & device updates
   • Push client truststore updates where possible; for devices that can't be updated, rely on cross-signed paths and TLS protocol negotiation.
   • For embedded/OTAs: deploy staged firmware that accepts new root/intermediate or includes cross-signed intermediate.
5. Code-signing and timestamps
   • Re-sign active artifacts with SHA-256. Ensure use of trusted RFC 3161 timestamping; timestamp countersignatures retain validity after signer cert expires.
   • For existing archived signatures: verify archived code using timestamped signatures; where missing, consider countersigning (if policy allows) or maintain a validated archive with hash-chain proofs.
6. Revocation & CRL/OCSP
   • Ensure CRL/OCSP responders support new certs and have high-availability. Publish revocations for deprecated SHA-1 CA certs once migration is safe.
   • Enable OCSP stapling on servers to control latency and privacy.
7. Testing & rollouts
   • Canary in controlled environments; progressively expand cohorts.
   • Use simulated legacy devices/libraries to validate fallback-to-sha1 behavior.
8. Cutover & deprecation
   • After coverage thresholds met and telemetry clean, deprecate SHA-1-signed intermediates: revoke or set short-lived revocation effective times.
   • Communicate deprecation windows to stakeholders.

Safety nets

• Maintain cross-signed chain until legacy population falls below threshold.
• Keep offline backups of old CA keys for audit/validation only; do not use them to sign new material.
• Implement emergency rollback: re-enable SHA-1 path if unexpected mass failures, but limit duration.

Monitoring & metrics

• Telemetry: certificate negotiation hashes (which hash algorithm used), OCSP failure rates, handshake failures per client fingerprint, OTA failure rates, code-sign verification errors.
• Observability: centralized dashboards, alerting on spike of verification failures, increased OCSP latency, CT log errors.
• Audit: CT log entries for new certs; periodic collision-detection scans on public artifacts.
• Post-migration cryptanalysis: monitor research and CVEs; be ready to accelerate revocation if SHA-1 practical attacks advance.

Operational controls & compliance

• Update PKI documentation, certificate policies, audit logs.
• Run cryptographic review of key sizes and signature algorithms (move to ECDSA/P-256 or Ed25519 where supported).
• Ensure legal/forensic access to archived SHA-1-signed artifacts for investigations.

Outcome: phased, measurable migration that preserves compatibility via cross-signing, protects long-term integrity via timestamping and re-signing, and maintains service through robust monitoring and rollback mechanisms.