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