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

[Maxim Kammerer <mk@xxxxxx>]

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.

-- 
Maxim Kammerer
Libertà Linux (discussion / support: http://dee.su/liberte-contribute)
_______________________________________________
tor-talk mailing list
tor-talk@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk