Re: When is the 'MyFamily' setting unnecessary?

[tor_ml]

On 09/13/2010 12:53 AM, and...@torproject.org wrote:

On Sun, Sep 12, 2010 at 02:38:18PM +0200, tor...@ymail.com wrote 1.1K bytes in 
31 lines about:

If it is technically not necessary, because tor would never use certain
nodes in one circuit. I would understand people running>20 nodes that
do not use 'MyFamily'.


It's easy, put all 20 nodes in the MyFamily line and just use that line
for all 20 nodes.


This is not about me. I sometimes ask tor node admins that run many 
nodes to set MyFamily. Then I get a reply "it is not necessary".
If I knew that it is not necessary I wouldn't contact them in the first 
place.


example:
1f94aaf1774d6d9e4c4b7bd242c3dc592c49db00 Pandora19
1fd8ad0a32bd4aaacf9180fd3870c87b6b463ca0 bizarre

I believe Jake, when he says that these nodes would never be used in the 
same circuit, but I would like to know why - just to avoid asking the 
next tor node admin in a similar case.



If there are certain rules I would stop asking people to set MyFamily if
one of these rules apply in the concrete scenario.

So there are no rules beside the "/16 network" - rule?


Perhaps it depends on what you mean by "rule".  The /16 network
diversity is in the tor source code.


Yes I mean the behaviour of the official tor software.


There are other proposals in the
mix for circuits to contain a unique AS and/or a unique continent per
node.


***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[Robert Ransom]

On Mon, 13 Sep 2010 00:26:02 -0400
Gregory Maxwell  wrote:

