chacha8.go

     1  // Copyright 2023 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 chacha8rand implements a pseudorandom generator
     6  // based on ChaCha8. It is used by both runtime and math/rand/v2
     7  // and must have no dependencies.
     8  package chacha8rand
     9  
    10  const (
    11  	ctrInc = 4  // increment counter by 4 between block calls
    12  	ctrMax = 16 // reseed when counter reaches 16
    13  	chunk  = 32 // each chunk produced by block is 32 uint64s
    14  	reseed = 4  // reseed with 4 words
    15  )
    16  
    17  // block is the chacha8rand block function.
    18  func block(seed *[4]uint64, blocks *[32]uint64, counter uint32)
    19  
    20  // A State holds the state for a single random generator.
    21  // It must be used from one goroutine at a time.
    22  // If used by multiple goroutines at a time, the goroutines
    23  // may see the same random values, but the code will not
    24  // crash or cause out-of-bounds memory accesses.
    25  type State struct {
    26  	buf  [32]uint64
    27  	seed [4]uint64
    28  	i    uint32
    29  	n    uint32
    30  	c    uint32
    31  }
    32  
    33  // Next returns the next random value, along with a boolean
    34  // indicating whether one was available.
    35  // If one is not available, the caller should call Refill
    36  // and then repeat the call to Next.
    37  //
    38  // Next is //go:nosplit to allow its use in the runtime
    39  // with per-m data without holding the per-m lock.
    40  //go:nosplit
    41  func (s *State) Next() (uint64, bool) {
    42  	i := s.i
    43  	if i >= s.n {
    44  		return 0, false
    45  	}
    46  	s.i = i + 1
    47  	return s.buf[i&31], true // i&31 eliminates bounds check
    48  }
    49  
    50  // Init seeds the State with the given seed value.
    51  func (s *State) Init(seed [32]byte) {
    52  	s.Init64([4]uint64{
    53  		leUint64(seed[0*8:]),
    54  		leUint64(seed[1*8:]),
    55  		leUint64(seed[2*8:]),
    56  		leUint64(seed[3*8:]),
    57  	})
    58  }
    59  
    60  // Init64 seeds the state with the given seed value.
    61  func (s *State) Init64(seed [4]uint64) {
    62  	s.seed = seed
    63  	block(&s.seed, &s.buf, 0)
    64  	s.c = 0
    65  	s.i = 0
    66  	s.n = chunk
    67  }
    68  
    69  // Refill refills the state with more random values.
    70  // After a call to Refill, an immediate call to Next will succeed
    71  // (unless multiple goroutines are incorrectly sharing a state).
    72  func (s *State) Refill() {
    73  	s.c += ctrInc
    74  	if s.c == ctrMax {
    75  		// Reseed with generated uint64s for forward secrecy.
    76  		// Normally this is done immediately after computing a block,
    77  		// but we do it immediately before computing the next block,
    78  		// to allow a much smaller serialized state (just the seed plus offset).
    79  		// This gives a delayed benefit for the forward secrecy
    80  		// (you can reconstruct the recent past given a memory dump),
    81  		// which we deem acceptable in exchange for the reduced size.
    82  		s.seed[0] = s.buf[len(s.buf)-reseed+0]
    83  		s.seed[1] = s.buf[len(s.buf)-reseed+1]
    84  		s.seed[2] = s.buf[len(s.buf)-reseed+2]
    85  		s.seed[3] = s.buf[len(s.buf)-reseed+3]
    86  		s.c = 0
    87  	}
    88  	block(&s.seed, &s.buf, s.c)
    89  	s.i = 0
    90  	s.n = uint32(len(s.buf))
    91  	if s.c == ctrMax-ctrInc {
    92  		s.n = uint32(len(s.buf)) - reseed
    93  	}
    94  }
    95  
    96  // Reseed reseeds the state with new random values.
    97  // After a call to Reseed, any previously returned random values
    98  // have been erased from the memory of the state and cannot be
    99  // recovered.
   100  func (s *State) Reseed() {
   101  	var seed [4]uint64
   102  	for i := range seed {
   103  		for {
   104  			x, ok := s.Next()
   105  			if ok {
   106  				seed[i] = x
   107  				break
   108  			}
   109  			s.Refill()
   110  		}
   111  	}
   112  	s.Init64(seed)
   113  }
   114  
   115  // Marshal marshals the state into a byte slice.
   116  // Marshal and Unmarshal are functions, not methods,
   117  // so that they will not be linked into the runtime
   118  // when it uses the State struct, since the runtime
   119  // does not need these.
   120  func Marshal(s *State) []byte {
   121  	data := make([]byte, 6*8)
   122  	copy(data, "chacha8:")
   123  	used := (s.c/ctrInc)*chunk + s.i
   124  	bePutUint64(data[1*8:], uint64(used))
   125  	for i, seed := range s.seed {
   126  		lePutUint64(data[(2+i)*8:], seed)
   127  	}
   128  	return data
   129  }
   130  
   131  type errUnmarshalChaCha8 struct{}
   132  
   133  func (*errUnmarshalChaCha8) Error() string {
   134  	return "invalid ChaCha8 encoding"
   135  }
   136  
   137  // Unmarshal unmarshals the state from a byte slice.
   138  func Unmarshal(s *State, data []byte) error {
   139  	if len(data) != 6*8 || string(data[:8]) != "chacha8:" {
   140  		return new(errUnmarshalChaCha8)
   141  	}
   142  	used := beUint64(data[1*8:])
   143  	if used > (ctrMax/ctrInc)*chunk-reseed {
   144  		return new(errUnmarshalChaCha8)
   145  	}
   146  	for i := range s.seed {
   147  		s.seed[i] = leUint64(data[(2+i)*8:])
   148  	}
   149  	s.c = ctrInc * (uint32(used) / chunk)
   150  	block(&s.seed, &s.buf, s.c)
   151  	s.i = uint32(used) % chunk
   152  	s.n = chunk
   153  	if s.c == ctrMax-ctrInc {
   154  		s.n = chunk - reseed
   155  	}
   156  	return nil
   157  }
   158  
   159  // binary.bigEndian.Uint64, copied to avoid dependency
   160  func beUint64(b []byte) uint64 {
   161  	_ = b[7] // bounds check hint to compiler; see golang.org/issue/14808
   162  	return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
   163  		uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
   164  }
   165  
   166  // binary.bigEndian.PutUint64, copied to avoid dependency
   167  func bePutUint64(b []byte, v uint64) {
   168  	_ = b[7] // early bounds check to guarantee safety of writes below
   169  	b[0] = byte(v >> 56)
   170  	b[1] = byte(v >> 48)
   171  	b[2] = byte(v >> 40)
   172  	b[3] = byte(v >> 32)
   173  	b[4] = byte(v >> 24)
   174  	b[5] = byte(v >> 16)
   175  	b[6] = byte(v >> 8)
   176  	b[7] = byte(v)
   177  }
   178  
   179  // binary.littleEndian.Uint64, copied to avoid dependency
   180  func leUint64(b []byte) uint64 {
   181  	_ = b[7] // bounds check hint to compiler; see golang.org/issue/14808
   182  	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
   183  		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
   184  }
   185  
   186  // binary.littleEndian.PutUint64, copied to avoid dependency
   187  func lePutUint64(b []byte, v uint64) {
   188  	_ = b[7] // early bounds check to guarantee safety of writes below
   189  	b[0] = byte(v)
   190  	b[1] = byte(v >> 8)
   191  	b[2] = byte(v >> 16)
   192  	b[3] = byte(v >> 24)
   193  	b[4] = byte(v >> 32)
   194  	b[5] = byte(v >> 40)
   195  	b[6] = byte(v >> 48)
   196  	b[7] = byte(v >> 56)
   197  }
   198
View as plain text