On Fri, Mar 30, 2012 at 01:54, Seth David Schoen <[email protected]> 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 [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
