Identification Protocols

Identification protocols serve a fundamental security concern: proving that we are indeed the identity that we claim to be. This is a difficult problem when going beyond theoretical and mathematical aspects. Indeed, identity protocols can be understood as a mean for gaining a privilege using some secret. The protocol must support conflicting properties to be usable in the real-world:

• It should be complete. If the interaction is honest, it works out as it is supposed to be.
• It should be sound. If someone does not own the secret, it cannot use the claimed identity. That is, the relying party would not validate the interaction.
• It should be user-friendly. Identification protocols should be for everyone, independently of age, educational background, gender or intellectual performance.

Having these three properties together is challenging and still an open problem. Before discussing concrete examples, Let’s abstract and define identification protocols:

An identification protocol is a triplet of algorithms \( \mathcal{I} = (G, P, V) \) where:

• \( G \) is a probabilistic key generation algorithm. It takes in input a security parameter \( \lambda \) and outputs \( (sk, vk) \).
  • sk is called secret key
  • vk is called verification key
• \( P \) is called the prover and takes as input a secret key \( sk \) and outputs an identity proof.
• \( V \) is called the verifier and takes as input a verification key \( vk \) and outputs either accept or reject.

Modeling the Attacker

There are many ways in which things can go wrong in such a protocol. To define meaning for the word “security” of our identification protocol, we need to precise the attacker’s capability. We start with minimal capability: we assume the attacker gets at some point all information that the Verifier is having and may use it to pass the protocol’s verifier algorithm upon a given identity. This model essentially captures a real-world compromise and exfiltration of a server’s database. We assume it happens once, and that all data that the server was storing is now also within the hands of the attacker. Our goal is to make sure that the protocol resists such an attacker.

A tale of password protocols

Our goal is to reason on the security of the identification protocol given the model we have for our attacker. We’ll define first a simple instance of an identification protocol and we’ll try to formally define the security notion. That is, we want to know when our protocol instance is considered broken and when it is not.

A first password protocol (v0.1)

We start by instantiating an identification protocol \( \mathcal{I} = (G, P, V) \) using a password as a secret key. We define the three algorithms \( G, P \) and \( V \):

• \( G:= (sk, vk) = (pwd, pwd) \overset{R}{\leftarrow} G() \)

That is, we define the algorithm \( G \) as a random password generator which outputs the same value for \( sk \) and \( vk \).

• \( P \) takes on input \( sk \), and \( V \) takes on input \( vk \). They interact as follows:

  • \( P \) sends \( pwd \) to \( V \)
  • \( V \) outputs accept if \( pwd == vk \), or outputs rejects.

The interaction can be visualized as follows, with an alternative response from the Verifier depending on the result of the verification:

sequenceDiagram
    participant P as Prover (P)
    participant V as Verifier (V)
    Note over P: sk = pwd
    Note over V: vk = pwd
    P->>V: send(pwd)
    alt pwd == vk
        V-->>P: accept
    else pwd != vk
        V-->>P: reject
    end

Now if the Verifier was compromised, well it is rather obvious that we have a problem. How can we define this security problem more formally such that we do not need to rely on intuition?

Defining the Protocol’s security

To define security, we rely on an Attack Game definition. Attack games are usually seen to model security for cryptographic constructions. They capture the interaction between entities modelling real-world interactions. We have a challenger playing the protocol honestly and which the Adversary is being challenged to break the security property. At the end of the interaction, we measure how likely the adversary is able to pass the challenge; this defines the success probability of the adversary. We could then define the security of the scheme on this probability of success, which we want it be close to 0 to be “secure”.

For our password protocol, the attack game unfolds as follows:

sequenceDiagram
    participant C as Challenger
    participant A as Adversary
    C->>C: (sk, vk) ← G()
    Note over C: keep vk
    C->>A: send vk (database compromise)
    A->>A: compute pwd* from vk
    A->>C: send(pwd*)
    alt pwd* == vk
        C-->>A: accept (adversary wins)
    else pwd* != vk
        C-->>A: reject (adversary loses)
    end

We define the quantity \( VCadv[\mathcal{I}, \mathcal{A}] \) as the probability for the adversary running algorithm \( \mathcal{A} \) against protocol \( \mathcal{I} \) to make the challenger accept. We will say that \( \mathcal{I} \) is secure against verifier compromise attack if \( VCadv[\mathcal{I}, \mathcal{A}] \) is negligible.

Looking at the attack game’s instantiation for our password protocol \( \mathcal{I} = v0.1\), it is obvious that the adversary succeeds with probability \(1\) Therefore, it means that this instance is insecure against a verifier compromise. How can we improve our protocol?

A second Password protocol (v0.2)

We update our key generation algorithm of protocol v0.1 using a cryptographic hash function, we have:

• \( G:= (sk, vk) = (pwd \overset{R}{\leftarrow} G(), H(pwd)) \)

The prover algorithm \( P \) stays unchanged, but we have to modify \( V \):

• \( V \) outputs accept if \( H(pwd) == vk \), or outputs rejects.

