On Mon, 13 Sep 2010 00:26:02 -0400 Gregory Maxwell <gmaxwell@xxxxxxxxx> wrote: > On Mon, Sep 13, 2010 at 12:11 AM, Robert Ransom <rransom.8774@xxxxxxxxx> wrote: > >> There we goâ > >> Perhaps the signature could be shipped only to the directory > >> authorities but left out of the published descriptors, no? > > No, the client needs to see it in the relay/bridge descriptor. > >> they'd need to be left outside of the part signed by the nodes, so > >> obviously some reworking is required there). > > Why? > > The client needs to see the public key for sure, since thats > effectively a family ID. Does it need to see the signature if instead > it trusts the bridges to have validated the signatures and correctly s/bridges/authorities/, I assume. > ignored/invalidated only and all the nodes with invalid signatures? > > If that was workable it would halve the amount of advertised data required. It's better to not rely on any trusted third party any more than we absolutely have to. For this, we don't need a TTP at all, so we shouldn't rely on one. > > Don't forget that the keys and signatures would need to be represented > > in ASCII in the descriptors. ÂIf you're willing to break backward > > compatibility anyway, there is some room for squeezing the existing > > family specifications down, as well (i.e. represent node identity key > > fingerprints in base64, or even base85 (only the clients should care > > about it, and they can probably eat the performance cost)). > > I was assuming hex, like the current families. 512/160=3.2 Obviously > base>16 would do even better... With smaller ecc and base85 it would > be rather close in size to the existing fingerprints. (assuming the > signature was omitted) OK. The signature system I had in mind was essentially the system in Â4 of <http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf> (the system proved at least as hard as DDH), with an added space optimization (mainly, compute h as a hash of y1, and publish only y1 and y2). On a curve modulo a 159-bit prime, a signature and its public key fit in a total of about 640 bits. The only system I know of with a shorter signature is the Boneh-Lynn-Shacham pairing-based scheme, with 160-bit signatures and a 512-bit public key, and in this application that's not a space improvement (total size: 672 bits per descriptor). > > Also, don't forget that we can use an elliptic curve modulo a 159-bit > > prime for this -- node family keys are relatively low-value > > authentication keys, and since they would only be used to sign nodes' > > ephemeral *signing* keys, they can be changed with rather little trouble. > > Agreed, that they can be small. Though changing them would require > per-node configuration. They ought to at least be strong enough to > discourage mischief, though 159-bit is still harder than anything that > I'm aware of being cracked and would probably leave guessing the > secret as the low hanging fruit. I think Dr. Bernstein is currently attacking a curve of about 130-bit order. Even using that curve for this purpose would discourage mischief: it's still quite hard to find the secret key, and even if you do find it, it's not very useful, or for very long. As I said, family secret keys would be low-value authentication keys, and it is easy to make a compromised family key useless (just stop using it). Unless the operator does something *really* dumb like use an easily guessed character string as his secret (and we can make that difficult by requiring that it be specified as exactly N base64 characters, possibly with a checksum prepended by whatever tool we provide to generate family keys), it's much faster to use an attack based on the group structure. There are elliptic-curve groups for which the only known algorithms to solve the discrete-logarithm problem are group-generic (i.e., they work on any cyclic group), and the group-generic methods take time proportional to the square root of the group order. Brute-force guessing takes time proportional to the group order itself. Robert Ransom
Attachment:
signature.asc
Description: PGP signature