On 2012-03-30, Maxim Kammerer <m...@dee.su> wrote: > On Fri, Mar 30, 2012 at 01:54, Seth David Schoen <sch...@eff.org> 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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk