entropy.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package entropy implements a CPU jitter-based SP 800-90B entropy source.
     6  package entropy
     7  
     8  import (
     9  	"crypto/internal/fips140deps/time"
    10  	"errors"
    11  	"sync/atomic"
    12  	"unsafe"
    13  )
    14  
    15  // Version returns the version of the entropy source.
    16  //
    17  // This is independent of the FIPS 140-3 module version, in order to reuse the
    18  // ESV certificate across module versions.
    19  func Version() string {
    20  	return "v1.0.0"
    21  }
    22  
    23  // ScratchBuffer is a large buffer that will be written to using atomics, to
    24  // generate noise from memory access timings. Its contents do not matter.
    25  type ScratchBuffer [1 << 25]byte
    26  
    27  // Seed returns a 384-bit seed with full entropy.
    28  //
    29  // memory is passed in to allow changing the allocation strategy without
    30  // modifying the frozen and certified entropy source in this package.
    31  //
    32  // Seed returns an error if the entropy source startup health tests fail, which
    33  // has a non-negligible chance of happening.
    34  func Seed(memory *ScratchBuffer) ([48]byte, error) {
    35  	// Collect w = 1024 samples, each certified to provide no less than h = 0.5
    36  	// bits of entropy, for a total of hᵢₙ = w × h = 512 bits of entropy, over
    37  	// nᵢₙ = w × n = 8192 bits of input data.
    38  	var samples [1024]byte
    39  	if err := Samples(samples[:], memory); err != nil {
    40  		return [48]byte{}, err
    41  	}
    42  
    43  	// Use a vetted unkeyed conditioning component, SHA-384, with nw = 384 and
    44  	// nₒᵤₜ = 384. Per the formula in SP 800-90B Section 3.1.5.1.2, the output
    45  	// entropy hₒᵤₜ is:
    46  	//
    47  	//     sage: n_in = 8192
    48  	//     sage: n_out = 384
    49  	//     sage: nw = 384
    50  	//     sage: h_in = 512
    51  	//     sage: P_high = 2^(-h_in)
    52  	//     sage: P_low = (1 - P_high) / (2^n_in - 1)
    53  	//     sage: n = min(n_out, nw)
    54  	//     sage: ψ = 2^(n_in - n) * P_low + P_high
    55  	//     sage: U = 2^(n_in - n) + sqrt(2 * n * 2^(n_in - n) * ln(2))
    56  	//     sage: ω = U * P_low
    57  	//     sage: h_out = -log(max(ψ, ω), 2)
    58  	//     sage: h_out.n()
    59  	//     384.000000000000
    60  	//
    61  	// According to Implementation Guidance D.K, Resolution 19, since
    62  	//
    63  	//   - the conditioning component is vetted,
    64  	//   - hᵢₙ = 512 ≥ nₒᵤₜ + 64 = 448, and
    65  	//   - nₒᵤₜ ≤ security strength of SHA-384 = 384 (per SP 800-107 Rev. 1, Table 1),
    66  	//
    67  	// we can claim the output has full entropy.
    68  	return SHA384(&samples), nil
    69  }
    70  
    71  // Samples starts a new entropy source, collects the requested number of
    72  // samples, conducts startup health tests, and returns the samples or an error
    73  // if the health tests fail.
    74  //
    75  // The health tests have a non-negligible chance of failing.
    76  func Samples(samples []uint8, memory *ScratchBuffer) error {
    77  	if len(samples) < 1024 {
    78  		return errors.New("entropy: at least 1024 samples are required for startup health tests")
    79  	}
    80  	s := newSource(memory)
    81  	for range 4 {
    82  		// Warm up the source to avoid any initial bias.
    83  		_ = s.Sample()
    84  	}
    85  	for i := range samples {
    86  		samples[i] = s.Sample()
    87  	}
    88  	if err := RepetitionCountTest(samples); err != nil {
    89  		return err
    90  	}
    91  	if err := AdaptiveProportionTest(samples); err != nil {
    92  		return err
    93  	}
    94  	return nil
    95  }
    96  
    97  type source struct {
    98  	memory   *ScratchBuffer
    99  	lcgState uint32
   100  	previous int64
   101  }
   102  
   103  func newSource(memory *ScratchBuffer) *source {
   104  	return &source{
   105  		memory:   memory,
   106  		lcgState: uint32(time.HighPrecisionNow()),
   107  		previous: time.HighPrecisionNow(),
   108  	}
   109  }
   110  
   111  // touchMemory performs a write to memory at the given index.
   112  //
   113  // The memory slice is passed in and may be shared across sources e.g. to avoid
   114  // the significant (~500µs) cost of zeroing a new allocation on every [Seed] call.
   115  func touchMemory(memory *ScratchBuffer, idx uint32) {
   116  	idx = idx / 4 * 4 // align to 32 bits
   117  	u32 := (*uint32)(unsafe.Pointer(&memory[idx]))
   118  	last := atomic.LoadUint32(u32)
   119  	atomic.SwapUint32(u32, last+13)
   120  }
   121  
   122  func (s *source) Sample() uint8 {
   123  	// Perform a few memory accesses in an unpredictable pattern to expose the
   124  	// next measurement to as much system noise as possible.
   125  	memory, lcgState := s.memory, s.lcgState
   126  	_ = memory[0] // hoist the nil check out of touchMemory
   127  	for range 64 {
   128  		lcgState = 1664525*lcgState + 1013904223
   129  		// Discard the lower bits, which tend to fall into short cycles.
   130  		idx := (lcgState >> 6) & (1<<25 - 1)
   131  		touchMemory(memory, idx)
   132  	}
   133  	s.lcgState = lcgState
   134  
   135  	t := time.HighPrecisionNow()
   136  	sample := t - s.previous
   137  	s.previous = t
   138  
   139  	// Reduce the symbol space to 256 values, assuming most of the entropy is in
   140  	// the least-significant bits, which represent the highest-resolution timing
   141  	// differences.
   142  	return uint8(sample)
   143  }
   144  
   145  // RepetitionCountTest implements the repetition count test from SP 800-90B
   146  // Section 4.4.1. It returns an error if any symbol is repeated C = 41 or more
   147  // times in a row.
   148  //
   149  // This C value is calculated from a target failure probability α = 2⁻²⁰ and a
   150  // claimed min-entropy per symbol h = 0.5 bits, using the formula in SP 800-90B
   151  // Section 4.4.1.
   152  //
   153  //	sage: α = 2^-20
   154  //	sage: H = 0.5
   155  //	sage: 1 + ceil(-log(α, 2) / H)
   156  //	41
   157  func RepetitionCountTest(samples []uint8) error {
   158  	x := samples[0]
   159  	count := 1
   160  	for _, y := range samples[1:] {
   161  		if y == x {
   162  			count++
   163  			if count >= 41 {
   164  				return errors.New("entropy: repetition count health test failed")
   165  			}
   166  		} else {
   167  			x = y
   168  			count = 1
   169  		}
   170  	}
   171  	return nil
   172  }
   173  
   174  // AdaptiveProportionTest implements the adaptive proportion test from SP 800-90B
   175  // Section 4.4.2. It returns an error if any symbol appears C = 410 or more
   176  // times in the last W = 512 samples.
   177  //
   178  // This C value is calculated from a target failure probability α = 2⁻²⁰, a
   179  // window size W = 512, and a claimed min-entropy per symbol h = 0.5 bits, using
   180  // the formula in SP 800-90B Section 4.4.2, equivalent to the Microsoft Excel
   181  // formula 1+CRITBINOM(W, power(2,(−H)),1−α).
   182  //
   183  //	sage: from scipy.stats import binom
   184  //	sage: α = 2^-20
   185  //	sage: H = 0.5
   186  //	sage: W = 512
   187  //	sage: C = 1 + binom.ppf(1 - α, W, 2**(-H))
   188  //	sage: ceil(C)
   189  //	410
   190  func AdaptiveProportionTest(samples []uint8) error {
   191  	var counts [256]int
   192  	for i, x := range samples {
   193  		counts[x]++
   194  		if i >= 512 {
   195  			counts[samples[i-512]]--
   196  		}
   197  		if counts[x] >= 410 {
   198  			return errors.New("entropy: adaptive proportion health test failed")
   199  		}
   200  	}
   201  	return nil
   202  }
   203
View as plain text