Wonderland CTF EVMVM Solution Address Bruteforcer

main.rs

use alloy_primitives::{Address, Keccak256, U256, keccak256, uint};
use k256::elliptic_curve::BatchNormalize;
use k256::elliptic_curve::sec1::ToEncodedPoint;
use k256::{AffinePoint, ProjectivePoint};
use rayon::prelude::*;
use std::time::Instant;

const BATCH: usize = 128;

/// Compute `len_slot - data_slot` (saturating) for a given address.
fn slots_diff(addr: &Address) -> U256 {
    let base = U256::from_be_slice(
        keccak256(
            [
                &[0u8; 12],
                addr.as_slice(),
                &uint!(3U256).to_be_bytes::<32>(),
            ]
            .concat(),
        )
        .as_slice(),
    );
    let len_slot = base + uint!(2U256);
    let data_slot = U256::from_be_slice(keccak256(&len_slot.to_be_bytes::<32>()).as_slice());
    len_slot.checked_sub(data_slot).unwrap_or(U256::MAX)
}

fn address_from_affine(p: &AffinePoint) -> Address {
    let enc = p.to_encoded_point(false);
    Address::from_raw_public_key(&enc.as_bytes()[1..])
}

fn main() {
    let num_threads: u64 = std::thread::available_parallelism()
        .map(|n| n.get() as u64)
        .unwrap_or(8);

    let pow = 224;
    let threshold = U256::from(1u64) << pow;
    let g_affine = ProjectivePoint::GENERATOR.to_affine();

    eprintln!(
        "Starting bruteforce with {} threads (batch {})",
        num_threads, BATCH
    );
    eprintln!("Condition: len_slot - data_slot < 2^{pow}");

    (0..num_threads).into_par_iter().for_each(|thread_id| {
        let seed: u64 = (thread_id + 1) << 52;
        let seed_bytes = U256::from(seed).to_be_bytes::<32>();
        let sk = k256::SecretKey::from_slice(&seed_bytes).expect("valid seed key");

        let mut cur = ProjectivePoint::GENERATOR * *sk.to_nonzero_scalar();
        let mut priv_key = U256::from(seed);
        let mut total: u64 = 0;
        let report_every: u64 = 10_000_000;
        let mut last_report = Instant::now();
        let mut last_total: u64 = 0;

        let mut projs = [ProjectivePoint::IDENTITY; BATCH];

        loop {
            // Fill batch: cheap projective mixed-additions, no inversions.
            projs[0] = cur;
            for i in 1..BATCH {
                projs[i] = projs[i - 1] + g_affine;
            }

            // Single batch inversion via Montgomery's trick (library-provided).
            let affines: [AffinePoint; BATCH] = <ProjectivePoint as BatchNormalize<
                [ProjectivePoint; BATCH],
            >>::batch_normalize(&projs);

            // Check every address in the batch.
            for (i, aff) in affines.iter().enumerate() {
                let addr = address_from_affine(aff);
                let diff = slots_diff(&addr);
                if diff < threshold {
                    let key = priv_key + U256::from(i);
                    println!("Private Key: 0x{:064x}", key);
                    println!("Thread:  {}", thread_id);
                    println!("Address: {}", addr);
                    println!("diff:    0x{:064x}", diff);
                    std::process::exit(0);
                }
            }

            // Advance to next batch.
            cur = projs[BATCH - 1] + g_affine;
            priv_key += U256::from(BATCH as u64);
            total += BATCH as u64;

            if total - last_total >= report_every {
                let now = Instant::now();
                let elapsed = now.duration_since(last_report).as_secs_f64();
                let rate = (total - last_total) as f64 / elapsed;
                eprintln!(
                    "[thread {}] checked {} keys ({:.0} addr/s)",
                    thread_id, total, rate
                );
                last_report = now;
                last_total = total;
            }
        }
    });
}