Re: [tor-talk] Choosing a name for a .onon

[Robert Ransom <rransom.8774@xxxxxxxxx>]

On 2012-03-30, Maxim Kammerer <mk@xxxxxx> wrote:
> On Fri, Mar 30, 2012 at 01:54, Seth David Schoen <schoen@xxxxxxx> wrote:
>> Choosing the first 40 bits of a hash generally requires trying an average
>> of 2ââ
>> possibilities; my laptop does about 3-4 million SHA1 operations per second
>> (per CPU core) so it would take me 3-4 days (per CPU core) of computation
>> to try that many possibilities on my laptop.
>
> Due to proliferation of Bitcoin, there are now very efficient SHA-256
> generators for off-the-shelf GPUs. The numbers at [1] suggest
> performance that's at least two orders of magnitude faster than your
> laptop â and for double-SHA-256 instead of a single SHA-1 (which I
> assume can be done by the same software after some simple adaptation).
>
> [1] https://en.bitcoin.it/wiki/Mining_hardware_comparison
>
>> Of course this requires being able to change something trivial about the
>> public key when generating the .onion address.
>
> Not necessarily â you can generate the hash first, and then check
> whether the public key is legal. I.e., generate a 512-bit prime p, and
> then go on with producing a completely random 512-bit e, and checking
> whether SHA-1(ASN.1-RSAPublicKey(modulus=p*e, exponent=65537)) (which
> is how Tor computes the .onion address) produces the desired result.
> If it does, check whether e is prime. Density of primes in the range
> of e is ~1/512, so that's just 9 bits more of search space, and
> primality checking efficiency doesn't matter much.

Shallot computes a single public modulus p*q and searches for a public
exponent e which produces a SHA-1 hash with the desired properties.
That's much faster than doing a 512-bit-by-512-bit bignum multiply for
each hash, *and* the search for a suitable exponent could (in theory)
be performed in parallel across many (untrusted) computers.


Robert Ransom
_______________________________________________
tor-talk mailing list
tor-talk@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk