README.md
Rendering markdown...
{
"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
}