# Vanitygen using short subphrases for CUDA

During the last week I have been working on a vanity generator for onion addresses on the TOR network. This blogpost is basically just a summary of my ideas.

The general idea is to split the work among several GPU units that performs the SHA-1 operations. Nothing new with that, this is done by Scallion [1]. Moreover, each core gets a small set of very short accepted subphrases. For instance,
$L$ = ['ac','bo','ca','ce','da','fa','ok'].

Using a clever technique called bucket hashing, we can achieve a fast look-up inside each thread. Once computed the hash, we mask out the $2^{2\cdot 5}$ MSB’s and shift down to $xy$. From a binary table $\mathbf{T}$ with $2^{10}$ entries, where a True-value is contained at the accepted subphrases of $L$ ($\mathbf{T}[ac] = \textnormal{True}$) and a False-value at the other positions ($\mathbf{T}[q3] = \textnormal{False}$).

We now chain the lookups in each thread. So for every two symbols, we perform a lookup and check the truth value in the table. If True, we continue the search until a stopping condition is satisfied. For instance, the lookups could be something like:

Such a path in the tree could yield 'fa'->'ce'->'bo'->'ok'.

The complexity for finding one such eight character .onion address would be $\mathcal{O}(2^{5\cdot N -1}/|L|^{N/2})$, where $N$ is length of the .onion.