Remember that a cryptographic hash function is one-way, has second-preimage resistance and is collision-resistant. So, the adversary compromising the server’s database would obtain hash values instead of passwords. These hashes do not depend on any key that could have been compromised as well, and should not be reversible.

Security analysis

Assuming the hashing function is one-way, we can derive the following theorem

Theorem: Supposing a hash function: \( H: \mathcal{P} \rightarrow \mathcal{Y} \) is one-way. Then the identification protocol \( \mathcal{I}_{v0.2} \) is secure against a verifier compromise.

There is however a subtlety with this theorem: how likely is that our hash is one-way? Sure\ it depends first on the fact that the algorithm must be a cryptographic hash, but it is sadly not a sufficient condition. The adversary could break the one-wayness of the hashing function by testing some value \( \in \mathcal{P} \), computing its hash, and checking whether the hashed value matches what we have obtained from the compromised server. How likely is that to happen?

If you look at the definition of \( \mathcal{I_{v0.2}} \), it depends on the generation algorithm. If the generation algorithm produces “weak passwords”, e.g., words from the dictionary, then the enumeration is trivial for a computer, the one-wayness cannot hold and so thus the security cannot hold.

The theorem holds if \( G \) produces strong passwords, i.e., if it produces value randomly from a set large enough, e.g., at least 80 bits of information; meaning it is large enough to have \( 2^{80} \) possibilities. Who/what is \( G \) in the real worlds? It depends. Sometimes, it is us! We pick a password ourselves, and we’re terrible at it. Our mind is not wired for this, we cannot pick truly randomly 15+ characters each time we need a password, and remember it. For example, if you pick a word existing within the dictionary and a few numbers, you’re likely to have selected a choice from a set whose size is just beyond a few millions of options, and this would not be one-way.

We can use tools to help, like encrypted password vaults. These are program one can store encrypted computer-assisted randomly generated strings. We don’t need to remember them if we can unlock the vault each time we need one of these passwords. Usually it means we need to remember one long string of random characters, and never use it anywhere else than for locally decrypting the vault.

Still, it could be interesting to have better intuition on typically how long a password should be, and what kind of attacks exist to revert a non-invertible function such as a cryptographic hash algorithm.

Attacking password protocol(s)

Understanding offense capabilities is sometimes necessary to design proper defense capabilities, especially when we cannot formally guarantee non-misuse. In the case of our password protocol, misuse would mean generating a password that isn’t strong.

Bruteforce

A bruteforce is the simplest form of computer-based attack: it simply explore the range of possible candidates until the right value is found. The success of this approach depends both on the size of the range, and on the speed of the bruteforce itself. Searching within a pre-defined range is straightforward to parallelize: similarly to the blockchain project searching within the nonce space for a block candidate, searching a password candidate can be split among logical threads, or graphical cores by splitting the search space among all logical compute available. hashcat is an open-source program for password recovery, it supports tons of different hashing functions, encoding and modes to bruteforce the desired space. To have a rough idea of how fast it is possible to reverse a hash, we can do as follows:

First, generate a hashed value:

printf "azerty1" | md5sum | cut -d ' ' -f1 > example.hash

Then run hashcat on this example:

hashcat -a 3 -m 0 -O -1 \?l\?d example.hash \?1\?1\?1\?1\?1\?1\?1

The program would output statistics and progress on search. On my setup, I am seeing 89913.8 MH/s, so about 90 billions attempts per second against md5. This is fast, but regarding md5, collisions can be found in about \( 2^{16} \) effort independently of the input space with known techniques, it is not a cryptographic hash function and should not be used.

What about SHA-256? SHA-256 is the current recommended cryptographic hash for general purpose.

printf "azerty1" | sha256sum | cut -d ' ' -f1 > example2.hash
hashcat -a 3 -m 1400 -O -1 \?l\?d example2.hash \?1\?1\?1\?1\?1\?1\?1

This time, I am seeing 11707.3 MH/s for bruteforcing, somewhat showing that running SHA-256 is nine times more expensive for my hardware than md5. This still allows me to bruteforce the search space pretty quickly. Indeed, 7 characters in the charset [a-z;0-9] is \( 36^7 \) possibilities which can still be searched in a few seconds since it is about 70 billions possibilities. We could increase the length of the password, until bruteforce is unusable. Since increasing the length of the password exponentially increases the search space, the bruteforce is becoming quickly much harder to perform. It is a \(O(N)\) algorithm with \( N \) the size of the search space.

Dictionary Attack

Conceptually, the idea is trying passwords that are most likely, composed of words, numbers or symbols placed as humans usually place them. We fully store pairs of (hash(value), value) for all values within the space we consider. Accessing the dictionary to verify whether a given hash belongs is \( O(1) \), but at the cost of \( O(N) \) memory. Similarly to the bruteforce, beyond a certain size of N, this becomes unmanageable.

Time-memory Trade-off (TMTO)

The fundamental issue with the Bruteforce and Dictionary attacks is that they fully use a single resource, either compute or memory. But we have both at our disposal. A time-memory tradeoff algorithm, as its name implies, is a technique that would allow to reverse a non-invertible function taking advantage of both resources to extend the search space to potentially larger \( N \). They work in two phases: a pre-computation phase, and an online phase.

• The pre-computation phase is designed to produce data aimed at speeding-up the search in the online-phase, such that that speed-up is available for each reversing attempt. That is, if one had 10 hashes to reverse, the speed-up would be for each of these reverse attempts. If there is only a single hash hash to reverse, then pre-computing + online phase is no better than a bruteforce in terms of compute.

• The online phase: This phase takes a value to reverse, and the memory computed during the pre-computation phase, and begins the search. The algorithm may not necessarily succeed in finding the pre-image; i.e., it can terminate without exploring the whole space, and miss the target. The reason for this is that it depends on whether the pre-computation phase is able to capture the whole space, and as we will discuss, this isn’t easy.

Hellman Tables

Let’s assume we want to reverse a function \( f: X \rightarrow Y \) such that \( y = f(x) \) but computing \( f^{-1}(y) = x \) is computationally hard. To simplify the presentation of the TMTO algorithms, we assume that \( X = Y \), that is the function takes element and output elements from the same set.

Table Preprocessing

The goal of the pre-processing phase is to explore the space of candidate values and save some of them in a way the search algorithm within the online phase will be speed-up by a factor \( m \). You can think of the pre-processing phase as building a mental palace where we generate (most of) the space of candidate values with a way to connect them to the values we save. Then the online phase will use the saved value to navigate through the mental palace and find the reversed hash. Note that this is an image, it is not exactly how it works.

We start by generating \( m \) distinct values \( x_i \) randomly from the function’s input space \( X \). For each of these \( x_i \) values, we build a chain of size \( t \) applying function \( f(\cdot) \) \( t \) times. For each chain, we end up to a pair of values \( (x_i, y_{it}) \) where \( x_i \) is the start of the \( i_{th} \) chain and \( y_{it} \) the final application of function \( f(\cdot) \)

