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

[Robert Ransom <rransom.8774@xxxxxxxxx>]

On 2012-03-30, Maxim Kammerer <mk@xxxxxx> wrote:
> On Fri, Mar 30, 2012 at 06:06, Robert Ransom <rransom.8774@xxxxxxxxx> 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@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk