Breaking BIP-39: A Deep Dive

I just wrapped up some intense projects aiming at cracking BIP-39, specifically looking at recovering beyond just 4 words. This is something that no Bitcoin recovery wallet provider seems to tackle these days because of the steep costs involved. I’ll lay out the details in sections, provide proof of concept, and share my tech insights. My work is all about using OpenCL for GPU parallelization while Python acts as the main controller. Currently, there are some brute-force tools like Hashcat that utilize wNAF-4 bits for calculating public keys (G × k) on the secp256k1 elliptic curve which is widely adopted in Bitcoin and ECDSA. Previously, we employed a 4-bit Non-Adjacent Form (wNAF) for point multiplication in our tools, but we've recently made a breakthrough with a new speedier method based on the traditional Comb technique. This new approach is designed for processing many random scalars at high rates, which can't be tackled with algorithms like Kangaroo or Pollard Rho. Method 1 Comb Technique (16×16 window) Approach: Standard Comb method using COMB_W = 16 and COMB_D = 16. Precomputed table size: 16 columns × 65,536 entries = 1,048,576 points (around 16-20 MB depending on the format). Algorithm features: - Exactly 16 doublings (fixed). - Up to 16 point additions (averaging around 8 for random scalars). - All additions are affine (z = 1), which is way cheaper than general Jacobian additions. - Highly regular control flow, making it perfect for GPU warp performance with minimal divergence. - Typical throughput on modern GPUs is incredibly high, often 5-10 times faster than wNAF when dealing with large batches.

PBKDF2-HMAC-SHA512 Without a doubt, PBKDF is the biggest bottleneck for breaking BIP-39, limiting high-end GPUs to 3-4 million processes per second. Fortunately, we managed to assemble a highly parallelizable kernel with few branches to accelerate cryptography and make the code more efficient. First HMAC computed outside the loopHandles the longer initial message ("mnemonic" salt + passphrase) separately, requiring two sha512_process calls for the inner hashTight main loopFor the remaining 2047 iterations, the message is only the previous U (64 bytes < block size), requiring just one sha512_process per inner HMAC + one for outer. Total per iteration: 2 SHA-512 compressions + minimal copies/XORs.Vectorized copies via COPY_EIGHTOpenCL compiler typically converts these to native vstore8/vload8 instructions.Efficient register usageEverything kept in __private ulong[8] arrays with no unnecessary spilling.Zero branching in the hot loop (except loop counter) — ideal for GPU execution.100% unrolled message expansionAll W₁₆ through W₇₉ are computed sequentially with no loops. Eliminates loop overhead and enables perfect instruction scheduling by the compiler. Huge throughput gain on GPUs.Carry-chain optimization for Maj function reusing A&B and B&C to reduce calculations within SHA compression.Saves one AND per round (80 ANDs total per compression) by passing bc_prev and chaining ab_current. Classic SHA-2 trick used in high-performance implementations (e.g., hashcat, ASICs)..bitselect for Ch functionUses the fastest native instruction on AMD/NVIDIA GPUs for Ch(x,y,z) = (x&y) ^ (~x&z).Optimized rotates and sigmas.Leverages OpenCL's built-in rotate() (hardware barrel shifter) and standard shift/rotate/XOR patterns for σ₀/σ₁.Fully unrolled 80 rounds.No loop in the main compression → maximum ILP (instruction-level parallelism). Each round is minimal (~12–15 effective instructions)..Dedicated sha512_hash_two_blocks_message function.Perfectly suited for the initial PBKDF2 message (mnemonic + "mnemonic" > 112 bytes), avoiding conditional logic inside the core compression.Relatively low register pressure Temporary W values are computed just-in-time and many are eliminated by dead-code elimination.Code I hope you like it, I'm open to improvement suggestions. Thank you.

Well, before I get enthralled with your computations and possibly test them, could you share the results you obtained for recovering let’s say 5 or 6 missing words from 12 words BIP39 compliant phrase, specifically, how long it would take using the methods you proposed?

It may be obvious to you, but how can we compile and run the code on our own device to attempt recovery/brute-force with our own BIP 39 words?

