twofish.go

Documentation: golang.org/x/crypto/twofish

     1  // Copyright 2011 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 twofish implements Bruce Schneier's Twofish encryption algorithm.
     6  //
     7  // Deprecated: Twofish is a legacy cipher and should not be used for new
     8  // applications. Also, this package does not and will not provide an optimized
     9  // implementation. Instead, use AES (from crypto/aes, if necessary in an AEAD
    10  // mode like crypto/cipher.NewGCM) or XChaCha20-Poly1305 (from
    11  // golang.org/x/crypto/chacha20poly1305).
    12  package twofish // import "golang.org/x/crypto/twofish"
    13  
    14  // Twofish is defined in https://www.schneier.com/paper-twofish-paper.pdf [TWOFISH]
    15  
    16  // This code is a port of the LibTom C implementation.
    17  // See http://libtom.org/?page=features&newsitems=5&whatfile=crypt.
    18  // LibTomCrypt is free for all purposes under the public domain.
    19  // It was heavily inspired by the go blowfish package.
    20  
    21  import (
    22  	"math/bits"
    23  	"strconv"
    24  )
    25  
    26  // BlockSize is the constant block size of Twofish.
    27  const BlockSize = 16
    28  
    29  const mdsPolynomial = 0x169 // x^8 + x^6 + x^5 + x^3 + 1, see [TWOFISH] 4.2
    30  const rsPolynomial = 0x14d  // x^8 + x^6 + x^3 + x^2 + 1, see [TWOFISH] 4.3
    31  
    32  // A Cipher is an instance of Twofish encryption using a particular key.
    33  type Cipher struct {
    34  	s [4][256]uint32
    35  	k [40]uint32
    36  }
    37  
    38  type KeySizeError int
    39  
    40  func (k KeySizeError) Error() string {
    41  	return "crypto/twofish: invalid key size " + strconv.Itoa(int(k))
    42  }
    43  
    44  // NewCipher creates and returns a Cipher.
    45  // The key argument should be the Twofish key, 16, 24 or 32 bytes.
    46  func NewCipher(key []byte) (*Cipher, error) {
    47  	keylen := len(key)
    48  
    49  	if keylen != 16 && keylen != 24 && keylen != 32 {
    50  		return nil, KeySizeError(keylen)
    51  	}
    52  
    53  	// k is the number of 64 bit words in key
    54  	k := keylen / 8
    55  
    56  	// Create the S[..] words
    57  	var S [4 * 4]byte
    58  	for i := 0; i < k; i++ {
    59  		// Computes [y0 y1 y2 y3] = rs . [x0 x1 x2 x3 x4 x5 x6 x7]
    60  		for j, rsRow := range rs {
    61  			for k, rsVal := range rsRow {
    62  				S[4*i+j] ^= gfMult(key[8*i+k], rsVal, rsPolynomial)
    63  			}
    64  		}
    65  	}
    66  
    67  	// Calculate subkeys
    68  	c := new(Cipher)
    69  	var tmp [4]byte
    70  	for i := byte(0); i < 20; i++ {
    71  		// A = h(p * 2x, Me)
    72  		for j := range tmp {
    73  			tmp[j] = 2 * i
    74  		}
    75  		A := h(tmp[:], key, 0)
    76  
    77  		// B = rolc(h(p * (2x + 1), Mo), 8)
    78  		for j := range tmp {
    79  			tmp[j] = 2*i + 1
    80  		}
    81  		B := h(tmp[:], key, 1)
    82  		B = bits.RotateLeft32(B, 8)
    83  
    84  		c.k[2*i] = A + B
    85  
    86  		// K[2i+1] = (A + 2B) <<< 9
    87  		c.k[2*i+1] = bits.RotateLeft32(2*B+A, 9)
    88  	}
    89  
    90  	// Calculate sboxes
    91  	switch k {
    92  	case 2:
    93  		for i := range c.s[0] {
    94  			c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][byte(i)]^S[0]]^S[4]], 0)
    95  			c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][byte(i)]^S[1]]^S[5]], 1)
    96  			c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][byte(i)]^S[2]]^S[6]], 2)
    97  			c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][byte(i)]^S[3]]^S[7]], 3)
    98  		}
    99  	case 3:
   100  		for i := range c.s[0] {
   101  			c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][sbox[1][byte(i)]^S[0]]^S[4]]^S[8]], 0)
   102  			c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][sbox[1][byte(i)]^S[1]]^S[5]]^S[9]], 1)
   103  			c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][sbox[0][byte(i)]^S[2]]^S[6]]^S[10]], 2)
   104  			c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][sbox[0][byte(i)]^S[3]]^S[7]]^S[11]], 3)
   105  		}
   106  	default:
   107  		for i := range c.s[0] {
   108  			c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][sbox[1][sbox[1][byte(i)]^S[0]]^S[4]]^S[8]]^S[12]], 0)
   109  			c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][sbox[1][sbox[0][byte(i)]^S[1]]^S[5]]^S[9]]^S[13]], 1)
   110  			c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][sbox[0][sbox[0][byte(i)]^S[2]]^S[6]]^S[10]]^S[14]], 2)
   111  			c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][sbox[0][sbox[1][byte(i)]^S[3]]^S[7]]^S[11]]^S[15]], 3)
   112  		}
   113  	}
   114  
   115  	return c, nil
   116  }
   117  
   118  // BlockSize returns the Twofish block size, 16 bytes.
   119  func (c *Cipher) BlockSize() int { return BlockSize }
   120  
   121  // store32l stores src in dst in little-endian form.
   122  func store32l(dst []byte, src uint32) {
   123  	dst[0] = byte(src)
   124  	dst[1] = byte(src >> 8)
   125  	dst[2] = byte(src >> 16)
   126  	dst[3] = byte(src >> 24)
   127  	return
   128  }
   129  
   130  // load32l reads a little-endian uint32 from src.
   131  func load32l(src []byte) uint32 {
   132  	return uint32(src[0]) | uint32(src[1])<<8 | uint32(src[2])<<16 | uint32(src[3])<<24
   133  }
   134  
   135  // The RS matrix. See [TWOFISH] 4.3
   136  var rs = [4][8]byte{
   137  	{0x01, 0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E},
   138  	{0xA4, 0x56, 0x82, 0xF3, 0x1E, 0xC6, 0x68, 0xE5},
   139  	{0x02, 0xA1, 0xFC, 0xC1, 0x47, 0xAE, 0x3D, 0x19},
   140  	{0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E, 0x03},
   141  }
   142  
   143  // sbox tables
   144  var sbox = [2][256]byte{
   145  	{
   146  		0xa9, 0x67, 0xb3, 0xe8, 0x04, 0xfd, 0xa3, 0x76, 0x9a, 0x92, 0x80, 0x78, 0xe4, 0xdd, 0xd1, 0x38,
   147  		0x0d, 0xc6, 0x35, 0x98, 0x18, 0xf7, 0xec, 0x6c, 0x43, 0x75, 0x37, 0x26, 0xfa, 0x13, 0x94, 0x48,
   148  		0xf2, 0xd0, 0x8b, 0x30, 0x84, 0x54, 0xdf, 0x23, 0x19, 0x5b, 0x3d, 0x59, 0xf3, 0xae, 0xa2, 0x82,
   149  		0x63, 0x01, 0x83, 0x2e, 0xd9, 0x51, 0x9b, 0x7c, 0xa6, 0xeb, 0xa5, 0xbe, 0x16, 0x0c, 0xe3, 0x61,
   150  		0xc0, 0x8c, 0x3a, 0xf5, 0x73, 0x2c, 0x25, 0x0b, 0xbb, 0x4e, 0x89, 0x6b, 0x53, 0x6a, 0xb4, 0xf1,
   151  		0xe1, 0xe6, 0xbd, 0x45, 0xe2, 0xf4, 0xb6, 0x66, 0xcc, 0x95, 0x03, 0x56, 0xd4, 0x1c, 0x1e, 0xd7,
   152  		0xfb, 0xc3, 0x8e, 0xb5, 0xe9, 0xcf, 0xbf, 0xba, 0xea, 0x77, 0x39, 0xaf, 0x33, 0xc9, 0x62, 0x71,
   153  		0x81, 0x79, 0x09, 0xad, 0x24, 0xcd, 0xf9, 0xd8, 0xe5, 0xc5, 0xb9, 0x4d, 0x44, 0x08, 0x86, 0xe7,
   154  		0xa1, 0x1d, 0xaa, 0xed, 0x06, 0x70, 0xb2, 0xd2, 0x41, 0x7b, 0xa0, 0x11, 0x31, 0xc2, 0x27, 0x90,
   155  		0x20, 0xf6, 0x60, 0xff, 0x96, 0x5c, 0xb1, 0xab, 0x9e, 0x9c, 0x52, 0x1b, 0x5f, 0x93, 0x0a, 0xef,
   156  		0x91, 0x85, 0x49, 0xee, 0x2d, 0x4f, 0x8f, 0x3b, 0x47, 0x87, 0x6d, 0x46, 0xd6, 0x3e, 0x69, 0x64,
   157  		0x2a, 0xce, 0xcb, 0x2f, 0xfc, 0x97, 0x05, 0x7a, 0xac, 0x7f, 0xd5, 0x1a, 0x4b, 0x0e, 0xa7, 0x5a,
   158  		0x28, 0x14, 0x3f, 0x29, 0x88, 0x3c, 0x4c, 0x02, 0xb8, 0xda, 0xb0, 0x17, 0x55, 0x1f, 0x8a, 0x7d,
   159  		0x57, 0xc7, 0x8d, 0x74, 0xb7, 0xc4, 0x9f, 0x72, 0x7e, 0x15, 0x22, 0x12, 0x58, 0x07, 0x99, 0x34,
   160  		0x6e, 0x50, 0xde, 0x68, 0x65, 0xbc, 0xdb, 0xf8, 0xc8, 0xa8, 0x2b, 0x40, 0xdc, 0xfe, 0x32, 0xa4,
   161  		0xca, 0x10, 0x21, 0xf0, 0xd3, 0x5d, 0x0f, 0x00, 0x6f, 0x9d, 0x36, 0x42, 0x4a, 0x5e, 0xc1, 0xe0,
   162  	},
   163  	{
   164  		0x75, 0xf3, 0xc6, 0xf4, 0xdb, 0x7b, 0xfb, 0xc8, 0x4a, 0xd3, 0xe6, 0x6b, 0x45, 0x7d, 0xe8, 0x4b,
   165  		0xd6, 0x32, 0xd8, 0xfd, 0x37, 0x71, 0xf1, 0xe1, 0x30, 0x0f, 0xf8, 0x1b, 0x87, 0xfa, 0x06, 0x3f,
   166  		0x5e, 0xba, 0xae, 0x5b, 0x8a, 0x00, 0xbc, 0x9d, 0x6d, 0xc1, 0xb1, 0x0e, 0x80, 0x5d, 0xd2, 0xd5,
   167  		0xa0, 0x84, 0x07, 0x14, 0xb5, 0x90, 0x2c, 0xa3, 0xb2, 0x73, 0x4c, 0x54, 0x92, 0x74, 0x36, 0x51,
   168  		0x38, 0xb0, 0xbd, 0x5a, 0xfc, 0x60, 0x62, 0x96, 0x6c, 0x42, 0xf7, 0x10, 0x7c, 0x28, 0x27, 0x8c,
   169  		0x13, 0x95, 0x9c, 0xc7, 0x24, 0x46, 0x3b, 0x70, 0xca, 0xe3, 0x85, 0xcb, 0x11, 0xd0, 0x93, 0xb8,
   170  		0xa6, 0x83, 0x20, 0xff, 0x9f, 0x77, 0xc3, 0xcc, 0x03, 0x6f, 0x08, 0xbf, 0x40, 0xe7, 0x2b, 0xe2,
   171  		0x79, 0x0c, 0xaa, 0x82, 0x41, 0x3a, 0xea, 0xb9, 0xe4, 0x9a, 0xa4, 0x97, 0x7e, 0xda, 0x7a, 0x17,
   172  		0x66, 0x94, 0xa1, 0x1d, 0x3d, 0xf0, 0xde, 0xb3, 0x0b, 0x72, 0xa7, 0x1c, 0xef, 0xd1, 0x53, 0x3e,
   173  		0x8f, 0x33, 0x26, 0x5f, 0xec, 0x76, 0x2a, 0x49, 0x81, 0x88, 0xee, 0x21, 0xc4, 0x1a, 0xeb, 0xd9,
   174  		0xc5, 0x39, 0x99, 0xcd, 0xad, 0x31, 0x8b, 0x01, 0x18, 0x23, 0xdd, 0x1f, 0x4e, 0x2d, 0xf9, 0x48,
   175  		0x4f, 0xf2, 0x65, 0x8e, 0x78, 0x5c, 0x58, 0x19, 0x8d, 0xe5, 0x98, 0x57, 0x67, 0x7f, 0x05, 0x64,
   176  		0xaf, 0x63, 0xb6, 0xfe, 0xf5, 0xb7, 0x3c, 0xa5, 0xce, 0xe9, 0x68, 0x44, 0xe0, 0x4d, 0x43, 0x69,
   177  		0x29, 0x2e, 0xac, 0x15, 0x59, 0xa8, 0x0a, 0x9e, 0x6e, 0x47, 0xdf, 0x34, 0x35, 0x6a, 0xcf, 0xdc,
   178  		0x22, 0xc9, 0xc0, 0x9b, 0x89, 0xd4, 0xed, 0xab, 0x12, 0xa2, 0x0d, 0x52, 0xbb, 0x02, 0x2f, 0xa9,
   179  		0xd7, 0x61, 0x1e, 0xb4, 0x50, 0x04, 0xf6, 0xc2, 0x16, 0x25, 0x86, 0x56, 0x55, 0x09, 0xbe, 0x91,
   180  	},
   181  }
   182  
   183  // gfMult returns a·b in GF(2^8)/p
   184  func gfMult(a, b byte, p uint32) byte {
   185  	B := [2]uint32{0, uint32(b)}
   186  	P := [2]uint32{0, p}
   187  	var result uint32
   188  
   189  	// branchless GF multiplier
   190  	for i := 0; i < 7; i++ {
   191  		result ^= B[a&1]
   192  		a >>= 1
   193  		B[1] = P[B[1]>>7] ^ (B[1] << 1)
   194  	}
   195  	result ^= B[a&1]
   196  	return byte(result)
   197  }
   198  
   199  // mdsColumnMult calculates y{col} where [y0 y1 y2 y3] = MDS · [x0]
   200  func mdsColumnMult(in byte, col int) uint32 {
   201  	mul01 := in
   202  	mul5B := gfMult(in, 0x5B, mdsPolynomial)
   203  	mulEF := gfMult(in, 0xEF, mdsPolynomial)
   204  
   205  	switch col {
   206  	case 0:
   207  		return uint32(mul01) | uint32(mul5B)<<8 | uint32(mulEF)<<16 | uint32(mulEF)<<24
   208  	case 1:
   209  		return uint32(mulEF) | uint32(mulEF)<<8 | uint32(mul5B)<<16 | uint32(mul01)<<24
   210  	case 2:
   211  		return uint32(mul5B) | uint32(mulEF)<<8 | uint32(mul01)<<16 | uint32(mulEF)<<24
   212  	case 3:
   213  		return uint32(mul5B) | uint32(mul01)<<8 | uint32(mulEF)<<16 | uint32(mul5B)<<24
   214  	}
   215  
   216  	panic("unreachable")
   217  }
   218  
   219  // h implements the S-box generation function. See [TWOFISH] 4.3.5
   220  func h(in, key []byte, offset int) uint32 {
   221  	var y [4]byte
   222  	for x := range y {
   223  		y[x] = in[x]
   224  	}
   225  	switch len(key) / 8 {
   226  	case 4:
   227  		y[0] = sbox[1][y[0]] ^ key[4*(6+offset)+0]
   228  		y[1] = sbox[0][y[1]] ^ key[4*(6+offset)+1]
   229  		y[2] = sbox[0][y[2]] ^ key[4*(6+offset)+2]
   230  		y[3] = sbox[1][y[3]] ^ key[4*(6+offset)+3]
   231  		fallthrough
   232  	case 3:
   233  		y[0] = sbox[1][y[0]] ^ key[4*(4+offset)+0]
   234  		y[1] = sbox[1][y[1]] ^ key[4*(4+offset)+1]
   235  		y[2] = sbox[0][y[2]] ^ key[4*(4+offset)+2]
   236  		y[3] = sbox[0][y[3]] ^ key[4*(4+offset)+3]
   237  		fallthrough
   238  	case 2:
   239  		y[0] = sbox[1][sbox[0][sbox[0][y[0]]^key[4*(2+offset)+0]]^key[4*(0+offset)+0]]
   240  		y[1] = sbox[0][sbox[0][sbox[1][y[1]]^key[4*(2+offset)+1]]^key[4*(0+offset)+1]]
   241  		y[2] = sbox[1][sbox[1][sbox[0][y[2]]^key[4*(2+offset)+2]]^key[4*(0+offset)+2]]
   242  		y[3] = sbox[0][sbox[1][sbox[1][y[3]]^key[4*(2+offset)+3]]^key[4*(0+offset)+3]]
   243  	}
   244  	// [y0 y1 y2 y3] = MDS . [x0 x1 x2 x3]
   245  	var mdsMult uint32
   246  	for i := range y {
   247  		mdsMult ^= mdsColumnMult(y[i], i)
   248  	}
   249  	return mdsMult
   250  }
   251  
   252  // Encrypt encrypts a 16-byte block from src to dst, which may overlap.
   253  // Note that for amounts of data larger than a block,
   254  // it is not safe to just call Encrypt on successive blocks;
   255  // instead, use an encryption mode like CBC (see crypto/cipher/cbc.go).
   256  func (c *Cipher) Encrypt(dst, src []byte) {
   257  	S1 := c.s[0]
   258  	S2 := c.s[1]
   259  	S3 := c.s[2]
   260  	S4 := c.s[3]
   261  
   262  	// Load input
   263  	ia := load32l(src[0:4])
   264  	ib := load32l(src[4:8])
   265  	ic := load32l(src[8:12])
   266  	id := load32l(src[12:16])
   267  
   268  	// Pre-whitening
   269  	ia ^= c.k[0]
   270  	ib ^= c.k[1]
   271  	ic ^= c.k[2]
   272  	id ^= c.k[3]
   273  
   274  	for i := 0; i < 8; i++ {
   275  		k := c.k[8+i*4 : 12+i*4]
   276  		t2 := S2[byte(ib)] ^ S3[byte(ib>>8)] ^ S4[byte(ib>>16)] ^ S1[byte(ib>>24)]
   277  		t1 := S1[byte(ia)] ^ S2[byte(ia>>8)] ^ S3[byte(ia>>16)] ^ S4[byte(ia>>24)] + t2
   278  		ic = bits.RotateLeft32(ic^(t1+k[0]), -1)
   279  		id = bits.RotateLeft32(id, 1) ^ (t2 + t1 + k[1])
   280  
   281  		t2 = S2[byte(id)] ^ S3[byte(id>>8)] ^ S4[byte(id>>16)] ^ S1[byte(id>>24)]
   282  		t1 = S1[byte(ic)] ^ S2[byte(ic>>8)] ^ S3[byte(ic>>16)] ^ S4[byte(ic>>24)] + t2
   283  		ia = bits.RotateLeft32(ia^(t1+k[2]), -1)
   284  		ib = bits.RotateLeft32(ib, 1) ^ (t2 + t1 + k[3])
   285  	}
   286  
   287  	// Output with "undo last swap"
   288  	ta := ic ^ c.k[4]
   289  	tb := id ^ c.k[5]
   290  	tc := ia ^ c.k[6]
   291  	td := ib ^ c.k[7]
   292  
   293  	store32l(dst[0:4], ta)
   294  	store32l(dst[4:8], tb)
   295  	store32l(dst[8:12], tc)
   296  	store32l(dst[12:16], td)
   297  }
   298  
   299  // Decrypt decrypts a 16-byte block from src to dst, which may overlap.
   300  func (c *Cipher) Decrypt(dst, src []byte) {
   301  	S1 := c.s[0]
   302  	S2 := c.s[1]
   303  	S3 := c.s[2]
   304  	S4 := c.s[3]
   305  
   306  	// Load input
   307  	ta := load32l(src[0:4])
   308  	tb := load32l(src[4:8])
   309  	tc := load32l(src[8:12])
   310  	td := load32l(src[12:16])
   311  
   312  	// Undo undo final swap
   313  	ia := tc ^ c.k[6]
   314  	ib := td ^ c.k[7]
   315  	ic := ta ^ c.k[4]
   316  	id := tb ^ c.k[5]
   317  
   318  	for i := 8; i > 0; i-- {
   319  		k := c.k[4+i*4 : 8+i*4]
   320  		t2 := S2[byte(id)] ^ S3[byte(id>>8)] ^ S4[byte(id>>16)] ^ S1[byte(id>>24)]
   321  		t1 := S1[byte(ic)] ^ S2[byte(ic>>8)] ^ S3[byte(ic>>16)] ^ S4[byte(ic>>24)] + t2
   322  		ia = bits.RotateLeft32(ia, 1) ^ (t1 + k[2])
   323  		ib = bits.RotateLeft32(ib^(t2+t1+k[3]), -1)
   324  
   325  		t2 = S2[byte(ib)] ^ S3[byte(ib>>8)] ^ S4[byte(ib>>16)] ^ S1[byte(ib>>24)]
   326  		t1 = S1[byte(ia)] ^ S2[byte(ia>>8)] ^ S3[byte(ia>>16)] ^ S4[byte(ia>>24)] + t2
   327  		ic = bits.RotateLeft32(ic, 1) ^ (t1 + k[0])
   328  		id = bits.RotateLeft32(id^(t2+t1+k[1]), -1)
   329  	}
   330  
   331  	// Undo pre-whitening
   332  	ia ^= c.k[0]
   333  	ib ^= c.k[1]
   334  	ic ^= c.k[2]
   335  	id ^= c.k[3]
   336  
   337  	store32l(dst[0:4], ia)
   338  	store32l(dst[4:8], ib)
   339  	store32l(dst[8:12], ic)
   340  	store32l(dst[12:16], id)
   341  }
   342
View as plain text