Kangaroo

Algorithme de Kangourou de Pollard accéléré par GPU pour résoudre le problème du logarithme discret sur courbe elliptique (ECDLP) sur secp256k1.

Fonctionnalités

• 🖥️ GPU multiplateforme — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) via wgpu
• 🦀 Rust pur + WGSL — pas de dépendance CUDA, shaders de calcul compilés à l'exécution
• ⚡ Points distingués — détection efficace des collisions avec bits DP auto-ajustés
• 🔄 Carte de négation — accélération d'environ 1,29× via des marches orientées par parité Y avec garde-fous anti-cycle
• 🦘 Kangourous multi-ensembles — troupeaux tame, wild1, wild2 pour une probabilité de collision plus élevée
• 🎯 Contraintes modulaires — si k ≡ R (mod M), réduire l'espace de recherche d'un facteur M
• ⚙️ Auto-étalonnage — ordonnancement GPU et taille du groupe de travail ajustés au démarrage
• 📊 Benchmarks intégrés — --benchmark pour tester le matériel, --save-benchmarks pour enregistrer les résultats
• 📦 Fournisseurs de données — sources d'énigmes enfichables (intégration boha pour les puzzles Bitcoin)
• 💻 Recours CPU — solveur CPU pur pour les tests et la comparaison

Pourquoi ce projet ?

La plupart des implémentations existantes de Kangourou (JeanLucPons/Kangaroo, RCKangaroo, etc.) ne supportent que les GPU NVIDIA via CUDA. Cette implémentation utilise WebGPU/wgpu qui permet le calcul GPU multiplateforme via Vulkan, Metal et DX12.

Installation

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

Depuis les sources

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

Avec le fournisseur boha

cargo build --release --features boha

Utilisation

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

Arguments

Soit --target soit --pubkey est requis.

Exemples

Utilisation d'un fournisseur de données (boha) :

# Résoudre une énigme avec les données boha (auto : pubkey, start, range)
kangaroo --target boha:b1000/66

# Surcharger la plage (rechercher un sous-ensemble plus petit)
kangaroo --target boha:b1000/66 --range 60

# Lister les énigmes disponibles
kangaroo --list-providers

Paramètres manuels :

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

Avec contrainte modulaire (k ≡ 37 mod 60) :

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40 \
    --mod-step 3c \
    --mod-start 25

Cela réduit l'espace de recherche d'environ 60×. Utile lorsque la structure partielle de la clé est connue (par exemple, clé générée avec un motif de pas prévisible).

Comment ça fonctionne

L'algorithme de Kangourou de Pollard résout le problème du logarithme discret en temps O(√n) où n est la plage de recherche. Il fonctionne ainsi :

1. Les kangourous apprivoisés (Tame) partent d'un point connu et effectuent des sauts aléatoires.
2. Les kangourous sauvages (Wild) partent de la clé publique cible et effectuent le même type de sauts.
3. Lorsqu'un kangourou sauvage et un apprivoisé atterrissent sur le même point (collision), on peut calculer la clé privée.

Optimisation des points distingués (DP) : au lieu de stocker tous les points visités, on ne stocke que ceux dont la coordonnée x possède un nombre spécifique de bits de tête nuls. Cela réduit considérablement l'utilisation mémoire tout en permettant la détection des collisions.

Performances

Opérations attendues : ~2^(range_bits/2)

Exécutez kangaroo --benchmark pour tester votre matériel sans toucher aux fichiers. Utilisez kangaroo --benchmark --save-benchmarks pour mettre à jour BENCHMARKS.md.

Cas d'utilisation

PAS utile pour :

• Recherche complète sur 256 bits (mathématiquement impossible)
• Force brute de passephrase BIP39 (utiliser plutôt une attaque par dictionnaire)
• Énigmes sans information partielle sur la clé

Utilisation en bibliothèque

use kangaroo::{KangarooSolver, GpuContext, GpuBackend, 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, GpuBackend::Auto))?;
    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(())
}

Fournisseurs de données

Kangaroo prend en charge des fournisseurs de données externes pour les sources d'énigmes. Les fournisseurs fournissent la clé publique, la plage de clés et d'autres métadonnées d'énigme.

boha (fonctionnalité optionnelle)

boha fournit des données d'énigmes cryptographiques, y compris les transactions de l'énigme Bitcoin (b1000).

Construire avec le support boha :

cargo build --release --features boha

Utilisation :

# Résoudre une énigme spécifique
kangaroo --target boha:b1000/66

# Lister les énigmes résolubles (non résolues avec clé publique connue)
kangaroo --list-providers

Le fournisseur valide les surcharges de plage – vous ne pouvez pas chercher en dehors de la plage de clés de l'énigme.

Architecture

src/
├── main.rs              # Point d'entrée CLI
├── lib.rs               # Point d'entrée de la bibliothèque + Args + run()
├── solver.rs            # Coordination du solveur GPU
├── cli.rs               # Utilitaires CLI (tracing, barre de progression)
├── benchmark.rs         # Suite de benchmarks intégrée
├── modular.rs           # Transformation de contrainte modulaire
├── math.rs              # Arithmétique 256 bits, génération de masque DP
├── convert.rs           # Conversions entre limbs/octets pour GPU↔CPU
├── provider/
│   ├── mod.rs           # Interface du système de fournisseurs
│   └── boha.rs          # Fournisseur boha (conditionnel à la fonctionnalité)
├── cpu/
│   ├── cpu_solver.rs    # Solveur CPU pur (test/comparaison)
│   ├── dp_table.rs      # Détection de collision par points distingués
│   └── init.rs          # Initialisation des kangourous + tables de sauts
├── crypto/
│   └── mod.rs           # Wrappers k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # Configuration du pipeline de calcul
│   └── buffers.rs       # Gestion des buffers GPU
├── gpu_crypto/
│   ├── context.rs       # Contexte GPU + sélection du backend
│   └── shaders/         # Bibliothèque de shaders WGSL
│       ├── field.wgsl   # Arithmétique de corps secp256k1
│       └── curve.wgsl   # Opérations sur points jacobiens
└── shaders/
    └── kangaroo_affine.wgsl  # Shader de calcul principal Kangourou

Prérequis

• Rust 1.70+
• GPU compatible Vulkan (AMD, NVIDIA, Intel) ou Metal (macOS)
• Sous Linux avec AMD RADV, Mesa 25.x ou plus récent est nécessaire (les versions plus anciennes de Mesa peuvent planter à cause de l'indexation dynamique WGSL dans les boucles de shaders)
• Pilotes GPU installés

Licence

Licence MIT – voir LICENSE pour les détails.

Projets connexes

• JeanLucPons/Kangaroo – Implémentation CUDA (NVIDIA uniquement)
• RCKangaroo – Implémentation CUDA (NVIDIA uniquement)
• boha – Bibliothèque de données d'énigmes et de primes cryptographiques