vendor/golang.org/x/crypto/twofish/twofish.go

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