flowchart LR
    subgraph XSpace ["<b>X</b>  (input space)"]
        direction TB

        subgraph C1 ["<i>Chain 1</i>"]
            direction TB
            s1["● x<sub>1</sub>"] -->|"f()"| n11["y<sub>11</sub>"] -->|"f()"| n12["y<sub>12</sub>"] -->|"f()"| e1["● y<sub>1t</sub>"]
        end

        subgraph C2 ["<i>Chain 2</i>"]
            direction TB
            s2["● x<sub>2</sub>"] -->|"f()"| n21["y<sub>21</sub>"] -->|"f()"| n22["y<sub>22</sub>"] -->|"f()"| e2["● y<sub>2t</sub>"]
        end

        subgraph C3 ["<i>Chain m</i>"]
            direction TB
            s3["● x<sub>m</sub>"] -->|"f()"| n31["y<sub>m1</sub>"] -->|"f()"| n32["⋮"] -->|"f()"| e3["● y<sub>mt</sub>"]
        end
    end

    style XSpace fill:transparent,stroke:currentColor,stroke-width:2px,stroke-dasharray: 5 5
    style C1 fill:none,stroke:none
    style C2 fill:none,stroke:none
    style C3 fill:none,stroke:none

    linkStyle 0,1,2,3,4,5,6,7,8 stroke:currentColor,stroke-width:1.5px

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x<sub>1</sub>, y<sub>1t</sub>)"]
        T2["(x<sub>2</sub>, y<sub>2t</sub>)"]
        T3["(⋮, ⋮)"]
        Tm["(x<sub>m</sub>, y<sub>mt</sub>)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    e1 -.-> T1
    e2 -.-> T2
    e3 -.-> Tm

    linkStyle 9,10,11 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Figure: Hellman Table Preprocessing. \( m \) chains of length \( t \). Each chain starts at a random \( x_i \) and iterates \( f(\cdot) \) \( t \) times. Only the \( m \) start-end pairs are stored, giving \( O(m) \) space to cover \( O(m \cdot t) \) candidate values. Figure generated with Qwen3.6-27B on local hardware.

Observe that generating and covering the whole space would depend on the choice of \( m \), \( t \), and from \( f(\cdot) \)’s properties. We can assume it to be uniformly random on its output. However, there is no guarantee that whole space can be covered, and no guarantee that each element within this table is unique.

Table Online Phase

Given some elements \( y_a, y_b, y_c, … \in Y \), and the pre-computed table \( T \), the online phase aims to recover \(x_a, x_b, x_c, … \) It is launched against each \( y \) once and may, with the help of the table generated at the pre-computation phase, allow to search over \( m \cdot t \) elements with a complexity \( O(t) \).

The online phase’s algorithm is as follows:

1. Given \( y \in Y \) to revert; check whether \( y \) is among the endpoints in \( T \). This is O(1) check. If it is the case, then it means that \( y = y_{jt} \) for some \( j \), and that the value that we’re looking for is \( y_{jt-1} \), which we could recover by applying \( f(\cdot) \) \( t-1 \) times over \( x_j \), effectively reconstructing the \( j_{th} \) chain.

2. if \( y \) is not among the endpoints, we apply \( y_{new} = f(y) \) and we check whether \( y_{new} \) is among the endpoints. If it is the case, then it means that \( y_{new} = y_{jt} \) for some \( j \), and that the value that we’re looking for is \( y_{jt-2} \), which we could recover by applying \( f(\cdot) \) \( t-2 \) times over \( x_j \), effectively reconstructing the \( j_{th} \) chain.

This logic continues until either we have successfully reverted \( y \) (it means \( y \) was generated during pre-computation phase), or we have exhausted all \( t \) iteration steps; that is, we have applied the above algorithm \( t \) times, and continuing would not allow to revert the value if a correspondence is found; indeed, it would mean it “outside” of our pre-computed rectangle.

flowchart TD

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x₁, y₁ₜ)"]
        T2["(x₂, y₂ₜ)"]
        T3["(⋮, ⋮)"]
        Tm["(xₘ, yₘₜ)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    subgraph Search ["Online search for y"]
        direction TB
        target["⟵  y  (target)"]
        chk0["y  ∈ T?"]
        step1["f(y)"]
        chk1["f(y)  ∈ T?"]
        step2["f(f(y))"]
        chk2["f(f(y))  ∈ T?"]
        dots0["⋮"]
        chkT["fᵗ⁻¹(y)  ∈ T?"]
    end

    style Search fill:transparent,stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    style target stroke:currentColor,stroke-width:2px
    style dots0 stroke:none

    target ==> chk0
    chk0 ==>|"no"| step1
    step1 ==> chk1
    chk1 ==>|"no"| step2
    step2 ==> chk2
    chk2 ==> dots0
    dots0 ==> chkT

    chk1 ==>|"yes ✓"| T2

    subgraph Replay ["Replay chain 2 from x₂"]
        direction LR
        rstart["x₂"] -->|"f()"| r1["y₂₁"] -->|"f()"| rfound["y (target)"] -->|"f()"| rlast["y₂ₜ"]
    end

    style Replay fill:transparent,stroke:currentColor,stroke-width:2px
    style rfound stroke:currentColor,stroke-width:3px

    T2 -.->|"start x₂"| rstart

    linkStyle 1,2,3,4,5 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    linkStyle 6 stroke:currentColor,stroke-width:1.5px,stroke-dasharray: 5 5
    linkStyle 7 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Figure: Hellman Table Online Phase. Given a target \( y \), iteratively apply \( f(\cdot) \) and check against the table’s endpoints. When a match is found (here \( f(y) = y_{2t} \)), replay the matched chain from its start \( x_2 \). The pre-image is the value immediately before the match, in this example \( y_{21}\). Figure generated with Qwen3.6-27B on local hardware.

Introducing a reduction function

We made a little simplification to cover the Hellman Table pre-computation and online computation phases. We said that our function \( f: X \rightarrow Y \) was defined with sets \( X = Y \). In practice, we usually have \( |X| << |Y| \), that is the size of the set \( X \) is much smaller. \( X \) could be the set of all passwords of 10 ascii characters, which would amount for \( 2^{70} \) possibilities, which is tiny compared to the size of say, SHA256’s output.

Since we have to chain application of \( f(\cdot) \), we need to map \( Y \) to \( X \), this is the role of the Reduction function, \( r: Y \rightarrow X \). We furthermore need the mapping to preserve the uniformity of \( Y \); that is, applying \( r(f(x)) \) is deterministic and gives a new \( x_{new} \) uniformly random in \( X \). The reduction function must be computationally efficient since it needs to be applied each time \( f(\cdot) \) is used. As an exercise, ask yourself how you could make/implement an efficient reduction function.

We can update the pre-computation phase and attack phase using the reduction function:

• Pre-computation phase

flowchart LR
    subgraph XSpace ["<b>X</b>  (input space)"]
        direction TB

        subgraph C1 ["<i>Chain 1</i>"]
            direction TB
            s1["● x₁"] -->|"r(f())"| n11["x₁₁"] -->|"r(f())"| n12["x₁₂"] -->|"r(f())"| e1["● x₁ₜ"]
        end

        subgraph C2 ["<i>Chain 2</i>"]
            direction TB
            s2["● x₂"] -->|"r(f())"| n21["x₂₁"] -->|"r(f())"| n22["x₂₂"] -->|"r(f())"| e2["● x₂ₜ"]
        end

        subgraph C3 ["<i>Chain m</i>"]
            direction TB
            s3["● xₘ"] -->|"r(f())"| n31["xₘ₁"] -->|"r(f())"| n32["⋮"] -->|"r(f())"| e3["● xₘₜ"]
        end
    end

    style XSpace fill:transparent,stroke:currentColor,stroke-width:2px,stroke-dasharray: 5 5
    style C1 fill:none,stroke:none
    style C2 fill:none,stroke:none
    style C3 fill:none,stroke:none

    linkStyle 0,1,2,3,4,5,6,7,8 stroke:currentColor,stroke-width:1.5px

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x₁, x₁ₜ)"]
        T2["(x₂, x₂ₜ)"]
        T3["(⋮, ⋮)"]
        Tm["(xₘ, xₘₜ)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    e1 -.-> T1
    e2 -.-> T2
    e3 -.-> Tm

    linkStyle 9,10,11 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Now it can probably be more obvious that the pre-computation phase aims to cover the whole input space \( X \). We store a pair \( \in (X, X) \) for each chain, and that makes up the Hellman Table.

• Online phase:

flowchart TD

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x<sub>1</sub>, x<sub>1t</sub>)"]
        T2["(x<sub>2</sub>, x<sub>2t</sub>)"]
        T3["(⋮, ⋮)"]
        Tm["(x<sub>m</sub>, x<sub>mt</sub>)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    subgraph Search ["Online search for y"]
        direction TB
        target["⟵  y  (target)"]
        chk0["r(y)  ∈ T?"]
        step1["r(f(y))"]
        chk1["r(f(y))  ∈ T?"]
        step2["r(f(r(f(y))))"]
        chk2["r(f(r(f(y))))  ∈ T?"]
        dots0["⋮"]
        chkT["(r(f(y)))<sup>t-1</sup> ∈ T?"]
    end

    style Search fill:transparent,stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    style target stroke:currentColor,stroke-width:2px
    style dots0 stroke:none

    target ==> chk0
    chk0 ==>|"no"| step1
    step1 ==> chk1
    chk1 ==>|"no"| step2
    step2 ==> chk2
    chk2 ==> dots0
    dots0 ==> chkT

    chk1 ==>|"yes ✓"| T2

    subgraph Replay ["Replay chain 2 from x<sub>2</sub>"]
        direction LR
        rstart["x<sub>2</sub>"] -->|"r(f())"| r1["x<sub>21</sub>"] -->|"f()"| rfound["y (target)"] -->|"r(f(r(y)))"| rlast["x<sub>2t</sub>"]
    end

    style Replay fill:transparent,stroke:currentColor,stroke-width:2px
    style rfound stroke:currentColor,stroke-width:3px

    T2 -.->|"start x₂"| rstart

    linkStyle 1,2,3,4,5 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    linkStyle 6 stroke:currentColor,stroke-width:1.5px,stroke-dasharray: 5 5
    linkStyle 7 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

The main difference with the previous instance is that we apply the reduction function over input hash target \( y \) to verify whether they’re within the table. The remaining of the algorithm proceeds with the same logic as before except that we use \( r \) accordingly to the pre-computation phase.

Given that \( |X| << |Y| \), we now have significantly increased the probability of collision occurring. They’re not negligible anymore; e.g., assuming \( |X| = 2^{70} \) for our 10-chars ascii example, it means that we’d expect to have a collision after \( 2^{35} \) applications of \( r(f(\cdot))) \) if \( r(f(\cdot)) \) is uniformly random. \( 2^{35} \) is very small compared to \( 2^{70} \), and the pre-computation phase should have ideally computed \( r(f(\cdot)) \) as close as possible to \( 2^{70} \); meaning that a large number of collisions happened.

