-
Notifications
You must be signed in to change notification settings - Fork 28
/
certificate.go
255 lines (236 loc) · 9.54 KB
/
certificate.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
// 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 security
import (
"bytes"
"crypto/sha256"
"strings"
"sync"
"v.io/v23/verror"
)
var (
errCantMarshalKey = verror.Register(pkgPath+".errCantMarshalKey", verror.NoRetry, "{1:}{2:}failed to marshal PublicKey into a Certificate{:_}")
errInapproriateCertSignature = verror.Register(pkgPath+".errInapproriateCertSignature", verror.NoRetry, "{1:}{2:}signature on certificate(for {3}) was not intended for certification (purpose={4}){:_}")
errBadBlessingExtensionInCert = verror.Register(pkgPath+".errBadBlessingExtensionInCert", verror.NoRetry, "{1:}{2:}invalid blessing extension in certificate(for {3}){:_}")
errBadCertSignature = verror.Register(pkgPath+".errBadCertSignature", verror.NoRetry, "{1:}{2:}invalid Signature in certificate(for \"{3}\"), signing key{:_}")
errBadBlessingEmptyExtension = verror.Register(pkgPath+".errBadBlessingEmptyExtension", verror.NoRetry, "{1:}{2:}invalid blessing extension(empty string){:_}")
errBadBlessingBadStart = verror.Register(pkgPath+".errBadBlessingBadStart", verror.NoRetry, "{1:}{2:}invalid blessing extension(starts with {3}){:_}")
errBadBlessingBadEnd = verror.Register(pkgPath+".errBadBlessingBadEnd", verror.NoRetry, "{1:}{2:}invalid blessing extension(ends with {3}){:_}")
errBadBlessingExtension = verror.Register(pkgPath+".errBadBlessingExtension", verror.NoRetry, "{1:}{2:}invalid blessing extension({3}){:_}")
errBadBlessingBadSubstring = verror.Register(pkgPath+".errBadBlessingBadSubstring", verror.NoRetry, "{1:}{2:}invalid blessing extension({3} has {4} as a substring){:_}")
// invalidBlessingSubStrings are strings that a blessing extension cannot have as a substring.
invalidBlessingSubStrings = []string{string(AllPrincipals), ChainSeparator + ChainSeparator /* double chain separator not allowed */, ",", "@@", "(", ")", "<", ">", "/"}
// invalidBlessingExtensions are strings that are disallowed as blessing extensions.
invalidBlessingExtensions = []string{string(NoExtension)}
// Cache of previously verified certificate chains (identified by the digest of the certificate chain).
// Used to reduce computation overhead of certificate verification when the same set of certificates are
// seen repeatedly.
//
// Caching scheme described in
// https://docs.google.com/document/d/1jGbhwKw2SRFUIV_C55GdAwd_UzZtRoSEnnskt0GzNw4/edit?usp=sharing
signatureCache = &sigCache{m: make(map[[sha256.Size]byte]bool)}
)
const signatureCacheMaxSize = 1 << 10 // 32 bytes * 1K = 32KB + map overhead in Go
func newUnsignedCertificate(extension string, key PublicKey, caveats ...Caveat) (*Certificate, error) {
err := validateExtension(extension)
if err != nil {
return nil, err
}
cert := &Certificate{Extension: extension, Caveats: caveats}
if cert.PublicKey, err = key.MarshalBinary(); err != nil {
return nil, verror.New(errCantMarshalKey, nil, err)
}
return cert, nil
}
func (c *Certificate) contentDigest(hashfn Hash) []byte {
var fields []byte
w := func(data []byte) {
fields = append(fields, hashfn.sum(data)...)
}
w(c.PublicKey)
w([]byte(c.Extension))
for _, cav := range c.Caveats {
fields = append(fields, cav.digest(hashfn)...)
}
return hashfn.sum(fields)
}
// chainedDigests returns the digest and contentDigest of a certificate chain
// formed by chaining c to an another certificate chain (identified by its
// digest).
//
// If len(chain) == 0, the implication is that 'c' is the first certificate
// (a.k.a. "root") of the chain.
func (c *Certificate) chainedDigests(hashfn Hash, chain []byte) (digest, contentDigest []byte) {
contentDigest = c.contentDigest(hashfn)
digest = hashfn.sum(append(contentDigest, c.Signature.digest(hashfn)...))
if len(chain) > 0 {
// c is not the "root" of the chain
// We hash (using 'hashfn') 'chain' and then append it to 'digest'
// (or 'contentDigest'). Hashing 'chain' is important as it may be
// of a different length from 'digest'. While the length of 'digest'
// is the length of the output of 'hashfn', the length of 'chain'
// would depend on the size of the public key in the last
// certificate of the chain represented by it. Hashing 'chain'
// using 'hasfn' guarantees that it will have the same length
// as 'digest'.
contentDigest = hashfn.sum(append(hashfn.sum(chain), contentDigest...))
digest = hashfn.sum(append(hashfn.sum(chain), digest...))
}
return
}
func validateExtension(extension string) error {
if len(extension) == 0 {
return verror.New(errBadBlessingEmptyExtension, nil)
}
if strings.HasPrefix(extension, ChainSeparator) {
return verror.New(errBadBlessingBadStart, nil, ChainSeparator)
}
if strings.HasSuffix(extension, ChainSeparator) {
return verror.New(errBadBlessingBadEnd, nil, ChainSeparator)
}
for _, n := range invalidBlessingExtensions {
if extension == n {
return verror.New(errBadBlessingExtension, nil, extension)
}
}
for _, n := range invalidBlessingSubStrings {
if strings.Contains(extension, n) {
return verror.New(errBadBlessingBadSubstring, nil, extension, n)
}
}
return nil
}
// Validation algorithm as specified in:
// https://docs.google.com/document/d/1jGbhwKw2SRFUIV_C55GdAwd_UzZtRoSEnnskt0GzNw4/edit?usp=sharing
func validateCertificateChain(chain []Certificate) (PublicKey, []byte, error) {
pubkey, err := UnmarshalPublicKey(chain[len(chain)-1].PublicKey)
if err != nil {
return nil, nil, err
}
var (
digest = make([][]byte, len(chain))
contentDigest = make([][]byte, len(chain))
)
digest[0], contentDigest[0] = chain[0].chainedDigests(chain[0].Signature.Hash, nil)
for i := 1; i < len(chain); i++ {
digest[i], contentDigest[i] = chain[i].chainedDigests(chain[i].Signature.Hash, digest[i-1])
}
chaindigest := digest[len(digest)-1]
// Verify certificates in reverse order as per the algorithm linked to above.
for i := len(chain) - 1; i >= 0; i-- {
c := chain[i]
// Check the in-memory cache
if signatureCache.verify(digest[i]) {
// chain[0:i] has been validated before
// and chain[i:] has been validated in this for loop.
signatureCache.cache(digest[i:])
return pubkey, chaindigest, nil
}
// Some basic sanity checks on the certificate.
if !bytes.Equal(c.Signature.Purpose, blessPurpose) {
return nil, nil, verror.New(errInapproriateCertSignature, nil, c.Extension, c.Signature.Purpose)
}
if err := validateExtension(c.Extension); err != nil {
return nil, nil, verror.New(errBadBlessingExtensionInCert, nil, c.Extension, err)
}
// Verify the signature.
var signer PublicKey
if i == 0 {
signer, err = UnmarshalPublicKey(chain[0].PublicKey)
} else {
signer, err = UnmarshalPublicKey(chain[i-1].PublicKey)
}
if err != nil {
return nil, nil, err
}
if !chain[i].Signature.Verify(signer, contentDigest[i]) {
return nil, nil, verror.New(errBadCertSignature, nil, chain[i].Extension, signer)
}
}
signatureCache.cache(digest)
return pubkey, chaindigest, nil
}
func digestsForCertificateChain(chain []Certificate) (digest, contentDigest []byte) {
for _, c := range chain {
digest, contentDigest = c.chainedDigests(c.Signature.Hash, digest)
}
return
}
// chainCertificate binds cert to an existing certificate chain and returns the
// resulting chain (and the final digest).
func chainCertificate(signer Signer, chain []Certificate, cert Certificate) ([]Certificate, []byte, error) {
parentDigest, _ := digestsForCertificateChain(chain)
_, cdigest := cert.chainedDigests(signer.PublicKey().hash(), parentDigest)
var err error
if cert.Signature, err = signer.Sign(blessPurpose, cdigest); err != nil {
return nil, nil, err
}
// digest has to be recomputed now that the signature has been set in the certificate.
digest, _ := cert.chainedDigests(signer.PublicKey().hash(), parentDigest)
cpy := make([]Certificate, len(chain)+1)
copy(cpy, chain)
cpy[len(cpy)-1] = cert
return cpy, digest, nil
}
// Concurrent access friendly map of previously verified certificate chains
// (identified by their digest).
//
// TODO(ashankar,ataly): sigCache.verify may leak information based on the
// time it takes to execute because sigCache.m does not provide "constant time"
// lookups (in the sense of crypto/subtle.ConstantTimeEq for example).
// Technically, constant time lookups are required as per:
// https://docs.google.com/document/d/1jGbhwKw2SRFUIV_C55GdAwd_UzZtRoSEnnskt0GzNw4/edit?usp=sharing
type sigCache struct {
disabled bool // Only here for microbenchmarks
sync.RWMutex
m map[[sha256.Size]byte]bool
}
func (s *sigCache) disable() {
s.Lock()
s.disabled = true
s.m = make(map[[sha256.Size]byte]bool)
s.Unlock()
}
func (s *sigCache) enable() {
s.Lock()
s.disabled = false
s.Unlock()
}
func (s *sigCache) verify(digest []byte) bool {
key := sha256.Sum256(digest)
s.RLock()
ret := s.m[key]
s.RUnlock()
return ret
}
func (s *sigCache) cache(digests [][]byte) {
keys := make([][sha256.Size]byte, len(digests))
for i, d := range digests {
keys[i] = sha256.Sum256(d)
}
s.Lock()
if s.disabled {
s.Unlock()
return
}
for _, k := range keys {
s.m[k] = true
}
// Might have gone over our size limit for the cache, remove entries.
// This may evict the entries that were just inserted, live with that.
if len(s.m) > signatureCacheMaxSize {
n := len(s.m) - signatureCacheMaxSize
m := 0
// Randomly evict and entry. Fortunately, map iteration is in random key order
// (see "Iteration Order" in http://blog.golang.org/go-maps-in-action)
for key, _ := range s.m {
delete(s.m, key)
m++
if m >= n {
break
}
}
}
s.Unlock()
}