ADR-003: Hybrid Post-Quantum Signatures (Ed25519 + ML-DSA-44)¶

Status¶

Accepted | 2025-12-28 (Implemented)

Context¶

The AEGIS override workflow uses BIP-322 Schnorr signatures (ADR-002) which provide strong classical security. However, cryptographically relevant quantum computers (CRQCs) could potentially break elliptic curve signatures via Shor's algorithm, enabling "harvest now, decrypt later" attacks.

Threat Model¶

Current Risk: LOW (no CRQCs exist today)
Future Risk: HIGH (15-30 year horizon per NIST estimates)
Attack Vector: "Harvest now, decrypt later"
Impact: Override signature forgery → governance bypass

NIST Standardization (August 2024)¶

NIST finalized three post-quantum algorithms in FIPS 203/204/205: - ML-KEM (FIPS 203): Key encapsulation (formerly CRYSTALS-Kyber) - ML-DSA (FIPS 204): Digital signatures (formerly CRYSTALS-Dilithium) - SLH-DSA (FIPS 205): Stateless hash-based signatures (formerly SPHINCS+)

Decision¶

Implement hybrid Ed25519 + ML-DSA-44 signatures with defense-in-depth verification.

Architecture¶

┌─────────────────────────────────────────────┐
│         HybridSignatureProvider              │
├─────────────────────────────────────────────┤
│  algorithm_name: "ed25519+ml-dsa-44"         │
│                                              │
│  SIGNATURE_SIZE  = 2,484 bytes               │
│    └─ Ed25519:    64 bytes                   │
│    └─ ML-DSA-44: 2,420 bytes                 │
│                                              │
│  PUBLIC_KEY_SIZE = 1,344 bytes               │
│    └─ Ed25519:    32 bytes                   │
│    └─ ML-DSA-44: 1,312 bytes                 │
│                                              │
│  PRIVATE_KEY_SIZE = 2,592 bytes              │
│    └─ Ed25519:    32 bytes                   │
│    └─ ML-DSA-44: 2,560 bytes                 │
└─────────────────────────────────────────────┘

Key Technical Decisions¶

Aspect	Decision	Rationale
Approach	Hybrid (classical + PQ)	Defense in depth, mitigates algorithm risk
Classical	Ed25519	Fast, well-understood, cryptography library
Post-Quantum	ML-DSA-44 (FIPS 204)	NIST Level 2, smallest PQ signature
Verification	BOTH must verify	Neither algorithm alone is sufficient
Library	liboqs-python	OQS consortium, reference implementation
Signing Mode	Hedged (randomized)	FIPS 204 compliant, side-channel resistant

Why ML-DSA-44 (Dilithium Level 2)?¶

Level	Security	Signature	Public Key	Decision
ML-DSA-44	NIST Level 2 (128-bit)	2,420 B	1,312 B	Selected
ML-DSA-65	NIST Level 3 (192-bit)	3,293 B	1,952 B	Overkill
ML-DSA-87	NIST Level 5 (256-bit)	4,595 B	2,592 B	Overkill

Level 2 matches Ed25519's classical security level, providing balanced protection without excessive overhead.

Implementation¶

Files Created¶

File	Purpose
`src/crypto/mldsa.py`	ML-DSA-44 wrapper using liboqs-python
`src/crypto/hybrid_provider.py`	HybridSignatureProvider implementation
`tests/crypto/test_mldsa.py`	ML-DSA unit tests (28+ tests)
`tests/crypto/test_hybrid_provider.py`	Hybrid provider tests (37+ tests)

Files Modified¶

File	Change
`src/crypto/__init__.py`	Export HYBRID_AVAILABLE, get_hybrid_provider()
`src/workflows/override.py`	SignatureRecord.algorithm field
`pyproject.toml`	liboqs-python dependency in pqc extras

Provider Priority¶

# src/crypto/__init__.py
def get_default_provider() -> SignatureProvider:
    """
    Priority:
    1. BIP322Provider (recommended, Bitcoin-native)
    2. Ed25519Provider (deprecated, legacy fallback)

    Note: HybridSignatureProvider is NOT default until fully validated.
    Use get_hybrid_provider() explicitly for post-quantum protection.
    """

Defense-in-Depth Verification¶

# src/crypto/hybrid_provider.py:verify()
def verify(signature: bytes, message_hash: bytes, public_key: bytes) -> bool:
    ed25519_valid = self._verify_ed25519(ed25519_sig, message_hash, ed25519_pub)
    mldsa_valid = self._verify_mldsa(mldsa_sig, message_hash, mldsa_pub)

    # BOTH must be valid (defense in depth)
    return ed25519_valid and mldsa_valid

Consequences¶

Positive¶

Quantum Resistance: Protection against future CRQCs
Defense in Depth: If one algorithm fails, the other provides security
NIST Compliance: Uses standardized FIPS 204 algorithm
Backward Compatible: Provider injection, existing signatures unaffected
Graceful Degradation: System works without liboqs installed

Negative¶

Size Increase: 2,484 byte signatures vs 64 bytes (39x larger)
Key Storage: 1,344 byte public keys vs 32 bytes (42x larger)
Optional Dependency: Requires liboqs-python (pip) and liboqs (native)
Verification Time: ~1ms vs ~0.1ms (10x slower)

Neutral¶

Hedged Signing: FIPS 204 uses randomized signing (non-deterministic)
Two-Phase Rollout: Hybrid opt-in now, default later when validated

Security Properties¶

Property	Status	Evidence
Defense in depth	✅	Both signatures must verify
Harvest-now-decrypt-later	✅	ML-DSA-44 quantum resistant
Side-channel resistance	✅	FIPS 204 hedged signing mode
Key compromise	✅	Both key pairs required
Algorithm agility	✅	Provider pattern enables swaps

Test Coverage¶

tests/crypto/test_mldsa.py: 30 tests
tests/crypto/test_hybrid_provider.py: 40 tests
tests/test_workflows.py: 3 integration tests

Total: 73 tests, 100% critical path coverage

Dependencies¶

Package	Version	Purpose
liboqs-python	>=0.10.0	NIST PQ algorithm bindings
liboqs (native)	0.14.0	OQS library (brew or source)
cryptography	>=41.0.0	Ed25519 signatures

References¶

External Standards¶

FIPS 204: ML-DSA - NIST post-quantum signature standard
FIPS 203: ML-KEM - NIST post-quantum key encapsulation
Open Quantum Safe - liboqs project

Internal Documents¶

GAP-Q1 Implementation Plan
Gap Analysis - GAP-Q1 entry
ADR-002: BIP-322 Signatures - Foundation layer

Changelog¶

Date	Change
2025-12-28	ADR created, implementation complete
2025-12-27	GAP-Q1 implementation completed