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:

treeadj

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.

[1] https://github.com/lachesis/scallion

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s