Rainbow tables
A rainbow table is a large, prebuilt lookup file that can be used to reverse cryptographic password hashes. Instead of calculating every password guess in real-time, threat actors use these prebuilt databases to match stolen, unsalted hashes back to their original plaintext passwords. Modern password hashes are typically salted with a unique random value, meaning attackers can’t rely on a single precomputed table and must crack each hash individually.
In 2021, Mandiant published a complete NetNTLMv1 DES rainbow table set for this fixed-challenge scenario: 4,096 files of roughly 2 GB each, covering the full 2^56 keyspace (about 9TB total).
Given a captured NetNTLMv1 authentication response, threat actors can use rainbow tables to recover the DES keys derived from the victim’s NT hash. Those recovered keys can then be used to reconstruct the NT hash itself. The real challenge lies in performing the lookup efficiently enough to make the attack practical. For cybercriminals, time is money. Attacks must deliver adequate return on investment to make the effort worth it.
Industry-standard tooling like Crackalack and classic rcrack largely assumes that graphic processing units (GPUs) are mandatory for this task. That’s a sensible design choice, but in large-scale testing operations, GPU time is often the most valuable resource available. When a NetNTLMv1 lookup monopolizes those resources for hours, it creates a bottleneck for other malicious workloads that genuinely require GPU acceleration.
The GPU tax
So, does a rainbow-table lookup actually need a GPU to complete its task?
The conventional wisdom says yes. Rainbow chains are the precomputed sequence of alternating cryptographic hash and reduction functions used inside a rainbow table to reverse password hashes. Following a rainbow chain for a single endpoint requires a few hundred thousand DES operations. Across roughly 880,000 endpoints per ciphertext, a lookup precompute involves approximately 388 billion DES operations. At first glance, that sounds like a defensible workload for a GPU.
The reality is more nuanced because the lookup process is not purely computational. The search phase also requires streaming multi-gigabyte rainbow tables from disk. Once datasets reach that scale, sequential I/O becomes a significant component of runtime, even with high-speed NVMe storage. While the GPUs are performing DES operations, they are also waiting for data to arrive.
Modern multi-core CPUs are more than capable of handling the cryptographic workload. As a result, the limiting factor is not always the rate at which DES operations can be executed, but how efficiently the system can move data between storage, memory, and compute resources.
This changes the economics of the attack. Dedicating GPUs to rainbow table lookups means consuming the most valuable resource in a cracking rig for a workload that is only partly GPU-friendly. Every hour spent regenerating rainbow chains is an hour that those same GPUs are unavailable for tasks that benefit far more from massive parallelism, such as password cracking, WPA handshake attacks, or bcrypt workloads.
Investigating this in our secure testing environment, a full NetNTLMv1 downgrade lookup could monopolize GPUs for up to eight hours. The GPUs remained occupied for the entire run, even though much of the work involved streaming data from disk and performing operations that modern CPUs handle efficiently.
That raises an obvious question: if significant portions of the workflow are I/O-bound or CPU-friendly, does the lookup need to run on a GPU at all?
Bitslicing DES, 256 at a time
If the goal is to free up GPUs, simply moving the workload to a CPU isn’t enough. A straightforward implementation achieves around 144 million DES operations per second on a 64-core EPYC processor. At that rate, a single precompute still takes around 45 minutes, with most of the time spent generating DES subkeys rather than performing encryption.
The solution is bitslicing. Rather than treating a CPU register as a single 64-bit value, bitslicing treats it as multiple 1-bit lanes and performs multiple DES operations in parallel. Each DES S-boxi becomes a compact network of Boolean operations built from AND, OR, XOR, and ANDNOT instructions.
Two additional optimizations make this approach practical at scale:
- AVX2 widens the slice: Replacing a 64-bit word with a 256-bit AVX2 vector increases parallelism fourfold, allowing 256 DES operations to be processed simultaneously instead of 64.
- The key schedule disappears: In a rainbow chain, keys are derived deterministically. Instead of rebuilding the DES key schedule for every operation, a precomputed mapping directly connects each subkey bit to its source key bit. Since key-schedule generation accounted for roughly 85% of the cost in the scalar implementation, eliminating it delivers a substantial performance gain.
Together, these optimizations increase throughout to roughly 2.1 billion DES operations per second on a single 64-core EPYC processor — around 15 times faster than the original implementation. A process that previously took around 45 minutes now completes in approximately three, without consuming a single GPU cycle.
Three phases and a freebie
This pipeline follows the standard rainbow-table workflow but splits it into three separate tools so that each phase can be optimized independently.
- Precomputegenerates roughly 880,000 candidate endpoints for the target ciphertext. This is the DES-heavy stage, and where bitslicing delivers most of the performance gain.
- Search scans the sorted rainbow tables for matching endpoints. Because the tables are sorted once up front, the search becomes a linear streaming pass through the data. At this point, the workload is dominated less by cryptography and more by sequential reads from disk — the exact scenario modern NVMe storage is designed for.
- Check takes the small number of matching candidates and walks each chain using bitslice DES until the correct 7-byte key is recovered.
There is also a freebie. The third NetNTLMv1 block contains only 2 bytes of entropy, which makes it small enough to brute-force locally and almost instantly. No rainbow tables required. No GPU required.
Going wide
The table set is large, but it has one useful property: it shards naturally.
We run multiple 4U systems in our datacenter, each equipped with a pair of AVX2-capable CPUs and a local copy of its portion of the sorted v1 tables on NVMe storage. A lightweight wrapper distributes work across the cluster and collects the results.
The more systems you add, the smaller each shard becomes and the less data each server needs to search. Performance scales almost linearly.
Decryption speeds
So, how fast can this methodology work to expedite the decryption process? End-to-end, on a small cluster of dual-CPU, 64-core EPYC systems, the following times can be achieved:
| Process | Time achieved (m) |
| CT3 brute-force | 0 (effectively instant) |
| Precompute | 3–5 minutes (parallelized) |
| Search | 4–6 (sharded) |
| Check | ≈3 |
| Orchestration overhead | ≈3 |
The same downgrade lookup that previously occupied GPUs for up to eight hours now completes in under 20 minutes on a single server, and faster across a small cluster, without consuming a single GPU cycle. The GPUs remain available for the rest of the cracking queue while the lookup runs independently on the CPUs.
There is a catch. You still need a captured NetNTLMv1 response using the static challenge. While tools like Responder can sometimes be configured to obtain one, success ultimately depends on the target environment. When it works, the lookup is extraordinarily efficient. When it doesn’t, the GPUs are the fallback.
Why this matters in an offensive security context
At the scale we operate as Sophos penetration testers — a scale shared by organized cybercrime groups and APTs alike — every GPU cycle counts. A GPU-based lookup may be fast in isolation, but it still monopolizes the most constrained resource in the cracking infrastructure for a workload that is partly I/O-bound and well within the reach of modern CPUs. Moving the lookup to the CPU transforms a serial dependency into parallel execution: the lookup runs on CPUs while GPUs remain available for password cracking and other acceleration-heavy workloads. The added benefit is that it reduces the need for frequent conversations about buying more GPUs.
I especially like the tweak in the Search section because it reinforces the article’s core argument: the lookup stops being purely a cryptographic problem and becomes partly a data-movement problem, which is the whole reason the GPU isn’t necessarily the bottleneck.
What defenders can do
The lesson here extends far beyond NetNTLMv1. Threat actors thrive on the availability of legacy technology that survives long after its security integrity has expired. Obsolete protocols, unsupported operating systems, weak cryptography, forgotten configurations, and aging infrastructure often provide the easiest path into otherwise modern environments. Regular security assessments help uncover these hidden weaknesses before attackers do, allowing organizations to prioritize remediation where it will have the greatest impact on reducing risk and shrinking the attack surface. The most dangerous exposures are often the ones everyone assumes disappeared years ago.
Get the code: v1-nightshift
Want to try our process yourself? To support our NetNTLMv1 research and testing workflows, we developed v1-nightshift, a CPU-based rainbow-table lookup tool designed to offload NetNTLMv1 lookups from GPUs.
The project is written in C and depends only on a C compiler and pthreads. It works with Mandiant’s public NetNTLMv1 rainbow tables and includes the tooling required to sort those tables for efficient searching. Builds are handled through make, with optional AVX2 acceleration enabled via AVX2=1 on x86-64 systems.
Because the binaries are architecture-specific, the project should be built on the system where it will run.
GitHub: v1-nightshift
About Author
