A Hybrid Classical-Quantum Rainbow Table Attack on Human Passwords
MA. Khajeian 1 · 2025
Read A Hybrid Classical-Quantum Rainbow Table Attack on Human Passwords by MA. Khajeian 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-14600.txt.
Introduction
Khajeian proposes a hybrid attack on human passwords in a 2025 paper. Long passwords that people invent are hard to crack because they are irregular and the search space is huge. Classical and quantum attacks each struggle with them on their own, so the author joins the two.
The method builds rainbow tables from dictionary words reshaped by rules that mimic real user habits. Tables are grouped into buckets for faster lookup and smaller storage. Inside each bucket, a distributed exact form of a quantum search algorithm does the hunting. That variant promises certain success with shallower circuits, which helps on noisy near term quantum machines. The author presents the framework as a more practical route to password recovery.
Catalog record
| CREATOR | MA. Khajeian 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-14600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Hybrid Classical-Quantum Rainbow Table Attack on Human Passwords MA. Khajeian 1 Abstract . Long, human-generated passwords pose significant challenges to both classical and quantum attacks due to their irregular structure and large search space. In this work, we propose an enhanced classical–quantum hybrid attack specifically designed for this scenario. Our approach constructs rainbow tables using dictionary-based password generation augmented with transformation rules that better capture real-world user behavior. These tables are organized into buckets, enabling faster lookup and reduced space complexity. For the search within each bucket, we employ a distributed exact variant of Grover’s algorithm. This method provides deterministic success and significantly lower circuit depth, enhancing robustness against noise—particularly depolarizing errors common in near-term quantum devices. Overall, our hybrid framework improves the efficiency and practicality of password recovery for long, human-readable passwords in realistic adversarial settings. Keywords. Rainbow Table Attack, Grover’s Algorithm, Human Password Recovery, Quantum Security 2020 Mathematics Subject Classification. Primary 68P25; Secondary 81P68 1. Introduction The growing use of lengthy, user-created passwords has weakened the effectiveness of conventional password-cracking techniques. Such passwords, typically built from recognizable words or easy-to-remember sequences, often evade detection by traditional brute-force methods and standard rainbow table attacks. In addition, the anticipated rise of quantum computing introduces new challenges and opportunities in password recovery. Although Grover’s algorithm offers a quadratic speedup for unstructured search, its direct application remains impractical in many real-world scenarios due to its high circuit depth and probabilistic nature. To address these challenges, we revisit and extend the use of structured rainbow tables for human-generated passwords. Building on prior work that introduces a “smart dictionary” using dictionary generators and transformation rules [ 4 ] , we adopt a structured approach. Passwords are broken down into components governed by composition patterns. This modeling captures human tendencies and enables compact, realistic coverage of the password space. As a result, precomputation becomes feasible even for long passwords. Based on this foundation, we propose a hybrid classical–quantum password cracking framework with two key innovations: • We partition the smart dictionary-derived rainbow table into buckets based on structural similarity or indexing heuristics. This reduces space complexity and enables fast, targeted lookups—particularly suitable for quantum memory access. • We use a distributed exact Grover variant [ 5 ] to perform quantum search within each bucket. This method offers deterministic success and lower quantum circuit depth, making it more robust to depolarizing noise. This paper is organized as follows: Section 2 covers fundamentals, Section 3 presents our hybrid quantum-classical approach, Section 4 shows experimental outcomes, with implementation details and conclusions following in Sections 5 and 6 . 2. Background This section covers the rainbow table attack method, human password pattern analysis, and a modified Grover quantum search approach. 2.1. Review of Rainbow Table Attack Rainbow tables are a time–memory trade-off technique used to invert cryptographic hash functions, particularly for password recovery. Originally introduced by Oechslin [ 2 ] , they allow attackers to precompute chains of hash outputs while storing only the first and last elements of each chain. This approach significantly reduces memory usage while enabling efficient lookups during the attack phase. 2.1.1. Rainbow Table Structure A rainbow table is composed of multiple chains, where each chain represents a sequence of alternating hash and reduction operations. The construction begins with a starting plaintext x_{0} , which is hashed to produce y_{0}=H(x_{0}) . This hash is then reduced using a reduction function R_{1} to obtain the next plaintext x_{1}=R_{1}(y_{0}) . The process continues for t steps, alternating between hash and reduction functions: x_{0}\xrightarrow{H}y_{0}\xrightarrow{R_{1}}x_{1}\xrightarrow{H}y_{1}\xrightarrow{R_{2}}\cdots\xrightarrow{R_{t}}x_{t} Only the starting plaintext x_{0} and the final output x_{t} are stored, forming the (x_{0},x_{t}) pair that represents the chain. To minimize chain collisions—where distinct inputs lead to the same endpoint—each reduction step uses a different function R_{i} . 2.1.2. Table Generation and Parameters The effectiveness of rainbow tables depends on several key parameters. The chain length t determines how many reduction steps are applied per chain. Longer chains reduce the number of required chains but increase lookup time. The number of chains m affects the table’s coverage—more chains improve success rates but require more storage. Reduction functions R_{1},R_{2},\dots,R_{t} convert hash outputs back into candidate plaintexts. The generation process is illustrated in Algorithm 1 . Algorithm 1 Ordinary Rainbow Table Generation 1: Dictionary of starting plaintexts, chain length t 2: Rainbow table entries 3: for all S_{start} in dictionary do 4: S\leftarrow S_{start} 5: for i\leftarrow 1 to t do 6: y\leftarrow H(S) \triangleright Apply hash function 7: S\leftarrow R_{i}(y) \triangleright Apply reduction function R_{i} 8: end for 9: Store pair (S_{start},S_{end}) in table 10: end for 2.1.3. Rainbow Table Lookup Process To look up a key in a rainbow table, the following procedure is used: First, apply the reduction function R_{n-1} to the ciphertext and check if the result matches any endpoint in the table. If a match is found, the corresponding chain can be reconstructed using the starting point. If no match is found, the process continues by applying R_{n-2} followed by f_{n-1} to check if the key appears in the second-to-last column of the table. This process is repeated iteratively, applying R_{n-3},f_{n-2},f_{n-1} , and so on. The total number of calculations required is \frac{t(t-1)}{2} [ 2 ] . 2.2. Modeling Human Passwords Zhang et al. [ 4 ] proposed an improved rainbow table attack targeting long, human-readable passwords. Traditional rainbow tables use fixed dictionaries and uniform reduction functions, which fail to capture the irregular patterns found in real-world passwords. To address this, the authors introduced a smart dictionary generated from high-frequency words and substrings in leaked datasets, combined with human-like transformation rules . These transformations include capitalizing letters, appending digits or years, using leetspeak substitutions (e.g., “o” to “0”), and inserting symbols. The result is a compact yet realistic password candidate set that reflects common user behavior without expanding the search space excessively. In their evaluation, the improved method achieved a success rate of 83% when recovering SHA1 hashes, demonstrating its effectiveness in cracking long, human-structured passwords. 2.3. Distributed Exact Grover’s Algorithm The Distributed Exact Grover’s Algorithm (DEGA) [ 5 ] partitions the original n -qubit search problem into \lfloor n/2\rfloor subfunctions \{g_{i}\}_{i=0}^{\lfloor n/2\rfloor-1} . Each subfunction g_{i} is derived from the target Boolean function f(x) by fixing selected groups of input bits. For i\in\{0,1,\ldots,\lfloor n/2\rfloor-2\} , the first 2i bits and the last (n-2(i+1)) bits of x are fixed. This yields 2^{n-2} subfunctions f_{i,j}:\{0,1\}^{2}\rightarrow\{0,1\} defined as f_{i,j}(m_{i})=f(y_{j,0}\cdots y_{j,2i-1}\,m_{i}\,y_{j,2i}\cdots y_{j,n-3}), where m_{i}\in\{0,1\}^{2} is the variable input and y_{j} enumerates all (n-2) -bit configurations. Each g_{i} is then constructed as g_{i}(m_{i})=\text{OR}\left(f_{i,0}(m_{i}),f_{i,1}(m_{i}),\ldots,f_{i,2^{n-2}-1}(m_{i})\right), (2.1) with \text{OR}(x)=\begin{cases}1,&|x|\geq 1\\ 0,&|x|=0\end{cases} and |x| denoting the Hamming weight. For the final case i=\lfloor n/2\rfloor-1 , the first 2i bits of x are fixed, and the remaining n-2i bits constitute the variable input m_{i} . The subfunction is given by f_{i,j}(m_{i})=f(y_{j,0}\cdots y_{j,2i-1}\,m_{i}), where the dimensionality of m_{i} depends on the parity of n : n-2i=\begin{cases}2,&\text{if }n\text{ is even}\\ 3,&\text{if }n\text{ is odd}\end{cases}. Then g_{i} is defined as g_{i}(m_{i})=\text{OR}\left(f_{i,0}(m_{i}),f_{i,1}(m_{i}),\ldots,f_{i,2^{2i}-1}(m_{i})\right). (2.2) This partitioning guarantees that the global target state \tau can be exactly reconstructed from the solutions of the subfunctions \{g_{i}\} , with each g_{i} isolating a distinct segment of \tau . Consequently, we obtain \lfloor n/2\rfloor subfunctions g_{i}(m_{i}) based