I want to suggest to add to topic's title that this toolset is intended to cracking a limited number of missing mnemonic recovery words. I didn't look so far thoroughly at the code on Github. Should everything necessary be published openly on Github, kudos for an insight to your optimizations (if they work out). I would love to see some valid comparison data, maybe not only for the beefiest GPUs available. Not sure if the GPU code compiles properly for other GPU than the heaviest gear available. Not everyone has a 5090... By comparison data I mean, how long does it take to crack 3, 4 or 5 (seems to be the upper limit for now for this tool?) words? Can the missing words be at any position? At first look I couldn't see any details on this (I might missed it). Some thorough testing is indeed required. I would prefer a well documented build toolchain over some executables which I can't trust as long as they aren't available with reproducible builds.

If you want to run the project on your own machines, I have multiple versions accumulated over months of research — new optimizations pop up almost daily. https://github.com/ipsbruno3?tab=repositories However, it still lacks the newest update for full 64-bit secp256k1 processing, so right now you're limited to around 1.2 million seeds per second on typical hardware. Results for up to 5 missing words are very promising — especially with serious compute power. Recovering the last 5 words is already feasible for under $50,000, something most of the community still considers impossible. 6 words is still far off, but following Moore's Law + our shift from OpenCL to dedicated ASIC hardware, I believe we'll see major breakthroughs in the coming years. We already have minimal working FPGA code on GitHub and are actively developing it to focus on dedicated ASIC chips, their advantage here is that their power consumption is ridiculously low for mnemonic retrieval; the project lacks investment but continues to be coded. Just for curiosity and comparison, here's a rough table of required investment (based on real benchmarks with RTX 5090-class GPUs): No magic here: it's still pure brute force and takes time, but my code has made 5-word searches practical (and 6 words possible at very high cost). Rough estimates (assuming an optimized rig with 8× RTX 5090 or equivalent): 1 missing word → < 1 second2 missing words → < 1 second → From here, I recommend using libraries like coincurve, btcrecover, seedcat, John Cantrell's bip-39-solver, or even hashcat — the search space is small enough. For speeds that beat the tools above, my code starts to shine. Quick comparison: Cantrell's bip-39-solver → ~500k seeds/s on a good GPUseedcat / standard hashcat → max ~1M seeds/s (without my specific optimizations) I've already submitted improvement suggestions to several of those repos: https://github.com/hashcat/hashcat/issues/4613 (example) Being brutally honest with current benchmarks: 3 missing words → < 1 hour 4 full words missing (any position in the wordlist) → ~12 days Last 5 words missing → ~550 days (~$50,000 in hardware) 5 full words missing (any position) → ~6 years (~over $192,000 hardware) Electrum Solver Another important thing I forgot to mention: these benchmarks are for standard BIP-39. For BIP-39 resolution in Electrum, we developed a new method. I used some checksum verifications that allowed us to reach over 50 million seeds per second on a 5090 GPU. I will soon post updates on that old Electrum recovery project. The results for Electrum run about 50x faster. Do you want me to post snippets of the Electrum code here? The big trick is to exclude invalid checksums before the final pbkdf validation. Electrum ends up having a space 128/4096 to 1/4096 smaller than traditional bip-39 because of this. As I said: no magic involved. But this is the best achievable today. And when you have placeholders (e.g., you know one word has 8 characters, or belongs to a smaller subset), we can shrink the search space dramatically — sometimes 20× or more (2048 → ~88 effective words). That not only slashes costs but paves a (long and hard) path to make 6 out of 12 words computationally feasible in the next decade. I tested the mnemonc-recover project on 2080 TI cards, all 30XX, 40XX and 50XX series, and the Blackwell RTX 6000 PRO series. I couldn't test it on AMD, but I removed some intrinsic code that was only specific to NVIDIA to try to make it portable to AMD as well – further testing is needed in this case. Integrated graphics cards like Intel also worked well (but it's extremely slow and not recommended). Feel free to clone, test, optimize — contributions are welcome!

What are you talking about? Yes, solving ECDLP by brute-forcing sequential keys is totally stupid, however, those "billions/s" that you are referring to are almost in the same speed category when using Kangaroo, because the same principle is used (doing many additions all at once), which can be batched just the same.

Yes, exactly! You are absolutely correct.. This project works with random points on the curve, while the Kangaroo method does not allow this. If it's just ECDSA, the Kangaroo method is still the most suitable, while point_add on the curve is the most suitable if you only need to do ECDSA + SHA + RIPEMD. While this project is designed and indicated exclusively for BIP-39, this project uses `point_mul` at distinct points on the curve, meaning it doesn't have the same limitations as previous methods, although it is obviously slower due to requiring more arithmetic operations.

