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

[Maxim Kammerer]

On Fri, Mar 30, 2012 at 01:54, Seth David Schoen <schoen at eff.org> wrote:
> Choosing the first 40 bits of a hash generally requires trying an average of 2b
4b
0
> 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 b 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 b 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
LibertC) Linux (discussion / support: http://dee.su/liberte-contribute)
_______________________________________________
tor-talk mailing list
tor-talk at lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE