chacha_generic.go

     1  // Copyright 2016 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 chacha20 implements the ChaCha20 and XChaCha20 encryption algorithms
     6  // as specified in RFC 8439 and draft-irtf-cfrg-xchacha-01.
     7  package chacha20
     8  
     9  import (
    10  	"crypto/cipher"
    11  	"encoding/binary"
    12  	"errors"
    13  	"math/bits"
    14  
    15  	"golang.org/x/crypto/internal/subtle"
    16  )
    17  
    18  const (
    19  	// KeySize is the size of the key used by this cipher, in bytes.
    20  	KeySize = 32
    21  
    22  	// NonceSize is the size of the nonce used with the standard variant of this
    23  	// cipher, in bytes.
    24  	//
    25  	// Note that this is too short to be safely generated at random if the same
    26  	// key is reused more than 2³² times.
    27  	NonceSize = 12
    28  
    29  	// NonceSizeX is the size of the nonce used with the XChaCha20 variant of
    30  	// this cipher, in bytes.
    31  	NonceSizeX = 24
    32  )
    33  
    34  // Cipher is a stateful instance of ChaCha20 or XChaCha20 using a particular key
    35  // and nonce. A *Cipher implements the cipher.Stream interface.
    36  type Cipher struct {
    37  	// The ChaCha20 state is 16 words: 4 constant, 8 of key, 1 of counter
    38  	// (incremented after each block), and 3 of nonce.
    39  	key     [8]uint32
    40  	counter uint32
    41  	nonce   [3]uint32
    42  
    43  	// The last len bytes of buf are leftover key stream bytes from the previous
    44  	// XORKeyStream invocation. The size of buf depends on how many blocks are
    45  	// computed at a time by xorKeyStreamBlocks.
    46  	buf [bufSize]byte
    47  	len int
    48  
    49  	// overflow is set when the counter overflowed, no more blocks can be
    50  	// generated, and the next XORKeyStream call should panic.
    51  	overflow bool
    52  
    53  	// The counter-independent results of the first round are cached after they
    54  	// are computed the first time.
    55  	precompDone      bool
    56  	p1, p5, p9, p13  uint32
    57  	p2, p6, p10, p14 uint32
    58  	p3, p7, p11, p15 uint32
    59  }
    60  
    61  var _ cipher.Stream = (*Cipher)(nil)
    62  
    63  // NewUnauthenticatedCipher creates a new ChaCha20 stream cipher with the given
    64  // 32 bytes key and a 12 or 24 bytes nonce. If a nonce of 24 bytes is provided,
    65  // the XChaCha20 construction will be used. It returns an error if key or nonce
    66  // have any other length.
    67  //
    68  // Note that ChaCha20, like all stream ciphers, is not authenticated and allows
    69  // attackers to silently tamper with the plaintext. For this reason, it is more
    70  // appropriate as a building block than as a standalone encryption mechanism.
    71  // Instead, consider using package golang.org/x/crypto/chacha20poly1305.
    72  func NewUnauthenticatedCipher(key, nonce []byte) (*Cipher, error) {
    73  	// This function is split into a wrapper so that the Cipher allocation will
    74  	// be inlined, and depending on how the caller uses the return value, won't
    75  	// escape to the heap.
    76  	c := &Cipher{}
    77  	return newUnauthenticatedCipher(c, key, nonce)
    78  }
    79  
    80  func newUnauthenticatedCipher(c *Cipher, key, nonce []byte) (*Cipher, error) {
    81  	if len(key) != KeySize {
    82  		return nil, errors.New("chacha20: wrong key size")
    83  	}
    84  	if len(nonce) == NonceSizeX {
    85  		// XChaCha20 uses the ChaCha20 core to mix 16 bytes of the nonce into a
    86  		// derived key, allowing it to operate on a nonce of 24 bytes. See
    87  		// draft-irtf-cfrg-xchacha-01, Section 2.3.
    88  		key, _ = HChaCha20(key, nonce[0:16])
    89  		cNonce := make([]byte, NonceSize)
    90  		copy(cNonce[4:12], nonce[16:24])
    91  		nonce = cNonce
    92  	} else if len(nonce) != NonceSize {
    93  		return nil, errors.New("chacha20: wrong nonce size")
    94  	}
    95  
    96  	key, nonce = key[:KeySize], nonce[:NonceSize] // bounds check elimination hint
    97  	c.key = [8]uint32{
    98  		binary.LittleEndian.Uint32(key[0:4]),
    99  		binary.LittleEndian.Uint32(key[4:8]),
   100  		binary.LittleEndian.Uint32(key[8:12]),
   101  		binary.LittleEndian.Uint32(key[12:16]),
   102  		binary.LittleEndian.Uint32(key[16:20]),
   103  		binary.LittleEndian.Uint32(key[20:24]),
   104  		binary.LittleEndian.Uint32(key[24:28]),
   105  		binary.LittleEndian.Uint32(key[28:32]),
   106  	}
   107  	c.nonce = [3]uint32{
   108  		binary.LittleEndian.Uint32(nonce[0:4]),
   109  		binary.LittleEndian.Uint32(nonce[4:8]),
   110  		binary.LittleEndian.Uint32(nonce[8:12]),
   111  	}
   112  	return c, nil
   113  }
   114  
   115  // The constant first 4 words of the ChaCha20 state.
   116  const (
   117  	j0 uint32 = 0x61707865 // expa
   118  	j1 uint32 = 0x3320646e // nd 3
   119  	j2 uint32 = 0x79622d32 // 2-by
   120  	j3 uint32 = 0x6b206574 // te k
   121  )
   122  
   123  const blockSize = 64
   124  
   125  // quarterRound is the core of ChaCha20. It shuffles the bits of 4 state words.
   126  // It's executed 4 times for each of the 20 ChaCha20 rounds, operating on all 16
   127  // words each round, in columnar or diagonal groups of 4 at a time.
   128  func quarterRound(a, b, c, d uint32) (uint32, uint32, uint32, uint32) {
   129  	a += b
   130  	d ^= a
   131  	d = bits.RotateLeft32(d, 16)
   132  	c += d
   133  	b ^= c
   134  	b = bits.RotateLeft32(b, 12)
   135  	a += b
   136  	d ^= a
   137  	d = bits.RotateLeft32(d, 8)
   138  	c += d
   139  	b ^= c
   140  	b = bits.RotateLeft32(b, 7)
   141  	return a, b, c, d
   142  }
   143  
   144  // SetCounter sets the Cipher counter. The next invocation of XORKeyStream will
   145  // behave as if (64 * counter) bytes had been encrypted so far.
   146  //
   147  // To prevent accidental counter reuse, SetCounter panics if counter is less
   148  // than the current value.
   149  //
   150  // Note that the execution time of XORKeyStream is not independent of the
   151  // counter value.
   152  func (s *Cipher) SetCounter(counter uint32) {
   153  	// Internally, s may buffer multiple blocks, which complicates this
   154  	// implementation slightly. When checking whether the counter has rolled
   155  	// back, we must use both s.counter and s.len to determine how many blocks
   156  	// we have already output.
   157  	outputCounter := s.counter - uint32(s.len)/blockSize
   158  	if s.overflow || counter < outputCounter {
   159  		panic("chacha20: SetCounter attempted to rollback counter")
   160  	}
   161  
   162  	// In the general case, we set the new counter value and reset s.len to 0,
   163  	// causing the next call to XORKeyStream to refill the buffer. However, if
   164  	// we're advancing within the existing buffer, we can save work by simply
   165  	// setting s.len.
   166  	if counter < s.counter {
   167  		s.len = int(s.counter-counter) * blockSize
   168  	} else {
   169  		s.counter = counter
   170  		s.len = 0
   171  	}
   172  }
   173  
   174  // XORKeyStream XORs each byte in the given slice with a byte from the
   175  // cipher's key stream. Dst and src must overlap entirely or not at all.
   176  //
   177  // If len(dst) < len(src), XORKeyStream will panic. It is acceptable
   178  // to pass a dst bigger than src, and in that case, XORKeyStream will
   179  // only update dst[:len(src)] and will not touch the rest of dst.
   180  //
   181  // Multiple calls to XORKeyStream behave as if the concatenation of
   182  // the src buffers was passed in a single run. That is, Cipher
   183  // maintains state and does not reset at each XORKeyStream call.
   184  func (s *Cipher) XORKeyStream(dst, src []byte) {
   185  	if len(src) == 0 {
   186  		return
   187  	}
   188  	if len(dst) < len(src) {
   189  		panic("chacha20: output smaller than input")
   190  	}
   191  	dst = dst[:len(src)]
   192  	if subtle.InexactOverlap(dst, src) {
   193  		panic("chacha20: invalid buffer overlap")
   194  	}
   195  
   196  	// First, drain any remaining key stream from a previous XORKeyStream.
   197  	if s.len != 0 {
   198  		keyStream := s.buf[bufSize-s.len:]
   199  		if len(src) < len(keyStream) {
   200  			keyStream = keyStream[:len(src)]
   201  		}
   202  		_ = src[len(keyStream)-1] // bounds check elimination hint
   203  		for i, b := range keyStream {
   204  			dst[i] = src[i] ^ b
   205  		}
   206  		s.len -= len(keyStream)
   207  		dst, src = dst[len(keyStream):], src[len(keyStream):]
   208  	}
   209  	if len(src) == 0 {
   210  		return
   211  	}
   212  
   213  	// If we'd need to let the counter overflow and keep generating output,
   214  	// panic immediately. If instead we'd only reach the last block, remember
   215  	// not to generate any more output after the buffer is drained.
   216  	numBlocks := (uint64(len(src)) + blockSize - 1) / blockSize
   217  	if s.overflow || uint64(s.counter)+numBlocks > 1<<32 {
   218  		panic("chacha20: counter overflow")
   219  	} else if uint64(s.counter)+numBlocks == 1<<32 {
   220  		s.overflow = true
   221  	}
   222  
   223  	// xorKeyStreamBlocks implementations expect input lengths that are a
   224  	// multiple of bufSize. Platform-specific ones process multiple blocks at a
   225  	// time, so have bufSizes that are a multiple of blockSize.
   226  
   227  	full := len(src) - len(src)%bufSize
   228  	if full > 0 {
   229  		s.xorKeyStreamBlocks(dst[:full], src[:full])
   230  	}
   231  	dst, src = dst[full:], src[full:]
   232  
   233  	// If using a multi-block xorKeyStreamBlocks would overflow, use the generic
   234  	// one that does one block at a time.
   235  	const blocksPerBuf = bufSize / blockSize
   236  	if uint64(s.counter)+blocksPerBuf > 1<<32 {
   237  		s.buf = [bufSize]byte{}
   238  		numBlocks := (len(src) + blockSize - 1) / blockSize
   239  		buf := s.buf[bufSize-numBlocks*blockSize:]
   240  		copy(buf, src)
   241  		s.xorKeyStreamBlocksGeneric(buf, buf)
   242  		s.len = len(buf) - copy(dst, buf)
   243  		return
   244  	}
   245  
   246  	// If we have a partial (multi-)block, pad it for xorKeyStreamBlocks, and
   247  	// keep the leftover keystream for the next XORKeyStream invocation.
   248  	if len(src) > 0 {
   249  		s.buf = [bufSize]byte{}
   250  		copy(s.buf[:], src)
   251  		s.xorKeyStreamBlocks(s.buf[:], s.buf[:])
   252  		s.len = bufSize - copy(dst, s.buf[:])
   253  	}
   254  }
   255  
   256  func (s *Cipher) xorKeyStreamBlocksGeneric(dst, src []byte) {
   257  	if len(dst) != len(src) || len(dst)%blockSize != 0 {
   258  		panic("chacha20: internal error: wrong dst and/or src length")
   259  	}
   260  
   261  	// To generate each block of key stream, the initial cipher state
   262  	// (represented below) is passed through 20 rounds of shuffling,
   263  	// alternatively applying quarterRounds by columns (like 1, 5, 9, 13)
   264  	// or by diagonals (like 1, 6, 11, 12).
   265  	//
   266  	//      0:cccccccc   1:cccccccc   2:cccccccc   3:cccccccc
   267  	//      4:kkkkkkkk   5:kkkkkkkk   6:kkkkkkkk   7:kkkkkkkk
   268  	//      8:kkkkkkkk   9:kkkkkkkk  10:kkkkkkkk  11:kkkkkkkk
   269  	//     12:bbbbbbbb  13:nnnnnnnn  14:nnnnnnnn  15:nnnnnnnn
   270  	//
   271  	//            c=constant k=key b=blockcount n=nonce
   272  	var (
   273  		c0, c1, c2, c3   = j0, j1, j2, j3
   274  		c4, c5, c6, c7   = s.key[0], s.key[1], s.key[2], s.key[3]
   275  		c8, c9, c10, c11 = s.key[4], s.key[5], s.key[6], s.key[7]
   276  		_, c13, c14, c15 = s.counter, s.nonce[0], s.nonce[1], s.nonce[2]
   277  	)
   278  
   279  	// Three quarters of the first round don't depend on the counter, so we can
   280  	// calculate them here, and reuse them for multiple blocks in the loop, and
   281  	// for future XORKeyStream invocations.
   282  	if !s.precompDone {
   283  		s.p1, s.p5, s.p9, s.p13 = quarterRound(c1, c5, c9, c13)
   284  		s.p2, s.p6, s.p10, s.p14 = quarterRound(c2, c6, c10, c14)
   285  		s.p3, s.p7, s.p11, s.p15 = quarterRound(c3, c7, c11, c15)
   286  		s.precompDone = true
   287  	}
   288  
   289  	// A condition of len(src) > 0 would be sufficient, but this also
   290  	// acts as a bounds check elimination hint.
   291  	for len(src) >= 64 && len(dst) >= 64 {
   292  		// The remainder of the first column round.
   293  		fcr0, fcr4, fcr8, fcr12 := quarterRound(c0, c4, c8, s.counter)
   294  
   295  		// The second diagonal round.
   296  		x0, x5, x10, x15 := quarterRound(fcr0, s.p5, s.p10, s.p15)
   297  		x1, x6, x11, x12 := quarterRound(s.p1, s.p6, s.p11, fcr12)
   298  		x2, x7, x8, x13 := quarterRound(s.p2, s.p7, fcr8, s.p13)
   299  		x3, x4, x9, x14 := quarterRound(s.p3, fcr4, s.p9, s.p14)
   300  
   301  		// The remaining 18 rounds.
   302  		for i := 0; i < 9; i++ {
   303  			// Column round.
   304  			x0, x4, x8, x12 = quarterRound(x0, x4, x8, x12)
   305  			x1, x5, x9, x13 = quarterRound(x1, x5, x9, x13)
   306  			x2, x6, x10, x14 = quarterRound(x2, x6, x10, x14)
   307  			x3, x7, x11, x15 = quarterRound(x3, x7, x11, x15)
   308  
   309  			// Diagonal round.
   310  			x0, x5, x10, x15 = quarterRound(x0, x5, x10, x15)
   311  			x1, x6, x11, x12 = quarterRound(x1, x6, x11, x12)
   312  			x2, x7, x8, x13 = quarterRound(x2, x7, x8, x13)
   313  			x3, x4, x9, x14 = quarterRound(x3, x4, x9, x14)
   314  		}
   315  
   316  		// Add back the initial state to generate the key stream, then
   317  		// XOR the key stream with the source and write out the result.
   318  		addXor(dst[0:4], src[0:4], x0, c0)
   319  		addXor(dst[4:8], src[4:8], x1, c1)
   320  		addXor(dst[8:12], src[8:12], x2, c2)
   321  		addXor(dst[12:16], src[12:16], x3, c3)
   322  		addXor(dst[16:20], src[16:20], x4, c4)
   323  		addXor(dst[20:24], src[20:24], x5, c5)
   324  		addXor(dst[24:28], src[24:28], x6, c6)
   325  		addXor(dst[28:32], src[28:32], x7, c7)
   326  		addXor(dst[32:36], src[32:36], x8, c8)
   327  		addXor(dst[36:40], src[36:40], x9, c9)
   328  		addXor(dst[40:44], src[40:44], x10, c10)
   329  		addXor(dst[44:48], src[44:48], x11, c11)
   330  		addXor(dst[48:52], src[48:52], x12, s.counter)
   331  		addXor(dst[52:56], src[52:56], x13, c13)
   332  		addXor(dst[56:60], src[56:60], x14, c14)
   333  		addXor(dst[60:64], src[60:64], x15, c15)
   334  
   335  		s.counter += 1
   336  
   337  		src, dst = src[blockSize:], dst[blockSize:]
   338  	}
   339  }
   340  
   341  // HChaCha20 uses the ChaCha20 core to generate a derived key from a 32 bytes
   342  // key and a 16 bytes nonce. It returns an error if key or nonce have any other
   343  // length. It is used as part of the XChaCha20 construction.
   344  func HChaCha20(key, nonce []byte) ([]byte, error) {
   345  	// This function is split into a wrapper so that the slice allocation will
   346  	// be inlined, and depending on how the caller uses the return value, won't
   347  	// escape to the heap.
   348  	out := make([]byte, 32)
   349  	return hChaCha20(out, key, nonce)
   350  }
   351  
   352  func hChaCha20(out, key, nonce []byte) ([]byte, error) {
   353  	if len(key) != KeySize {
   354  		return nil, errors.New("chacha20: wrong HChaCha20 key size")
   355  	}
   356  	if len(nonce) != 16 {
   357  		return nil, errors.New("chacha20: wrong HChaCha20 nonce size")
   358  	}
   359  
   360  	x0, x1, x2, x3 := j0, j1, j2, j3
   361  	x4 := binary.LittleEndian.Uint32(key[0:4])
   362  	x5 := binary.LittleEndian.Uint32(key[4:8])
   363  	x6 := binary.LittleEndian.Uint32(key[8:12])
   364  	x7 := binary.LittleEndian.Uint32(key[12:16])
   365  	x8 := binary.LittleEndian.Uint32(key[16:20])
   366  	x9 := binary.LittleEndian.Uint32(key[20:24])
   367  	x10 := binary.LittleEndian.Uint32(key[24:28])
   368  	x11 := binary.LittleEndian.Uint32(key[28:32])
   369  	x12 := binary.LittleEndian.Uint32(nonce[0:4])
   370  	x13 := binary.LittleEndian.Uint32(nonce[4:8])
   371  	x14 := binary.LittleEndian.Uint32(nonce[8:12])
   372  	x15 := binary.LittleEndian.Uint32(nonce[12:16])
   373  
   374  	for i := 0; i < 10; i++ {
   375  		// Diagonal round.
   376  		x0, x4, x8, x12 = quarterRound(x0, x4, x8, x12)
   377  		x1, x5, x9, x13 = quarterRound(x1, x5, x9, x13)
   378  		x2, x6, x10, x14 = quarterRound(x2, x6, x10, x14)
   379  		x3, x7, x11, x15 = quarterRound(x3, x7, x11, x15)
   380  
   381  		// Column round.
   382  		x0, x5, x10, x15 = quarterRound(x0, x5, x10, x15)
   383  		x1, x6, x11, x12 = quarterRound(x1, x6, x11, x12)
   384  		x2, x7, x8, x13 = quarterRound(x2, x7, x8, x13)
   385  		x3, x4, x9, x14 = quarterRound(x3, x4, x9, x14)
   386  	}
   387  
   388  	_ = out[31] // bounds check elimination hint
   389  	binary.LittleEndian.PutUint32(out[0:4], x0)
   390  	binary.LittleEndian.PutUint32(out[4:8], x1)
   391  	binary.LittleEndian.PutUint32(out[8:12], x2)
   392  	binary.LittleEndian.PutUint32(out[12:16], x3)
   393  	binary.LittleEndian.PutUint32(out[16:20], x12)
   394  	binary.LittleEndian.PutUint32(out[20:24], x13)
   395  	binary.LittleEndian.PutUint32(out[24:28], x14)
   396  	binary.LittleEndian.PutUint32(out[28:32], x15)
   397  	return out, nil
   398  }
   399
View as plain text