Remove TreeNonce? about keytransparency HOT 9 CLOSED

The purpose of the per-merkle-tree nonce is the prevent a leaf node from
one tree being valid in another. Follow up with jbonneau to see if there's
a safe way to remove this requirement.

On Fri, Aug 14, 2015 at 12:52 PM, Andres Erbsen [email protected]
wrote:

IIRC, the purpose of the per-merkle-tree nonce was to allow the provider
to change the tree structure between epochs, aiming to prevent direct
differential measurements of the churn of the userbase. As our tree
structure is public anyway, rerandomizing it does not make sense. And the
MerkleTree interface (and impl) would be simpler without that parameter.
Is there any reason that I am missing why we still need it?

—
Reply to this email directly or view it on GitHub
#65.

Gary Belvin | Software Engineer | [email protected] | Security Team

from keytransparency.

A leaf with contents x (including the index and nonce, which a good user would pick randomly anyway) is indeed valid regardless of the context, and any tree can include it. Is there a reason we want to avoid that?

from keytransparency.

+jbonneau

Joe, We're taking a second look at what security property the TreeNonce
provides.
If individual leaf nodes should be valid no matter what tree they are in,
what value does the TreeNonce provide?

-Gary

On Fri, Aug 21, 2015 at 10:01 AM, Andres Erbsen [email protected]
wrote:

A leaf with contents x (including the index and nonce, which a good user
would pick randomly anyway) is indeed valid regardless of the context, and
any tree can include it. Is there a reason we want to avoid that?

—
Reply to this email directly or view it on GitHub
#65 (comment)
.

Gary Belvin | Software Engineer | [email protected] | Security Team

from keytransparency.

This is mostly an issue of avoiding a "certificational weakness" of the
crypto.

If you don't include this nonce, then if you manage to find two colliding
entries for me ie H("jcb", K) = H("jcb", K') you can use these to MITM me
at any tree where jcb is registered.

It's not entirely unreasonable to say "we're screwed if collisions like
that can be found" but stuff like this is standard to ensure you squeeze
every possible possible bit of security out of the underlying primitives

On Fri, Aug 21, 2015 at 10:08 AM, Gary Belvin [email protected]
wrote:

+jbonneau

Joe, We're taking a second look at what security property the TreeNonce
provides.
If individual leaf nodes should be valid no matter what tree they are in,
what value does the TreeNonce provide?

-Gary

On Fri, Aug 21, 2015 at 10:01 AM, Andres Erbsen [email protected]
wrote:

A leaf with contents x (including the index and nonce, which a good user
would pick randomly anyway) is indeed valid regardless of the context,
and
any tree can include it. Is there a reason we want to avoid that?

—
Reply to this email directly or view it on GitHub
<
https://github.com/google/e2e-key-server/issues/65#issuecomment-133495013>
.

Gary Belvin | Software Engineer | [email protected] | Security Team

—
Reply to this email directly or view it on GitHub
#65 (comment)
.

from keytransparency.

Separate issue: Andres mentioned "the tree structure is public" so
re-randomizing doesn't make sense. I'm not sure I follow

On Fri, Aug 21, 2015 at 10:13 AM, Joseph Bonneau [email protected] wrote:

This is mostly an issue of avoiding a "certificational weakness" of the
crypto.

If you don't include this nonce, then if you manage to find two colliding
entries for me ie H("jcb", K) = H("jcb", K') you can use these to MITM me
at any tree where jcb is registered.

It's not entirely unreasonable to say "we're screwed if collisions like
that can be found" but stuff like this is standard to ensure you squeeze
every possible possible bit of security out of the underlying primitives

On Fri, Aug 21, 2015 at 10:08 AM, Gary Belvin [email protected]
wrote:

+jbonneau

Joe, We're taking a second look at what security property the TreeNonce
provides.
If individual leaf nodes should be valid no matter what tree they are in,
what value does the TreeNonce provide?

-Gary

On Fri, Aug 21, 2015 at 10:01 AM, Andres Erbsen <[email protected]

wrote:

A leaf with contents x (including the index and nonce, which a good user
would pick randomly anyway) is indeed valid regardless of the context,
and
any tree can include it. Is there a reason we want to avoid that?

—
Reply to this email directly or view it on GitHub
<
#65 (comment)

.

Gary Belvin | Software Engineer | [email protected] | Security Team

—
Reply to this email directly or view it on GitHub
#65 (comment)
.

from keytransparency.

Currently, this is how a leaf node's value is calculated:

Hash(N = TreeNonce, L = LeafIdentifier, D = Depth, I = Index, HE = Hash(Entry))

Where:

• Hash: is a SHA-256 hash function.
• TreeNonce is a 16 byte random nonce.
• LeafIdentifier is a fixed one byte identifying a leaf.
• Depth: is the depth of the leaf node.
• Index: is the index of the leaf node which is the output of the VUF function.
• Entry: is the the entry update which contains the profile commitment. The profile commitment is computed as the SHA-512 of the profile and its nonce.

I think, and correct me if I'm wrong, we should be fine whether we use or we don't use the TreeNonce.

Also, I agree with @jcb82 that if a collision has been found, we're screwed with and without TreeNonce.

from keytransparency.

The thinking here is that each tree will have it's own VUF, so a collision
in one tree wouldn't be applicable for the same user in another tree.

On Wed, Sep 2, 2015 at 10:14 AM, Cesar Ghali [email protected]
wrote:

Currently, this is how a leaf node's value is calculated:

Hash(N = TreeNonce, L = LeafIdentifier, D = Depth, I = Index, HE = Hash(Entry))

Where:

• Hash: is a SHA-256 hash function.
• TreeNonce is a 16 byte random nonce.
• LeafIdentifier is a fixed one byte identifying a leaf.
• Depth: is the depth of the leaf node.
• Index: is the index of the leaf node which is the output of the VUF
  function.
• Entry: is the the entry update which contains the profile
  commitment. The profile commitment is computed as the SHA-512 of the
  profile and its nonce.

I think, and correct me if I'm wrong, we should be fine whether we use or
we don't use the TreeNonce.

Also, I agree with @jcb82 https://github.com/jcb82 that if a collision
has been found, we're screwed with and without TreeNonce.

—
Reply to this email directly or view it on GitHub
#65 (comment)
.

Gary Belvin | Software Engineer | [email protected] | Security Team

from keytransparency.

On Wed, Sep 2, 2015 at 10:43 AM, Gary Belvin [email protected]
wrote:

The thinking here is that each tree will have it's own VUF, so a collision
in one tree wouldn't be applicable for the same user in another tree.

Yes this is a good point. If two trees don't use different VUF's they could
use the same Tree Nonce just as easily. So TreeNonce can probably be
dropped as long as the VUF is in place. But it also doesn't really hurt too
much to keep it around

from keytransparency.

Nonce is removed in #131.

from keytransparency.