1package merkletree2
2
3import (
4	"crypto/sha512"
5	"errors"
6	"fmt"
7	"math/big"
8	"math/rand"
9	"sort"
10	"strconv"
11	"testing"
12
13	"github.com/keybase/client/go/msgpack"
14
15	"github.com/stretchr/testify/require"
16)
17
18func makePositionFromStringForTesting(s string) (Position, error) {
19	posInt, err := strconv.ParseInt(s, 2, 64)
20	if err != nil {
21		return Position{}, err
22	}
23	return (Position)(*big.NewInt(posInt)), nil
24}
25
26func getTreeCfgsWith1_2_3BitsPerIndexBlinded(t *testing.T) (config1bit, config2bits, config3bits Config) {
27	config1bit, err := NewConfig(IdentityHasherBlinded{}, true, 1, 1, 1, ConstructStringValueContainer)
28	require.NoError(t, err)
29
30	config2bits, err = NewConfig(IdentityHasherBlinded{}, true, 2, 1, 1, ConstructStringValueContainer)
31	require.NoError(t, err)
32
33	config3bits, err = NewConfig(IdentityHasherBlinded{}, true, 3, 1, 3, ConstructStringValueContainer)
34	require.NoError(t, err)
35
36	return config1bit, config2bits, config3bits
37}
38
39func getTreeCfgsWith1_2_3BitsPerIndexUnblinded(t *testing.T) (config1bit, config2bits, config3bits Config) {
40	config1bit, err := NewConfig(IdentityHasher{}, false, 1, 1, 1, ConstructStringValueContainer)
41	require.NoError(t, err)
42
43	config2bits, err = NewConfig(IdentityHasher{}, false, 2, 1, 1, ConstructStringValueContainer)
44	require.NoError(t, err)
45
46	config3bits, err = NewConfig(IdentityHasher{}, false, 3, 1, 3, ConstructStringValueContainer)
47	require.NoError(t, err)
48
49	return config1bit, config2bits, config3bits
50}
51
52func getSampleKVPS3bits() (kvps1, kvps2, kvps3 []KeyValuePair) {
53	kvps1 = []KeyValuePair{
54		{Key: []byte{0x00, 0x00, 0x00}, Value: "key0x000000Seqno1"},
55		{Key: []byte{0x00, 0x00, 0x01}, Value: "key0x000001Seqno1"},
56		{Key: []byte{0x00, 0x10, 0x00}, Value: "key0x001000Seqno1"},
57		{Key: []byte{0xff, 0xff, 0xff}, Value: "key0xffffffSeqno1"},
58	}
59
60	kvps2 = []KeyValuePair{
61		{Key: []byte{0x00, 0x00, 0x00}, Value: "key0x000000Seqno2"},
62		{Key: []byte{0x00, 0x00, 0x01}, Value: "key0x000001Seqno2"},
63		{Key: []byte{0x00, 0x10, 0x00}, Value: "key0x001000Seqno2"},
64		{Key: []byte{0xff, 0xff, 0xfe}, Value: "key0xfffffeSeqno2"},
65		{Key: []byte{0xff, 0xff, 0xff}, Value: "key0xffffffSeqno2"},
66	}
67
68	kvps3 = []KeyValuePair{
69		{Key: []byte{0x00, 0x00, 0x00}, Value: "key0x000000Seqno3"},
70		{Key: []byte{0x00, 0x00, 0x01}, Value: "key0x000001Seqno3"},
71		{Key: []byte{0x00, 0x10, 0x00}, Value: "key0x001000Seqno3"},
72		{Key: []byte{0xff, 0xff, 0xfd}, Value: "key0xfffffdSeqno3"},
73		{Key: []byte{0xff, 0xff, 0xfe}, Value: "key0xfffffeSeqno3"},
74		{Key: []byte{0xff, 0xff, 0xff}, Value: "key0xffffffSeqno3"},
75	}
76	return kvps1, kvps2, kvps3
77}
78
79func getSampleKVPS1bit() (kvps1, kvps2, kvps3 []KeyValuePair) {
80	kvps1 = []KeyValuePair{
81		{Key: []byte{0x00}, Value: "key0x00Seqno1"},
82		{Key: []byte{0x01}, Value: "key0x01Seqno1"},
83		{Key: []byte{0x10}, Value: "key0x10Seqno1"},
84		{Key: []byte{0xff}, Value: "key0xffSeqno1"}}
85
86	kvps2 = []KeyValuePair{
87		{Key: []byte{0x00}, Value: "key0x00Seqno2"},
88		{Key: []byte{0x01}, Value: "key0x01Seqno2"},
89		{Key: []byte{0x10}, Value: "key0x10Seqno2"},
90		{Key: []byte{0xfe}, Value: "key0xfeSeqno2"},
91		{Key: []byte{0xff}, Value: "key0xffSeqno2"},
92	}
93
94	kvps3 = []KeyValuePair{
95		{Key: []byte{0x00}, Value: "key0x00Seqno3"},
96		{Key: []byte{0x01}, Value: "key0x01Seqno3"},
97		{Key: []byte{0x10}, Value: "key0x10Seqno3"},
98		{Key: []byte{0xfd}, Value: "key0xfdSeqno3"},
99		{Key: []byte{0xfe}, Value: "key0xfeSeqno3"},
100		{Key: []byte{0xff}, Value: "key0xffSeqno3"},
101	}
102
103	return kvps1, kvps2, kvps3
104}
105
106// Useful to debug tests. Hash(b) == b
107type IdentityHasher struct{}
108
109var _ Encoder = IdentityHasher{}
110
111func (i IdentityHasher) Encode(o interface{}) (dst []byte, err error) {
112	return dst, i.EncodeTo(o, &dst)
113}
114
115func (i IdentityHasher) EncodeTo(o interface{}, out *[]byte) (err error) {
116	enc, err := msgpack.EncodeCanonical(o)
117	if err != nil {
118		return err
119	}
120	*out = append((*out)[:0], enc...)
121	return nil
122}
123
124func (i IdentityHasher) GetEncodingType() EncodingType {
125	return EncodingTypeForTesting
126}
127
128func (i IdentityHasher) Decode(dest interface{}, src []byte) error {
129	return msgpack.Decode(dest, src)
130}
131
132func (i IdentityHasher) HashKeyEncodedValuePairWithKeySpecificSecret(kevp KeyEncodedValuePair, _ KeySpecificSecret) (Hash, error) {
133	return i.Encode(kevp)
134}
135
136func (i IdentityHasher) HashKeyEncodedValuePairWithKeySpecificSecretTo(kevp KeyEncodedValuePair, _ KeySpecificSecret, h *Hash) (err error) {
137	*h, err = i.Encode(kevp)
138	return err
139}
140
141func (i IdentityHasher) EncodeAndHashGeneric(o interface{}) ([]byte, Hash, error) {
142	enc, err := i.Encode(o)
143	if err != nil {
144		return nil, nil, fmt.Errorf("Encoding error in IdentityHasher for %v: %v", o, err)
145	}
146	return enc, Hash(enc), nil
147}
148
149func (i IdentityHasher) HashGeneric(o interface{}, h *Hash) (err error) {
150	_, *h, err = i.EncodeAndHashGeneric(o)
151	return err
152}
153
154func (i IdentityHasher) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, kss KeySpecificSecret) (Hash, error) {
155	encVal, err := i.Encode(kvp.Value)
156	if err != nil {
157		return nil, err
158	}
159	return i.HashKeyEncodedValuePairWithKeySpecificSecret(KeyEncodedValuePair{Key: kvp.Key, Value: encVal}, kss)
160}
161
162func (i IdentityHasher) GenerateMasterSecret(Seqno) (MasterSecret, error) {
163	return nil, errors.New("Should not call GenerateMasterSecret on an unblinded hasher")
164}
165
166func (i IdentityHasher) ComputeKeySpecificSecret(ms MasterSecret, k Key) KeySpecificSecret {
167	return nil
168}
169
170func (i IdentityHasher) ComputeKeySpecificSecretTo(ms MasterSecret, k Key, kss *KeySpecificSecret) {
171}
172
173// Useful to debug tests. Hash(b) == b, with extra blinding fields injected as appropriate
174type IdentityHasherBlinded struct{}
175
176var _ Encoder = IdentityHasherBlinded{}
177
178func (i IdentityHasherBlinded) GetEncodingType() EncodingType {
179	return EncodingTypeForTesting
180}
181
182func (i IdentityHasherBlinded) EncodeAndHashGeneric(o interface{}) ([]byte, Hash, error) {
183	enc, err := msgpack.EncodeCanonical(o)
184	if err != nil {
185		return nil, nil, fmt.Errorf("Msgpack error in IdentityHasher for %v: %v", o, err)
186	}
187	return enc, Hash(enc), nil
188}
189
190func (i IdentityHasherBlinded) HashGeneric(o interface{}, h *Hash) (err error) {
191	_, *h, err = i.EncodeAndHashGeneric(o)
192	return err
193}
194
195func (i IdentityHasherBlinded) Encode(o interface{}) (dst []byte, err error) {
196	return dst, i.EncodeTo(o, &dst)
197}
198
199func (i IdentityHasherBlinded) EncodeTo(o interface{}, out *[]byte) (err error) {
200	enc, err := msgpack.EncodeCanonical(o)
201	if err != nil {
202		return err
203	}
204	*out = append((*out)[:0], enc...)
205	return nil
206}
207
208func (i IdentityHasherBlinded) Decode(dest interface{}, src []byte) error {
209	return msgpack.Decode(dest, src)
210}
211
212func (i IdentityHasherBlinded) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, kss KeySpecificSecret) (Hash, error) {
213	encVal, err := i.Encode(kvp.Value)
214	if err != nil {
215		return nil, err
216	}
217	return i.HashKeyEncodedValuePairWithKeySpecificSecret(KeyEncodedValuePair{Key: kvp.Key, Value: encVal}, kss)
218}
219
220func (i IdentityHasherBlinded) HashKeyEncodedValuePairWithKeySpecificSecret(kevp KeyEncodedValuePair, kss KeySpecificSecret) (Hash, error) {
221	enc, err := i.Encode(struct {
222		Kevp KeyEncodedValuePair
223		Kss  KeySpecificSecret
224	}{Kevp: kevp, Kss: kss})
225	if err != nil {
226		panic(err)
227	}
228	return Hash(enc), nil
229}
230
231func (i IdentityHasherBlinded) HashKeyEncodedValuePairWithKeySpecificSecretTo(kevp KeyEncodedValuePair, kss KeySpecificSecret, h *Hash) (err error) {
232	*h, err = i.HashKeyEncodedValuePairWithKeySpecificSecret(kevp, kss)
233	return err
234}
235
236func (i IdentityHasherBlinded) GenerateMasterSecret(Seqno) (MasterSecret, error) {
237	ms := make([]byte, 1)
238	_, err := rand.Read(ms)
239	return MasterSecret(ms), err
240}
241
242func (i IdentityHasherBlinded) ComputeKeySpecificSecret(ms MasterSecret, k Key) KeySpecificSecret {
243	kss, err := msgpack.EncodeCanonical(struct {
244		Ms MasterSecret
245		K  Key
246	}{Ms: ms, K: k})
247	if err != nil {
248		panic(err)
249	}
250	return KeySpecificSecret(kss)
251}
252
253func (i IdentityHasherBlinded) ComputeKeySpecificSecretTo(ms MasterSecret, k Key, kss *KeySpecificSecret) {
254	var err error
255	*kss, err = msgpack.EncodeCanonical(struct {
256		Ms MasterSecret
257		K  Key
258	}{Ms: ms, K: k})
259	if err != nil {
260		panic(err)
261	}
262}
263
264// returns two disjoint lists of sorted and unique keys of size numPairs1, numPairs2
265func makeRandomKeysForTesting(keysByteLength uint, numPairs1, numPairs2 int) ([]Key, []Key, error) {
266	numPairs := numPairs1 + numPairs2
267
268	if keysByteLength < 8 && numPairs > 1<<(keysByteLength*8) {
269		return nil, nil, fmt.Errorf("too many keys requested !")
270	}
271
272	keyMap := make(map[string]bool, numPairs)
273	for len(keyMap) < numPairs {
274		key := make([]byte, keysByteLength)
275		_, err := rand.Read(key)
276		if err != nil {
277			return nil, nil, err
278		}
279		keyMap[string(key)] = true
280	}
281
282	keyStrings1 := make([]string, 0, numPairs1)
283	keyStrings2 := make([]string, 0, numPairs2)
284
285	i := 0
286	for k := range keyMap {
287		if i < numPairs1 {
288			keyStrings1 = append(keyStrings1, k)
289			i++
290		} else {
291			keyStrings2 = append(keyStrings2, k)
292		}
293	}
294
295	sort.Strings(keyStrings1)
296	sort.Strings(keyStrings2)
297
298	keys1 := make([]Key, numPairs1)
299	for i, k := range keyStrings1 {
300		keys1[i] = Key(k)
301	}
302
303	keys2 := make([]Key, numPairs2)
304	for i, k := range keyStrings2 {
305		keys2[i] = Key(k)
306	}
307
308	return keys1, keys2, nil
309}
310
311func makeRandomKVPFromKeysForTesting(keys []Key) ([]KeyValuePair, error) {
312	kvps := make([]KeyValuePair, len(keys))
313	valBuffer := make([]byte, 10)
314	for i, key := range keys {
315		kvps[i].Key = key
316		_, err := rand.Read(valBuffer)
317		if err != nil {
318			return nil, err
319		}
320		kvps[i].Value = string(valBuffer)
321	}
322	return kvps, nil
323}
324
325func ConstructStringValueContainer() interface{} {
326	return ""
327}
328
329type SHA512_256Encoder struct{}
330
331var _ Encoder = SHA512_256Encoder{}
332
333func (e SHA512_256Encoder) GetEncodingType() EncodingType {
334	return EncodingTypeForTesting
335}
336
337func (e SHA512_256Encoder) Encode(o interface{}) (dst []byte, err error) {
338	return dst, e.EncodeTo(o, &dst)
339}
340
341func (e SHA512_256Encoder) EncodeTo(o interface{}, out *[]byte) (err error) {
342	enc, err := msgpack.EncodeCanonical(o)
343	if err != nil {
344		return err
345	}
346	*out = append((*out)[:0], enc...)
347	return nil
348}
349
350func (e SHA512_256Encoder) Decode(dest interface{}, src []byte) error {
351	return msgpack.Decode(dest, src)
352}
353
354func (e SHA512_256Encoder) EncodeAndHashGeneric(o interface{}) ([]byte, Hash, error) {
355	enc, err := e.Encode(o)
356	if err != nil {
357		return nil, nil, err
358	}
359	hasher := sha512.New512_256()
360	_, err = hasher.Write(enc)
361	if err != nil {
362		return nil, nil, err
363	}
364	return enc, hasher.Sum(nil), nil
365}
366
367func (e SHA512_256Encoder) HashGeneric(o interface{}, h *Hash) (err error) {
368	_, *h, err = e.EncodeAndHashGeneric(o)
369	return err
370}
371
372func (e SHA512_256Encoder) HashKeyValuePairWithKeySpecificSecret(kvp KeyValuePair, kss KeySpecificSecret) (Hash, error) {
373	encVal, err := e.Encode(kvp.Value)
374	if err != nil {
375		return nil, err
376	}
377	return e.HashKeyEncodedValuePairWithKeySpecificSecret(KeyEncodedValuePair{Key: kvp.Key, Value: encVal}, kss)
378}
379
380func (e SHA512_256Encoder) HashKeyEncodedValuePairWithKeySpecificSecret(kevp KeyEncodedValuePair, kss KeySpecificSecret) (Hash, error) {
381	if len(kss) > 0 {
382		panic("This encoder does not support blinding with secrets.")
383	}
384	// TODO this double encoding is unnecessary. Consider removing.
385	enc, err := e.Encode(kevp)
386	if err != nil {
387		return nil, err
388	}
389	hasher := sha512.New512_256()
390	_, err = hasher.Write(enc)
391	if err != nil {
392		return nil, err
393	}
394	return hasher.Sum(nil), nil
395}
396
397func (e SHA512_256Encoder) HashKeyEncodedValuePairWithKeySpecificSecretTo(kevp KeyEncodedValuePair, kss KeySpecificSecret, h *Hash) (err error) {
398	*h, err = e.HashKeyEncodedValuePairWithKeySpecificSecret(kevp, kss)
399	return err
400}
401
402func (e SHA512_256Encoder) GenerateMasterSecret(_ Seqno) (MasterSecret, error) {
403	return nil, fmt.Errorf("This encoder does not support blinding")
404}
405
406func (e SHA512_256Encoder) ComputeKeySpecificSecret(_ MasterSecret, _ Key) KeySpecificSecret {
407	return nil
408}
409
410func (e SHA512_256Encoder) ComputeKeySpecificSecretTo(ms MasterSecret, k Key, kss *KeySpecificSecret) {
411}
412