Reduction: Impact on False positives

There several consequences to collisions. First, we’re essentially loosing compute power during the pre-computation phase: when two values collide on the table, all succeeding values until the end of the chain are identical, so we’re losing compute power to generate them once again. We can’t “remember” what value was previously generated, since it’ll take too much memory, and the whole point of a TMTO is to store only endpoints of the chains.

A second issue is that collision can happen as well during the online phase! That is, when we generated the chain \( f(r(y)) \) -> \( f(r(\cdot)) \) -> … and we find a match with the table, it is possible one element of our chain collided with one element of a pre-computed chain, meaning that we would not be able to find \( y\)’s pre-image since the beginning of the chain on which ours collided may not be on the table.

flowchart TD
    subgraph Search ["Online search for y"]
        direction LRhttps://www-ee.stanford.edu/~hellman/publications/36.pdf
        target["⟵ y (target)"] -->|"r()"| ry["r(y)"]
        ry -->|"f()"| ynew["y<sub>new</sub>"]
        ynew -->|"r()"| xcolS["x<sub>ji</sub>"]
        xcolS -.->|"r(f()) iterations"| endS["x<sub>jt</sub>"]
    end

    subgraph Replay ["Replay chain j from x<sub>j</sub>"]
        direction LR
        start["x<sub>j</sub>"] -.->|"r(f()) iterations"| xprev["x<sub>ji-1</sub>"]
        xprev -->|"f()"| yj["y<sub>ji</sub>"]
        yj -->|"r()"| xcolR["x<sub>ji</sub>"]
        xcolR -.->|"r(f()) iterations"| endR["x<sub>jt</sub>"]
    end

    endS -.->|"Matches endpoint in table ✓"| endR

    note["<b>False Positive:</b> target <i>y</i> is not found during replay!<br>The chains merged because r(y<sub>new</sub>) = r(y<sub>ji</sub>) = x<sub>ji</sub>"]
    note -.-> yj
    note -.-> ynew

    style Search fill:transparent,stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    style Replay fill:transparent,stroke:currentColor,stroke-width:2px
    style target stroke:currentColor,stroke-width:2px
    style xcolS stroke:currentColor,stroke-width:3px
    style xcolR stroke:currentColor,stroke-width:3px
    style note fill:transparent,stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Figure: False Positive during Online Phase. The target hash \( y \) initiates a chain that collides with a pre-computed chain at \( x_{ji} \) due to the reduction function \( r(\cdot) \). The endpoints match, but replaying the pre-computed chain from \( x_j \) does not yield \( y \), because the merge occurred after \( y \) would have been generated. Figure generated with Qwen3.6-27B on local hardware.

