Kangaroo

GPU-accelerated Pollard's Kangaroo algorithm for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) on secp256k1.

Features

• Cross-platform GPU support via wgpu (Vulkan/Metal/DX12)
  • AMD GPUs (via Vulkan/RADV)
  • NVIDIA GPUs (via Vulkan)
  • Intel GPUs (via Vulkan)
  • Apple Silicon (via Metal)
• Pure Rust implementation with WGSL compute shaders
• Distinguished Points optimization for efficient collision detection
• CPU fallback for testing and comparison

Why This Project?

Most existing Kangaroo implementations (JeanLucPons/Kangaroo, RCKangaroo, etc.) only support NVIDIA GPUs via CUDA. This implementation uses WebGPU/wgpu which provides cross-platform GPU compute through Vulkan, Metal, and DX12.

Installation

cargo install kangaroo

Or build from source:

git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release

Usage

kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>

Required Arguments

Optional Arguments

Example

Find a private key in a 40-bit range:

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40

How It Works

The Pollard's Kangaroo algorithm solves the discrete logarithm problem in O(√n) time where n is the search range. It works by:

1. Tame kangaroos start from a known point and make random jumps
2. Wild kangaroos start from the target public key and make the same type of jumps
3. When a wild and tame kangaroo land on the same point (collision), we can compute the private key

Distinguished Points (DP) optimization: Instead of storing all visited points, we only store points whose x-coordinate has a specific number of leading zero bits. This dramatically reduces memory usage while still allowing collision detection.

Performance

Expected operations: ~2^(range_bits/2)

*Times vary significantly based on GPU performance

Use Cases

NOT useful for:

• Full 256-bit key search (mathematically impossible)
• BIP39 passphrase brute-force (use dictionary attack instead)
• Puzzles without partial key information

Library Usage

use kangaroo::{KangarooSolver, GpuContext, parse_pubkey, parse_hex_u256, verify_key};

fn main() -> anyhow::Result<()> {
    let pubkey = parse_pubkey("03...")?;
    let start = parse_hex_u256("8000000000")?;

    let ctx = pollster::block_on(GpuContext::new(0))?;
    let mut solver = KangarooSolver::new(
        ctx,
        pubkey.clone(),
        start,
        40,  // range_bits
        12,  // dp_bits
        1024, // num_kangaroos
    )?;

    loop {
        if let Some(key) = solver.step()? {
            if verify_key(&key, &pubkey) {
                println!("Found: {}", hex::encode(&key));
                break;
            }
        }
    }

    Ok(())
}

Architecture

src/
├── main.rs              # CLI entry point
├── lib.rs               # Library entry point
├── cli.rs               # CLI utilities
├── cpu/
│   ├── solver.rs        # GPU solver coordination
│   ├── cpu_solver.rs    # Pure CPU solver
│   └── dp_table.rs      # DP collision detection
├── crypto/
│   └── mod.rs           # k256/secp256k1 wrappers
├── gpu/
│   ├── mod.rs           # GPU module
│   ├── pipeline.rs      # Compute pipeline
│   └── buffers.rs       # GPU buffer management
├── gpu_crypto/
│   ├── context.rs       # GPU context abstraction
│   └── shaders/         # WGSL shader sources
│       ├── field.wgsl           # secp256k1 field arithmetic
│       └── curve_jacobian.wgsl  # Jacobian point operations
└── shaders/
    └── kangaroo_jacobian.wgsl  # Main Kangaroo compute shader

Requirements

• Rust 1.70+
• Vulkan-capable GPU (AMD, NVIDIA, Intel) or Metal (macOS)
• GPU drivers installed

License

MIT License - see LICENSE for details.

Related Projects

• JeanLucPons/Kangaroo - CUDA implementation (NVIDIA only)
• RCKangaroo - CUDA implementation (NVIDIA only)