One small practical thing I'd add for anyone running this on consumer Windows GPUs: Be advised that WDDM and TDR weirdness can silently ruin your day. If you can, run the heavy kernels in a setup where the driver isn't babysitting the desktop, and always sanity-check your throughput with fixed test vectors so you don't benchmark a bug at 200 MH/s and celebrate it, lol.

Unless it's intended to exclude Electrum 2FA and Electrum 2FA SegWit version numbers, namely 0x101 and 0x102, I suggest to include it to the valid version numbers above. It's MultiSig but if the user know at least one of its used address (used to spend), the tool can check if the candidate seed can derive one of the pubKey in its redeem script. Better if you can include a way to be able to indicate the electrum seed type. So in case where users remember their Electrum wallet type or any of their (used) address, minimizing it to a single version number can slightly optimize the search space. But given the readme "Pre‑Filter" notes in your other repo for electrum seed, this may be in your roadmap already?

I have some news regarding pbkdf processing with good results (some hard-coded again). Recently, during some tests, I leveraged a very interesting (and poorly documented) trick: reusing SCHEDULE values from SHA-512 by exploiting the fixed output of the HMAC within the main loop (e.g., the 2048 iterations in PBKDF2-SHA512). In SHA-512, the message schedule expands the initial 16 words (0-15) into 80 words. In PBKDF2-HMAC, words 8-15 are always fixed due to the HMAC padding (0x80 followed by zeros and the length of 1536 bits). We can precompute these in a `__constant` array called `PBKDF_TRIMN` and create a custom `sha512_process_inner` function that only processes the first 8 dynamic words (0-7), substituting words 8-15 with the fixed array. Then, we compute W[16+] manually using fewer operations. This is the core "magic": By reducing the processing from 16 words to just 8, we eliminate more than 50% of the schedule computations. The fixed part (`PBKDF_TRIMN`) shifts calculations to compile-time, significantly reducing runtime instructions. For instance, operations like L0/L1 on constants are evaluated by the compiler, not at runtime. Feature Impact: On its own, this provides a +25-30% speedup in benchmarks. The consistent use of constant values in SHA-512 also opens opportunities for mathematically precomputing even larger constant segments (I'm still exploring this—keep an eye on my GitHub). Code Example: https://github.com/ipsbruno3/pbkdf_optimizations/tree/main The optimization won't materialize if you don't use `__constant` directly in the code. If you simply use zeros in a regular array, the compiler won't recognize the constancy and will treat it as a normal variable, keeping runtime performance nearly identical. That's why I hard-coded `PBKDF_TRIMN` directly and created a dedicated function for the PBKDF loop. This minimizes branches (no extra ifs or ternaries) and tailors the function to that specific case. Another key observation: MAJ can be optimized by reusing values (e.g., b&c). On devices without optimized bitselect, it's better to reuse these for efficiency instead of the standard: Use this instead: If bitselect isn't supported, reuse values across rounds like this for example: This saves an "&" operation per round by reusing the previous _ab as bc_prev: ____________________ How to reduce the pressure on registers by reusing INNER[16] instead of INNER[32] OUTER[32] I managed to significantly reduce the use of registers in PBKDF. I used an elegant trick with masks, reusing the IPAD value for OPAD with a value of 0x6A6A6A6A6A6A6A6AUL. Another elegant trick (but it might break the code's portability) is that some brute-force operations are fixed, for example, in BIP-39 you usually only search by "mnemonic" salt. So the concept here was to allocate this value to __constant memory and reduce the use of registers to the final part of inner_pad. Lastly, and no less importantly, sha512_process_inner is a conceptual version of sha_process. The difference is that it was designed to work inside the pbkdf iteration loop and only uses the first 8 ulongs of the array; the remaining 8 are constant values, as I mentioned above. Because of this, I needed to rewrite sha512_process_constant into a version that would accept "message" as a __constant value. Tests were performed and it worked well for my use case (NVIDIA 20/30/40/50 cards work fine). It's highly conceptual, but it works and probably with some #defines or some code to generate the constants in Python (or on your host) before compilation, it could become more portable for use in crackers like Hashcat or John the Ripper. Benchmarks The gains, including all my optimizations, reached 2,300,000 complete BIP-39 mnemonic seeds verified per second on RTX 5090. This includes the entire generation of the mnemonic phrase concatenated with spaces, all the overhead of the host calling the kernel, and all the secp256k1 calculations. For comparison, John Cantrell's code could verify around ~143,000 mnemonics per second on a 2080Ti; on the same video card, I managed to stabilize around 490,000 seeds per second, a jump of over 300%. _____ I also recommend you take a look at my repo for sec256k1 with the comb method; it's faster than Hashcat's wnafs and also faster than the traditional sec256k1 library that JTR uses today: https://github.com/ipsbruno3/fast_secp256k1_opencl Here we reached a peak of 100 million random keys generated per second on the curve (using point_mul), while point_add, requiring less processing, can reach 3 billion per second (RTX 5090). _____ Obviously this isn't a plugin ("user-friendly"); recomends perform proper testing with my recommendations to avoid breaking your hash in the middle. I believe this is the current state of the art; hashcat and jnr, despite being efficient for SHA in general, still have highly inefficient kernels due to poor optimization of the secp256k1 curve. The issue of reusing constant values ​​hasn't been implemented either (although there's a JTR issue addressing it). In future, we will make the project more user-friendly, so that ordinary users can use it. Unfortunately, everything is still very conceptual and scientific. You're right, in my "mnemonic-recover" repository I only included SegWit type ELECTRUM in the scan, maybe a note there would be good, but this could be adjusted to further reduce the search area. __

