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

[Robert Ransom]

On 2012-03-29, Seth David Schoen <schoen at eff.org> wrote:

> 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.)

In the old-style (PGP 2.x) key ID format, a portion of the public RSA
modulus was directly used as the key ID.  The most
difficult-to-implement algorithm that you could possibly want to use
to attack that involves a lattice computation, and succeeds far faster
than brute-force.

New-style (OpenPGP) key IDs are hashes of the public key; the only
attack that can produce a desired key ID is brute-force search.
(That's not hard though -- for RSA, generate a keypair in the usual
manner, then change the public exponent (as Shallot does); for DSA or
ElGamal, generate a keypair and then search for powers of the group
generator and of the public key which lead to the desired hash.  Both
attacks allow the brute-force search to be performed on computers
which cannot be trusted to know the private key.)

So yes, short PGP key IDs are very bad news.  Avoid them if you can
(but I doubt that you can).


Robert Ransom