v.io/syncbase/x/ref/services/syncbase/signing: Add signing mechanism to allow for syncbase updates to be signed.
This chaange adds mechanisms to allow syncbase to sign the upadtes
made by its clients so that when these updates are received by other
syncgroup members, the signatures can be checked.
The primary interface is in
v.io/syncbase/x/ref/services/syncbase/signing
It is significantly more complicated than one might wish. See the
comment at the top of signing/signing.go for the rationale.
Suggestions on how to relieve the various issues in simpler ways
would be welcome.
Suggested reviewing order:
Read the comment at the top of signing/signing.go for an overview.
Then bottom up:
signing/krl
- a placeholder key revocation list. I added this just so if we
ever get such a thing, we know where the calls will go.
signing/hashcache
- a simple cache for data that can be reused across signatures
signing
- The primary interface that signs and checks data. The test
contains various benchmarks, and shows how the interface is
expected to be used by the various participating syncbase
servers.
- the validationcache.go module uses signing/hashcache to cache particular
types of data. Performs all the marshalling and hashing that would
otherwise be repeated per signature. It's in the same package as
signing.go because the two share types.
Change-Id: I4a830b4811ffa63cb9391261a2c35fd77da60ba6
diff --git a/x/ref/services/syncbase/signing/hashcache/hashcache.go b/x/ref/services/syncbase/signing/hashcache/hashcache.go
new file mode 100644
index 0000000..26e8c94
--- /dev/null
+++ b/x/ref/services/syncbase/signing/hashcache/hashcache.go
@@ -0,0 +1,77 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package hashcache implements a simple cache intended to be indexed by hash
+// values. The keys are of type []byte. Values are arbitrary interface{}
+// values. Entries may expire if not used for a duration specified by the
+// client.
+package hashcache
+
+import "sync"
+import "time"
+
+// An internalValue is the client's data plus the data's expiry time.
+type internalValue struct {
+ data interface{}
+ expiry time.Time
+}
+
+// A Cache allows the user to store arbitrary values, keyed by the contents of
+// byte vectors. Entries may be added, deleted, and looked up. They may
+// expire if not used.
+type Cache struct {
+ expiry time.Duration
+ mu sync.Mutex // protects fields below.
+ entries map[string]*internalValue
+ insertionsSinceGC int // number of insertions since last GC
+}
+
+// New() returns a pointer to a new, empty Cache.
+// Entries may expire if not used for "expiry".
+func New(expiry time.Duration) *Cache {
+ return &Cache{expiry: expiry, entries: make(map[string]*internalValue)}
+}
+
+// Lookup() returns the data associated with key[] in *c, and whether there is
+// such a value. The client may not modify the returned data; it is shared
+// with *c.
+func (c *Cache) Lookup(key []byte) (data interface{}, isPresent bool) {
+ var value *internalValue
+ c.mu.Lock()
+ value, isPresent = c.entries[string(key)]
+ if isPresent {
+ value.expiry = time.Now().Add(c.expiry)
+ data = value.data
+ }
+ c.mu.Unlock()
+ return data, isPresent
+}
+
+// Add() associates data with key[] in *c. Any data previously associated with
+// key[] are forgotten. The implementation may discard the association at some
+// future time (set by NewCache()) to limit the size of the cache. data may
+// not be modified after this call; it is shared with *c.
+func (c *Cache) Add(key []byte, data interface{}) {
+ c.mu.Lock()
+ now := time.Now()
+ c.entries[string(key)] = &internalValue{data: data, expiry: now.Add(c.expiry)}
+ c.insertionsSinceGC++
+ // Scan to expire entries if 20% were added since last scan.
+ if c.insertionsSinceGC*5 > len(c.entries) {
+ for ik, iv := range c.entries {
+ if iv.expiry.Before(now) {
+ delete(c.entries, ik)
+ }
+ }
+ c.insertionsSinceGC = 0
+ }
+ c.mu.Unlock()
+}
+
+// Delete() removes any association of data with key[] in *c.
+func (c *Cache) Delete(key []byte) {
+ c.mu.Lock()
+ delete(c.entries, string(key))
+ c.mu.Unlock()
+}
diff --git a/x/ref/services/syncbase/signing/hashcache/hashcache_test.go b/x/ref/services/syncbase/signing/hashcache/hashcache_test.go
new file mode 100644
index 0000000..96ba865
--- /dev/null
+++ b/x/ref/services/syncbase/signing/hashcache/hashcache_test.go
@@ -0,0 +1,83 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package hashcache_test tests the hashcache package.
+package hashcache_test
+
+import "runtime"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/hashcache"
+
+// checkHashesWithNoData() checks that hash[start:] have no data in the cache.
+// (The start index is passed, rather than expecting the caller to sub-slice,
+// so that error messages refer to the index.)
+func checkHashesWithNoData(t *testing.T, cache *hashcache.Cache, start int, hash [][]byte) {
+ _, _, callerLine, _ := runtime.Caller(1)
+ for i := start; i != len(hash); i++ {
+ value, found := cache.Lookup(hash[i])
+ if value != nil || found {
+ t.Errorf("line %d: unset cache entry hash[%d]=%v has value %v, but is expected not to be set", callerLine, i, hash[i], value)
+ }
+ }
+}
+
+func TestCache(t *testing.T) {
+ hash := [][]byte{
+ []byte{0x00, 0x01, 0x02, 0x3},
+ []byte{0x04, 0x05, 0x06, 0x7},
+ []byte{0x08, 0x09, 0x0a, 0xb}}
+ var value interface{}
+ var found bool
+ var want string
+
+ cache := hashcache.New(5 * time.Second)
+
+ // The cache should initially have none of the keys.
+ checkHashesWithNoData(t, cache, 0, hash)
+
+ // Add the first key, and check that it's there.
+ want = "hash0"
+ cache.Add(hash[0], want)
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ checkHashesWithNoData(t, cache, 1, hash)
+
+ // Add the second key, and check that both it and the first key are there.
+ want = "hash1"
+ cache.Add(hash[1], want)
+ value, found = cache.Lookup(hash[1])
+ if s, ok := value.(string); !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 1, hash[1], s, want)
+ }
+ want = "hash0"
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ checkHashesWithNoData(t, cache, 2, hash)
+
+ // Wait for all entries to time out.
+ time.Sleep(6 * time.Second) // sleep past expiry time
+
+ // Add the first key again, and so many that it will trigger garbage
+ // collection.
+ for i := 0; i != 10; i++ {
+ want = "hash0 again"
+ cache.Add(hash[0], want)
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ }
+ // The entry for hash1 should have expired, since the expiry time has
+ // passed, and many things have been inserted into the cache.
+ checkHashesWithNoData(t, cache, 1, hash)
+
+ cache.Delete(hash[0])
+ checkHashesWithNoData(t, cache, 0, hash)
+}
diff --git a/x/ref/services/syncbase/signing/krl/krl.go b/x/ref/services/syncbase/signing/krl/krl.go
new file mode 100644
index 0000000..422f53e
--- /dev/null
+++ b/x/ref/services/syncbase/signing/krl/krl.go
@@ -0,0 +1,39 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package krl implements a trivial, in-memory key revocation list.
+// It is a placeholder for a real key revocation mechanism.
+package krl
+
+import "crypto/sha256"
+import "time"
+
+// A KRL is a key revocation list. It maps the hashes of keys that have been revoked
+// to revocation times.
+type KRL struct {
+ table map[[sha256.Size]byte]time.Time
+}
+
+var notYetRevoked = time.Now().Add(100 * 365 * 24 * time.Hour) // far future
+
+// New() returns a pointer to a new, empty key recovation list.
+func New() *KRL {
+ return &KRL{table: make(map[[sha256.Size]byte]time.Time)}
+}
+
+// Revoke() inserts an entry into *krl recording that key[] was revoked at time
+// "when".
+func (krl *KRL) Revoke(key []byte, when time.Time) {
+ krl.table[sha256.Sum256(key)] = when
+}
+
+// RevocationTime() returns the revocation time for key[].
+// If key[] is not in the list, a time in the far future is returned.
+func (krl *KRL) RevocationTime(key []byte) (whenRevoked time.Time) {
+ var found bool
+ if whenRevoked, found = krl.table[sha256.Sum256(key)]; !found {
+ whenRevoked = notYetRevoked
+ }
+ return whenRevoked
+}
diff --git a/x/ref/services/syncbase/signing/krl/krl_test.go b/x/ref/services/syncbase/signing/krl/krl_test.go
new file mode 100644
index 0000000..73f48ad
--- /dev/null
+++ b/x/ref/services/syncbase/signing/krl/krl_test.go
@@ -0,0 +1,54 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package krl tests the key revocation list package.
+package krl_test
+
+import "runtime"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+
+// checkKeysNotRevoked() checks that key[start:] have not been revoked. (The
+// start index is passed, rather than expecting the called to sub-slice, so
+// that error messages refer to the expected index.)
+func checkKeysNotRevoked(t *testing.T, krl *krl.KRL, start int, key [][]byte, now time.Time) {
+ _, _, callerLine, _ := runtime.Caller(1)
+ year := 365 * 24 * time.Hour
+ for i := start; i != len(key); i++ {
+ revoked := krl.RevocationTime(key[i])
+ if revoked.Before(now.Add(year)) {
+ t.Errorf("line %d: unrevoked key[%d]=%v has revocation time %v, which is not far enough in the future", callerLine, i, key[i], revoked)
+ }
+ }
+}
+
+func TestKRL(t *testing.T) {
+ now := time.Now()
+ key := [][]byte{
+ []byte{0x00, 0x01, 0x02, 0x3},
+ []byte{0x04, 0x05, 0x06, 0x7},
+ []byte{0x08, 0x09, 0x0a, 0xb}}
+ var revoked time.Time
+
+ krl := krl.New()
+
+ checkKeysNotRevoked(t, krl, 0, key, now)
+
+ krl.Revoke(key[0], now)
+ if revoked = krl.RevocationTime(key[0]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[0], revoked, now)
+ }
+ checkKeysNotRevoked(t, krl, 1, key, now)
+
+ krl.Revoke(key[1], now)
+ if revoked = krl.RevocationTime(key[0]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[0], revoked, now)
+ }
+ if revoked = krl.RevocationTime(key[1]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[1], revoked, now)
+ }
+ checkKeysNotRevoked(t, krl, 2, key, now)
+}
diff --git a/x/ref/services/syncbase/signing/signeddata.vdl b/x/ref/services/syncbase/signing/signeddata.vdl
new file mode 100644
index 0000000..4b4ceb8
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signeddata.vdl
@@ -0,0 +1,72 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package signing
+
+import "v.io/v23/security"
+
+// A DataWithSignature represents a signed, and possibily validated, collection
+// of Item structs.
+//
+// If IsValidated==false and the AuthorSigned signature is valid, it means:
+// The signer whose Blessings have hash BlessingsHash asserts Data.
+//
+// If IsValidated==true and both AuthorSigned and ValidatorSigned signatures are is valid,
+// it means both:
+// 1) The signer whose Blessings b have hash BlessingsHash asserts Data.
+// 2) If vd is the ValidatorData with hash ValidatorDataHash, the owner of
+// vd.PublicKey asserts that it checked that at least the names vd.Names[] were
+// valid in b.
+//
+// The sender obtains:
+// - BlessingsHash (and the wire form of the blessings) with ValidationCache.AddBlessings().
+// - ValidatorDataHash (and the wire form of the ValidataData) with ValidationCache.AddValidatorData().
+//
+// The receiver looks up:
+// - BlessingsHash with ValidationCache.LookupBlessingsData()
+// - ValidatorDataHash with ValidationCache.LookupValidatorData()
+//
+// If not yet there, the receiver inserts the valus into its ValidationCache with:
+// - ValidationCache.AddWireBlessings()
+// - ValidationCache.AddValidatorData()
+type DataWithSignature struct {
+ Data []Item
+ // BlessingsHash is a key for the validation cache; the corresponding
+ // cached value is a security.Blessings.
+ BlessingsHash []byte
+ // AuthorSigned is the signature of Data and BlessingsHash using the
+ // private key associated with the blessings hashed in BlessingsHash.
+ AuthorSigned security.Signature
+
+ IsValidated bool // Whether fields below are meaningful.
+
+ // ValidatorDataHash is a key for the validation cache returned by
+ // ValidatorData.Hash(); the corresponding cached value is the
+ // ValidatorData.
+ ValidatorDataHash []byte
+ ValidatorSigned security.Signature
+}
+
+// An Item represents either a marshalled data item or its SHA-256 hash.
+// The Data field is a []byte, rather than an "any" to make signatures
+// determistic. VOM encoding is not deterministic for two reasons:
+// - map elements may be marshalled in any order
+// - different versions of VOM may marshal in different ways.
+// Thus, the initial producer of a data item marshals the data once, and it is
+// this marshalled form that is transmitted from device to device. If the
+// data were unmarshalled and then remarsahalled, the signatures might not
+// match. The Hash field is used instead of the Data field when the recipient
+// of the DataWithSignature is not permitted to see certain Items' Data
+// fields.
+type Item union {
+ Data []byte // Marshalled form of data.
+ Hash []byte // Hash of what would have been in Data, as returned by SumByteVectorWithLength(Data).
+}
+
+// WireValidatorData is the wire form of ValidatorData.
+// It excludes the unmarshalled form of the public key.
+type WireValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
diff --git a/x/ref/services/syncbase/signing/signeddata.vdl.go b/x/ref/services/syncbase/signing/signeddata.vdl.go
new file mode 100644
index 0000000..f96fe50
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signeddata.vdl.go
@@ -0,0 +1,128 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file was auto-generated by the vanadium vdl tool.
+// Source: signeddata.vdl
+
+package signing
+
+import (
+ // VDL system imports
+ "v.io/v23/vdl"
+
+ // VDL user imports
+ "v.io/v23/security"
+)
+
+// A DataWithSignature represents a signed, and possibily validated, collection
+// of Item structs.
+//
+// If IsValidated==false and the AuthorSigned signature is valid, it means:
+// The signer whose Blessings have hash BlessingsHash asserts Data.
+//
+// If IsValidated==true and both AuthorSigned and ValidatorSigned signatures are is valid,
+// it means both:
+// 1) The signer whose Blessings b have hash BlessingsHash asserts Data.
+// 2) If vd is the ValidatorData with hash ValidatorDataHash, the owner of
+// vd.PublicKey asserts that it checked that at least the names vd.Names[] were
+// valid in b.
+//
+// The sender obtains:
+// - BlessingsHash (and the wire form of the blessings) with ValidationCache.AddBlessings().
+// - ValidatorDataHash (and the wire form of the ValidataData) with ValidationCache.AddValidatorData().
+//
+// The receiver looks up:
+// - BlessingsHash with ValidationCache.LookupBlessingsData()
+// - ValidatorDataHash with ValidationCache.LookupValidatorData()
+//
+// If not yet there, the receiver inserts the valus into its ValidationCache with:
+// - ValidationCache.AddWireBlessings()
+// - ValidationCache.AddValidatorData()
+type DataWithSignature struct {
+ Data []Item
+ // BlessingsHash is a key for the validation cache; the corresponding
+ // cached value is a security.Blessings.
+ BlessingsHash []byte
+ // AuthorSigned is the signature of Data and BlessingsHash using the
+ // private key associated with the blessings hashed in BlessingsHash.
+ AuthorSigned security.Signature
+ IsValidated bool // Whether fields below are meaningful.
+ // ValidatorDataHash is a key for the validation cache returned by
+ // ValidatorData.Hash(); the corresponding cached value is the
+ // ValidatorData.
+ ValidatorDataHash []byte
+ ValidatorSigned security.Signature
+}
+
+func (DataWithSignature) __VDLReflect(struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.DataWithSignature"`
+}) {
+}
+
+type (
+ // Item represents any single field of the Item union type.
+ //
+ // An Item represents either a marshalled data item or its SHA-256 hash.
+ // The Data field is a []byte, rather than an "any" to make signatures
+ // determistic. VOM encoding is not deterministic for two reasons:
+ // - map elements may be marshalled in any order
+ // - different versions of VOM may marshal in different ways.
+ // Thus, the initial producer of a data item marshals the data once, and it is
+ // this marshalled form that is transmitted from device to device. If the
+ // data were unmarshalled and then remarsahalled, the signatures might not
+ // match. The Hash field is used instead of the Data field when the recipient
+ // of the DataWithSignature is not permitted to see certain Items' Data
+ // fields.
+ Item interface {
+ // Index returns the field index.
+ Index() int
+ // Interface returns the field value as an interface.
+ Interface() interface{}
+ // Name returns the field name.
+ Name() string
+ // __VDLReflect describes the Item union type.
+ __VDLReflect(__ItemReflect)
+ }
+ // ItemData represents field Data of the Item union type.
+ ItemData struct{ Value []byte } // Marshalled form of data.
+ // ItemHash represents field Hash of the Item union type.
+ ItemHash struct{ Value []byte } // Hash of what would have been in Data, as returned by SumByteVectorWithLength(Data).
+ // __ItemReflect describes the Item union type.
+ __ItemReflect struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.Item"`
+ Type Item
+ Union struct {
+ Data ItemData
+ Hash ItemHash
+ }
+ }
+)
+
+func (x ItemData) Index() int { return 0 }
+func (x ItemData) Interface() interface{} { return x.Value }
+func (x ItemData) Name() string { return "Data" }
+func (x ItemData) __VDLReflect(__ItemReflect) {}
+
+func (x ItemHash) Index() int { return 1 }
+func (x ItemHash) Interface() interface{} { return x.Value }
+func (x ItemHash) Name() string { return "Hash" }
+func (x ItemHash) __VDLReflect(__ItemReflect) {}
+
+// WireValidatorData is the wire form of ValidatorData.
+// It excludes the unmarshalled form of the public key.
+type WireValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
+
+func (WireValidatorData) __VDLReflect(struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.WireValidatorData"`
+}) {
+}
+
+func init() {
+ vdl.Register((*DataWithSignature)(nil))
+ vdl.Register((*Item)(nil))
+ vdl.Register((*WireValidatorData)(nil))
+}
diff --git a/x/ref/services/syncbase/signing/signing.go b/x/ref/services/syncbase/signing/signing.go
new file mode 100644
index 0000000..0115f37
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signing.go
@@ -0,0 +1,358 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package signing signs syncbase updates using public key signatures, and
+// allows these signatures to be checked on other nodes.
+//
+// The functionality is geared specifically towards syncbase synchronization
+// because it is designed to allow a signature to remain valid during its
+// propagation across the syncgroup once it has been accepted by at least one
+// member of a syncgroup, even if the original key or its blessings are
+// invalidated in the meantime.
+//
+// There are three types of participant:
+// - an "author", which creates an update, and signs it with Sign().
+// - one or more "validators", each of which receives a change directly from
+// the author, and applies Check() to validate it.
+// - zero or more "checkers', each of whom receives a change from a validator
+// or another checker, and applied Check() to check it.
+//
+// A validator checks the signature and blessings provided by the author, and
+// then appends its own signature, vouching for the fact that the author's
+// signature was good at the time the validator saw it.
+//
+// A checker checks the signatures of both the author and validator but uses
+// weaker checks for signature validity than a validator. In particular, it
+// uses a significant grace period for key expiry so that a change admitted to
+// the syncgroup by a validator has an opportunity to propagate to all the
+// nodes in the syncgroup if the keys or blessings are revoked after the change
+// is admitted, but before it is fully propagated. The intent is that the
+// grace period be chosen to be greater than the diameter of the syncgroup
+// (measured in time). One way to ensure that is to insist that members sync
+// with a central server at least every T time units, and make the grace period
+// be 2T. The central server may sign the data anew to allow new members to pick
+// it up.
+//
+// The model is further complicated by performance concerns. An update written
+// to syncbase might be quite small (perhaps tens of bytes) but:
+// a) a public key signature or verification can take on the order of a
+// millisecond. (Currently, ECDSA signing might a little under 1ms and
+// verification just over 2ms on a workstation. A checker performs two such
+// verifications.)
+// b) unmarshalling even a simple Blessings object can take milliseconds. (!)
+// c) marshalling a public key can take 10us.
+// d) a Blessings object is of the order of a kilobyte of more, which may
+// represent substantial space overhead if duplicated.
+//
+// Because of (a), we wish to batch syncbase updates, so that a single
+// signature check applies to several updates. Thus the Data in a
+// DataWithSignature is a vector of Item, rather than a single Item.
+//
+// However, we will not always wish to put all updates in the same batch. For
+// example, an author and a validator might share two different syncgroups with
+// different memberships. In such a case, the author might keep the batches
+// for one syncgoup separate from batches for the other syncgroup, even though
+// the author blessings and validator identities are the same for all the
+// batches. Thus, because of (b,c,d), it's worth decoupling the author's
+// Blessings data and the validator's key data separately from the signed
+// batches itself, so that the blessings and validator data can be processed
+// once, even though several batches of updates are being sent. A
+// ValidationCache is used to hold this data separately, and allow it to be
+// sent just once, rather than once per signature.
+//
+// Lastly, imagine that the author sends a batch of 10 updates to a validator,
+// and the validator then syncs with a checker that is permitted to see only
+// half of the updates; perhaps ACLs prevent if from seeing the others. This
+// requires that the signature on the batch remain valid even if some of the
+// updates in the batch are removed. This is accomplished via the Item type,
+// which is a VDL union type that contains either the bytes of the marshalled
+// form of the update, or (if the update must not be sent) the SHA-256 hash of
+// the data (which can be computed with SumByteVectorWithLength()).
+package signing
+
+import "bytes"
+import "crypto/sha256"
+import "encoding/binary"
+import "hash"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+import "v.io/v23/context"
+import "v.io/v23/security"
+import "v.io/v23/verror"
+
+const pkgPath = "v.io/syncbase/x/ref/services/syncbase/signing"
+
+// These are among the errors may be returned by Check(), and indicate that the
+// operation should be retried when new data has been added to the
+// ValidationCache. The errors are public to make it easier for the client to
+// test for them.
+var (
+ ErrNeedAuthorBlessingsAndValidatorDataForHash = verror.Register(
+ pkgPath+".ErrNeedAuthorBlessingsAndValidatorDataForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache contains neither the author blessings nor the validator data{:_}")
+ ErrNeedAuthorBlessingsForHash = verror.Register(
+ pkgPath+".ErrNeedAuthorBlessingsForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache does not contain the author blessings{:_}")
+ ErrNeedValidatorDataForHash = verror.Register(
+ pkgPath+".ErrNeedValidatorDataForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache does not contain the validator data{:_}")
+)
+
+// These errors are less likely to be tested for, and so are not exported.
+var (
+ errAuthorKeyIsRevoked = verror.Register(
+ pkgPath+".errAuthorKeyIsRevoked",
+ verror.NoRetry,
+ "{1:}{2:} The author key has been revoked{:_}")
+ errBadAuthorSignature = verror.Register(
+ pkgPath+".errBadAuthorSignature",
+ verror.NoRetry,
+ "{1:}{2:} Author signature verification failed{:_}")
+ errBadValidatorSignature = verror.Register(
+ pkgPath+".errBadValidatorSignature",
+ verror.NoRetry,
+ "{1:}{2:} Validator signature verification failed{:_}")
+ errAuthorBlessingsHaveNoValidNames = verror.Register(
+ pkgPath+".errAuthorBlessingsHaveNoValidNames",
+ verror.NoRetry,
+ "{1:}{2:} Author Blessings have no valid names{:_}")
+ errMayNotValidateOwnSignature = verror.Register(
+ pkgPath+".errMayNotValidateOwnSignature",
+ verror.NoRetry,
+ "{1:}{2:} Author may not validate its own signature{:_}")
+ errSenderIsNotAuthor = verror.Register(
+ pkgPath+".errSenderIsNotAuthor",
+ verror.NoRetry,
+ "{1:}{2:} Author is not sender of RPC; will not validate{:_}")
+ errValidatesWrongNames = verror.Register(
+ pkgPath+".errValidatesWrongNames",
+ verror.NoRetry,
+ "{1:}{2:} The validated names are not a subset of the names sent by the checker{:_}")
+ errValidatorIsSigner = verror.Register(
+ pkgPath+".errValidatorIsSigner",
+ verror.NoRetry,
+ "{1:}{2:} The signature was validated by its author; treating as invalid{:_}")
+ errValidatorKeyIsRevoked = verror.Register(
+ pkgPath+".errValidatorKeyIsRevoked",
+ verror.NoRetry,
+ "{1:}{2:} The validator key is revoked{:_}")
+)
+
+// --------------------------------------------
+
+// SignData() uses authorPrincipal to sign data using blessings (which must be
+// associated with the authorPrincipal). A pointer to a newly constructed
+// DataWithSignature with IsValidated==false is returned. Ensures that the
+// blessings are stored in *cache. Typically, "authorPrincipal" is obtained from
+// v23.GetPrincipal(ctx).
+//
+// If a recipient of the result *d complains that it does not understand the
+// hash d.BlessingHash, the signer should present it with
+// blessingsData.MarshalledBlessings, which will allow the recipient to
+// construct the Blessings. The Blessings are transmitted out of line because
+// they are large, and may be reused for multiple signatures.
+func SignData(ctx *context.T, cache *ValidationCache, authorPrincipal security.Principal,
+ blessings security.Blessings, data []Item) (d *DataWithSignature, blessingsData *BlessingsData, err error) {
+
+ d = new(DataWithSignature)
+ d.Data = data
+ d.BlessingsHash, blessingsData, err = cache.AddBlessings(ctx, blessings)
+ if err == nil {
+ d.AuthorSigned, err = authorPrincipal.Sign(d.authorSignatureHash())
+ }
+ return d, blessingsData, err
+}
+
+// hashByteVectorWithLength() calls hasher.Write() on a representation of
+// len(b), followed by the contents of b.
+func hashByteVectorWithLength(hasher hash.Hash, b []byte) {
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(b)))
+ hasher.Write(length[:])
+ hasher.Write(b)
+}
+
+// SumByteVectorWithLength() returns a SHA-256 hash of
+// len(b), followed by the contents of b.
+func SumByteVectorWithLength(b []byte) []byte {
+ hasher := sha256.New()
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(b)))
+ hasher.Write(length[:])
+ hasher.Write(b)
+ return hasher.Sum(nil)[:]
+}
+
+// authorSignatureHash() returns the hash that the author should sign.
+func (d *DataWithSignature) authorSignatureHash() []byte {
+ hasher := sha256.New()
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(d.Data)))
+ hasher.Write(length[:])
+ for i := range d.Data {
+ if data, gotData := d.Data[i].(ItemData); gotData {
+ hasher.Write(SumByteVectorWithLength(data.Value))
+ } else if hash, gotHash := d.Data[i].(ItemHash); gotHash {
+ hasher.Write(hash.Value)
+ } else {
+ // d.Data is neither a Data nor a Hash. This shouldn't
+ // happen unless the mashalled data is somehow
+ // corrupted. The signature will not match unless the
+ // original author of the data was seeing the same.
+ hasher.Write([]byte("no data"))
+ }
+ }
+ hashByteVectorWithLength(hasher, d.BlessingsHash)
+ return hasher.Sum(nil)[:]
+}
+
+// validatorSignatureHash() returns the hash that the validator should sign,
+// given the hash that the author signed.
+func (d *DataWithSignature) validatorSignatureHash(authorSignatureHash []byte) []byte {
+ var buffer [32]byte
+ var buf []byte = buffer[:]
+ if len(d.AuthorSigned.Hash) > len(buf) {
+ buf = make([]byte, len(d.AuthorSigned.Hash))
+ }
+ hasher := sha256.New()
+ hashByteVectorWithLength(hasher, authorSignatureHash)
+ hashByteVectorWithLength(hasher, d.AuthorSigned.Purpose)
+ hashByteVectorWithLength(hasher, buf[:copy(buf, d.AuthorSigned.Hash)])
+ hashByteVectorWithLength(hasher, d.AuthorSigned.R)
+ hashByteVectorWithLength(hasher, d.AuthorSigned.S)
+ hashByteVectorWithLength(hasher, d.ValidatorDataHash)
+ return hasher.Sum(nil)[:]
+}
+
+// Check() verifies the signature(s) on *d:
+//
+// If d.IsValidated==false, checks that:
+// 1. the author's signature is available in *cache.
+// 2. the author's signature over its blessings and the data is
+// cyprotgraphically valid.
+// 3. security.SigningBlessingNames() yields a non-empty list of names when
+// applied to the author's blessings.
+// 4. the author's public key is not known to be revoked.
+// 5. the local's public key (call.LocalPrincipal().PublicKey()) is not known
+// to be revoked.
+// 6. the author's public key is the public key of the RPC caller.
+// 7. the author's public key and the local public key differ.
+// If checks pass and there are no other errors:
+// - records the list of names found in check (3) in the ValidationData
+// - adds a validation signature using the local public key (which is now the
+// validator)
+// - sets d.IsValidated
+// - returns the list of names found in check (3), and a nil error.
+// Otherwise returns a nil list of names and a non-nil error.
+//
+// If d.Validated==true, checks that:
+// 1. the author's signature and the validator data are available in *cache.
+// 2. the author's signature over its blessings and the data is
+// cyprotgraphically valid.
+// 8. the list of names stored in the ValidatorData by the validator is
+// non-empty.
+// 9. the author's public key and the validator's public key differ.
+// 10. the list of names stored in the ValidatorData by the validator is a
+// subset of the list of names that the author's blessings could have
+// represented.
+// 11. the author's public key is not known to be revoked more than
+// gracePeriod ago.
+// 12. the validator's public key is not known to be revoked more than
+// gracePeriod ago.
+// 13. the validator's signature is cryptographically valid.
+// If checks pass and there are no other errors:
+// - returns the list of names in the validator's data, and a nil error.
+// Otherwise returns a nil list of names and a non-nil error.
+func (d *DataWithSignature) Check(ctx *context.T, cache *ValidationCache, call security.Call,
+ krl *krl.KRL, gracePeriod time.Duration) (names []string, err error) {
+
+ // Verify that we have the Blessings and ValidatorData.
+ var authorBlessingsData *BlessingsData = cache.LookupBlessingsData(ctx, d.BlessingsHash)
+ var validatorData *ValidatorData
+ if d.IsValidated {
+ validatorData = cache.LookupValidatorData(ctx, d.ValidatorDataHash)
+ }
+ if authorBlessingsData == nil || (validatorData == nil && d.IsValidated) { // Check (1).
+ if authorBlessingsData == nil && (validatorData == nil && d.IsValidated) {
+ err = verror.New(ErrNeedAuthorBlessingsAndValidatorDataForHash, ctx)
+ } else if authorBlessingsData == nil {
+ err = verror.New(ErrNeedAuthorBlessingsForHash, ctx)
+ } else {
+ err = verror.New(ErrNeedValidatorDataForHash, ctx)
+ }
+ }
+
+ // Check the author signature.
+ var authorSignatureHash []byte
+ if err == nil {
+ authorSignatureHash = d.authorSignatureHash()
+ if !d.AuthorSigned.Verify(authorBlessingsData.UnmarshalledBlessings.PublicKey(), authorSignatureHash) { // Check (2).
+ err = verror.New(errBadAuthorSignature, ctx)
+ }
+ }
+
+ // Check or create the validator signature.
+ now := time.Now()
+ if err != nil {
+ // err already set
+ } else if !d.IsValidated {
+ // Not yet validated, so this run will attempt to validate.
+ var validatedNames []string
+ var localKeyMarshalled []byte
+ var senderKeyMarshalled []byte
+ validatedNames, _ = security.SigningBlessingNames(ctx, call.LocalPrincipal(),
+ authorBlessingsData.UnmarshalledBlessings)
+ if len(validatedNames) == 0 { // Check (3).
+ err = verror.New(errAuthorBlessingsHaveNoValidNames, ctx)
+ } else if localKeyMarshalled, err = call.LocalPrincipal().PublicKey().MarshalBinary(); err != nil {
+ // err already set
+ } else if krl.RevocationTime(authorBlessingsData.MarshalledPublicKey).Before(now) { // Check (4).
+ err = verror.New(errAuthorKeyIsRevoked, ctx)
+ } else if krl.RevocationTime(localKeyMarshalled).Before(now) { // Check (5).
+ err = verror.New(errValidatorKeyIsRevoked, ctx)
+ } else if senderKeyMarshalled, err = call.RemoteBlessings().PublicKey().MarshalBinary(); err != nil {
+ // err already set
+ } else if !bytes.Equal(senderKeyMarshalled, authorBlessingsData.MarshalledPublicKey) { // Check (6).
+ err = verror.New(errSenderIsNotAuthor, ctx)
+ } else if bytes.Equal(localKeyMarshalled, authorBlessingsData.MarshalledPublicKey) { // Check (7).
+ err = verror.New(errMayNotValidateOwnSignature, ctx)
+ } else {
+ // Local principal is different from author, so can validate.
+ validatorData = &ValidatorData{
+ Names: validatedNames,
+ PublicKey: call.LocalPrincipal().PublicKey(),
+ MarshalledPublicKey: localKeyMarshalled,
+ }
+ d.ValidatorDataHash = cache.AddValidatorData(ctx, validatorData)
+ d.ValidatorSigned, err = call.LocalPrincipal().Sign(d.validatorSignatureHash(authorSignatureHash))
+ d.IsValidated = (err == nil)
+ }
+ } else { // Data already validated; check the validator siganture.
+ if len(validatorData.Names) == 0 { // Check (8).
+ err = verror.New(errAuthorBlessingsHaveNoValidNames, ctx)
+ } else if bytes.Equal(validatorData.MarshalledPublicKey, authorBlessingsData.MarshalledPublicKey) { // Check (9).
+ err = verror.New(errValidatorIsSigner, ctx)
+ } else if !authorBlessingsData.UnmarshalledBlessings.CouldHaveNames(validatorData.Names) { // Check (10).
+ err = verror.New(errValidatesWrongNames, ctx)
+ } else if krl.RevocationTime(authorBlessingsData.MarshalledPublicKey).Before(now.Add(-gracePeriod)) { // Check (11).
+ err = verror.New(errAuthorKeyIsRevoked, ctx)
+ } else if krl.RevocationTime(validatorData.MarshalledPublicKey).Before(now.Add(-gracePeriod)) { // Check (12).
+ err = verror.New(errValidatorKeyIsRevoked, ctx)
+ } else if !d.ValidatorSigned.Verify(validatorData.PublicKey, d.validatorSignatureHash(authorSignatureHash)) { // Check (13).
+ err = verror.New(errBadValidatorSignature, ctx)
+ } // else success.
+ }
+
+ // If there were no errors, return the list of names from the validator.
+ if err == nil {
+ names = make([]string, len(validatorData.Names))
+ copy(names, validatorData.Names)
+ }
+
+ return names, err
+}
diff --git a/x/ref/services/syncbase/signing/signing_test.go b/x/ref/services/syncbase/signing/signing_test.go
new file mode 100644
index 0000000..96881f3
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signing_test.go
@@ -0,0 +1,421 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package signing_test implements a test for the package
+// v.io/syncbase/x/ref/services/syncbase/signing
+package signing_test
+
+import "crypto/sha256"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing"
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+import "v.io/v23/naming"
+import "v.io/v23/security"
+import "v.io/v23/vdl"
+import "v.io/v23/vom"
+import "v.io/v23/verror"
+import "v.io/x/ref/test"
+import lib_security "v.io/x/ref/lib/security"
+
+import _ "v.io/x/ref/runtime/factories/generic"
+
+// --------------------------------------
+// The following implements a fake security.Call.
+type fakeCall struct {
+ localPrincipal security.Principal
+ localBlessings security.Blessings
+ remoteBlessings security.Blessings
+}
+
+func (fc *fakeCall) Timestamp() time.Time { return time.Now() }
+func (fc *fakeCall) Method() string { return "the_method_name" }
+func (fc *fakeCall) MethodTags() []*vdl.Value { return nil }
+func (fc *fakeCall) Suffix() string { return "the_suffix" }
+func (fc *fakeCall) LocalDischarges() map[string]security.Discharge { return nil }
+func (fc *fakeCall) RemoteDischarges() map[string]security.Discharge { return nil }
+func (fc *fakeCall) LocalPrincipal() security.Principal { return fc.localPrincipal }
+func (fc *fakeCall) LocalBlessings() security.Blessings { return fc.localBlessings }
+func (fc *fakeCall) RemoteBlessings() security.Blessings { return fc.remoteBlessings }
+func (fc *fakeCall) LocalEndpoint() naming.Endpoint { return nil }
+func (fc *fakeCall) RemoteEndpoint() naming.Endpoint { return nil }
+
+// --------------------------------------
+
+// A principalDesc holds the local state of a single principal in the tests below.
+type principalDesc struct {
+ name string
+ principal security.Principal
+ blessings security.Blessings
+ krl *krl.KRL
+ authorBlessingsData *signing.BlessingsData
+ names []string
+ marshalledBlessings []byte
+ blessingsHash []byte
+ validatorData *signing.ValidatorData
+ validatorHash []byte
+ cache *signing.ValidationCache
+ data *signing.DataWithSignature
+}
+
+// makePrincipal() returns a pointer to a newly-initialized principalDesc,
+// with a unique key, and a single blessing named with its own name.
+func makePrincipal(t testing.TB, name string) (desc *principalDesc) {
+ var err error
+ desc = new(principalDesc)
+ desc.name = name
+ desc.principal, err = lib_security.NewPrincipal()
+ if err != nil {
+ t.Fatalf("security.CreatePrincipal %q failed: %v", desc.name, err)
+ }
+ desc.blessings, err = desc.principal.BlessSelf(desc.name)
+ if err != nil {
+ t.Fatalf("principal.BlessSelf %q failed: %v", desc.name, err)
+ }
+ desc.krl = krl.New()
+ desc.cache = signing.NewValidationCache(5 * time.Second)
+ return desc
+}
+
+// makePrincipals() creares one principal per name, and adds
+// the blessings of each to the roots of all.
+func makePrincipals(t testing.TB, names ...string) (principals []*principalDesc) {
+ for i := range names {
+ principals = append(principals, makePrincipal(t, names[i]))
+ }
+ for i := range principals {
+ for j := range principals {
+ principals[j].principal.AddToRoots(principals[i].blessings)
+ }
+ }
+ return principals
+}
+
+// BenchmarkHashData() measures the time taken to do a cryptogrqaphic hash of
+// 1kBytes.
+func BenchmarkHashData(b *testing.B) {
+ var block [1024]byte
+ hasher := sha256.New()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ hasher.Write(block[:])
+ }
+}
+
+// BenchmarkSignData() measures the time taken to sign something with
+// signing.SignData().
+func BenchmarkSignData(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+ author := makePrincipal(b, "author")
+ dataToSign := []signing.Item{signing.ItemData{Value: []byte("hello")}}
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ }
+ if err != nil {
+ panic(err)
+ }
+}
+
+// BenchmarkSign1000Data() measures the time taken to sign 1000 small data
+// items with signing.SignData().
+func BenchmarkSign1000Data(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+ author := makePrincipal(b, "author")
+ var dataToSign []signing.Item
+ for i := 0; i != 1000; i++ {
+ dataToSign = append(dataToSign, signing.ItemData{Value: []byte("hello")})
+ }
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ }
+ if err != nil {
+ panic(err)
+ }
+}
+
+// BenchmarkSignData() measures the time taken to check a validated signature
+// with DataWithSignature.Check().
+func BenchmarkCheckData(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+
+ principals := makePrincipals(b, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ dataToSign := []signing.Item{signing.ItemData{Value: []byte("hello")}}
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ panic(err)
+ }
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ validator.names, err = author.data.Check(ctx, author.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ panic(err)
+ }
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ checker.names, err = author.data.Check(ctx, author.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ }
+}
+
+// BenchmarkSign1000Data() measures the time taken to check a validated
+// signature over 1000 small data items with DataWithSignature.Check().
+func BenchmarkCheck1000Data(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+
+ principals := makePrincipals(b, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ var dataToSign []signing.Item
+ for i := 0; i != 1000; i++ {
+ dataToSign = append(dataToSign, signing.ItemData{Value: []byte("hello")})
+ }
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ panic(err)
+ }
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ validator.names, err = author.data.Check(ctx, author.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ panic(err)
+ }
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ checker.names, err = author.data.Check(ctx, author.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ }
+}
+
+// BenchmarkMarshallBlessings() measures the time taken to marshal a Blessings.
+func BenchmarkMarshallBlessings(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ author.marshalledBlessings, err = vom.Encode(author.blessings)
+ }
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+}
+
+// BenchmarkUnmarshallBlessings() measures the time taken to unmashal a Blessings.
+func BenchmarkUnmarshallBlessings(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ author.marshalledBlessings, err = vom.Encode(author.blessings)
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+ var blessings security.Blessings
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ err = vom.Decode(author.marshalledBlessings, &blessings)
+ }
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+}
+
+// BenchmarkMarshallPublicKey() measures the time taken to marshal a PublicKey.
+func BenchmarkMarshallPublicKey(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, err = author.principal.PublicKey().MarshalBinary()
+ }
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+}
+
+// BenchmarkUnmarshallPublicKey() measures the time taken to unmarshal a PublicKey.
+func BenchmarkUnmarshallPublicKey(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ var marshalledKey []byte
+ marshalledKey, err = author.principal.PublicKey().MarshalBinary()
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, err = security.UnmarshalPublicKey(marshalledKey)
+ }
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+}
+
+// TestSignData() tests that a complete flow of signing, validating, and
+// checking works on a DataWithSignature.
+func TestSignData(t *testing.T) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+
+ var err error
+
+ principals := makePrincipals(t, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ // Add each princpipal's blessings to each principal's roots.
+ pdList := []*principalDesc{author, validator, checker}
+ for i := 0; i != len(pdList); i++ {
+ for j := 0; j != len(pdList); j++ {
+ pdList[j].principal.AddToRoots(pdList[i].blessings)
+ }
+ }
+
+ // --------------------------------------
+ // Author
+ // Sign some data.
+ dataToSign := []signing.Item{
+ signing.ItemData{Value: []byte("hello")},
+ signing.ItemData{Value: []byte("world")},
+ signing.ItemData{Value: []byte("!")},
+ }
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ t.Fatalf("signing.SignData failed: %v", err)
+ }
+ if author.data.IsValidated {
+ t.Fatalf("signing.SignData generated data with IsValidated set")
+ }
+
+ // --------------------------------------
+ // Validator
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ // The validator receives author.data from the author.
+ validator.data = new(signing.DataWithSignature)
+ *validator.data = *author.data
+ // Initially the validator doesn't have the author BlessingsData.
+ validator.authorBlessingsData = validator.cache.LookupBlessingsData(ctx, validator.data.BlessingsHash)
+ if validator.authorBlessingsData != nil {
+ t.Errorf("found non-nil BlessingsData for validator.data.BlessingsHash in validator's ValidationCache")
+ }
+ validator.names, err = validator.data.Check(ctx, validator.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedAuthorBlessingsForHash.ID {
+ t.Fatalf("validator.data.Check got err %v, want %s", err, signing.ErrNeedAuthorBlessingsForHash.ID)
+ }
+
+ // The validator receives the author's marshalled blessings from the author.
+ validator.marshalledBlessings = author.authorBlessingsData.MarshalledBlessings
+ validator.blessingsHash, validator.authorBlessingsData, err = validator.cache.AddWireBlessings(ctx, validator.marshalledBlessings)
+ if err != nil {
+ t.Fatalf("validator can't add author's marshalled belssings to its ValidationCache: %v", err)
+ }
+
+ validator.names, err = validator.data.Check(ctx, validator.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ t.Fatalf("validator error calling Check() on data: %v", err)
+ }
+ if !validator.data.IsValidated {
+ t.Fatalf("signing.Check didn't set IsValidated")
+ }
+ // Validator's cache should now have the author's BlessingData, and the validator's ValidatorData.
+ validator.authorBlessingsData = validator.cache.LookupBlessingsData(ctx, validator.data.BlessingsHash)
+ if validator.authorBlessingsData == nil {
+ t.Errorf("didn't finf BlessingsData for validator.data.BlessingsHash in validator's ValidationCache")
+ }
+ validator.validatorData = validator.cache.LookupValidatorData(ctx, validator.data.ValidatorDataHash)
+
+ // --------------------------------------
+ // Checker
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ // The checker recieves validator.data from the validator, except that
+ // data item 1 is replaced by its hash, because (for example) the
+ // check is not allowed to see it.
+ checker.data = new(signing.DataWithSignature)
+ *checker.data = *validator.data
+ checker.data.Data[1] = signing.ItemHash{Value: signing.SumByteVectorWithLength(checker.data.Data[1].(signing.ItemData).Value)}
+
+ // Initially the checker doesn't have the author BlessingsData, or the validator ValidatorData.
+ checker.authorBlessingsData = checker.cache.LookupBlessingsData(ctx, checker.data.BlessingsHash)
+ if checker.authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for checker.data.BlessingsHash hash in checker's ValidationCache")
+ }
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedAuthorBlessingsAndValidatorDataForHash.ID {
+ t.Fatalf("checker.data.Check got err %v, want %s", err, signing.ErrNeedAuthorBlessingsAndValidatorDataForHash.ID)
+ }
+
+ // The checker receives the author's marshalled blessings from the validator.
+ checker.marshalledBlessings = validator.marshalledBlessings
+ checker.blessingsHash, checker.authorBlessingsData, err = checker.cache.AddWireBlessings(ctx, checker.marshalledBlessings)
+ if err != nil {
+ t.Fatalf("checker can't add author's marshalled belssings to its ValidationCache: %v", err)
+ }
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedValidatorDataForHash.ID {
+ t.Fatalf("checker.data.Check got err %v, want %s", err, signing.ErrNeedValidatorDataForHash.ID)
+ }
+
+ // The checker receives the validator's data from the validator, passing through the wire format.
+ wvd := signing.ToWireValidatorData(validator.validatorData)
+ var vd signing.ValidatorData
+ vd, err = signing.FromWireValidatorData(&wvd)
+ if err != nil {
+ t.Fatalf("signing.FromWireValidatorData got error: %v", err)
+ }
+ checker.validatorData = &vd
+
+ // The checker adds the ValidatorData to its cache.
+ checker.validatorHash = checker.cache.AddValidatorData(ctx, checker.validatorData)
+
+ // And now the Check() operation should work.
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if err != nil {
+ t.Fatalf("checker.data.Check got unexpected err %v", err)
+ }
+}
diff --git a/x/ref/services/syncbase/signing/validationcache.go b/x/ref/services/syncbase/signing/validationcache.go
new file mode 100644
index 0000000..1c95bd0
--- /dev/null
+++ b/x/ref/services/syncbase/signing/validationcache.go
@@ -0,0 +1,190 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This module implements a cache of data associated with the
+// signatures, keyed by hash values of the data. The intent is that
+// communicating devices will refer to the data using hashes, and transmit the
+// data itself only if the device on the other side does not have the data in
+// its cache.
+
+package signing
+
+import "crypto/sha256"
+import "encoding/binary"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/hashcache"
+import "v.io/v23/context"
+import "v.io/v23/security"
+import "v.io/v23/vom"
+
+// --------------------------------------------
+
+// A BlessingsData contains information about a security.Blessings object. The
+// object itself is referred to by UnmarshalledBlessings. The implementation
+// constructs all instances; the client should not modify fields.
+type BlessingsData struct {
+ UnmarshalledBlessings security.Blessings // The Blessings.
+ MarshalledBlessings []byte // VOM encoded Blessings.
+ MarshalledPublicKey []byte // Value from blessings.PublicKey().MarshalBinary().
+}
+
+// A ValidatorData is the extra data that a validator signs when validating and
+// signing a DataWithSignature. Clients may construct instances to pass to
+// AddValidatorData(), but should not modify the fields of a constructed
+// ValidatorData.
+type ValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ PublicKey security.PublicKey // The key used to create ValidatorSigned.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
+
+// hash() returns the hash of *vd. This hash should be used in the
+// ValidatorDataHash field of DataWithSignature, and as the cache key of *vd
+// in a ValidationCache.
+func (vd *ValidatorData) hash() []byte {
+ hasher := sha256.New()
+ var buffer [256]byte
+ var buf []byte = buffer[:]
+ binary.LittleEndian.PutUint64(buf[:], uint64(len(vd.Names)))
+ hasher.Write(buf[:8])
+ for i := range vd.Names {
+ if len(vd.Names[i]) > len(buf) {
+ buf = make([]byte, len(vd.Names[i])+256)
+ }
+ hashByteVectorWithLength(hasher, []byte(vd.Names[i]))
+ }
+ hashByteVectorWithLength(hasher, vd.MarshalledPublicKey)
+ return hasher.Sum(nil)[:]
+}
+
+// A ValidationCache records recently-seen instances of BlessingsData and
+// ValidatorData values, keys by hashes of the blessings and validator keys
+// respectively. Values may expire from the cache if unused for a duration
+// specified with NewValidationCache().
+type ValidationCache struct {
+ blessingsCache *hashcache.Cache
+ validatorCache *hashcache.Cache
+}
+
+// NewValidationCache() returns a pointer to a new, empty ValidationCache with
+// the specified expiry duration..
+func NewValidationCache(expiry time.Duration) *ValidationCache {
+ return &ValidationCache{
+ blessingsCache: hashcache.New(expiry),
+ validatorCache: hashcache.New(expiry)}
+}
+
+// LookupBlessingsData() returns a pointer to the BlessingsData associated with
+// blessingsHash in *vc. blessingsHash should have been returned by a previous
+// call to AddBlessings() or AddWireBlessings() (possibly on another machine).
+// nil is returned if the data is not present. The client should not modify
+// *result, since it is shared with *vc.
+func (vc *ValidationCache) LookupBlessingsData(ctx *context.T, blessingsHash []byte) (result *BlessingsData) {
+ value, found := vc.blessingsCache.Lookup(blessingsHash)
+ if found {
+ result = value.(*BlessingsData)
+ }
+ return result
+}
+
+// addBlessings() adds a BlessingsData for blessings to *vc, and returns a hash
+// value, which if passed to LookupBlessingsData() will yield a pointer to the
+// BlessingsData, or a non-nil error. The fields of BlessingsData other than
+// MarshalledBlessings and UnmarshalledBlessings are constructed by this
+// routine. Requires that blessings and marshalledBlessings represent the same
+// data, or that marshalledBlessings be nil.
+func (vc *ValidationCache) addBlessings(ctx *context.T, blessings security.Blessings,
+ marshalledBlessings []byte) (blessingsHash []byte, data *BlessingsData, err error) {
+
+ blessingsHash = blessings.UniqueID()
+ if value, found := vc.blessingsCache.Lookup(blessingsHash); found {
+ data = value.(*BlessingsData)
+ } else { // not found
+ var marshalledKey []byte
+ if marshalledBlessings == nil {
+ marshalledBlessings, err = vom.Encode(blessings)
+ }
+ if err == nil {
+ marshalledKey, err = blessings.PublicKey().MarshalBinary()
+ }
+ if err == nil {
+ data = &BlessingsData{
+ UnmarshalledBlessings: blessings,
+ MarshalledBlessings: marshalledBlessings,
+ MarshalledPublicKey: marshalledKey}
+ vc.blessingsCache.Add(blessingsHash, data)
+ }
+ }
+ return blessingsHash, data, err
+}
+
+// AddBlessings() adds a BlessingsData for blessings to *cv, and
+// returns a hash value, which if passed to LookupBlessingsData() will yield a
+// pointer to the BlessingsData, or a non-nil error. The fields of
+// BlessingsData other than UnmarshalledBlessings are constructed by this
+// routine.
+func (vc *ValidationCache) AddBlessings(ctx *context.T, blessings security.Blessings) (blessingsHash []byte, data *BlessingsData, err error) {
+ return vc.addBlessings(ctx, blessings, nil)
+}
+
+// AddWireBlessings() adds a BlessingsData for blessings to *cv, and
+// returns a hash value, which if passed to LookupBlessingsData() will yield a
+// pointer to the BlessingsData, or a non-nil error. The fields of
+// BlessingsData other than MarshalledBlessings are constructed by this
+// routine.
+func (vc *ValidationCache) AddWireBlessings(ctx *context.T,
+ marshalledBlessings []byte) (blessingsHash []byte, data *BlessingsData, err error) {
+
+ var blessings security.Blessings
+ err = vom.Decode(marshalledBlessings, &blessings)
+ if err == nil {
+ blessingsHash, data, err = vc.addBlessings(ctx, blessings, marshalledBlessings)
+ }
+ return blessingsHash, data, err
+}
+
+// LookupValidatorData() returns a pointer to the ValidatorData associated with
+// hash validatorHash in *vc validatorHash should have been returned by a
+// previous call to AddValidatorData() (possibly on another machine). nil is
+// returned if the data is not present. The client should not modifiy *result,
+// since it it shared with *vc.
+func (vc *ValidationCache) LookupValidatorData(ctx *context.T, validatorHash []byte) (result *ValidatorData) {
+ value, found := vc.validatorCache.Lookup(validatorHash)
+ if found {
+ result = value.(*ValidatorData)
+ }
+ return result
+}
+
+// AddValidatorData() adds a ValidatorData *vd to cache *vc, and returns a hash
+// value, which if passed to LookupValidatorData() will yield a pointer to the
+// ValidatorData. The client should not modify *vd after the call, since it is
+// shared with *vc.
+func (vc *ValidationCache) AddValidatorData(ctx *context.T, vd *ValidatorData) (validatorDataHash []byte) {
+ validatorDataHash = vd.hash()
+ vc.validatorCache.Add(validatorDataHash, vd)
+ return validatorDataHash
+}
+
+// ToWireValidatorData() puts the wire form of ValidatorData *vd in *wvd.
+func ToWireValidatorData(vd *ValidatorData) (wvd WireValidatorData) {
+ wvd.Names = make([]string, len(vd.Names))
+ copy(wvd.Names, vd.Names)
+ wvd.MarshalledPublicKey = make([]byte, len(vd.MarshalledPublicKey))
+ copy(wvd.MarshalledPublicKey, vd.MarshalledPublicKey)
+ return wvd
+}
+
+// FromWireValidatorData() puts the in-memory form of WireValidatorData *wvd in *vd.
+func FromWireValidatorData(wvd *WireValidatorData) (vd ValidatorData, err error) {
+ vd.PublicKey, err = security.UnmarshalPublicKey(wvd.MarshalledPublicKey)
+ if err == nil {
+ vd.Names = make([]string, len(wvd.Names))
+ copy(vd.Names, wvd.Names)
+ vd.MarshalledPublicKey = make([]byte, len(wvd.MarshalledPublicKey))
+ copy(vd.MarshalledPublicKey, wvd.MarshalledPublicKey)
+ }
+ return vd, err
+}
diff --git a/x/ref/services/syncbase/signing/validationcache_test.go b/x/ref/services/syncbase/signing/validationcache_test.go
new file mode 100644
index 0000000..a45835b
--- /dev/null
+++ b/x/ref/services/syncbase/signing/validationcache_test.go
@@ -0,0 +1,189 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file tests the validationcache.go module.
+
+package signing_test
+
+import "bytes"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing"
+import "v.io/v23/security"
+import "v.io/x/ref/test"
+import _ "v.io/x/ref/runtime/factories/generic"
+import lib_security "v.io/x/ref/lib/security"
+
+// A principalVDesc holds the local state of a single principal in the tests below.
+type principalVDesc struct {
+ name string
+ principal security.Principal
+ blessings security.Blessings
+ blessingsHash []byte
+ blessingsData *signing.BlessingsData
+ validatorHash []byte
+ validatorData *signing.ValidatorData
+ cache *signing.ValidationCache
+}
+
+// makePrincipalVDesc() returns a pointer to a newly-initialized principalVDesc,
+// with a unique key, and a single blessing named with its own name.
+func makePrincipalVDesc(t *testing.T, name string) (desc *principalVDesc) {
+ var err error
+ desc = new(principalVDesc)
+ desc.name = name
+ desc.principal, err = lib_security.NewPrincipal()
+ if err != nil {
+ t.Fatalf("lib_security.NewPrincipal %q failed: %v", desc.name, err)
+ }
+ desc.blessings, err = desc.principal.BlessSelf(desc.name)
+ if err != nil {
+ t.Fatalf("principal.BlessSelf %q failed: %v", desc.name, err)
+ }
+ desc.cache = signing.NewValidationCache(5 * time.Second)
+ return desc
+}
+
+func TestValidationCache(t *testing.T) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+
+ var err error
+
+ // Make a principalVDesc for each of the author, validator, and checker.
+ // (The author creates a signed change; the validator is a device
+ // author syncs with; the checker is a device a validator syncs with.)
+ author := makePrincipalVDesc(t, "author")
+ validator := makePrincipalVDesc(t, "validator")
+ checker := makePrincipalVDesc(t, "checker")
+
+ // Add each princpipal's blessings to each principal's roots.
+ pdList := []*principalVDesc{author, validator, checker}
+ for i := 0; i != len(pdList); i++ {
+ for j := 0; j != len(pdList); j++ {
+ pdList[j].principal.AddToRoots(pdList[i].blessings)
+ }
+ }
+
+ // --------------------------------------
+ // Author
+ arbitraryBlessingsData := author.cache.LookupBlessingsData(ctx, []byte{0x00})
+ if arbitraryBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for nonsense hash in author's ValidationCache")
+ }
+ author.blessingsHash, author.blessingsData, err = author.cache.AddBlessings(ctx, author.blessings)
+ if err != nil {
+ t.Fatalf("error from author.cache.AddBlessings(): %v", err)
+ }
+ // Check that the author's data is as we expect.
+ if author.cache.LookupBlessingsData(ctx, author.blessingsHash) != author.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in author's ValidationCache: %v vs %v",
+ author.cache.LookupBlessingsData(ctx, author.blessingsHash), author.blessingsData)
+ }
+
+ // --------------------------------------
+ // Validator
+ // The validator receives author.blessingsHash from the author.
+ // Initially the validator doesn't have the author BlessingsData.
+ authorBlessingsData := validator.cache.LookupBlessingsData(ctx, author.blessingsHash)
+ if authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for author.blessingsHash hash in validator's ValidationCache")
+ }
+ // The validator receives the author's marshalled blessings from the author.
+ validator.blessingsHash, validator.blessingsData, err =
+ validator.cache.AddWireBlessings(ctx, author.blessingsData.MarshalledBlessings)
+ if err != nil {
+ t.Fatalf("validator can't add author's marshalled blessings to its ValidationCache: %v", err)
+ }
+ if !bytes.Equal(author.blessingsHash, validator.blessingsHash) {
+ t.Errorf("validator's copy of the blessingsHash different from author's")
+ }
+ // Check that we could have got the blessingsData with a lookup if this were the second time.
+ if validator.cache.LookupBlessingsData(ctx, validator.blessingsHash) != validator.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in validator's ValidationCache")
+ }
+ var marshalledPublicKey []byte
+ marshalledPublicKey, err = validator.principal.PublicKey().MarshalBinary()
+ if err != nil {
+ t.Fatalf("validator.principal.PublicKey().MarshalBinary() got error: %v", err)
+ }
+
+ var validatedNames []string
+ validatedNames, _ = security.SigningBlessingNames(ctx, validator.principal,
+ validator.blessingsData.UnmarshalledBlessings)
+ validator.validatorData = &signing.ValidatorData{
+ Names: validatedNames,
+ PublicKey: validator.principal.PublicKey(),
+ MarshalledPublicKey: marshalledPublicKey}
+ validator.validatorHash = validator.cache.AddValidatorData(ctx, validator.validatorData)
+ if validator.cache.LookupValidatorData(ctx, validator.validatorHash) != validator.validatorData {
+ t.Fatalf("LookupValidatorData returned wrong ValidatorData pointer in validator")
+ }
+
+ // --------------------------------------
+ // Checker
+ // The checker receives validator.blessingsHash from the validator.
+ // Initially the checker doesn't have the author BlessingsData.
+ authorBlessingsData = checker.cache.LookupBlessingsData(ctx, validator.blessingsHash)
+ if authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for author.blessingsHash hash in checker's ValidationCache")
+ }
+ // The checker receives the author's marshalled blessings from the validator.
+ checker.blessingsHash, checker.blessingsData, err =
+ checker.cache.AddWireBlessings(ctx, validator.blessingsData.MarshalledBlessings)
+ if err != nil {
+ t.Fatalf("checker can't add author's marshalled blessings (from validator) to ValidationCache: %v", err)
+ }
+ if !bytes.Equal(author.blessingsHash, checker.blessingsHash) {
+ t.Errorf("checker's copy of the blessingsHash different from author's")
+ }
+ // Check that we could have got the blessingsData with a lookup if this where the second time.
+ if checker.cache.LookupBlessingsData(ctx, checker.blessingsHash) != checker.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in checker's ValidationCache")
+ }
+ // The checker recieves validator.validatorHash from the validator.
+ // Initially the checker doesn't have the ValidatorData.
+ validatorData := checker.cache.LookupValidatorData(ctx, validator.validatorHash)
+ if validatorData != nil {
+ t.Errorf("found non-nil validator data for validator.validatorHash hash in checker's ValidationCache")
+ }
+ // The checker receives the validator's data from the validator (or another checker).
+ checker.validatorHash = checker.cache.AddValidatorData(ctx, validator.validatorData)
+ if !bytes.Equal(validator.validatorHash, checker.validatorHash) {
+ t.Fatalf("checker's copy of the validatorHash different from validator's")
+ }
+ // Get the validatorData
+ checker.validatorData = checker.cache.LookupValidatorData(ctx, checker.validatorHash)
+ if checker.validatorData == nil {
+ t.Fatalf("found nil valdidatorData for checker.validatorHash hash in checker's ValidationCache")
+ }
+}
+
+func TestWireValidatorData(t *testing.T) {
+ var err error
+
+ pDesc := makePrincipalVDesc(t, "some_principal")
+
+ var vd signing.ValidatorData
+ vd.Names = []string{"wombat", "foo"}
+ vd.PublicKey = pDesc.principal.PublicKey()
+ vd.MarshalledPublicKey, err = vd.PublicKey.MarshalBinary()
+ if err != nil {
+ t.Fatalf("failed to marshel public key: %v\n", err)
+ }
+
+ var wvd signing.WireValidatorData
+ var vd2 signing.ValidatorData
+
+ wvd = signing.ToWireValidatorData(&vd)
+ vd2, err = signing.FromWireValidatorData(&wvd)
+ if err != nil {
+ t.Fatalf("FromWireValidatorData failed: %v\n", err)
+ }
+ if len(vd.Names) != len(vd2.Names) {
+ t.Fatalf("ToWireValidatorData/FromWireValidatorData failed to transfer Names list correctly:\nold\n%v\n\nnew\n%v\n\nwire\n%v\n",
+ vd, vd2, wvd)
+ }
+}
