ocb.go

Documentation: github.com/ProtonMail/go-crypto/ocb

     1  // Copyright (C) 2019 ProtonTech AG
     2  
     3  // Package ocb provides an implementation of the OCB (offset codebook) mode of
     4  // operation, as described in RFC-7253 of the IRTF and in Rogaway, Bellare,
     5  // Black and Krovetz - OCB: A BLOCK-CIPHER MODE OF OPERATION FOR EFFICIENT
     6  // AUTHENTICATED ENCRYPTION (2003).
     7  // Security considerations (from RFC-7253): A private key MUST NOT be used to
     8  // encrypt more than 2^48 blocks. Tag length should be at least 12 bytes (a
     9  // brute-force forging adversary succeeds after 2^{tag length} attempts). A
    10  // single key SHOULD NOT be used to decrypt ciphertext with different tag
    11  // lengths. Nonces need not be secret, but MUST NOT be reused.
    12  // This package only supports underlying block ciphers with 128-bit blocks,
    13  // such as AES-{128, 192, 256}, but may be extended to other sizes.
    14  package ocb
    15  
    16  import (
    17  	"bytes"
    18  	"crypto/cipher"
    19  	"crypto/subtle"
    20  	"errors"
    21  	"github.com/ProtonMail/go-crypto/internal/byteutil"
    22  	"math/bits"
    23  )
    24  
    25  type ocb struct {
    26  	block     cipher.Block
    27  	tagSize   int
    28  	nonceSize int
    29  	mask      mask
    30  	// Optimized en/decrypt: For each nonce N used to en/decrypt, the 'Ktop'
    31  	// internal variable can be reused for en/decrypting with nonces sharing
    32  	// all but the last 6 bits with N. The prefix of the first nonce used to
    33  	// compute the new Ktop, and the Ktop value itself, are stored in
    34  	// reusableKtop. If using incremental nonces, this saves one block cipher
    35  	// call every 63 out of 64 OCB encryptions, and stores one nonce and one
    36  	// output of the block cipher in memory only.
    37  	reusableKtop reusableKtop
    38  }
    39  
    40  type mask struct {
    41  	// L_*, L_$, (L_i)_{i ∈ N}
    42  	lAst []byte
    43  	lDol []byte
    44  	L    [][]byte
    45  }
    46  
    47  type reusableKtop struct {
    48  	noncePrefix []byte
    49  	Ktop        []byte
    50  }
    51  
    52  const (
    53  	defaultTagSize   = 16
    54  	defaultNonceSize = 15
    55  )
    56  
    57  const (
    58  	enc = iota
    59  	dec
    60  )
    61  
    62  func (o *ocb) NonceSize() int {
    63  	return o.nonceSize
    64  }
    65  
    66  func (o *ocb) Overhead() int {
    67  	return o.tagSize
    68  }
    69  
    70  // NewOCB returns an OCB instance with the given block cipher and default
    71  // tag and nonce sizes.
    72  func NewOCB(block cipher.Block) (cipher.AEAD, error) {
    73  	return NewOCBWithNonceAndTagSize(block, defaultNonceSize, defaultTagSize)
    74  }
    75  
    76  // NewOCBWithNonceAndTagSize returns an OCB instance with the given block
    77  // cipher, nonce length, and tag length. Panics on zero nonceSize and
    78  // exceedingly long tag size.
    79  //
    80  // It is recommended to use at least 12 bytes as tag length.
    81  func NewOCBWithNonceAndTagSize(
    82  	block cipher.Block, nonceSize, tagSize int) (cipher.AEAD, error) {
    83  	if block.BlockSize() != 16 {
    84  		return nil, ocbError("Block cipher must have 128-bit blocks")
    85  	}
    86  	if nonceSize < 1 {
    87  		return nil, ocbError("Incorrect nonce length")
    88  	}
    89  	if nonceSize >= block.BlockSize() {
    90  		return nil, ocbError("Nonce length exceeds blocksize - 1")
    91  	}
    92  	if tagSize > block.BlockSize() {
    93  		return nil, ocbError("Custom tag length exceeds blocksize")
    94  	}
    95  	return &ocb{
    96  		block:     block,
    97  		tagSize:   tagSize,
    98  		nonceSize: nonceSize,
    99  		mask:      initializeMaskTable(block),
   100  		reusableKtop: reusableKtop{
   101  			noncePrefix: nil,
   102  			Ktop:        nil,
   103  		},
   104  	}, nil
   105  }
   106  
   107  func (o *ocb) Seal(dst, nonce, plaintext, adata []byte) []byte {
   108  	if len(nonce) > o.nonceSize {
   109  		panic("crypto/ocb: Incorrect nonce length given to OCB")
   110  	}
   111  	ret, out := byteutil.SliceForAppend(dst, len(plaintext)+o.tagSize)
   112  	o.crypt(enc, out, nonce, adata, plaintext)
   113  	return ret
   114  }
   115  
   116  func (o *ocb) Open(dst, nonce, ciphertext, adata []byte) ([]byte, error) {
   117  	if len(nonce) > o.nonceSize {
   118  		panic("Nonce too long for this instance")
   119  	}
   120  	if len(ciphertext) < o.tagSize {
   121  		return nil, ocbError("Ciphertext shorter than tag length")
   122  	}
   123  	sep := len(ciphertext) - o.tagSize
   124  	ret, out := byteutil.SliceForAppend(dst, len(ciphertext))
   125  	ciphertextData := ciphertext[:sep]
   126  	tag := ciphertext[sep:]
   127  	o.crypt(dec, out, nonce, adata, ciphertextData)
   128  	if subtle.ConstantTimeCompare(ret[sep:], tag) == 1 {
   129  		ret = ret[:sep]
   130  		return ret, nil
   131  	}
   132  	for i := range out {
   133  		out[i] = 0
   134  	}
   135  	return nil, ocbError("Tag authentication failed")
   136  }
   137  
   138  // On instruction enc (resp. dec), crypt is the encrypt (resp. decrypt)
   139  // function. It returns the resulting plain/ciphertext with the tag appended.
   140  func (o *ocb) crypt(instruction int, Y, nonce, adata, X []byte) []byte {
   141  	//
   142  	// Consider X as a sequence of 128-bit blocks
   143  	//
   144  	// Note: For encryption (resp. decryption), X is the plaintext (resp., the
   145  	// ciphertext without the tag).
   146  	blockSize := o.block.BlockSize()
   147  
   148  	//
   149  	// Nonce-dependent and per-encryption variables
   150  	//
   151  	// Zero out the last 6 bits of the nonce into truncatedNonce to see if Ktop
   152  	// is already computed.
   153  	truncatedNonce := make([]byte, len(nonce))
   154  	copy(truncatedNonce, nonce)
   155  	truncatedNonce[len(truncatedNonce)-1] &= 192
   156  	Ktop := make([]byte, blockSize)
   157  	if bytes.Equal(truncatedNonce, o.reusableKtop.noncePrefix) {
   158  		Ktop = o.reusableKtop.Ktop
   159  	} else {
   160  		// Nonce = num2str(TAGLEN mod 128, 7) || zeros(120 - bitlen(N)) || 1 || N
   161  		paddedNonce := append(make([]byte, blockSize-1-len(nonce)), 1)
   162  		paddedNonce = append(paddedNonce, truncatedNonce...)
   163  		paddedNonce[0] |= byte(((8 * o.tagSize) % (8 * blockSize)) << 1)
   164  		// Last 6 bits of paddedNonce are already zero. Encrypt into Ktop
   165  		paddedNonce[blockSize-1] &= 192
   166  		Ktop = paddedNonce
   167  		o.block.Encrypt(Ktop, Ktop)
   168  		o.reusableKtop.noncePrefix = truncatedNonce
   169  		o.reusableKtop.Ktop = Ktop
   170  	}
   171  
   172  	// Stretch = Ktop || ((lower half of Ktop) XOR (lower half of Ktop << 8))
   173  	xorHalves := make([]byte, blockSize/2)
   174  	byteutil.XorBytes(xorHalves, Ktop[:blockSize/2], Ktop[1:1+blockSize/2])
   175  	stretch := append(Ktop, xorHalves...)
   176  	bottom := int(nonce[len(nonce)-1] & 63)
   177  	offset := make([]byte, len(stretch))
   178  	byteutil.ShiftNBytesLeft(offset, stretch, bottom)
   179  	offset = offset[:blockSize]
   180  
   181  	//
   182  	// Process any whole blocks
   183  	//
   184  	// Note: For encryption Y is ciphertext || tag, for decryption Y is
   185  	// plaintext || tag.
   186  	checksum := make([]byte, blockSize)
   187  	m := len(X) / blockSize
   188  	for i := 0; i < m; i++ {
   189  		index := bits.TrailingZeros(uint(i + 1))
   190  		if len(o.mask.L)-1 < index {
   191  			o.mask.extendTable(index)
   192  		}
   193  		byteutil.XorBytesMut(offset, o.mask.L[bits.TrailingZeros(uint(i+1))])
   194  		blockX := X[i*blockSize : (i+1)*blockSize]
   195  		blockY := Y[i*blockSize : (i+1)*blockSize]
   196  		byteutil.XorBytes(blockY, blockX, offset)
   197  		switch instruction {
   198  		case enc:
   199  			o.block.Encrypt(blockY, blockY)
   200  			byteutil.XorBytesMut(blockY, offset)
   201  			byteutil.XorBytesMut(checksum, blockX)
   202  		case dec:
   203  			o.block.Decrypt(blockY, blockY)
   204  			byteutil.XorBytesMut(blockY, offset)
   205  			byteutil.XorBytesMut(checksum, blockY)
   206  		}
   207  	}
   208  	//
   209  	// Process any final partial block and compute raw tag
   210  	//
   211  	tag := make([]byte, blockSize)
   212  	if len(X)%blockSize != 0 {
   213  		byteutil.XorBytesMut(offset, o.mask.lAst)
   214  		pad := make([]byte, blockSize)
   215  		o.block.Encrypt(pad, offset)
   216  		chunkX := X[blockSize*m:]
   217  		chunkY := Y[blockSize*m : len(X)]
   218  		byteutil.XorBytes(chunkY, chunkX, pad[:len(chunkX)])
   219  		// P_* || bit(1) || zeroes(127) - len(P_*)
   220  		switch instruction {
   221  		case enc:
   222  			paddedY := append(chunkX, byte(128))
   223  			paddedY = append(paddedY, make([]byte, blockSize-len(chunkX)-1)...)
   224  			byteutil.XorBytesMut(checksum, paddedY)
   225  		case dec:
   226  			paddedX := append(chunkY, byte(128))
   227  			paddedX = append(paddedX, make([]byte, blockSize-len(chunkY)-1)...)
   228  			byteutil.XorBytesMut(checksum, paddedX)
   229  		}
   230  		byteutil.XorBytes(tag, checksum, offset)
   231  		byteutil.XorBytesMut(tag, o.mask.lDol)
   232  		o.block.Encrypt(tag, tag)
   233  		byteutil.XorBytesMut(tag, o.hash(adata))
   234  		copy(Y[blockSize*m+len(chunkY):], tag[:o.tagSize])
   235  	} else {
   236  		byteutil.XorBytes(tag, checksum, offset)
   237  		byteutil.XorBytesMut(tag, o.mask.lDol)
   238  		o.block.Encrypt(tag, tag)
   239  		byteutil.XorBytesMut(tag, o.hash(adata))
   240  		copy(Y[blockSize*m:], tag[:o.tagSize])
   241  	}
   242  	return Y
   243  }
   244  
   245  // This hash function is used to compute the tag. Per design, on empty input it
   246  // returns a slice of zeros, of the same length as the underlying block cipher
   247  // block size.
   248  func (o *ocb) hash(adata []byte) []byte {
   249  	//
   250  	// Consider A as a sequence of 128-bit blocks
   251  	//
   252  	A := make([]byte, len(adata))
   253  	copy(A, adata)
   254  	blockSize := o.block.BlockSize()
   255  
   256  	//
   257  	// Process any whole blocks
   258  	//
   259  	sum := make([]byte, blockSize)
   260  	offset := make([]byte, blockSize)
   261  	m := len(A) / blockSize
   262  	for i := 0; i < m; i++ {
   263  		chunk := A[blockSize*i : blockSize*(i+1)]
   264  		index := bits.TrailingZeros(uint(i + 1))
   265  		// If the mask table is too short
   266  		if len(o.mask.L)-1 < index {
   267  			o.mask.extendTable(index)
   268  		}
   269  		byteutil.XorBytesMut(offset, o.mask.L[index])
   270  		byteutil.XorBytesMut(chunk, offset)
   271  		o.block.Encrypt(chunk, chunk)
   272  		byteutil.XorBytesMut(sum, chunk)
   273  	}
   274  
   275  	//
   276  	// Process any final partial block; compute final hash value
   277  	//
   278  	if len(A)%blockSize != 0 {
   279  		byteutil.XorBytesMut(offset, o.mask.lAst)
   280  		// Pad block with 1 || 0 ^ 127 - bitlength(a)
   281  		ending := make([]byte, blockSize-len(A)%blockSize)
   282  		ending[0] = 0x80
   283  		encrypted := append(A[blockSize*m:], ending...)
   284  		byteutil.XorBytesMut(encrypted, offset)
   285  		o.block.Encrypt(encrypted, encrypted)
   286  		byteutil.XorBytesMut(sum, encrypted)
   287  	}
   288  	return sum
   289  }
   290  
   291  func initializeMaskTable(block cipher.Block) mask {
   292  	//
   293  	// Key-dependent variables
   294  	//
   295  	lAst := make([]byte, block.BlockSize())
   296  	block.Encrypt(lAst, lAst)
   297  	lDol := byteutil.GfnDouble(lAst)
   298  	L := make([][]byte, 1)
   299  	L[0] = byteutil.GfnDouble(lDol)
   300  
   301  	return mask{
   302  		lAst: lAst,
   303  		lDol: lDol,
   304  		L:    L,
   305  	}
   306  }
   307  
   308  // Extends the L array of mask m up to L[limit], with L[i] = GfnDouble(L[i-1])
   309  func (m *mask) extendTable(limit int) {
   310  	for i := len(m.L); i <= limit; i++ {
   311  		m.L = append(m.L, byteutil.GfnDouble(m.L[i-1]))
   312  	}
   313  }
   314  
   315  func ocbError(err string) error {
   316  	return errors.New("crypto/ocb: " + err)
   317  }
   318
View as plain text