On Fri, Mar 30, 2012 at 01:54, Seth David Schoen <schoen@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@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