fix: [SOVEREIGNTY] Audit NostrIdentity for side-channel timing attacks (closes #801)

FINDINGS-issue-801.md

@@ -0,0 +1,305 @@
+# Security Audit: NostrIdentity BIP340 Schnorr Signatures — Timing Side-Channel Analysis
+
+**Issue:** #801
+**Repository:** Timmy_Foundation/the-nexus
+**File:** `nexus/nostr_identity.py`
+**Auditor:** mimo-v2-pro swarm worker
+**Date:** 2026-04-10
+
+---
+
+## Summary
+
+The pure-Python BIP340 Schnorr signature implementation in `NostrIdentity` has **multiple timing side-channel vulnerabilities** that could allow an attacker with precise timing measurements to recover the private key. The implementation is suitable for prototyping and non-adversarial environments but **must not be used in production** without the fixes described below.
+
+---
+
+## Architecture
+
+The Nostr sovereign identity system consists of two files:
+
+- **`nexus/nostr_identity.py`** — Pure-Python secp256k1 + BIP340 Schnorr signature implementation. No external dependencies. Contains `NostrIdentity` class for key generation, event signing, and pubkey derivation.
+- **`nexus/nostr_publisher.py`** — Async WebSocket publisher that sends signed Nostr events to public relays (damus.io, nos.lol, snort.social).
+- **`app.js` (line 507)** — Browser-side `NostrAgent` class uses **mock signatures** (`mock_id`, `mock_sig`), not real crypto. Not affected.
+
+---
+
+## Vulnerabilities Found
+
+### 1. Branch-Dependent Scalar Multiplication — CRITICAL
+
+**Location:** `nostr_identity.py:41-47` — `point_mul()`
+
+```python
+def point_mul(p, n):
+    r = None
+    for i in range(256):
+        if (n >> i) & 1:        # <-- branch leaks Hamming weight
+            r = point_add(r, p)
+        p = point_add(p, p)
+    return r
+```
+
+**Problem:** The `if (n >> i) & 1` branch causes `point_add(r, p)` to execute only when the bit is 1. An attacker measuring signature generation time can determine which bits of the scalar are set, recovering the private key from a small number of timed signatures.
+
+**Severity:** CRITICAL — direct private key recovery.
+
+**Fix:** Use a constant-time double-and-always-add algorithm:
+
+```python
+def point_mul(p, n):
+    r = (None, None)
+    for i in range(256):
+        bit = (n >> i) & 1
+        r0 = point_add(r, p)         # always compute both
+        r = r0 if bit else r          # constant-time select
+        p = point_add(p, p)
+    return r
+```
+
+Or better: use Montgomery ladder which avoids point doubling on the identity.
+
+---
+
+### 2. Branch-Dependent Point Addition — CRITICAL
+
+**Location:** `nostr_identity.py:28-39` — `point_add()`
+
+```python
+def point_add(p1, p2):
+    if p1 is None: return p2       # <-- branch leaks operand state
+    if p2 is None: return p1       # <-- branch leaks operand state
+    (x1, y1), (x2, y2) = p1, p2
+    if x1 == x2 and y1 != y2: return None  # <-- branch leaks equality
+    if x1 == x2:                          # <-- branch leaks equality
+        m = (3 * x1 * x1 * inverse(2 * y1, P)) % P
+    else:
+        m = ((y2 - y1) * inverse(x2 - x1, P)) % P
+    ...
+```
+
+**Problem:** Multiple conditional branches leak whether inputs are the identity point, whether x-coordinates are equal, and whether y-coordinates are negations. Combined with the scalar multiplication above, this gives an attacker detailed timing information about intermediate computations.
+
+**Severity:** CRITICAL — compounds the scalar multiplication leak.
+
+**Fix:** Replace with a branchless point addition using Jacobian or projective coordinates with dummy operations:
+
+```python
+def point_add(p1, p2):
+    # Use Jacobian coordinates; always perform full addition
+    # Use conditional moves (simulated with arithmetic masking)
+    # for selecting between doubling and addition paths
+```
+
+---
+
+### 3. Branch-Dependent Y-Parity Check in Signing — HIGH
+
+**Location:** `nostr_identity.py:57-58` — `sign_schnorr()`
+
+```python
+R = point_mul(G, k)
+if R[1] % 2 != 0:       # <-- branch leaks parity of R's y-coordinate
+    k = N - k
+```
+
+**Problem:** The conditional negation of `k` based on the y-parity of R leaks information about the nonce through timing. While less critical than the point_mul leak (it's a single bit), combined with other leaks it aids key recovery.
+
+**Severity:** HIGH
+
+**Fix:** Use arithmetic masking:
+
+```python
+R = point_mul(G, k)
+parity = R[1] & 1
+k = (k * (1 - parity) + (N - k) * parity) % N  # constant-time select
+```
+
+---
+
+### 4. Non-Constant-Time Modular Inverse — MEDIUM
+
+**Location:** `nostr_identity.py:25-26` — `inverse()`
+
+```python
+def inverse(a, n):
+    return pow(a, n - 2, n)
+```
+
+**Problem:** CPython's built-in `pow()` with 3 args uses Montgomery ladder internally, which is *generally* constant-time for fixed-size operands. However:
+- This is an implementation detail, not a guarantee.
+- PyPy, GraalPy, and other Python runtimes may use different algorithms.
+- The exponent `n-2` has a fixed Hamming weight for secp256k1's `N`, so this specific case is less exploitable, but relying on it is fragile.
+
+**Severity:** MEDIUM — implementation-dependent; low risk on CPython specifically.
+
+**Fix:** Implement Fermat's little theorem inversion with blinding, or use a dedicated constant-time GCD algorithm (extended binary GCD).
+
+---
+
+### 5. Non-RFC6979 Nonce Generation — LOW (but non-standard)
+
+**Location:** `nostr_identity.py:55`
+
+```python
+k = int.from_bytes(sha256(privkey.to_bytes(32, 'big') + msg_hash), 'big') % N
+```
+
+**Problem:** The nonce derivation is `SHA256(privkey || msg_hash)` which is deterministic but doesn't follow RFC6979 (HMAC-based DRBG). Issues:
+- Not vulnerable to timing (it's a single hash), but could be vulnerable to related-message attacks if the same key signs messages with predictable relationships.
+- BIP340 specifies `tagged_hash("BIP0340/nonce", ...)` with specific domain separation, which is not used here.
+
+**Severity:** LOW — not a timing issue but a cryptographic correctness concern.
+
+**Fix:** Follow RFC6979 or BIP340's tagged hash approach:
+
+```python
+def sign_schnorr(msg_hash, privkey):
+    # BIP340 nonce generation with tagged hash
+    t = privkey.to_bytes(32, 'big')
+    if R_y_is_odd:
+        t = bytes(b ^ 0x01 for b in t)  # negate if needed
+    k = int.from_bytes(tagged_hash("BIP0340/nonce", t + pubkey + msg_hash), 'big') % N
+```
+
+---
+
+### 6. Private Key Bias in Random Generation — LOW
+
+**Location:** `nostr_identity.py:69`
+
+```python
+self.privkey = int.from_bytes(os.urandom(32), 'big') % N
+```
+
+**Problem:** `os.urandom(32)` produces values in `[0, 2^256)`, while `N` is slightly less than `2^256`. The modulo reduction introduces a negligible bias (~2^-128). Not exploitable in practice, but not the cleanest approach.
+
+**Severity:** LOW — theoretically biased, practically unexploitable.
+
+**Fix:** Use rejection sampling or derive from a hash:
+
+```python
+def generate_privkey():
+    while True:
+        candidate = int.from_bytes(os.urandom(32), 'big')
+        if 0 < candidate < N:
+            return candidate
+```
+
+---
+
+### 7. No Scalar/Point Blinding — MEDIUM
+
+**Location:** Global — no blinding anywhere in the implementation.
+
+**Problem:** The implementation has no countermeasures against:
+- **Power analysis** (DPA/SPA) on embedded systems
+- **Cache-timing attacks** on shared hardware (VMs, cloud)
+- **Electromagnetic emanation** attacks
+
+Adding random blinding to scalar multiplication (multiply by `r * r^-1` where `r` is random) would significantly raise the bar for side-channel attacks beyond simple timing.
+
+**Severity:** MEDIUM — not timing-specific, but important for hardening.
+
+---
+
+## What's NOT Vulnerable (Good News)
+
+1. **The JS-side `NostrAgent` in `app.js`** uses mock signatures (`mock_id`, `mock_sig`) — not real crypto, not affected.
+2. **`nostr_publisher.py`** correctly imports and uses `NostrIdentity` without modifying its internals.
+3. **The hash functions** (`sha256`, `hmac_sha256`) use Python's `hashlib` which delegates to OpenSSL — these are constant-time.
+4. **The JSON serialization** in `sign_event()` is deterministic and doesn't leak timing.
+
+---
+
+## Recommended Fix (Full Remediation)
+
+### Priority 1: Replace with secp256k1-py or coincurve (IMMEDIATE)
+
+The fastest, most reliable fix is to stop using the pure-Python implementation entirely:
+
+```python
+# nostr_identity.py — replacement using coincurve
+import coincurve
+import hashlib
+import json
+import os
+
+class NostrIdentity:
+    def __init__(self, privkey_hex=None):
+        if privkey_hex:
+            self.privkey = bytes.fromhex(privkey_hex)
+        else:
+            self.privkey = os.urandom(32)
+        self.pubkey = coincurve.PrivateKey(self.privkey).public_key.format(compressed=True)[1:].hex()
+
+    def sign_event(self, event):
+        event_data = [0, event['pubkey'], event['created_at'], event['kind'], event['tags'], event['content']]
+        serialized = json.dumps(event_data, separators=(',', ':'))
+        msg_hash = hashlib.sha256(serialized.encode()).digest()
+        event['id'] = msg_hash.hex()
+        # Use libsecp256k1's BIP340 Schnorr (constant-time C implementation)
+        event['sig'] = coincurve.PrivateKey(self.privkey).sign_schnorr(msg_hash).hex()
+        return event
+```
+
+**Effort:** ~2 hours (swap implementation, add `coincurve` to `requirements.txt`, test)
+**Risk:** Adds a C dependency. If pure-Python is required (sovereignty constraint), use Priority 2.
+
+### Priority 2: Pure-Python Constant-Time Rewrite (IF PURE PYTHON REQUIRED)
+
+If the sovereignty constraint (no C dependencies) must be maintained, rewrite the elliptic curve operations:
+
+1. **Replace `point_mul`** with Montgomery ladder (constant-time by design)
+2. **Replace `point_add`** with Jacobian coordinate addition that always performs both doubling and addition, selecting with arithmetic masking
+3. **Replace `inverse`** with extended binary GCD with blinding
+4. **Fix nonce generation** to follow RFC6979 or BIP340 tagged hashes
+5. **Fix key generation** to use rejection sampling
+
+**Effort:** ~8-12 hours (careful implementation + test vectors from BIP340 spec)
+**Risk:** Pure-Python crypto is inherently slower (~100ms per signature vs ~1ms with libsecp256k1)
+
+### Priority 3: Hybrid Approach
+
+Use `coincurve` when available, fall back to pure-Python with warnings:
+
+```python
+try:
+    import coincurve
+    USE_LIB = True
+except ImportError:
+    USE_LIB = False
+    import warnings
+    warnings.warn("Using pure-Python Schnorr — vulnerable to timing attacks. Install coincurve for production use.")
+```
+
+**Effort:** ~3 hours
+
+---
+
+## Effort Estimate
+
+| Fix | Effort | Risk Reduction | Recommended |
+|-----|--------|----------------|-------------|
+| Replace with coincurve (Priority 1) | 2h | Eliminates all timing issues | YES — do this |
+| Pure-Python constant-time rewrite (Priority 2) | 8-12h | Eliminates timing issues | Only if no-C constraint is firm |
+| Hybrid (Priority 3) | 3h | Full for installed, partial for fallback | Good compromise |
+| Findings doc + PR (this work) | 2h | Documents the problem | DONE |
+
+---
+
+## Test Vectors
+
+The BIP340 specification includes test vectors at https://github.com/bitcoin/bips/blob/master/bip-00340/test-vectors.csv
+
+Any replacement implementation MUST pass all test vectors before deployment.
+
+---
+
+## Conclusion
+
+The pure-Python BIP340 Schnorr implementation in `NostrIdentity` is **vulnerable to timing side-channel attacks** that could recover the private key. The primary issue is branch-dependent execution in scalar multiplication and point addition. The fastest fix is replacing with `coincurve` (libsecp256k1 binding). If pure-Python sovereignty is required, a constant-time rewrite using Montgomery ladder and arithmetic masking is needed.
+
+The JS-side `NostrAgent` in `app.js` uses mock signatures and is not affected.
+
+**Recommendation:** Ship `coincurve` replacement immediately. It's 2 hours of work and eliminates the entire attack surface.