This situations depends on the size of the table, and from the size of the input space \( X \), we have the following theorem:

false positive in a Hellman Table: The expected number of false positives \( E(X) \) is bounded by:

$$ E(X) \leq \frac{mt(t+1)}{2|X|} $$

A Hellman table should be quite large: it could be billions of lines and hundreds of millions of columns; plugging these values within the formulae would give an intuition of the probability to find the right pre-image when a match is found. It is small, even if we assume that the pre-computation was perfect, i.e., we generated a table that contains all value from \( X \).

In practice, the table is not perfect, and it is very possible we only find false positives during the online phase and never actually reverse our target \( y \). To reduce the probability of wasted computation during pre-computation and thus to increase the probability of success, we can split the table into many tables, each with a different reduction function. If a collision occurs on two different tables, these lines would not “merge”, as the two different reduction functions would select a different mapping and the next evaluation of \( f(\cdot) \) would produce a different random value. It is then all about finding the right value of \( m, t \) for each table (and a right number of tables), to make sure we’re likely to reverse the target, and do not waste too much time during the online phase to deal with false positives.

Making this analysis is far from trivial. We first need to analyze the probability of success.

Analyzing Probability of Success

The full analysis can be read on the original CRYPTO paper published in 1980. The reasoning is as follows:

Let \( N \) the size of \( X \). The probability of success of the online phase depends on whether the value we are looking for was computed during the pre-computation phase; that is, we are trying to establish what probability a given value \( x \in X \) belongs to the pre-computation. To compute this probability, we need to evaluate \( Pr[x_{ij}\text{ is new}] \), the probability that event \( x_{ij} \) is new to the table, which means \( x_{ij} \) was not generated before. We have:

\begin{align} Pr[x_{ij}\text{ is new}] &\geq Pr[x_{i0}, x_{i1}, …, x_{ij}\text{ are new}] \\ &= Pr[x_{i0}\text{ is new}]\cdot Pr[x_{i1}\text{ is new} | x_{i0}\text{ is new}] \cdot … \cdot \\ & Pr[x_{ij}\text{ is new}]\cdot Pr[x_{ij}\text{ is new}|x_{i0},…,x_{ij-1} \text{ are new}] \\ &= \frac{N-|A_{i0}|}{N} \cdot \frac{N-|A_{i0}|-1}{N} \cdot … \cdot \frac{N-|A_{i0}|-j}{N} \end{align}

Where \( A_{ij} \) are the set of elements covered up to index \( ij \) and \( |A_{ij}| \) denotes its size. Each element of the last equation can be lower-bounded but the value \( \frac{N-it}{N} \) since \( it > |A_{i0}| \), thus \( Pr[x_{ij}\text{ is new}] \) can be lower-bounded by \( (\frac{N-it}{N})^{j+1} \). From this inequation, we can derive a lower-bound for the probability of success to reverse a given hash: it is the sum of probability that each element within the table are new, divided by the total number of elements in \( X \):

$$ Pr[Success] \geq \frac{1}{N} \cdot \sum_{i=1}^{m}\sum_{j=0}^{t-1}(\frac{N-it}{N})^{j+1} $$

Now that we have this equation, we can reason on the choice of \( m \) and \( t \). Intuitively, \( Pr[x_{ij}\text{ is new}] \) is getting smaller as \( ij \) increases, and at some point the value could be negligible (i.e., meaning the probability to generate a ’‘new’’ \( x_{ij} \) becomes close to 0). And indeed, \( (\frac{N-it}{N})^{j+1} \) can be approximated using the exponential function: \( (1 + x)^n \approx e^{nx} \) when \(n \) is large and \( x \) is small, which exactly what we have here:

$$ (\frac{N-it}{N})^{j+1} \approx e^{\frac{-ijt}{N}} $$

For large \( ij \) the last term approximates by \( e^{\frac{-mt^2}{N}}\), and thus choosing values for \(m, t\) such that \(mt^2 >> N\) exponentially decreases to 0.

So, any choice of \( m, t \) such that \( mt^2 = N \) is admissible. Intuitively we can pick any rectangle shape that satisfies this equation, and the chosen shape should depend of our relative compute and memory strength. If we have a lot a memory, and we want to reverse value quickly, then we have to reduce \( t \) and increase \(m \) while preserving the above relation.