> On Mon, Sep 13, 2010 at 12:11 AM, Robert Ransom  
> 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
 (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


signature.asc
Description: PGP signature

Re: When is the 'MyFamily' setting unnecessary?

[Gregory Maxwell]

On Mon, Sep 13, 2010 at 12:11 AM, Robert Ransom  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
ignored/invalidated only and all the nodes with invalid signatures?

If that was workable it would halve the amount of advertised data required.

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

> 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.
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[Robert Ransom]

On Sun, 12 Sep 2010 23:36:30 -0400
Gregory Maxwell  wrote:

> On Sun, Sep 12, 2010 at 9:40 PM, Robert Ransom  wrote:
> > That's the wrong approach.  The config file should contain a random
> > secret key shared among all relays in a family, and the relays should
> > publish in their descriptors a public key derived from that secret key
> > along with a signature of the relay's current signing key with that
> > secret key.  With DJB's Curve25519 elliptic-curve parameters, the
> > public key can take only 511 bits, and the signature can take only 506
> > bits.  A smaller curve could fit the public key into 319 bits and the
> > signature into about 320 bits (the precise size would be determined by
> > the group order).
> >
> > This would not be backward-compatible with existing clients, but it
> > avoids the current quadratic blowup in both the config files and the
> > total descriptor size.
> 
> 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.

>(obviously
> they'd need to be left outside of the part signed by the nodes, so
> obviously some reworking is required there).

???

Why?

>  Directories would ignore
> nodes that claim families that they can't back up with a valid
> signature. This would open up some attacks by a conspiracy of evil
> directories but it would be detectable and no worse than other kinds
> of attacks available to similarly compromised directories.

I don't see how it could open up any *new* attacks -- the directory
authorities can already ignore relays, or mark them as Invalid, with
near impunity.

> With the signatures left out of the descriptor and 511 bit keys the
> break-even point for descriptor size is four nodes in a family.  A
> very quick check with my cached descriptor data locally suggests that
> this would reduce the aggregate descriptor size significantly compared
> to the current scheme.  (there are enough families with _many_ nodes,
> to offset the fact that most families are small)

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

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.


Robert Ransom


signature.asc
Description: PGP signature

Re: When is the 'MyFamily' setting unnecessary?

[Sebastian Hahn]

On Sep 13, 2010, at 5:36 AM, Gregory Maxwell wrote:

Making families more scalable would also admit things like semi-public
families.  E.g. you could share a family key with all the node
operators in a common building. Detecting things like same network can
be done automatically with enough reliability, likewise for very
coarse geographies, but fine geographical configuration would take
manual intervention... I don't know if anyone would bother configuring
this, but it would be nice if the system scaled well enough to support
it.


There are other neat things you could do. A node can suddenly start
belonging to more than one familty, so that I might put all my own
nodes in one family, and then that one node that another guy has
access too can be put in his family, too.

This all needs a solid design and a proposal, but I think if you
manage to build it in a way that is easy to set up for operators
this might have a chance in the future (obviously you'd need to
wait with actually using it until client versions that don't understand
it are obsolete, but that is just an argument for starting the proposal
quickly).

Sebastian

***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[Gregory Maxwell]

On Sun, Sep 12, 2010 at 9:40 PM, Robert Ransom  wrote:
> That's the wrong approach.  The config file should contain a random
> secret key shared among all relays in a family, and the relays should
> publish in their descriptors a public key derived from that secret key
> along with a signature of the relay's current signing key with that
> secret key.  With DJB's Curve25519 elliptic-curve parameters, the
> public key can take only 511 bits, and the signature can take only 506
> bits.  A smaller curve could fit the public key into 319 bits and the
> signature into about 320 bits (the precise size would be determined by
> the group order).
>
> This would not be backward-compatible with existing clients, but it
> avoids the current quadratic blowup in both the config files and the
> total descriptor size.

There we go—

Perhaps the signature could be shipped only to the directory
authorities but left out of the published descriptors, no? (obviously
they'd need to be left outside of the part signed by the nodes, so
obviously some reworking is required there). Directories would ignore
nodes that claim families that they can't back up with a valid
signature. This would open up some attacks by a conspiracy of evil
directories but it would be detectable and no worse than other kinds
of attacks available to similarly compromised directories.

With the signatures left out of the descriptor and 511 bit keys the
break-even point for descriptor size is four nodes in a family.  A
very quick check with my cached descriptor data locally suggests that
this would reduce the aggregate descriptor size significantly compared
to the current scheme.  (there are enough families with _many_ nodes,
to offset the fact that most families are small)

Making families more scalable would also admit things like semi-public
families.  E.g. you could share a family key with all the node
operators in a common building. Detecting things like same network can
be done automatically with enough reliability, likewise for very
coarse geographies, but fine geographical configuration would take
manual intervention... I don't know if anyone would bother configuring
this, but it would be nice if the system scaled well enough to support
it.
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[Robert Ransom]

On Sun, 12 Sep 2010 20:28:33 -0400
Gregory Maxwell  wrote:

> Has anyone previously suggested using a shared secret for family
> configuration?  The protocol might look something like this:
> 
> The user configures a secret per family which the node is a member of.
> For each family the secret is processed with key strengthening (such
> as PBKDF2 or, better, scrypt) and a (say) 64-bit family ID and a
> 128-bit family-key are derived.  Nodes publish the family IDs.  Upon
> discovering a new node with a common family ID the node contacts the
> matching node and uses the non-advertised family key in a handshake
> (this could be a zero knowledge protocol like socialist millionaires
> or just encrypting a concatenation of nodeIDs and nonces) to prove
> that the key is shared.  After proving the secret is really shared the
> nodes store the results and update their family advertisements.
> 
> This would simplify family configuration down to setting a single
> common secret string per family but wouldn't create any change in
> behaviour for non-family nodes and could also exist side by side with
> the old mechanism.

That's the wrong approach.  The config file should contain a random
secret key shared among all relays in a family, and the relays should
publish in their descriptors a public key derived from that secret key
along with a signature of the relay's current signing key with that
secret key.  With DJB's Curve25519 elliptic-curve parameters, the
public key can take only 511 bits, and the signature can take only 506
bits.  A smaller curve could fit the public key into 319 bits and the
signature into about 320 bits (the precise size would be determined by
the group order).

This would not be backward-compatible with existing clients, but it
avoids the current quadratic blowup in both the config files and the
total descriptor size.


Robert Ransom


signature.asc
Description: PGP signature

Re: When is the 'MyFamily' setting unnecessary?

[Gregory Maxwell]

On Sun, Sep 12, 2010 at 6:53 PM,   wrote:
> On Sun, Sep 12, 2010 at 02:38:18PM +0200, tor...@ymail.com wrote 1.1K bytes 
> in 31 lines about:
>> If it is technically not necessary, because tor would never use certain
>> nodes in one circuit. I would understand people running >20 nodes that
>> do not use 'MyFamily'.
>
> It's easy, put all 20 nodes in the MyFamily line and just use that line
> for all 20 nodes.
>
>> If there are certain rules I would stop asking people to set MyFamily if
>> one of these rules apply in the concrete scenario.
>>
>> So there are no rules beside the "/16 network" - rule?
>
> Perhaps it depends on what you mean by "rule".  The /16 network
> diversity is in the tor source code.  There are other proposals in the
> mix for circuits to contain a unique AS and/or a unique continent per
> node.

A unique AS would be a much better restriction than unique /16...
unique /16 is really just a weak proxy for unique AS.

Even ignoring the other useful disclosure properties of myfamily you
shouldn't skip disclosing the family even if the nodes are in the same
/16 simply because that restriction may be replaced with another one
(e.g. same ASN) in the future.

It is a bit unfortunate that myfamily adds a fair bit of configuration
load (N^2) as the number of nodes becomes large, it's especially
annoying if you slowly add nodes to a family since you have to go back
and hit the all the other configurations for every node you add.

Has anyone previously suggested using a shared secret for family
configuration?  The protocol might look something like this:

The user configures a secret per family which the node is a member of.
For each family the secret is processed with key strengthening (such
as PBKDF2 or, better, scrypt) and a (say) 64-bit family ID and a
128-bit family-key are derived.  Nodes publish the family IDs.  Upon
discovering a new node with a common family ID the node contacts the
matching node and uses the non-advertised family key in a handshake
(this could be a zero knowledge protocol like socialist millionaires
or just encrypting a concatenation of nodeIDs and nonces) to prove
that the key is shared.  After proving the secret is really shared the
nodes store the results and update their family advertisements.

This would simplify family configuration down to setting a single
common secret string per family but wouldn't create any change in
behaviour for non-family nodes and could also exist side by side with
the old mechanism.
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[andrew]

On Sun, Sep 12, 2010 at 02:38:18PM +0200, tor...@ymail.com wrote 1.1K bytes in 
31 lines about:
> If it is technically not necessary, because tor would never use certain  
> nodes in one circuit. I would understand people running >20 nodes that  
> do not use 'MyFamily'.

It's easy, put all 20 nodes in the MyFamily line and just use that line
for all 20 nodes.

> If there are certain rules I would stop asking people to set MyFamily if  
> one of these rules apply in the concrete scenario.
>
> So there are no rules beside the "/16 network" - rule?

Perhaps it depends on what you mean by "rule".  The /16 network
diversity is in the tor source code.  There are other proposals in the
mix for circuits to contain a unique AS and/or a unique continent per
node.

-- 
Andrew Lewman
The Tor Project
pgp 0x31B0974B
+1-781-352-0568

Website: https://www.torproject.org/
Blog: https://blog.torproject.org/
Identi.ca: torproject
Skype:  lewmanator
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[tor_ml]

On 09/12/2010 02:11 PM, Sebastian Hahn wrote:


On Sep 12, 2010, at 1:24 PM, tor_ml wrote:


Hi,

I'm curious in which cases tor would _never_ use certain nodes to
create one circuit and therefore makes the 'MyFamily' setting
unnecessary.

I heard only of one "rule" (I guess on this list but I'm not sure):
- tor would not use nodes within the same /16 network to create a circuit

are there more such rules?


There currently aren't.

Even if all the nodes you run are in the same /16 it is considered
polite to set MyFamily though, to make the link of owners explicit.


If it is technically not necessary, because tor would never use certain 
nodes in one circuit. I would understand people running >20 nodes that 
do not use 'MyFamily'.


If there are certain rules I would stop asking people to set MyFamily if 
one of these rules apply in the concrete scenario.


So there are no rules beside the "/16 network" - rule?
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

Re: When is the 'MyFamily' setting unnecessary?

[Sebastian Hahn]

On Sep 12, 2010, at 1:24 PM, tor_ml wrote:


Hi,

I'm curious in which cases tor would _never_ use certain nodes to  
create one circuit and therefore makes the 'MyFamily' setting  
unnecessary.


I heard only of one "rule" (I guess on this list but I'm not sure):
- tor would not use nodes within the same /16 network to create a  
circuit


are there more such rules?


There currently aren't.

Even if all the nodes you run are in the same /16 it is considered
polite to set MyFamily though, to make the link of owners explicit.

Sebastian

***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/

When is the 'MyFamily' setting unnecessary?

[tor_ml]

Hi,

I'm curious in which cases tor would _never_ use certain nodes to create 
one circuit and therefore makes the 'MyFamily' setting unnecessary.


I heard only of one "rule" (I guess on this list but I'm not sure):
- tor would not use nodes within the same /16 network to create a circuit

are there more such rules?
***
To unsubscribe, send an e-mail to majord...@torproject.org with
unsubscribe or-talkin the body. http://archives.seul.org/or/talk/