Re: [tor-talk] Choosing a name for a .onon
On 2012-03-30, Asheesh Laroia ashe...@asheesh.org wrote: As the author of that asheesh.org note, I suggest you read it carefully. (-: After reading that note four times, I still see no details about your attack tool. In particular, pay attention to how key timestamps are used in OpenPGP! It's interesting and was surprising to me at first, too. Your note does not contain the word “timestamp”. According to RFC 4880, the key generation timestamp is near the beginning of the key blob. Thus, every time you change the timestamp, you need to re-hash a relatively long fixed string (the public modulus in an RSA key, or the group parameters in a DLP-based key). Changing the timestamp may be useful for DSA or ElGamal keys (I'm not convinced of that), but it's not helpful in generating an RSA key with chosen key ID. Robert Ransom ___ tor-talk mailing list tor-talk@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
Re: [tor-talk] Choosing a name for a .onon
On Thu, Mar 29, 2012 at 6:47 PM, Adrian Crenshaw irong...@irongeek.com wrote: Hi all, I was under the impression that the .onion names for Tor Hidden Services were pseudo-random based on the public key. How was someone able to choose one/choose some character in one? As an example: http://silkroadvb5piz3r.onion (hope it is not against policy to post that link, only example I know. ) How did they choose the first 8 characters? Using a brute force search tool like http://gitorious.org/shallot/shallot/ I'd advise against it— while I don't have a study to back me up I expect 'readable' names like that discourage good security practices— that they cause people to use addresses (spread in that look like yours, perhaps) without verifying the source— and when people do compare they are probably more likely to just compare the readable parts. sure, the computation is a bit of a barrier— but it's easier for the attacker (who may generate fake onions for many sites at once) then it is for the defender. ___ tor-talk mailing list tor-talk@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
Re: [tor-talk] Choosing a name for a .onon
Adrian Crenshaw writes: Hi all, I was under the impression that the .onion names for Tor Hidden Services were pseudo-random based on the public key. How was someone able to choose one/choose some character in one? As an example: http://silkroadvb5piz3r.onion (hope it is not against policy to post that link, only example I know. ) How did they choose the first 8 characters? The basic answer is try a lot of possibilities on a computer until the one you want comes up! According to https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=rend-spec.txt the .onion name is a base32-encoded version of the first 80 bits of the SHA1 of the hidden service public key. base32 is 5 bits per character, so the prefix silkroad in the .onion address above is 5×8=40 bits (indeed, exactly half of the 80 bits in the entire .onion name). 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. Since hash value searches are completely parallelizable, you can make this arbitrarily faster by adding more computers to the search. Of course this requires being able to change something trivial about the public key when generating the .onion address. (Generating a new public key from scratch would be very time-consuming; making a 1024-bit keypair from scratch on my machine takes around 0.1 second, depending on how lucky the key-generation process gets, which is considerably longer than the 0.003 seconds that trying a SHA1 operation requires.) I'm not sure exactly what you would change because I'm not sure what data is (or can be) included in a hidden service public key, but there's probably something you can change without actually needing to make a new keypair. There's a nice description of the possibility of creating a public key with a chosen set of bits at the beginning or end at http://www.asheesh.org/note/debian/short-key-ids-are-bad-news.html although note that the Tor hidden service identifiers are 80 bits, while PGP short key IDs are only 32 bits, so it's 2⁴⁸ times as hard to fake a hidden service as it is to make a colliding PGP short key ID. (Full PGP fingerprints are 160 bits.) I first got interested in this when I used to develop a live-CD called LNX-BBC (for bootable business card). At that time we were using MD5 checksums on our web site, and I wrote a program to try lots of possibilities so that all of our MD5 values started with bbcbbc in hexadecimal (on average only 2²⁴ MD5 attempts). For more on the base32 encoding, see https://en.wikipedia.org/wiki/Base32 -- Seth Schoen sch...@eff.org Senior Staff Technologist https://www.eff.org/ Electronic Frontier Foundation https://www.eff.org/join 454 Shotwell Street, San Francisco, CA 94110 +1 415 436 9333 x107 ___ tor-talk mailing list tor-talk@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
Re: [tor-talk] Choosing a name for a .onon
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. -- Maxim Kammerer Liberté 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
Re: [tor-talk] Choosing a name for a .onon
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
Re: [tor-talk] Choosing a name for a .onon
On 2012-03-30, Maxim Kammerer m...@dee.su wrote:
On Fri, Mar 30, 2012 at 06:06, Robert Ransom rransom.8...@gmail.com wrote:
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.
For some reason I thought that that would produce non-standard RSA
keys, perhaps because the old ssl-genrsa only supported e={3,65537}
(whereas the new ssl-genpkey doesn't have this limitation). Isn't the
point of e like 3 or 65537 (with few bits set) to make encryption
fast?
Yes. (Note that hidden service identity public keys are only used for
signature verification, which is not the same as encryption with any
modern padding scheme.)
But Tor didn't enforce that requirement for hidden service identity
keys soon enough, and I don't think OpenSSL's RSA implementation
benefits much from those particular choices of e (other than from the
fact that they're short).
Do you know whether Shallot-produced RSA keys have any
noticeable detrimental effect on relays load because of the
unrestricted exponent?
Maybe a little. No one will let Shallot run long enough to produce a
really big public exponent, though. (Relays raise 1024-bit numbers to
320-bit powers all the time for forward secrecy. Shallot won't
generate 320-bit public exponents.)
Maliciously generated hidden service identity keys could have much
larger public exponents, but hopefully no one will bother implementing
that DoS attack.
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.
Sure, but you don't have to do it in the most straightforward way. You
can multiply once, and then add 2p for each hash. The overhead for a
GPU / FPGA implementation should be negligible, and the search can be
parallelized as well.
Maybe. But note that the public exponent is stored at the end of the
public key blob, so updating the exponent (or a piece of it) also
makes generating each hash easier.
If adding large multiples of p, the nodes can be
untrusted, too, I guess.
No -- the Euclidean algorithm would break that *very* quickly.
Robert Ransom
___
tor-talk mailing list
tor-talk@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