For such choice of \( m, t \), the probability of success \( Pr[Success] \) can be numerically evaluated to \( \approx 0.8\cdot \frac{mt}{N} \), which would be small. That’s why we need multiple tables, each satisfying \( mt^2 = N \), and each having a different reduction function. In that case, the probability of of finding the value within a given table is independent from another table, and the success for \( \ell \) tables would evaluated to:

$$ Pr[success] \geq 1 - (1 - \frac{1}{N} \cdot \sum_{i=1}^{m}\sum_{j=0}^{t-1}(\frac{N-it}{N})^{j+1})^\ell $$

Thus, the choice of \(m, t \) such that \( mt^2 = N \), and a number of tables \( \ell = t \) leads to \( Pr[success] \geq 0.8 \). During the online phase, each table could be explored in parallel by different threads, processes, or even different computers.

Rainbow Tables

Hellman Table’s TMTO is improved in 2003 by Philippe Oechslin in their CRYPTO’03 publication. The main idea within this research is to change how we build chains during the pre-computation to avoid the “merge” issue within Hellman’s table. Recall in Hellman’s table that any collision after reduction between two elements within the table admits the same following chain of elements, since \( f(\cdot) \) and \(r(\cdot) \) are deterministic functions. Rainbow Table are designed to prevent the merge effect if a collision occurs at different columns within the pre-computation. Preventing merge during the pre-computation phase would then increase the success probability during the online phase.

Rainbow Table Pre-processing

flowchart LR
    subgraph XSpace ["<b>X</b>  (input space)"]
        direction TB

        subgraph C1 ["<i>Chain 1</i>"]
            direction TB
            s1["● x<sub>1</sub>"] -->|"r<sub>1</sub>(f())"| n11["x<sub>11</sub>"] -->|"r<sub>2</sub>(f())"| n12["x<sub>12</sub>"] -->|"r<sub>t</sub>(f())"| e1["● x<sub>1t</sub>"]
        end

        subgraph C2 ["<i>Chain 2</i>"]
            direction TB
            s2["● x<sub>2</sub>"] -->|"r<sub>1</sub>(f())"| n21["x<sub>21</sub>"] -->|"r<sub>2</sub>(f())"| n22["x<sub>22</sub>"] -->|"r<sub>t</sub>(f())"| e2["● x<sub>2t</sub>"]
        end

        subgraph C3 ["<i>Chain m</i>"]
            direction TB
            s3["● x<sub>m</sub>"] -->|"r<sub>1</sub>(f())"| n31["x<sub>m1</sub>"] -->|"r<sub>2</sub>(f())"| n32["⋮"] -->|"r<sub>t</sub>(f())"| e3["● x<sub>mt</sub>"]
        end
    end

    style XSpace fill:transparent,stroke:currentColor,stroke-width:2px,stroke-dasharray: 5 5
    style C1 fill:none,stroke:none
    style C2 fill:none,stroke:none
    style C3 fill:none,stroke:none

    linkStyle 0,1,2,3,4,5,6,7,8 stroke:currentColor,stroke-width:1.5px

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x<sub>1</sub>, x<sub>1t</sub>)"]
        T2["(x<sub>2</sub>, x<sub>2t</sub>)"]
        T3["(⋮, ⋮)"]
        Tm["(x<sub>m</sub>, x<sub>mt</sub>)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    e1 -.-> T1
    e2 -.-> T2
    e3 -.-> Tm

    linkStyle 9,10,11 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Figure: Rainbow Table Preprocessing. \( m \) chains of length \( t \). Each chain starts at a random \( x_i \) and iterates using a sequence of distinct reduction functions \( r_1, r_2, \ldots, r_t \). Only the start-end pairs are stored. The changing reduction functions prevent chains from permanently merging if they collide at different positions.

Since chains are not merging, there is no particular need to have multiple tables in theory. So instead of having \( t \) tables of size \( mt \), a rainbow table can be of size \( mt \times t \). In practice however, we may need to split the \( mt \) rows of the big rainbow table into \( t \) pieces to search in parallel during the online phase, if we have \( t \) compute cores.

A nice observation with Rainbow table is that a merge occurs on a collision between two values on two different chains if they belong to the same column. In that case, the remaining of both \( r_i(f_i(\cdot)) \) computations are exactly the same. That means that we can easily check whether a merge occurred: if an endpoint we just computed already exist within our pre-computed database of endpoints, then it is a merge and the chain can be discarded.

Having unique chains is however more and more difficult, as we are more and more likely to merge eventually after computing millions of billions of chains.

Rainbow Table Attack Phase

flowchart TD

    subgraph Table ["O(m) storage"]
        direction TB
        T1["(x<sub>1</sub>, x<sub>1t</sub>)"]
        T2["(x<sub>2</sub>, x<sub>2t</sub>)"]
        T3["(⋮, ⋮)"]
        Tm["(x<sub>m</sub>, x<sub>mt</sub>)"]
    end

    style Table fill:transparent,stroke:currentColor,stroke-width:2px

    subgraph Search ["Online search for y"]
        direction TB
        target["⟵  y  (target)"]
        chk0["r<sub>t</sub>(y)  ∈ T?"]
        step1["r<sub>t</sub>(f(r<sub>t-1</sub>(y)))"]
        chk1["r<sub>t</sub>(f(r<sub>t-1</sub>(y)))  ∈ T?"]
        step2["r<sub>t</sub>(f(r<sub>t-1</sub>(f(r<sub>t-2</sub>(y)))))"]
        chk2["r<sub>t</sub>(f(r<sub>t-1</sub>(f(r<sub>t-2</sub>(y)))))  ∈ T?"]
        dots0["⋮"]
        chkT["r<sub>t</sub>(f(...r<sub>1</sub>(y))) ∈ T?"]
    end

    style Search fill:transparent,stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    style target stroke:currentColor,stroke-width:2px
    style dots0 stroke:none

    target ==> chk0
    chk0 ==>|"no"| step1
    step1 ==> chk1
    chk1 ==>|"no"| step2
    step2 ==> chk2
    chk2 ==> dots0
    dots0 ==> chkT

    chk1 ==>|"yes ✓"| T2

    subgraph Replay ["Replay chain 2 from x<sub>2</sub>"]
        direction LR
        rstart["x<sub>2</sub>"] -->|"r<sub>1</sub>(f())"| r1["x<sub>21</sub>"] -->|"f()"| rfound["y (target)"] -->|"sequence of r_i(f())"| rlast["x<sub>2t</sub>"]
    end

    style Replay fill:transparent,stroke:currentColor,stroke-width:2px
    style rfound stroke:currentColor,stroke-width:3px

    T2 -.->|"start x<sub>2</sub>"| rstart

    linkStyle 1,2,3,4,5 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3
    linkStyle 6 stroke:currentColor,stroke-width:1.5px,stroke-dasharray: 5 5
    linkStyle 7 stroke:currentColor,stroke-width:1px,stroke-dasharray: 3 3

Figure: Rainbow Table Online Phase. The search starts by assuming \( y \) is at the end of a chain, applying \( r_t \). If no match, it assumes \( y \) is at position \( t-1 \), applying \( r_{t-1} \) then \( f \) then \( r_t \), and so on. Upon a match, the specific chain is replayed from its start using the sequence of reduction functions until \( y \) is found.

A main difference with Hellman tables is how the reductions functions on each column impact the online phase’s algorithm. In the case of Hellman, within a given table, we have at most \( t \) applications of \( f(\cdot) \) (ignoring false positives) to visit the whole table. Observe that with Rainbow tables, we need to “restart” the computation each time we check a column. We end up to \( 1 + 2 + 3 + 4 + … + t \) applications of \( f(\cdot) \) (ignoring false positives) to visit the whole table. This is \( \frac{t(t+1)}{2} \) applications of \( f(\cdot) \).

This may look more expensive than Hellman table, but in practice it is likely unclear: these \( t \) searches within the Rainbow table are not sequential and can be parallelizable over a single big table. In the case of Hellman, we rather have a split of \( t \) tables, each with a single sequential search. The winner in terms of how fast we search within the entire set of data to reverse a given hash is likely quite dependent of the system architecture, and how much it fits the software paralellization logic.

However, Rainbow tables win the \( Pr[success] \) since less compute is expected to be wasted during the pre-computation.

A third and final password Protocol

Having discussed the best password-based cryptanalysis algorithms, we now try to find a way to be safe from them. Recall the strength of these algorithms lie in the fact the entire research space need to be bruteforced only once (the pre-computation), and then they can enjoy significant reduction of compute effort to reverse any \( y \in Y \).

What if we could force somehow the size of \( X \) to be so large that no pre-computation on earth could ever produce even a tiny fraction of the search space? One method could to impose client-side constraint on the user to provide a password large enough and “random-looking”, but this is not user-friendly, and “random-looking” is difficult to enforce on a human being.

Another approach could be to add random values to the password provided by the user before hashing. If we select at random these values, and we do that for each user, it is equivalent to getting a random value from the user, in the sense we’re inflating the set \( X \). We just need to remember each of these random values, that is, storing this random value next to the hashed random+password. This is called a salt. It can be public, but needs to be unique for each user, otherwise we could compute a table accounting for a given random salt, and benefit for a speed-up to reverse more than one hash.

Note that the salt does not defend against bruteforce. We still need the initial password sent by the user to be within a set large enough such that a bruteforce is out of reach. Using a slow hashing function specific for password is also helpful, but there might be a careful tuning to do between preventing offline bruteforce and avoiding to facilitate online Distributed Denial of Service. If you’re curious, checkout Argon2.

So, here’s a third version of a our password protocol:

We update our key generation algorithm of protocol v0.2 using a salt, we have:

• \( G:= (sk, vk) = (pwd \overset{R}{\leftarrow} G(), (salt \overset{R}{\leftarrow} \{0, 1\}^n, H(salt+pwd)) \)

\( vk \) is a tuple (salt, hash).

The prover algorithm \( P \) stays unchanged, but we have to modify \( V \):

• \( V \) outputs accept if \( H(salt+pwd) == vk[1] \), or outputs rejects.