fix.go

Documentation: github.com/google/certificate-transparency-go/fixchain

     1  // Copyright 2016 Google LLC. All Rights Reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  // Package fixchain holds code to help fix the validation chains for certificates.
    16  package fixchain
    17  
    18  import (
    19  	"encoding/pem"
    20  	"net/http"
    21  
    22  	"github.com/google/certificate-transparency-go/x509"
    23  )
    24  
    25  // Fix attempts to fix the certificate chain for the certificate that is passed
    26  // to it, with respect to the given roots.  Fix returns a list of successfully
    27  // constructed chains, and a list of errors it encountered along the way.  The
    28  // presence of FixErrors does not mean the fix was unsuccessful.  Callers should
    29  // check for returned chains to determine success.
    30  func Fix(cert *x509.Certificate, chain []*x509.Certificate, roots *x509.CertPool, client *http.Client) ([][]*x509.Certificate, []*FixError) {
    31  	fix := &toFix{
    32  		cert:  cert,
    33  		chain: newDedupedChain(chain),
    34  		roots: roots,
    35  		cache: newURLCache(client, false),
    36  	}
    37  	return fix.handleChain()
    38  }
    39  
    40  const maxChainLength = 20
    41  
    42  type toFix struct {
    43  	cert  *x509.Certificate
    44  	chain *dedupedChain
    45  	roots *x509.CertPool
    46  	opts  *x509.VerifyOptions
    47  	cache *urlCache
    48  }
    49  
    50  func (fix *toFix) handleChain() ([][]*x509.Certificate, []*FixError) {
    51  	intermediates := x509.NewCertPool()
    52  	for _, c := range fix.chain.certs {
    53  		intermediates.AddCert(c)
    54  	}
    55  
    56  	fix.opts = &x509.VerifyOptions{
    57  		Intermediates:     intermediates,
    58  		Roots:             fix.roots,
    59  		DisableTimeChecks: true,
    60  		KeyUsages:         []x509.ExtKeyUsage{x509.ExtKeyUsageAny},
    61  	}
    62  
    63  	var retferrs []*FixError
    64  	chains, ferrs := fix.constructChain()
    65  	if ferrs != nil {
    66  		retferrs = append(retferrs, ferrs...)
    67  		chains, ferrs = fix.fixChain()
    68  		if ferrs != nil {
    69  			retferrs = append(retferrs, ferrs...)
    70  		}
    71  	}
    72  	return chains, retferrs
    73  }
    74  
    75  func (fix *toFix) constructChain() ([][]*x509.Certificate, []*FixError) {
    76  	chains, err := fix.cert.Verify(*fix.opts)
    77  	if err != nil {
    78  		return chains, []*FixError{
    79  			{
    80  				Type:  VerifyFailed,
    81  				Cert:  fix.cert,
    82  				Chain: fix.chain.certs,
    83  				Error: err,
    84  			},
    85  		}
    86  	}
    87  	return chains, nil
    88  }
    89  
    90  // toFix.fixChain() tries to fix the certificate chain in the toFix struct for
    91  // the cert in the toFix struct wrt the roots in the toFix struct.
    92  // toFix.fixChain() uses the opts provided in the toFix struct to verify the
    93  // chain, and uses the cache in the toFix struct to go and get any potentially
    94  // missing intermediate certs.
    95  // toFix.fixChain() returns a slice of valid and verified chains for this cert
    96  // to the roots in the toFix struct, and a slice of the errors encountered
    97  // during the fixing process.
    98  func (fix *toFix) fixChain() ([][]*x509.Certificate, []*FixError) {
    99  	var retferrs []*FixError
   100  
   101  	// Ensure the leaf certificate is included as part of the certificate chain.
   102  	dchain := *fix.chain
   103  	dchain.addCertToFront(fix.cert)
   104  
   105  	explored := make([]bool, len(dchain.certs))
   106  	lookup := make(map[[hashSize]byte]int)
   107  	for i, cert := range dchain.certs {
   108  		lookup[hash(cert)] = i
   109  	}
   110  
   111  	// For each certificate in the given certificate chain...
   112  	for i, cert := range dchain.certs {
   113  		// If the chains from this certificate have already been built and
   114  		// added to the pool of intermediates, skip.
   115  		if explored[i] {
   116  			continue
   117  		}
   118  
   119  		seen := make(map[[hashSize]byte]bool)
   120  		// Build all the chains possible that begin from this certificate,
   121  		// and add each certificate found along the way to the pool of
   122  		// intermediates against which to verify fix.cert.  If the addition of
   123  		// these intermediates causes chains for fix.cert to be verified,
   124  		// fix.augmentIntermediates() will return those chains.
   125  		chains, ferrs := fix.augmentIntermediates(cert, 1, seen)
   126  		if ferrs != nil {
   127  			retferrs = append(retferrs, ferrs...)
   128  		}
   129  		// If adding certs from the chains stemming from this cert resulted in
   130  		// successful verification of chains for fix.cert to fix.root, return
   131  		// the chains.
   132  		if chains != nil {
   133  			return chains, retferrs
   134  		}
   135  
   136  		// Mark any seen certs that match certs in the original chain as already
   137  		// explored.
   138  		for certHash := range seen {
   139  			index, ok := lookup[certHash]
   140  			if ok {
   141  				explored[index] = true
   142  			}
   143  		}
   144  	}
   145  
   146  	return nil, append(retferrs, &FixError{
   147  		Type:  FixFailed,
   148  		Cert:  fix.cert,
   149  		Chain: fix.chain.certs,
   150  	})
   151  }
   152  
   153  // TODO(katjoyce): Extend fixing algorithm to build all of the chains for
   154  // toFix.cert and log all of the resulting intermediates.
   155  
   156  // toFix.augmentIntermediates() builds all possible chains that stem from the
   157  // given cert, and adds every certificate it finds in these chains to the pool
   158  // of intermediate certs in toFix.opts.  Every time a new certificate is added
   159  // to this pool, it tries to re-verify toFix.cert wrt toFix.roots.
   160  // If this verification is ever successful, toFix.augmentIntermediates() returns
   161  // the verified chains for toFix.cert wrt toFix.roots.  Also returned are any
   162  // errors that were encountered along the way.
   163  //
   164  // toFix.augmentIntermediates() builds all possible chains from cert by using a
   165  // recursive algorithm on the urls in the AIA information of each certificate
   166  // discovered. length represents the position of the current given cert in the
   167  // larger chain, and is used to impose a max length to which chains can be
   168  // explored.  seen is a slice in which all certs that are encountered during the
   169  // search are noted down.
   170  func (fix *toFix) augmentIntermediates(cert *x509.Certificate, length int, seen map[[hashSize]byte]bool) ([][]*x509.Certificate, []*FixError) {
   171  	// If this cert takes the chain past maxChainLength, or if this cert has
   172  	// already been explored, return.
   173  	if length > maxChainLength || seen[hash(cert)] {
   174  		return nil, nil
   175  	}
   176  	// Mark this cert as already explored.
   177  	seen[hash(cert)] = true
   178  
   179  	// Add this cert to the pool of intermediates.  If this results in successful
   180  	// verification of one or more chains for fix.cert, return the chains.
   181  	fix.opts.Intermediates.AddCert(cert)
   182  	chains, err := fix.cert.Verify(*fix.opts)
   183  	if err == nil {
   184  		return chains, nil
   185  	}
   186  
   187  	// For each url in the AIA information of cert, get the corresponding
   188  	// certificates and recursively build the chains from those certificates,
   189  	// adding every cert to the pool of intermediates, running the verifier at
   190  	// every cert addition, and returning verified chains of fix.cert as soon
   191  	// as they are found.
   192  	var retferrs []*FixError
   193  	for _, url := range cert.IssuingCertificateURL {
   194  		icerts, ferr := fix.getIntermediates(url)
   195  		if ferr != nil {
   196  			retferrs = append(retferrs, ferr)
   197  		}
   198  
   199  		for _, icert := range icerts {
   200  			chains, ferrs := fix.augmentIntermediates(icert, length+1, seen)
   201  			if ferrs != nil {
   202  				retferrs = append(retferrs, ferrs...)
   203  			}
   204  			if chains != nil {
   205  				return chains, retferrs
   206  			}
   207  		}
   208  	}
   209  	return nil, retferrs
   210  }
   211  
   212  // Get the certs that correspond to the given url.
   213  func (fix *toFix) getIntermediates(url string) ([]*x509.Certificate, *FixError) {
   214  	var icerts []*x509.Certificate
   215  	// PKCS#7 additions as (at time of writing) there is no standard Go PKCS#7
   216  	// implementation
   217  	r := urlReplacement(url)
   218  	if r != nil {
   219  		return r, nil
   220  	}
   221  
   222  	body, err := fix.cache.getURL(url)
   223  	if err != nil {
   224  		return nil, &FixError{
   225  			Type:  CannotFetchURL,
   226  			Cert:  fix.cert,
   227  			Chain: fix.chain.certs,
   228  			URL:   url,
   229  			Error: err,
   230  		}
   231  	}
   232  
   233  	icert, err := x509.ParseCertificate(body)
   234  	if x509.IsFatal(err) {
   235  		s, _ := pem.Decode(body)
   236  		if s != nil {
   237  			icert, err = x509.ParseCertificate(s.Bytes)
   238  		}
   239  	}
   240  
   241  	if x509.IsFatal(err) {
   242  		return nil, &FixError{
   243  			Type:  ParseFailure,
   244  			Cert:  fix.cert,
   245  			Chain: fix.chain.certs,
   246  			URL:   url,
   247  			Bad:   body,
   248  			Error: err,
   249  		}
   250  	}
   251  
   252  	icerts = append(icerts, icert)
   253  	return icerts, nil
   254  }
   255
View as plain text