The SCHEDULE value reuse trick is clever, since most people just throw PBKDF2 at the GPU and call it a day without thinking about what's actually happening inside those 2048 iterations. Precomputing the fixed HMAC padding into `__constant` memory and cutting the word processing in half is exactly the kind of thing that separates "I downloaded hashcat" from "I actually understand what hashcat is doing." 2.3 million seeds/sec on a 5090 is genuinely impressive. For context, that's still centuries for a full 12-word brute force  , but for partial seed recovery where you know most words or have a limited search space? That's getting into "actually practical" territory. The jump over Cantrell's ~143k mnemonic/sec on a 2080Ti shows how much headroom was left on the table. The secp256k1 OpenCL repo is bookmarked. I've been using a cobbled-together setup with libsecp256k1 bindings that works but definitely isn't optimized for batch operations. If your point_add is really hitting 3 billion/sec on consumer hardware that's worth investigating.

Does this accelerate the recovery of master keys of encrypted private keys, when the wallet hash is known, and brute-forcing different passwords (PBKDF + decrypt padding check) is the only feasible way?

Within the benchmark test you will see how many iterations to adjust; this was necessary to avoid the kernel call head. Furthermore, `point_add` is a relatively simple operation; if you know some intrinsic tricks of the processor or GPU you can improve it even further. 3 billion per second is achievable up to this point. For 5 missing words, we’re already doing well — it’s slow, but feasible over the course of months. If you want to extrapolate to 6 missing words, you’ll need additional hints. For example, suppose the unknowns are the last words, and you also know that the 6th word has 8 characters. That alone reduces the search space in two ways: You cut the final checksum constraint by 1/16 And you restrict the candidate set because only 88 words in the BIP-39 wordlist have 8 characters, which is about a 23.27× reduction So this single hint reduces the total search space by roughly 23×. Without it, cracking 6 missing words is basically not realistic; with it, it starts becoming humanly achievable. That said, the incentive would have to be huge — likely more than 100 RTX 5090-class GPUs running for ~25 years. https://www.wolframalpha.com/input?i=%282048%5E6%2F16%2F23.27%29%2F%2884600*2300000*100*365%29 A GPU at this level costs around $2,000 each, so you’re looking at roughly $200,000 in hardware, plus electricity — which becomes extremely expensive as the timeline stretches out. For perspective, 27 years at this scale is about 13.6 GWh of energy, which could easily put the total cost in the ballpark of $3,000,000. So what’s my point? We’re getting to a stage where this is becoming “practical”. The real question is: are there people who have lost more than $3 million in BTC? ___ As we can see, electricity is still the biggest bottleneck in terms of costs. That's why we're thinking about prototyping FPGAs, since their energy consumption is 1% of what a GPU would, but ASICs are very expensive to develop and I don't have the money, only the code.