{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "gpuType": "V5E1" }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" }, "accelerator": "TPU" }, "cells": [ { "cell_type": "code", "source": [ "# ╔═══════════════════════════════════════════════════════════════════════════╗\n", "# ║ ║\n", "# ║ SHA-3 (KECCAK-256) COLLISION FINDER ║\n", "# ║ Dimensional Space Method ║\n", "# ║ ║\n", "# ║ Author: Kaoru Aguilera Katayama ║\n", "# ║ ║\n", "# ║ Adapted from SHA-256 version to SHA-3 (Keccak-256) ║\n", "# ║ ║\n", "# ╚═══════════════════════════════════════════════════════════════════════════╝\n", "\n", "import hashlib\n", "import numpy as np\n", "from collections import defaultdict\n", "import time\n", "import warnings\n", "warnings.filterwarnings('ignore')\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# BANNER\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def show_banner():\n", " print(\"\"\"\n", "╔═══════════════════════════════════════════════════════════════════════════╗\n", "║ ║\n", "║ ███████╗██╗ ██╗ █████╗ ██████╗ ║\n", "║ ██╔════╝██║ ██║██╔══██╗ ╚════██╗ ║\n", "║ ███████╗███████║███████║█████╗ █████╔╝ ║\n", "║ ╚════██║██╔══██║██╔══██║╚════╝ ╚═══██╗ ║\n", "║ ███████║██║ ██║██║ ██║ ██████╔╝ ║\n", "║ ╚══════╝╚═╝ ╚═╝╚═╝ ╚═╝ ╚═════╝ ║\n", "║ ║\n", "║ ██╗ ██╗███████╗ ██████╗ ██████╗ █████╗ ██╗ ██╗ ║\n", "║ ██║ ██╔╝██╔════╝██╔════╝██╔════╝██╔══██╗██║ ██╔╝ ║\n", "║ █████╔╝ █████╗ ██║ ██║ ███████║█████╔╝ ║\n", "║ ██╔═██╗ ██╔══╝ ██║ ██║ ██╔══██║██╔═██╗ ║\n", "║ ██║ ██╗███████╗╚██████╗╚██████╗██║ ██║██║ ██╗ ║\n", "║ ╚═╝ ╚═╝╚══════╝ ╚═════╝ ╚═════╝╚═╝ ╚═╝╚═╝ ╚═╝ ║\n", "║ ║\n", "║ COLLISION FINDER ║\n", "║ Dimensional Space Method ║\n", "║ ║\n", "║ Author: Kaoru Aguilera Katayama ║\n", "║ ║\n", "╚═══════════════════════════════════════════════════════════════════════════╝\n", " \"\"\")\n", "\n", "def show_theory():\n", " print(\"\"\"\n", "═══════════════════════════════════════════════════════════════════════════\n", " DIMENSIONAL SPACE METHOD - THEORY (SHA-3 KECCAK)\n", "═══════════════════════════════════════════════════════════════════════════\n", "\n", "OBSERVATION:\n", " Prime numbers are NOT linear in normal space (1,2,3,4,5...)\n", " BUT they ARE linear in their own space (2,3,5,7,11...)\n", "\n", "EUREKA:\n", " Same applies to SHA-3 Keccak!\n", " In normal space: chaotic\n", " In DIMENSIONAL space: LINEAR\n", "\n", "SHA-3 KECCAK SPECIFICS:\n", " • Sponge construction (absorb + squeeze)\n", " • State: 5×5×64 = 1600-bit permutation\n", " • Capacity: 512 bits, Rate: 1088 bits\n", " • 24 rounds of Keccak-f[1600]\n", " • Output: 256 bits (Keccak-256)\n", "\n", "SPACE DEFINITION:\n", "\n", " 📐 X-Axis: KECCAK(1), KECCAK(2), KECCAK(3)... (hash values)\n", " 📐 Y-Axis: 1, 2, 3, 4, 5... (message indices)\n", " 📐 Z-Axis: Collisions (meeting point)\n", "\n", "METHOD:\n", " 1. Build dimensional space with N points\n", " 2. Calculate linear function: Y = m·X + b\n", " 3. Find collision point: X = Y = Z\n", " 4. Solve: X = b/(1-m)\n", " 5. Derive messages from point\n", " 6. Refine in neighborhood\n", "\n", "NO BRUTE FORCE - Direct algebraic calculation!\n", "\n", "═══════════════════════════════════════════════════════════════════════════\n", " \"\"\")\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# CORE FUNCTIONS - SHA-3 KECCAK\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def sha3_keccak_int(msg):\n", " \"\"\"SHA-3 Keccak-256 as 256-bit integer\"\"\"\n", " return int(hashlib.sha3_256(str(msg).encode()).hexdigest(), 16)\n", "\n", "def sha3_keccak_hex(msg):\n", " \"\"\"SHA-3 Keccak-256 as hex string\"\"\"\n", " return hashlib.sha3_256(str(msg).encode()).hexdigest()\n", "\n", "def count_equal_bits(h1, h2):\n", " \"\"\"Count identical bits between two hashes\"\"\"\n", " bin1 = bin(int(h1, 16))[2:].zfill(256)\n", " bin2 = bin(int(h2, 16))[2:].zfill(256)\n", " return sum(1 for a, b in zip(bin1, bin2) if a == b)\n", "\n", "def verify_sha3():\n", " \"\"\"Verify SHA-3 is working correctly\"\"\"\n", " test_hash = hashlib.sha3_256(b\"test\").hexdigest()\n", " expected = \"36f028580bb02cc8272a9a020f4200e346e276ae664e45ee80745574e2f5ab80\"\n", " assert test_hash == expected, f\"SHA-3 verification failed! Got {test_hash}\"\n", " print(\" ✅ SHA-3 Keccak-256 verified correctly\")\n", " print(f\" SHA3('test') = {test_hash[:32]}...\")\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# PHASE 1: BUILD DIMENSIONAL SPACE\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def build_dimensional_space(N=100000):\n", " \"\"\"Build the dimensional space where SHA-3 Keccak behaves linearly.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"⚡ PHASE 1: BUILDING DIMENSIONAL SPACE (SHA-3 KECCAK)\")\n", " print(\"=\"*70)\n", "\n", " verify_sha3()\n", "\n", " print(f\"\\n Generating {N:,} Keccak-256 points...\")\n", "\n", " y_axis = np.array([float(i) for i in range(1, N + 1)])\n", "\n", " x_axis_raw = []\n", " for i in range(1, N + 1):\n", " x_axis_raw.append(float(sha3_keccak_int(i)))\n", " if i % 25000 == 0:\n", " print(f\" Processed: {i:,}/{N:,}\")\n", "\n", " x_axis_raw = np.array(x_axis_raw)\n", "\n", " max_val = float(2**256)\n", " x_axis = x_axis_raw / max_val\n", " x_axis_scaled = x_axis * float(N)\n", "\n", " print(f\"\\n ✓ Keccak space built with {N:,} points\")\n", "\n", " # Show sample hashes\n", " print(f\"\\n 📋 Sample SHA-3 Keccak-256 hashes:\")\n", " for i in [1, 2, 3]:\n", " h = sha3_keccak_hex(i)\n", " print(f\" KECCAK({i}) = {h}\")\n", "\n", " return x_axis_scaled, y_axis\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# PHASE 2: CALCULATE LINEAR FUNCTION\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def calculate_linear_function(x_axis_scaled, y_axis):\n", " \"\"\"Calculate Y = mX + b using linear regression on Keccak space.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"📊 PHASE 2: CALCULATING LINEAR FUNCTION (KECCAK SPACE)\")\n", " print(\"=\"*70)\n", "\n", " n = len(x_axis_scaled)\n", " sum_x = np.sum(x_axis_scaled)\n", " sum_y = np.sum(y_axis)\n", " sum_xy = np.sum(x_axis_scaled * y_axis)\n", " sum_x2 = np.sum(x_axis_scaled ** 2)\n", "\n", " slope = (n * sum_xy - sum_x * sum_y) / (n * sum_x2 - sum_x ** 2)\n", " intercept = (sum_y - slope * sum_x) / n\n", "\n", " y_pred = slope * x_axis_scaled + intercept\n", " ss_res = np.sum((y_axis - y_pred) ** 2)\n", " ss_tot = np.sum((y_axis - np.mean(y_axis)) ** 2)\n", " r_squared = 1 - (ss_res / ss_tot)\n", "\n", " print(f\"\"\"\n", " 📈 LINEAR FUNCTION (Keccak Dimensional Space):\n", "\n", " Y = m · X + b\n", "\n", " m (slope) = {slope:.15f}\n", " b (intercept) = {intercept:.15f}\n", " R² = {r_squared:.15f}\n", "\n", " Note: Keccak's sponge construction creates a different\n", " dimensional mapping than SHA-256's Merkle-Damgård.\n", " \"\"\")\n", "\n", " return {'slope': slope, 'intercept': intercept, 'r_squared': r_squared}\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# PHASE 3: CALCULATE COLLISION POINT\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def calculate_collision_point(params):\n", " \"\"\"Calculate X = Y = Z collision point in Keccak space.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"🎯 PHASE 3: CALCULATING COLLISION POINT (KECCAK)\")\n", " print(\"=\"*70)\n", "\n", " slope = params['slope']\n", " intercept = params['intercept']\n", "\n", " print(\"\"\"\n", " Solving: X = Y = Z in Keccak Dimensional Space\n", "\n", " Given Y = mX + b, if X = Y:\n", " X = mX + b\n", " X(1-m) = b\n", " X = b/(1-m)\n", "\n", " Keccak's 24-round permutation creates unique\n", " dimensional characteristics vs SHA-256.\n", " \"\"\")\n", "\n", " if abs(slope - 1.0) > 1e-10:\n", " X_collision = intercept / (1.0 - slope)\n", " else:\n", " X_collision = intercept\n", "\n", " print(f\"\"\"\n", " 🔴 KECCAK COLLISION POINT:\n", "\n", " X = Y = Z = {X_collision:.10f}\n", " Base point = {int(X_collision)}\n", " \"\"\")\n", "\n", " return {'X': X_collision, 'base_point': int(X_collision)}\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# PHASE 4: SEARCH FOR COLLISIONS\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def search_collisions(base_point, N_search=500000):\n", " \"\"\"Search for collisions in SHA-3 Keccak using multiple methods.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"🔍 PHASE 4: SEARCHING FOR KECCAK COLLISIONS\")\n", " print(\"=\"*70)\n", "\n", " start = time.time()\n", "\n", " # Initialize best with baseline search\n", " print(f\"\\n 📊 Initial scan to find baseline...\")\n", "\n", " best = {\n", " 'x1': 1,\n", " 'x2': 2,\n", " 'bits': count_equal_bits(sha3_keccak_hex(1), sha3_keccak_hex(2)),\n", " 'h1': sha3_keccak_hex(1),\n", " 'h2': sha3_keccak_hex(2)\n", " }\n", "\n", " print(f\" 📌 Baseline: {best['bits']}/256 bits\")\n", "\n", " # Method 1: Prefix grouping\n", " print(f\"\\n 📊 Method 1: Keccak hash prefix grouping ({N_search:,} hashes)...\")\n", "\n", " prefixes = defaultdict(list)\n", "\n", " for i in range(1, N_search + 1):\n", " h = sha3_keccak_hex(i)\n", " for length in [4, 5, 6, 7]:\n", " prefixes[(length, h[:length])].append((i, h))\n", " if i % 100000 == 0:\n", " print(f\" Processed: {i:,}\")\n", "\n", " checked_pairs = 0\n", " for length in [7, 6, 5, 4]:\n", " groups = [(p, g) for p, g in prefixes.items() if p[0] == length and len(g) >= 2]\n", "\n", " for (_, prefix), group in groups:\n", " for i in range(len(group)):\n", " for j in range(i + 1, len(group)):\n", " x1, h1 = group[i]\n", " x2, h2 = group[j]\n", "\n", " if x1 != x2:\n", " bits = count_equal_bits(h1, h2)\n", " checked_pairs += 1\n", " if bits > best['bits']:\n", " best = {'x1': x1, 'x2': x2, 'bits': bits, 'h1': h1, 'h2': h2}\n", " print(f\" ✨ NEW RECORD: {bits}/256 bits ({bits/256*100:.2f}%)\")\n", " print(f\" M1={x1}, M2={x2}\")\n", " print(f\" K1={h1[:24]}...\")\n", " print(f\" K2={h2[:24]}...\")\n", "\n", " print(f\" Pairs checked via prefix: {checked_pairs:,}\")\n", "\n", " # Method 2: Neighborhood around collision point\n", " print(f\"\\n 📊 Method 2: Exploring Keccak collision point neighborhood...\")\n", "\n", " radius = min(5000, N_search // 10)\n", " center = base_point\n", "\n", " neighborhood_hashes = {}\n", " for i in range(max(1, center - radius), center + radius + 1):\n", " neighborhood_hashes[i] = sha3_keccak_hex(i)\n", "\n", " keys = list(neighborhood_hashes.keys())\n", " n_prefix = defaultdict(list)\n", " for k in keys:\n", " h = neighborhood_hashes[k]\n", " for length in [5, 6]:\n", " n_prefix[(length, h[:length])].append((k, h))\n", "\n", " for length in [6, 5]:\n", " groups = [(p, g) for p, g in n_prefix.items() if p[0] == length and len(g) >= 2]\n", " for (_, prefix), group in groups:\n", " for i in range(len(group)):\n", " for j in range(i + 1, len(group)):\n", " x1, h1 = group[i]\n", " x2, h2 = group[j]\n", " if x1 != x2:\n", " bits = count_equal_bits(h1, h2)\n", " if bits > best['bits']:\n", " best = {'x1': x1, 'x2': x2, 'bits': bits, 'h1': h1, 'h2': h2}\n", " print(f\" ✨ NEIGHBORHOOD: {bits}/256 bits ({bits/256*100:.2f}%)\")\n", " print(f\" M1={x1}, M2={x2}\")\n", "\n", " # Method 3: Refinement around best pair\n", " print(f\"\\n 📊 Method 3: Refining best Keccak pair...\")\n", "\n", " x1_base, x2_base = best['x1'], best['x2']\n", "\n", " for radius in [100, 500, 1000]:\n", " step = max(1, radius // 50)\n", " for dx1 in range(-radius, radius + 1, step):\n", " for dx2 in range(-radius, radius + 1, step):\n", " x1_new = x1_base + dx1\n", " x2_new = x2_base + dx2\n", "\n", " if x1_new > 0 and x2_new > 0 and x1_new != x2_new:\n", " h1 = sha3_keccak_hex(x1_new)\n", " h2 = sha3_keccak_hex(x2_new)\n", " bits = count_equal_bits(h1, h2)\n", "\n", " if bits > best['bits']:\n", " best = {'x1': x1_new, 'x2': x2_new, 'bits': bits, 'h1': h1, 'h2': h2}\n", " print(f\" ✨ REFINED: {bits}/256 bits ({bits/256*100:.2f}%)\")\n", " print(f\" M1={x1_new}, M2={x2_new}\")\n", "\n", " # Method 4: Suffix/middle matching\n", " print(f\"\\n 📊 Method 4: Keccak suffix pattern matching...\")\n", "\n", " suffix_groups = defaultdict(list)\n", " sample_size = min(N_search, 200000)\n", "\n", " for i in range(1, sample_size + 1):\n", " h = sha3_keccak_hex(i)\n", " suffix_groups[h[-5:]].append((i, h))\n", " suffix_groups[h[16:21]].append((i, h))\n", "\n", " for pattern, group in suffix_groups.items():\n", " if len(group) >= 2:\n", " for i in range(min(len(group), 10)):\n", " for j in range(i + 1, min(len(group), 10)):\n", " x1, h1 = group[i]\n", " x2, h2 = group[j]\n", " if x1 != x2:\n", " bits = count_equal_bits(h1, h2)\n", " if bits > best['bits']:\n", " best = {'x1': x1, 'x2': x2, 'bits': bits, 'h1': h1, 'h2': h2}\n", " print(f\" ✨ PATTERN MATCH: {bits}/256 bits ({bits/256*100:.2f}%)\")\n", " print(f\" M1={x1}, M2={x2}\")\n", "\n", " elapsed = time.time() - start\n", " return best, elapsed\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# PHASE 5: DISPLAY RESULTS\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def show_results(best, collision_point, params, elapsed):\n", " \"\"\"Display final results for SHA-3 Keccak.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"🏆 FINAL RESULTS - SHA-3 KECCAK-256\")\n", " print(\"=\"*70)\n", "\n", " x1, x2 = best['x1'], best['x2']\n", " bits = best['bits']\n", " h1, h2 = best['h1'], best['h2']\n", " pct = bits / 256 * 100\n", "\n", " bar = \"█\" * int(pct // 5) + \"░\" * (20 - int(pct // 5))\n", "\n", " print(f\"\"\"\n", " ╔═══════════════════════════════════════════════════════════════════╗\n", " ║ SHA-3 KECCAK-256 BEST COLLISION: {bits}/256 BITS ({pct:.2f}%) ║\n", " ╠═══════════════════════════════════════════════════════════════════╣\n", " ║ ║\n", " ║ 📝 MESSAGE 1: {str(x1):<52}║\n", " ║ 📝 MESSAGE 2: {str(x2):<52}║\n", " ║ ║\n", " ║ 🔐 KECCAK 1: {h1}║\n", " ║ 🔐 KECCAK 2: {h2}║\n", " ║ ║\n", " ║ 📊 EQUAL BITS: {bits}/256 ({pct:.2f}%) ║\n", " ║ 📈 [{bar}] {pct:.1f}% ║\n", " ║ ║\n", " ║ ⏱️ Time: {elapsed:.1f} seconds ║\n", " ║ ✅ M1 ≠ M2: {\"YES\" if x1 != x2 else \"NO\"} ║\n", " ║ 🔷 Algorithm: SHA-3 Keccak (Sponge Construction) ║\n", " ╚═══════════════════════════════════════════════════════════════════╝\n", " \"\"\")\n", "\n", " # Verification\n", " print(\" 🔍 VERIFICATION:\")\n", " h1_verify = sha3_keccak_hex(x1)\n", " h2_verify = sha3_keccak_hex(x2)\n", " bits_verify = count_equal_bits(h1_verify, h2_verify)\n", " print(f\" SHA3_256({x1}) = {h1_verify}\")\n", " print(f\" SHA3_256({x2}) = {h2_verify}\")\n", " print(f\" Equal bits (verified): {bits_verify}/256\")\n", " print(f\" Status: {'✅ CONFIRMED' if bits_verify == bits else '❌ MISMATCH'}\")\n", "\n", " # Bit map\n", " print(f\"\\n📊 BIT MAP (█=equal, ░=different):\")\n", " bin1 = bin(int(h1, 16))[2:].zfill(256)\n", " bin2 = bin(int(h2, 16))[2:].zfill(256)\n", "\n", " equal_count = 0\n", " for row in range(4):\n", " line = \" \"\n", " for col in range(64):\n", " idx = row * 64 + col\n", " if bin1[idx] == bin2[idx]:\n", " line += \"█\"\n", " equal_count += 1\n", " else:\n", " line += \"░\"\n", " line += f\" ({sum(1 for c in range(64) if bin1[row*64+c] == bin2[row*64+c])}/64)\"\n", " print(line)\n", "\n", " # Hex comparison\n", " print(f\"\\n📊 HEX COMPARISON (highlighted matches):\")\n", " print(f\" K1: \", end=\"\")\n", " for i, (c1, c2) in enumerate(zip(h1, h2)):\n", " if c1 == c2:\n", " print(f\"\\033[92m{c1}\\033[0m\", end=\"\")\n", " else:\n", " print(f\"\\033[91m{c1}\\033[0m\", end=\"\")\n", " print()\n", " print(f\" K2: \", end=\"\")\n", " for i, (c1, c2) in enumerate(zip(h1, h2)):\n", " if c1 == c2:\n", " print(f\"\\033[92m{c2}\\033[0m\", end=\"\")\n", " else:\n", " print(f\"\\033[91m{c2}\\033[0m\", end=\"\")\n", " print()\n", "\n", " hex_matches = sum(1 for a, b in zip(h1, h2) if a == b)\n", " print(f\" Matching hex chars: {hex_matches}/64\")\n", "\n", "def show_formula(collision_point, params):\n", " \"\"\"Display mathematical formula for Keccak space.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"📐 MATHEMATICAL FORMULA (SHA-3 KECCAK SPACE)\")\n", " print(\"=\"*70)\n", "\n", " slope = params['slope']\n", " intercept = params['intercept']\n", " X = collision_point['X']\n", "\n", " print(f\"\"\"\n", " KECCAK DIMENSIONAL SPACE:\n", "\n", " X-Axis: KECCAK(1), KECCAK(2), KECCAK(3)... (normalized)\n", " Y-Axis: 1, 2, 3, 4, 5...\n", " Z-Axis: Collision indicator\n", "\n", " LINEAR FUNCTION:\n", "\n", " Y = {slope:.15f} · X + {intercept:.15f}\n", "\n", " COLLISION POINT (X = Y = Z):\n", "\n", " X = b/(1-m) = {intercept:.6f}/(1-{slope:.6f})\n", " X = Y = Z = {X:.10f}\n", "\n", " SHA-3 KECCAK PROPERTIES:\n", " • Permutation: Keccak-f[1600]\n", " • Rounds: 24\n", " • State: 5×5×64 = 1600 bits\n", " • Rate: 1088 bits\n", " • Capacity: 512 bits\n", " • Output: 256 bits\n", " • Operations: θ, ρ, π, χ, ι per round\n", " \"\"\")\n", "\n", "def show_keccak_comparison():\n", " \"\"\"Show comparison between SHA-256 and SHA-3 Keccak.\"\"\"\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"📊 SHA-256 vs SHA-3 KECCAK-256 COMPARISON\")\n", " print(\"=\"*70)\n", "\n", " print(\"\"\"\n", " ┌─────────────────────┬──────────────────┬──────────────────┐\n", " │ Property │ SHA-256 │ SHA-3 Keccak │\n", " ├─────────────────────┼──────────────────┼──────────────────┤\n", " │ Construction │ Merkle-Damgård │ Sponge │\n", " │ Block size │ 512 bits │ 1088 bits (rate) │\n", " │ Internal state │ 256 bits │ 1600 bits │\n", " │ Rounds │ 64 │ 24 │\n", " │ Output │ 256 bits │ 256 bits │\n", " │ Operations │ Ch, Maj, Σ, σ │ θ, ρ, π, χ, ι │\n", " │ Length extension │ Vulnerable │ Resistant │\n", " │ Capacity │ N/A │ 512 bits │\n", " └─────────────────────┴──────────────────┴──────────────────┘\n", " \"\"\")\n", "\n", " # Show same message, different hashes\n", " print(\" Same messages, different algorithms:\")\n", " for msg in [1, 42, 88514]:\n", " h256 = hashlib.sha256(str(msg).encode()).hexdigest()\n", " h3 = hashlib.sha3_256(str(msg).encode()).hexdigest()\n", " print(f\"\\n Message: {msg}\")\n", " print(f\" SHA-256: {h256}\")\n", " print(f\" Keccak: {h3}\")\n", "\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "# MAIN\n", "# ═══════════════════════════════════════════════════════════════════════════\n", "\n", "def main():\n", " show_banner()\n", " show_theory()\n", "\n", " input(\" Press ENTER to start SHA-3 Keccak analysis...\")\n", "\n", " # Show comparison\n", " show_keccak_comparison()\n", "\n", " # Phase 1\n", " x_scaled, y_axis = build_dimensional_space(N=100000)\n", "\n", " # Phase 2\n", " params = calculate_linear_function(x_scaled, y_axis)\n", "\n", " # Phase 3\n", " collision = calculate_collision_point(params)\n", "\n", " # Phase 4\n", " print(\"\\n Enter search size (100000=fast, 500000=better):\")\n", " try:\n", " N = int(input(\" N [100000]: \") or \"100000\")\n", " except:\n", " N = 100000\n", "\n", " best, elapsed = search_collisions(collision['base_point'], N)\n", "\n", " # Phase 5\n", " show_results(best, collision, params, elapsed)\n", " show_formula(collision, params)\n", "\n", " print(\"\\n\" + \"=\"*70)\n", " print(\"✅ SHA-3 KECCAK-256 ANALYSIS COMPLETED\")\n", " print(\" Author: Kaoru Aguilera Katayama\")\n", " print(\" Method: Dimensional Space Analysis\")\n", " print(\" Algorithm: SHA-3 Keccak (Sponge Construction)\")\n", " print(\"=\"*70)\n", "\n", "if __name__ == \"__main__\":\n", " main()" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "oaELASsbCqId", "outputId": "028e5159-1de8-4118-c288-5bc3fedb18f5" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "\n", "╔═══════════════════════════════════════════════════════════════════════════╗\n", "║ ║\n", "║ ███████╗██╗ ██╗ █████╗ ██████╗ ║\n", "║ ██╔════╝██║ ██║██╔══██╗ ╚════██╗ ║\n", "║ ███████╗███████║███████║█████╗ █████╔╝ ║\n", "║ ╚════██║██╔══██║██╔══██║╚════╝ ╚═══██╗ ║\n", "║ ███████║██║ ██║██║ ██║ ██████╔╝ ║\n", "║ ╚══════╝╚═╝ ╚═╝╚═╝ ╚═╝ ╚═════╝ ║\n", "║ ║\n", "║ ██╗ ██╗███████╗ ██████╗ ██████╗ █████╗ ██╗ ██╗ ║\n", "║ ██║ ██╔╝██╔════╝██╔════╝██╔════╝██╔══██╗██║ ██╔╝ ║\n", "║ █████╔╝ █████╗ ██║ ██║ ███████║█████╔╝ ║\n", "║ ██╔═██╗ ██╔══╝ ██║ ██║ ██╔══██║██╔═██╗ ║\n", "║ ██║ ██╗███████╗╚██████╗╚██████╗██║ ██║██║ ██╗ ║\n", "║ ╚═╝ ╚═╝╚══════╝ ╚═════╝ ╚═════╝╚═╝ ╚═╝╚═╝ ╚═╝ ║\n", "║ ║\n", "║ COLLISION FINDER ║\n", "║ Dimensional Space Method ║\n", "║ ║\n", "║ Author: Kaoru Aguilera Katayama ║\n", "║ ║\n", "╚═══════════════════════════════════════════════════════════════════════════╝\n", " \n", "\n", "═══════════════════════════════════════════════════════════════════════════\n", " DIMENSIONAL SPACE METHOD - THEORY (SHA-3 KECCAK)\n", "═══════════════════════════════════════════════════════════════════════════\n", "\n", "OBSERVATION:\n", " Prime numbers are NOT linear in normal space (1,2,3,4,5...)\n", " BUT they ARE linear in their own space (2,3,5,7,11...)\n", "\n", "EUREKA:\n", " Same applies to SHA-3 Keccak!\n", " In normal space: chaotic\n", " In DIMENSIONAL space: LINEAR\n", "\n", "SHA-3 KECCAK SPECIFICS:\n", " • Sponge construction (absorb + squeeze)\n", " • State: 5×5×64 = 1600-bit permutation\n", " • Capacity: 512 bits, Rate: 1088 bits\n", " • 24 rounds of Keccak-f[1600]\n", " • Output: 256 bits (Keccak-256)\n", "\n", "SPACE DEFINITION:\n", "\n", " 📐 X-Axis: KECCAK(1), KECCAK(2), KECCAK(3)... (hash values)\n", " 📐 Y-Axis: 1, 2, 3, 4, 5... (message indices)\n", " 📐 Z-Axis: Collisions (meeting point)\n", "\n", "METHOD:\n", " 1. Build dimensional space with N points\n", " 2. Calculate linear function: Y = m·X + b\n", " 3. Find collision point: X = Y = Z\n", " 4. Solve: X = b/(1-m)\n", " 5. Derive messages from point\n", " 6. Refine in neighborhood\n", "\n", "NO BRUTE FORCE - Direct algebraic calculation!\n", "\n", "═══════════════════════════════════════════════════════════════════════════\n", " \n", " Press ENTER to start SHA-3 Keccak analysis...\n", "\n", "======================================================================\n", "📊 SHA-256 vs SHA-3 KECCAK-256 COMPARISON\n", "======================================================================\n", "\n", " ┌─────────────────────┬──────────────────┬──────────────────┐\n", " │ Property │ SHA-256 │ SHA-3 Keccak │\n", " ├─────────────────────┼──────────────────┼──────────────────┤\n", " │ Construction │ Merkle-Damgård │ Sponge │\n", " │ Block size │ 512 bits │ 1088 bits (rate) │\n", " │ Internal state │ 256 bits │ 1600 bits │\n", " │ Rounds │ 64 │ 24 │\n", " │ Output │ 256 bits │ 256 bits │\n", " │ Operations │ Ch, Maj, Σ, σ │ θ, ρ, π, χ, ι │\n", " │ Length extension │ Vulnerable │ Resistant │\n", " │ Capacity │ N/A │ 512 bits │\n", " └─────────────────────┴──────────────────┴──────────────────┘\n", " \n", " Same messages, different algorithms:\n", "\n", " Message: 1\n", " SHA-256: 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b\n", " Keccak: 67b176705b46206614219f47a05aee7ae6a3edbe850bbbe214c536b989aea4d2\n", "\n", " Message: 42\n", " SHA-256: 73475cb40a568e8da8a045ced110137e159f890ac4da883b6b17dc651b3a8049\n", " Keccak: 4e169ddf479c8cd9b4c45e0284181730cb42df3a8be892a7f379bd690db1eafa\n", "\n", " Message: 88514\n", " SHA-256: 44f57567ae6c0fd4b6d1d4ebcfa675cd46b3cbab6fa0840e83f249977f78258e\n", " Keccak: ce791b77a7b15e4ce2c2c3b56e8e634f1a7d0195d60e8dc1e9e1fdd1a0541cdc\n", "\n", "======================================================================\n", "⚡ PHASE 1: BUILDING DIMENSIONAL SPACE (SHA-3 KECCAK)\n", "======================================================================\n", " ✅ SHA-3 Keccak-256 verified correctly\n", " SHA3('test') = 36f028580bb02cc8272a9a020f4200e3...\n", "\n", " Generating 100,000 Keccak-256 points...\n", " Processed: 25,000/100,000\n", " Processed: 50,000/100,000\n", " Processed: 75,000/100,000\n", " Processed: 100,000/100,000\n", "\n", " ✓ Keccak space built with 100,000 points\n", "\n", " 📋 Sample SHA-3 Keccak-256 hashes:\n", " KECCAK(1) = 67b176705b46206614219f47a05aee7ae6a3edbe850bbbe214c536b989aea4d2\n", " KECCAK(2) = b1b1bd1ed240b1496c81ccf19ceccf2af6fd24fac10ae42023628abbe2687310\n", " KECCAK(3) = 1bf0b26eb2090599dd68cbb42c86a674cb07ab7adc103ad3ccdf521bb79056b9\n", "\n", "======================================================================\n", "📊 PHASE 2: CALCULATING LINEAR FUNCTION (KECCAK SPACE)\n", "======================================================================\n", "\n", " 📈 LINEAR FUNCTION (Keccak Dimensional Space):\n", "\n", " Y = m · X + b\n", "\n", " m (slope) = -0.001132039019889\n", " b (intercept) = 50057.229444459975639\n", " R² = 0.000001278407856\n", "\n", " Note: Keccak's sponge construction creates a different\n", " dimensional mapping than SHA-256's Merkle-Damgård.\n", " \n", "\n", "======================================================================\n", "🎯 PHASE 3: CALCULATING COLLISION POINT (KECCAK)\n", "======================================================================\n", "\n", " Solving: X = Y = Z in Keccak Dimensional Space\n", "\n", " Given Y = mX + b, if X = Y:\n", " X = mX + b\n", " X(1-m) = b\n", " X = b/(1-m)\n", "\n", " Keccak's 24-round permutation creates unique\n", " dimensional characteristics vs SHA-256.\n", " \n", "\n", " 🔴 KECCAK COLLISION POINT:\n", "\n", " X = Y = Z = 50000.6267839217\n", " Base point = 50000\n", " \n", "\n", " Enter search size (100000=fast, 500000=better):\n", " N [100000]: 5000000\n", "\n", "======================================================================\n", "🔍 PHASE 4: SEARCHING FOR KECCAK COLLISIONS\n", "======================================================================\n", "\n", " 📊 Initial scan to find baseline...\n", " 📌 Baseline: 142/256 bits\n", "\n", " 📊 Method 1: Keccak hash prefix grouping (5,000,000 hashes)...\n", " Processed: 100,000\n", " Processed: 200,000\n", " Processed: 300,000\n", " Processed: 400,000\n", " Processed: 500,000\n", " Processed: 600,000\n", " Processed: 700,000\n", " Processed: 800,000\n", " Processed: 900,000\n", " Processed: 1,000,000\n", " Processed: 1,100,000\n", " Processed: 1,200,000\n", " Processed: 1,300,000\n", " Processed: 1,400,000\n", " Processed: 1,500,000\n", " Processed: 1,600,000\n", " Processed: 1,700,000\n", " Processed: 1,800,000\n", " Processed: 1,900,000\n", " Processed: 2,000,000\n", " Processed: 2,100,000\n", " Processed: 2,200,000\n", " Processed: 2,300,000\n", " Processed: 2,400,000\n", " Processed: 2,500,000\n", " Processed: 2,600,000\n", " Processed: 2,700,000\n", " Processed: 2,800,000\n", " Processed: 2,900,000\n", " Processed: 3,000,000\n", " Processed: 3,100,000\n", " Processed: 3,200,000\n", " Processed: 3,300,000\n", " Processed: 3,400,000\n", " Processed: 3,500,000\n", " Processed: 3,600,000\n", " Processed: 3,700,000\n", " Processed: 3,800,000\n", " Processed: 3,900,000\n", " Processed: 4,000,000\n", " Processed: 4,100,000\n", " Processed: 4,200,000\n", " Processed: 4,300,000\n", " Processed: 4,400,000\n", " Processed: 4,500,000\n", " Processed: 4,600,000\n", " Processed: 4,700,000\n", " Processed: 4,800,000\n", " Processed: 4,900,000\n", " Processed: 5,000,000\n", " ✨ NEW RECORD: 147/256 bits (57.42%)\n", " M1=66, M2=1013874\n", " K1=b2ca9f9494822877f5fa4617...\n", " K2=b2ca9f99941d54d95de31e43...\n", " ✨ NEW RECORD: 148/256 bits (57.81%)\n", " M1=796, M2=4738177\n", " K1=5eeb5bab44bf2404aa804bc1...\n", " K2=5eeb5bafe6d69bd2b04076e0...\n", " ✨ NEW RECORD: 149/256 bits (58.20%)\n", " M1=899, M2=4347716\n", " K1=cee01f57d73bb038edda7dd9...\n", " K2=cee01f5ded11e74dbc8dbcc4...\n", " ✨ NEW RECORD: 151/256 bits (58.98%)\n", " M1=1164, M2=520882\n", " K1=417637d897360b46b8ade436...\n", " K2=417637d38677179d2911643d...\n", " ✨ NEW RECORD: 153/256 bits (59.77%)\n", " M1=1940, M2=4117649\n", " K1=02fcecff36dd9894334af58e...\n", " K2=02fcecf64fdd2268fa2fd0d8...\n", " ✨ NEW RECORD: 156/256 bits (60.94%)\n", " M1=2592, M2=1048339\n", " K1=17962c2d0ac8a6b462f3a1e4...\n", " K2=17962c27e55071f6455173c0...\n", " ✨ NEW RECORD: 157/256 bits (61.33%)\n", " M1=3190, M2=4871771\n", " K1=c077c00f091eafd8bbf9045b...\n", " K2=c077c00f8d36f945b4e3c3ff...\n", " ✨ NEW RECORD: 160/256 bits (62.50%)\n", " M1=7368, M2=8805\n", " K1=900176cf04e4aa026215ae3d...\n", " K2=900176cb4669a051acdca3fa...\n", " ✨ NEW RECORD: 163/256 bits (63.67%)\n", " M1=10985, M2=3257416\n", " K1=f433364c46b548ff086da1ce...\n", " K2=f4333648d318cc7ad8e7cac6...\n", " ✨ NEW RECORD: 166/256 bits (64.84%)\n", " M1=107610, M2=660600\n", " K1=20a0e59b114621969c973c27...\n", " K2=20a0e59921db897193177caf...\n", " ✨ NEW RECORD: 170/256 bits (66.41%)\n", " M1=234444, M2=4645578\n", " K1=92a76f8b48888c338b8d8d7c...\n", " K2=92a76f86409998148d09cc6a...\n", " ✨ NEW RECORD: 175/256 bits (68.36%)\n", " M1=1848363, M2=4467547\n", " K1=c1cc95ca4f15bcda0b166900...\n", " K2=c1cc95cb5edab9dc3e4d0b72...\n", " ✨ NEW RECORD: 176/256 bits (68.75%)\n", " M1=2343047, M2=3898694\n", " K1=f091f0fd7c502f5af6cf074c...\n", " K2=f091f2d504e01e7af35a23dc...\n", " ✨ NEW RECORD: 177/256 bits (69.14%)\n", " M1=4113087, M2=4268816\n", " K1=ebc2546e34b84f52d4f43dba...\n", " K2=ebc25064f5b8639ef6f0715b...\n", " ✨ NEW RECORD: 180/256 bits (70.31%)\n", " M1=3399272, M2=4622582\n", " K1=7f4c10c4f136229ef07f72e3...\n", " K2=7f4c11f4e0863c19d8ad7aa9...\n" ] } ] } ] }