search

google / keytransparency

A transparent and secure way to look up public keys.
https://security.googleblog.com/2017/01/security-through-transparency.html
Apache License 2.0
1.58k stars 151 forks source link

Remove TreeNonce? #65

Closed andres-erbsen closed 9 years ago

andres-erbsen commented 9 years ago

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?

gdbelvin commented 9 years ago

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 notifications@github.com 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 https://github.com/google/e2e-key-server/issues/65.

Gary Belvin | Software Engineer | gdb@google.com | Security Team

andres-erbsen commented 9 years ago

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?

gdbelvin commented 9 years ago

+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 notifications@github.com 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 | gdb@google.com | Security Team

jcb82 commented 9 years ago

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 notifications@github.com 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 notifications@github.com 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 | gdb@google.com | Security Team

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

jcb82 commented 9 years ago

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 jbonneau@gmail.com 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 notifications@github.com 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 <notifications@github.com

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 | gdb@google.com | Security Team

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

cesarghali commented 9 years ago

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

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

Where:

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.

gdbelvin commented 9 years ago

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 notifications@github.com 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 https://github.com/google/e2e-key-server/issues/65#issuecomment-137175672 .

Gary Belvin | Software Engineer | gdb@google.com | Security Team

jcb82 commented 9 years ago

On Wed, Sep 2, 2015 at 10:43 AM, Gary Belvin notifications@github.com 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

cesarghali commented 9 years ago

Nonce is removed in #131.