nonce.go

Documentation: github.com/letsencrypt/boulder/nonce

     1  // Package nonce implements a service for generating and redeeming nonces.
     2  // To generate a nonce, it encrypts a monotonically increasing counter (latest)
     3  // using an authenticated cipher. To redeem a nonce, it checks that the nonce
     4  // decrypts to a valid integer between the earliest and latest counter values,
     5  // and that it's not on the cross-off list. To avoid a constantly growing cross-off
     6  // list, the nonce service periodically retires the oldest counter values by
     7  // finding the lowest counter value in the cross-off list, deleting it, and setting
     8  // "earliest" to its value. To make this efficient, the cross-off list is represented
     9  // two ways: Once as a map, for quick lookup of a given value, and once as a heap,
    10  // to quickly find the lowest value.
    11  // The MaxUsed value determines how long a generated nonce can be used before it
    12  // is forgotten. To calculate that period, divide the MaxUsed value by average
    13  // redemption rate (valid POSTs per second).
    14  package nonce
    15  
    16  import (
    17  	"container/heap"
    18  	"context"
    19  	"crypto/aes"
    20  	"crypto/cipher"
    21  	"crypto/hmac"
    22  	"crypto/rand"
    23  	"crypto/sha256"
    24  	"encoding/base64"
    25  	"errors"
    26  	"fmt"
    27  	"math/big"
    28  	"sync"
    29  	"time"
    30  
    31  	"github.com/prometheus/client_golang/prometheus"
    32  	"google.golang.org/grpc"
    33  	"google.golang.org/protobuf/types/known/emptypb"
    34  
    35  	noncepb "github.com/letsencrypt/boulder/nonce/proto"
    36  )
    37  
    38  const (
    39  	// PrefixLen is the character length of a nonce prefix.
    40  	PrefixLen = 8
    41  
    42  	// DeprecatedPrefixLen is the character length of a nonce prefix.
    43  	//
    44  	// DEPRECATED: Use PrefixLen instead.
    45  	// TODO(#6610): Remove once we've moved to derivable prefixes by default.
    46  	DeprecatedPrefixLen = 4
    47  
    48  	// NonceLen is the character length of a nonce, excluding the prefix.
    49  	NonceLen       = 32
    50  	defaultMaxUsed = 65536
    51  )
    52  
    53  var errInvalidNonceLength = errors.New("invalid nonce length")
    54  
    55  // PrefixCtxKey is exported for use as a key in a context.Context.
    56  type PrefixCtxKey struct{}
    57  
    58  // HMACKeyCtxKey is exported for use as a key in a context.Context.
    59  type HMACKeyCtxKey struct{}
    60  
    61  // DerivePrefix derives a nonce prefix from the provided listening address and
    62  // key. The prefix is derived by take the first 8 characters of the base64url
    63  // encoded HMAC-SHA256 hash of the listening address using the provided key.
    64  func DerivePrefix(grpcAddr, key string) string {
    65  	h := hmac.New(sha256.New, []byte(key))
    66  	h.Write([]byte(grpcAddr))
    67  	return base64.RawURLEncoding.EncodeToString(h.Sum(nil))[:PrefixLen]
    68  }
    69  
    70  // NonceService generates, cancels, and tracks Nonces.
    71  type NonceService struct {
    72  	mu               sync.Mutex
    73  	latest           int64
    74  	earliest         int64
    75  	used             map[int64]bool
    76  	usedHeap         *int64Heap
    77  	gcm              cipher.AEAD
    78  	maxUsed          int
    79  	prefix           string
    80  	nonceCreates     prometheus.Counter
    81  	nonceEarliest    prometheus.Gauge
    82  	nonceRedeems     *prometheus.CounterVec
    83  	nonceHeapLatency prometheus.Histogram
    84  	// TODO(#6610): Remove this field once we've moved to derivable prefixes by
    85  	// default.
    86  	prefixLen int
    87  }
    88  
    89  type int64Heap []int64
    90  
    91  func (h int64Heap) Len() int           { return len(h) }
    92  func (h int64Heap) Less(i, j int) bool { return h[i] < h[j] }
    93  func (h int64Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    94  
    95  func (h *int64Heap) Push(x interface{}) {
    96  	*h = append(*h, x.(int64))
    97  }
    98  
    99  func (h *int64Heap) Pop() interface{} {
   100  	old := *h
   101  	n := len(old)
   102  	x := old[n-1]
   103  	*h = old[0 : n-1]
   104  	return x
   105  }
   106  
   107  // NewNonceService constructs a NonceService with defaults
   108  func NewNonceService(stats prometheus.Registerer, maxUsed int, prefix string) (*NonceService, error) {
   109  	// If a prefix is provided it must be four characters and valid base64. The
   110  	// prefix is required to be base64url as RFC8555 section 6.5.1 requires that
   111  	// nonces use that encoding. As base64 operates on three byte binary
   112  	// segments we require the prefix to be three or six bytes (four or eight
   113  	// characters) so that the bytes preceding the prefix wouldn't impact the
   114  	// encoding.
   115  	//
   116  	// TODO(#6610): Update this comment once we've moved to eight character
   117  	// prefixes by default.
   118  	if prefix != "" {
   119  		// TODO(#6610): Refactor once we've moved to derivable prefixes by
   120  		// default.
   121  		if len(prefix) != PrefixLen && len(prefix) != DeprecatedPrefixLen {
   122  			return nil, fmt.Errorf(
   123  				"'noncePrefix' must be %d or %d characters, not %d",
   124  				PrefixLen,
   125  				DeprecatedPrefixLen,
   126  				len(prefix),
   127  			)
   128  		}
   129  		if _, err := base64.RawURLEncoding.DecodeString(prefix); err != nil {
   130  			return nil, errors.New("nonce prefix must be valid base64url")
   131  		}
   132  	}
   133  
   134  	key := make([]byte, 16)
   135  	if _, err := rand.Read(key); err != nil {
   136  		return nil, err
   137  	}
   138  
   139  	c, err := aes.NewCipher(key)
   140  	if err != nil {
   141  		panic("Failure in NewCipher: " + err.Error())
   142  	}
   143  	gcm, err := cipher.NewGCM(c)
   144  	if err != nil {
   145  		panic("Failure in NewGCM: " + err.Error())
   146  	}
   147  
   148  	if maxUsed <= 0 {
   149  		maxUsed = defaultMaxUsed
   150  	}
   151  
   152  	nonceCreates := prometheus.NewCounter(prometheus.CounterOpts{
   153  		Name: "nonce_creates",
   154  		Help: "A counter of nonces generated",
   155  	})
   156  	stats.MustRegister(nonceCreates)
   157  	nonceEarliest := prometheus.NewGauge(prometheus.GaugeOpts{
   158  		Name: "nonce_earliest",
   159  		Help: "A gauge with the current earliest valid nonce value",
   160  	})
   161  	stats.MustRegister(nonceEarliest)
   162  	nonceRedeems := prometheus.NewCounterVec(prometheus.CounterOpts{
   163  		Name: "nonce_redeems",
   164  		Help: "A counter of nonce validations labelled by result",
   165  	}, []string{"result", "error"})
   166  	stats.MustRegister(nonceRedeems)
   167  	nonceHeapLatency := prometheus.NewHistogram(prometheus.HistogramOpts{
   168  		Name: "nonce_heap_latency",
   169  		Help: "A histogram of latencies of heap pop operations",
   170  	})
   171  	stats.MustRegister(nonceHeapLatency)
   172  
   173  	return &NonceService{
   174  		earliest:         0,
   175  		latest:           0,
   176  		used:             make(map[int64]bool, maxUsed),
   177  		usedHeap:         &int64Heap{},
   178  		gcm:              gcm,
   179  		maxUsed:          maxUsed,
   180  		prefix:           prefix,
   181  		nonceCreates:     nonceCreates,
   182  		nonceEarliest:    nonceEarliest,
   183  		nonceRedeems:     nonceRedeems,
   184  		nonceHeapLatency: nonceHeapLatency,
   185  		// TODO(#6610): Remove this field once we've moved to derivable prefixes
   186  		// by default.
   187  		prefixLen: len(prefix),
   188  	}, nil
   189  }
   190  
   191  func (ns *NonceService) encrypt(counter int64) (string, error) {
   192  	// Generate a nonce with upper 4 bytes zero
   193  	nonce := make([]byte, 12)
   194  	for i := 0; i < 4; i++ {
   195  		nonce[i] = 0
   196  	}
   197  	_, err := rand.Read(nonce[4:])
   198  	if err != nil {
   199  		return "", err
   200  	}
   201  
   202  	// Encode counter to plaintext
   203  	pt := make([]byte, 8)
   204  	ctr := big.NewInt(counter)
   205  	pad := 8 - len(ctr.Bytes())
   206  	copy(pt[pad:], ctr.Bytes())
   207  
   208  	// Encrypt
   209  	ret := make([]byte, NonceLen)
   210  	ct := ns.gcm.Seal(nil, nonce, pt, nil)
   211  	copy(ret, nonce[4:])
   212  	copy(ret[8:], ct)
   213  
   214  	return ns.prefix + base64.RawURLEncoding.EncodeToString(ret), nil
   215  }
   216  
   217  func (ns *NonceService) decrypt(nonce string) (int64, error) {
   218  	body := nonce
   219  	if ns.prefix != "" {
   220  		var prefix string
   221  		var err error
   222  		prefix, body, err = ns.splitNonce(nonce)
   223  		if err != nil {
   224  			return 0, err
   225  		}
   226  		if ns.prefix != prefix {
   227  			return 0, fmt.Errorf("nonce contains invalid prefix: expected %q, got %q", ns.prefix, prefix)
   228  		}
   229  	}
   230  	decoded, err := base64.RawURLEncoding.DecodeString(body)
   231  	if err != nil {
   232  		return 0, err
   233  	}
   234  	if len(decoded) != NonceLen {
   235  		return 0, errInvalidNonceLength
   236  	}
   237  
   238  	n := make([]byte, 12)
   239  	for i := 0; i < 4; i++ {
   240  		n[i] = 0
   241  	}
   242  	copy(n[4:], decoded[:8])
   243  
   244  	pt, err := ns.gcm.Open(nil, n, decoded[8:], nil)
   245  	if err != nil {
   246  		return 0, err
   247  	}
   248  
   249  	ctr := big.NewInt(0)
   250  	ctr.SetBytes(pt)
   251  	return ctr.Int64(), nil
   252  }
   253  
   254  // Nonce provides a new Nonce.
   255  func (ns *NonceService) Nonce() (string, error) {
   256  	ns.mu.Lock()
   257  	ns.latest++
   258  	latest := ns.latest
   259  	ns.mu.Unlock()
   260  	defer ns.nonceCreates.Inc()
   261  	return ns.encrypt(latest)
   262  }
   263  
   264  // Valid determines whether the provided Nonce string is valid, returning
   265  // true if so.
   266  func (ns *NonceService) Valid(nonce string) bool {
   267  	c, err := ns.decrypt(nonce)
   268  	if err != nil {
   269  		ns.nonceRedeems.WithLabelValues("invalid", "decrypt").Inc()
   270  		return false
   271  	}
   272  
   273  	ns.mu.Lock()
   274  	defer ns.mu.Unlock()
   275  	if c > ns.latest {
   276  		ns.nonceRedeems.WithLabelValues("invalid", "too high").Inc()
   277  		return false
   278  	}
   279  
   280  	if c <= ns.earliest {
   281  		ns.nonceRedeems.WithLabelValues("invalid", "too low").Inc()
   282  		return false
   283  	}
   284  
   285  	if ns.used[c] {
   286  		ns.nonceRedeems.WithLabelValues("invalid", "already used").Inc()
   287  		return false
   288  	}
   289  
   290  	ns.used[c] = true
   291  	heap.Push(ns.usedHeap, c)
   292  	if len(ns.used) > ns.maxUsed {
   293  		s := time.Now()
   294  		ns.earliest = heap.Pop(ns.usedHeap).(int64)
   295  		ns.nonceEarliest.Set(float64(ns.earliest))
   296  		ns.nonceHeapLatency.Observe(time.Since(s).Seconds())
   297  		delete(ns.used, ns.earliest)
   298  	}
   299  
   300  	ns.nonceRedeems.WithLabelValues("valid", "").Inc()
   301  	return true
   302  }
   303  
   304  // splitNonce splits a nonce into a prefix and a body.
   305  func (ns *NonceService) splitNonce(nonce string) (string, string, error) {
   306  	if len(nonce) < ns.prefixLen {
   307  		return "", "", errInvalidNonceLength
   308  	}
   309  	return nonce[:ns.prefixLen], nonce[ns.prefixLen:], nil
   310  }
   311  
   312  // splitDeprecatedNonce splits a nonce into a prefix and a body.
   313  //
   314  // Deprecated: Use NonceService.splitDeprecatedNonce instead.
   315  // TODO(#6610): Remove this function once we've moved to derivable prefixes by
   316  // default.
   317  func splitDeprecatedNonce(nonce string) (string, string, error) {
   318  	if len(nonce) < DeprecatedPrefixLen {
   319  		return "", "", errInvalidNonceLength
   320  	}
   321  	return nonce[:DeprecatedPrefixLen], nonce[DeprecatedPrefixLen:], nil
   322  }
   323  
   324  // RemoteRedeem checks the nonce prefix and routes the Redeem RPC
   325  // to the associated remote nonce service.
   326  //
   327  // TODO(#6610): Remove this function once we've moved to derivable prefixes by
   328  // default.
   329  func RemoteRedeem(ctx context.Context, noncePrefixMap map[string]Redeemer, nonce string) (bool, error) {
   330  	prefix, _, err := splitDeprecatedNonce(nonce)
   331  	if err != nil {
   332  		return false, nil
   333  	}
   334  	nonceService, present := noncePrefixMap[prefix]
   335  	if !present {
   336  		return false, nil
   337  	}
   338  	resp, err := nonceService.Redeem(ctx, &noncepb.NonceMessage{Nonce: nonce})
   339  	if err != nil {
   340  		return false, err
   341  	}
   342  	return resp.Valid, nil
   343  }
   344  
   345  // NewServer returns a new Server, wrapping a NonceService.
   346  func NewServer(inner *NonceService) *Server {
   347  	return &Server{inner: inner}
   348  }
   349  
   350  // Server implements the gRPC nonce service.
   351  type Server struct {
   352  	noncepb.UnimplementedNonceServiceServer
   353  	inner *NonceService
   354  }
   355  
   356  // Redeem accepts a nonce from a gRPC client and redeems it using the inner nonce service.
   357  func (ns *Server) Redeem(ctx context.Context, msg *noncepb.NonceMessage) (*noncepb.ValidMessage, error) {
   358  	return &noncepb.ValidMessage{Valid: ns.inner.Valid(msg.Nonce)}, nil
   359  }
   360  
   361  // Nonce generates a nonce and sends it to a gRPC client.
   362  func (ns *Server) Nonce(_ context.Context, _ *emptypb.Empty) (*noncepb.NonceMessage, error) {
   363  	nonce, err := ns.inner.Nonce()
   364  	if err != nil {
   365  		return nil, err
   366  	}
   367  	return &noncepb.NonceMessage{Nonce: nonce}, nil
   368  }
   369  
   370  // Getter is an interface for an RPC client that can get a nonce.
   371  type Getter interface {
   372  	Nonce(ctx context.Context, in *emptypb.Empty, opts ...grpc.CallOption) (*noncepb.NonceMessage, error)
   373  }
   374  
   375  // Redeemer is an interface for an RPC client that can redeem a nonce.
   376  type Redeemer interface {
   377  	Redeem(ctx context.Context, in *noncepb.NonceMessage, opts ...grpc.CallOption) (*noncepb.ValidMessage, error)
   378  }
   379  
   380  // NewGetter returns a new noncepb.NonceServiceClient which can only be used to
   381  // get nonces.
   382  func NewGetter(cc grpc.ClientConnInterface) Getter {
   383  	return noncepb.NewNonceServiceClient(cc)
   384  }
   385  
   386  // NewRedeemer returns a new noncepb.NonceServiceClient which can only be used
   387  // to redeem nonces.
   388  func NewRedeemer(cc grpc.ClientConnInterface) Redeemer {
   389  	return noncepb.NewNonceServiceClient(cc)
   390  }
   391
View as plain text