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,
. = ['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 MSB’s and shift down to
. From a binary table
with
entries, where a True-value is contained at the accepted subphrases of
(
) and a False-value at the other positions (
).
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 , where
is length of the .onion.