ctpolicy.go

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

     1  // Copyright 2018 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 ctpolicy contains structs describing CT policy requirements and corresponding logic.
    16  package ctpolicy
    17  
    18  import (
    19  	"fmt"
    20  	"sync"
    21  
    22  	"github.com/google/certificate-transparency-go/loglist3"
    23  	"github.com/google/certificate-transparency-go/x509"
    24  )
    25  
    26  const (
    27  	// BaseName is name for the group covering all logs.
    28  	BaseName = "All-logs"
    29  )
    30  
    31  // LogGroupInfo holds information on a single group of logs specified by Policy.
    32  type LogGroupInfo struct {
    33  	Name          string
    34  	LogURLs       map[string]bool    // set of members
    35  	MinInclusions int                // Required number of submissions.
    36  	IsBase        bool               // True only for Log-group covering all logs.
    37  	LogWeights    map[string]float32 // weights used for submission, default weight is 1
    38  	wMu           sync.RWMutex       // guards weights
    39  }
    40  
    41  func (group *LogGroupInfo) setMinInclusions(i int) error {
    42  	if i < 0 {
    43  		return fmt.Errorf("cannot assign negative minimal inclusions number")
    44  	}
    45  	// Assign given number even if it's bigger than group size.
    46  	group.MinInclusions = i
    47  	if i > len(group.LogURLs) {
    48  		return fmt.Errorf("trying to assign %d minimal inclusion number while only %d logs are part of group %q", i, len(group.LogURLs), group.Name)
    49  	}
    50  	return nil
    51  }
    52  
    53  func (group *LogGroupInfo) populate(ll *loglist3.LogList, included func(op *loglist3.Operator) bool) {
    54  	group.LogURLs = make(map[string]bool)
    55  	group.LogWeights = make(map[string]float32)
    56  	for _, op := range ll.Operators {
    57  		if included(op) {
    58  			for _, l := range op.Logs {
    59  				group.LogURLs[l.URL] = true
    60  				group.LogWeights[l.URL] = 1.0
    61  			}
    62  		}
    63  	}
    64  }
    65  
    66  // satisfyMinimalInclusion returns whether number of positive weights is
    67  // bigger or equal to minimal inclusion number.
    68  func (group *LogGroupInfo) satisfyMinimalInclusion(weights map[string]float32) bool {
    69  	nonZeroNum := 0
    70  	for logURL, w := range weights {
    71  		if group.LogURLs[logURL] && w > 0.0 {
    72  			nonZeroNum++
    73  			if nonZeroNum >= group.MinInclusions {
    74  				return true
    75  			}
    76  		}
    77  	}
    78  	return false
    79  }
    80  
    81  // SetLogWeights applies suggested weights to the Log-group. Does not reset
    82  // weights and returns error when there are not enough positive weights
    83  // provided to reach minimal inclusion number.
    84  func (group *LogGroupInfo) SetLogWeights(weights map[string]float32) error {
    85  	for logURL, w := range weights {
    86  		if w < 0.0 {
    87  			return fmt.Errorf("trying to assign negative weight %v to Log %q", w, logURL)
    88  		}
    89  	}
    90  	if !group.satisfyMinimalInclusion(weights) {
    91  		return fmt.Errorf("trying to assign weights %v resulting in inability to reach minimal inclusion number %d", weights, group.MinInclusions)
    92  	}
    93  	group.wMu.Lock()
    94  	defer group.wMu.Unlock()
    95  	// All group weights initially reset to 0.0
    96  	for logURL := range group.LogURLs {
    97  		group.LogWeights[logURL] = 0.0
    98  	}
    99  	for logURL, w := range weights {
   100  		if group.LogURLs[logURL] {
   101  			group.LogWeights[logURL] = w
   102  		}
   103  	}
   104  	return nil
   105  }
   106  
   107  // SetLogWeight tries setting the weight for a single Log of the Log-group.
   108  // Does not reset the weight and returns error if weight is non-positive and
   109  // its setting will result in inability to reach minimal inclusion number.
   110  func (group *LogGroupInfo) SetLogWeight(logURL string, w float32) error {
   111  	if !group.LogURLs[logURL] {
   112  		return fmt.Errorf("trying to assign weight to Log %q not belonging to the group", logURL)
   113  	}
   114  	if w < 0.0 {
   115  		return fmt.Errorf("trying to assign negative weight %v to Log %q", w, logURL)
   116  	}
   117  	newWeights := make(map[string]float32)
   118  	for l, wt := range group.LogWeights {
   119  		newWeights[l] = wt
   120  	}
   121  	newWeights[logURL] = w
   122  	if !group.satisfyMinimalInclusion(newWeights) {
   123  		return fmt.Errorf("assigning weight %v to Log %q will result in inability to reach minimal inclusion number %d", w, logURL, group.MinInclusions)
   124  	}
   125  	group.wMu.Lock()
   126  	defer group.wMu.Unlock()
   127  	group.LogWeights = newWeights
   128  	return nil
   129  }
   130  
   131  // GetSubmissionSession produces list of log-URLs of the Log-group.
   132  // Order of the list is weighted random defined by Log-weights within the group
   133  func (group *LogGroupInfo) GetSubmissionSession() []string {
   134  	if len(group.LogURLs) == 0 {
   135  		return make([]string, 0)
   136  	}
   137  	session := make([]string, 0)
   138  	// modelling weighted random with exclusion
   139  
   140  	unProcessedWeights := make(map[string]float32)
   141  	for logURL, w := range group.LogWeights {
   142  		unProcessedWeights[logURL] = w
   143  	}
   144  
   145  	group.wMu.RLock()
   146  	defer group.wMu.RUnlock()
   147  	for range group.LogURLs {
   148  		sampleLog, err := weightedRandomSample(unProcessedWeights)
   149  		if err != nil {
   150  			// session still valid, not covering all Logs
   151  			return session
   152  		}
   153  		session = append(session, sampleLog)
   154  		delete(unProcessedWeights, sampleLog)
   155  	}
   156  	return session
   157  }
   158  
   159  // LogPolicyData contains info on log-partition and submission requirements
   160  // for a single cert. Key always matches value Name field.
   161  type LogPolicyData map[string]*LogGroupInfo
   162  
   163  // TotalLogs returns number of logs within set of Log-groups.
   164  // Taking possible intersection into account.
   165  func (groups LogPolicyData) TotalLogs() int {
   166  	unifiedLogs := make(map[string]bool)
   167  	for _, g := range groups {
   168  		if g.IsBase {
   169  			return len(g.LogURLs)
   170  		}
   171  		for l := range g.LogURLs {
   172  			unifiedLogs[l] = true
   173  		}
   174  	}
   175  	return len(unifiedLogs)
   176  }
   177  
   178  // CTPolicy interface describes requirements determined for logs in terms of
   179  // per-group-submit.
   180  type CTPolicy interface {
   181  	// LogsByGroup provides info on Log-grouping. Returns an error if it's not
   182  	// possible to satisfy the policy with the provided loglist.
   183  	LogsByGroup(cert *x509.Certificate, approved *loglist3.LogList) (LogPolicyData, error)
   184  	Name() string
   185  }
   186  
   187  // BaseGroupFor creates and propagates all-log group.
   188  func BaseGroupFor(approved *loglist3.LogList, incCount int) (*LogGroupInfo, error) {
   189  	baseGroup := LogGroupInfo{Name: BaseName, IsBase: true}
   190  	baseGroup.populate(approved, func(op *loglist3.Operator) bool { return true })
   191  	err := baseGroup.setMinInclusions(incCount)
   192  	return &baseGroup, err
   193  }
   194  
   195  // lifetimeInMonths calculates and returns cert lifetime expressed in months
   196  // flooring incomplete month.
   197  func lifetimeInMonths(cert *x509.Certificate) int {
   198  	startYear, startMonth, startDay := cert.NotBefore.Date()
   199  	endYear, endMonth, endDay := cert.NotAfter.Date()
   200  	lifetimeInMonths := (int(endYear)-int(startYear))*12 + (int(endMonth) - int(startMonth))
   201  	if endDay < startDay {
   202  		// partial month
   203  		lifetimeInMonths--
   204  	}
   205  	return lifetimeInMonths
   206  }
   207  
   208  // GroupSet is set of Log-group names.
   209  type GroupSet map[string]bool
   210  
   211  // GroupByLogs reverses match-map between Logs and Groups.
   212  // Returns map from log-URLs to set of Group-names that contain the log.
   213  func GroupByLogs(lg LogPolicyData) map[string]GroupSet {
   214  	result := make(map[string]GroupSet)
   215  	for groupname, g := range lg {
   216  		for logURL := range g.LogURLs {
   217  			if _, seen := result[logURL]; !seen {
   218  				result[logURL] = make(GroupSet)
   219  			}
   220  			result[logURL][groupname] = true
   221  		}
   222  	}
   223  	return result
   224  }
   225
View as plain text