MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
twofish.cpp
1 /*
2  Copyright (c) 2006, 2012, Oracle and/or its affiliates. All rights reserved.
3 
4  This program is free software; you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation; version 2 of the License.
7 
8  This program is distributed in the hope that it will be useful,
9  but WITHOUT ANY WARRANTY; without even the implied warranty of
10  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  GNU General Public License for more details.
12 
13  You should have received a copy of the GNU General Public License
14  along with this program; see the file COPYING. If not, write to the
15  Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
16  MA 02110-1301 USA.
17 */
18 
19 /* C++ based on Wei Dai's twofish.cpp from CryptoPP */
20 /* x86 asm original */
21 
22 
23 #if defined(TAOCRYPT_KERNEL_MODE)
24  #define DO_TAOCRYPT_KERNEL_MODE
25 #endif // only some modules now support this
26 
27 #include "runtime.hpp"
28 #include "twofish.hpp"
29 
30 
31 
32 namespace TaoCrypt {
33 
34 
35 #if defined(DO_TWOFISH_ASM)
36 
37 // ia32 optimized version
38 void Twofish::Process(byte* out, const byte* in, word32 sz)
39 {
40  if (!isMMX) {
41  Mode_BASE::Process(out, in, sz);
42  return;
43  }
44 
45  word32 blocks = sz / BLOCK_SIZE;
46 
47  if (mode_ == ECB)
48  while (blocks--) {
49  if (dir_ == ENCRYPTION)
50  AsmEncrypt(in, out);
51  else
52  AsmDecrypt(in, out);
53 
54  out += BLOCK_SIZE;
55  in += BLOCK_SIZE;
56  }
57  else if (mode_ == CBC) {
58  if (dir_ == ENCRYPTION)
59  while (blocks--) {
60  r_[0] ^= *(word32*)in;
61  r_[1] ^= *(word32*)(in + 4);
62  r_[2] ^= *(word32*)(in + 8);
63  r_[3] ^= *(word32*)(in + 12);
64 
65  AsmEncrypt((byte*)r_, (byte*)r_);
66  memcpy(out, r_, BLOCK_SIZE);
67 
68  out += BLOCK_SIZE;
69  in += BLOCK_SIZE;
70  }
71  else
72  while (blocks--) {
73  AsmDecrypt(in, out);
74 
75  *(word32*)out ^= r_[0];
76  *(word32*)(out + 4) ^= r_[1];
77  *(word32*)(out + 8) ^= r_[2];
78  *(word32*)(out + 12) ^= r_[3];
79 
80  memcpy(r_, in, BLOCK_SIZE);
81 
82  out += BLOCK_SIZE;
83  in += BLOCK_SIZE;
84  }
85  }
86 }
87 
88 #endif // DO_TWOFISH_ASM
89 
90 
91 namespace { // locals
92 
93 // compute (c * x^4) mod (x^4 + (a + 1/a) * x^3 + a * x^2 + (a + 1/a) * x + 1)
94 // over GF(256)
95 static inline unsigned int Mod(unsigned int c)
96 {
97  static const unsigned int modulus = 0x14d;
98  unsigned int c2 = (c<<1) ^ ((c & 0x80) ? modulus : 0);
99  unsigned int c1 = c2 ^ (c>>1) ^ ((c & 1) ? (modulus>>1) : 0);
100  return c | (c1 << 8) | (c2 << 16) | (c1 << 24);
101 }
102 
103 // compute RS(12,8) code with the above polynomial as generator
104 // this is equivalent to multiplying by the RS matrix
105 static word32 ReedSolomon(word32 high, word32 low)
106 {
107  for (unsigned int i=0; i<8; i++) {
108  high = Mod(high>>24) ^ (high<<8) ^ (low>>24);
109  low <<= 8;
110  }
111  return high;
112 }
113 
114 } // local namespace
115 
116 
117 
118 inline word32 Twofish::h0(word32 x, const word32* key, unsigned int kLen)
119 {
120  x = x | (x<<8) | (x<<16) | (x<<24);
121  switch(kLen)
122  {
123 #define Q(a, b, c, d, t) q_[a][GETBYTE(t,0)] ^ (q_[b][GETBYTE(t,1)] << 8) ^ \
124  (q_[c][GETBYTE(t,2)] << 16) ^ (q_[d][GETBYTE(t,3)] << 24)
125  case 4: x = Q(1, 0, 0, 1, x) ^ key[6];
126  case 3: x = Q(1, 1, 0, 0, x) ^ key[4];
127  case 2: x = Q(0, 1, 0, 1, x) ^ key[2];
128  x = Q(0, 0, 1, 1, x) ^ key[0];
129  }
130  return x;
131 }
132 
133 inline word32 Twofish::h(word32 x, const word32* key, unsigned int kLen)
134 {
135  x = h0(x, key, kLen);
136  return mds_[0][GETBYTE(x,0)] ^ mds_[1][GETBYTE(x,1)] ^
137  mds_[2][GETBYTE(x,2)] ^ mds_[3][GETBYTE(x,3)];
138 }
139 
140 
141 void Twofish::SetKey(const byte* userKey, word32 keylen, CipherDir /*dummy*/)
142 {
143  unsigned int len = (keylen <= 16 ? 2 : (keylen <= 24 ? 3 : 4));
144  word32 key[8];
145  GetUserKey(LittleEndianOrder, key, len*2, userKey, keylen);
146 
147  unsigned int i;
148  for (i=0; i<40; i+=2) {
149  word32 a = h(i, key, len);
150  word32 b = rotlFixed(h(i+1, key+1, len), 8);
151  k_[i] = a+b;
152  k_[i+1] = rotlFixed(a+2*b, 9);
153  }
154 
155  word32 svec[8];
156  for (i=0; i<len; i++)
157  svec[2*(len-i-1)] = ReedSolomon(key[2*i+1], key[2*i]);
158 
159  for (i=0; i<256; i++) {
160  word32 t = h0(i, svec, len);
161  s_[0][i] = mds_[0][GETBYTE(t, 0)];
162  s_[1][i] = mds_[1][GETBYTE(t, 1)];
163  s_[2][i] = mds_[2][GETBYTE(t, 2)];
164  s_[3][i] = mds_[3][GETBYTE(t, 3)];
165  }
166 }
167 
168 
169 void Twofish::ProcessAndXorBlock(const byte* in, const byte* xOr, byte* out)
170  const
171 {
172  if (dir_ == ENCRYPTION)
173  encrypt(in, xOr, out);
174  else
175  decrypt(in, xOr, out);
176 }
177 
178 #define G1(x) (s_[0][GETBYTE(x,0)] ^ s_[1][GETBYTE(x,1)] ^ \
179  s_[2][GETBYTE(x,2)] ^ s_[3][GETBYTE(x,3)])
180 #define G2(x) (s_[0][GETBYTE(x,3)] ^ s_[1][GETBYTE(x,0)] ^ \
181  s_[2][GETBYTE(x,1)] ^ s_[3][GETBYTE(x,2)])
182 
183 #define ENCROUND(n, a, b, c, d) \
184  x = G1 (a); y = G2 (b); \
185  x += y; y += x + k[2 * (n) + 1]; \
186  (c) ^= x + k[2 * (n)]; \
187  (c) = rotrFixed(c, 1); \
188  (d) = rotlFixed(d, 1) ^ y
189 
190 #define ENCCYCLE(n) \
191  ENCROUND (2 * (n), a, b, c, d); \
192  ENCROUND (2 * (n) + 1, c, d, a, b)
193 
194 #define DECROUND(n, a, b, c, d) \
195  x = G1 (a); y = G2 (b); \
196  x += y; y += x; \
197  (d) ^= y + k[2 * (n) + 1]; \
198  (d) = rotrFixed(d, 1); \
199  (c) = rotlFixed(c, 1); \
200  (c) ^= (x + k[2 * (n)])
201 
202 #define DECCYCLE(n) \
203  DECROUND (2 * (n) + 1, c, d, a, b); \
204  DECROUND (2 * (n), a, b, c, d)
205 
206 
207 typedef BlockGetAndPut<word32, LittleEndian> gpBlock;
208 
209 void Twofish::encrypt(const byte* inBlock, const byte* xorBlock,
210  byte* outBlock) const
211 {
212  word32 x, y, a, b, c, d;
213 
214  gpBlock::Get(inBlock)(a)(b)(c)(d);
215 
216  a ^= k_[0];
217  b ^= k_[1];
218  c ^= k_[2];
219  d ^= k_[3];
220 
221  const word32 *k = k_+8;
222 
223  ENCCYCLE (0);
224  ENCCYCLE (1);
225  ENCCYCLE (2);
226  ENCCYCLE (3);
227  ENCCYCLE (4);
228  ENCCYCLE (5);
229  ENCCYCLE (6);
230  ENCCYCLE (7);
231 
232  c ^= k_[4];
233  d ^= k_[5];
234  a ^= k_[6];
235  b ^= k_[7];
236 
237  gpBlock::Put(xorBlock, outBlock)(c)(d)(a)(b);
238 }
239 
240 
241 void Twofish::decrypt(const byte* inBlock, const byte* xorBlock,
242  byte* outBlock) const
243 {
244  word32 x, y, a, b, c, d;
245 
246  gpBlock::Get(inBlock)(c)(d)(a)(b);
247 
248  c ^= k_[4];
249  d ^= k_[5];
250  a ^= k_[6];
251  b ^= k_[7];
252 
253  const word32 *k = k_+8;
254  DECCYCLE (7);
255  DECCYCLE (6);
256  DECCYCLE (5);
257  DECCYCLE (4);
258  DECCYCLE (3);
259  DECCYCLE (2);
260  DECCYCLE (1);
261  DECCYCLE (0);
262 
263  a ^= k_[0];
264  b ^= k_[1];
265  c ^= k_[2];
266  d ^= k_[3];
267 
268  gpBlock::Put(xorBlock, outBlock)(a)(b)(c)(d);
269 }
270 
271 
272 
273 #if defined(DO_TWOFISH_ASM)
274  #ifdef __GNUC__
275  #define AS1(x) asm(#x);
276  #define AS2(x, y) asm(#x ", " #y);
277 
278  #define PROLOG() \
279  asm(".intel_syntax noprefix"); \
280  AS2( movd mm3, edi ) \
281  AS2( movd mm4, ebx ) \
282  AS2( movd mm5, esi ) \
283  AS2( movd mm6, ebp ) \
284  AS2( mov edi, DWORD PTR [ebp + 8] ) \
285  AS2( mov esi, DWORD PTR [ebp + 12] )
286 
287  #define EPILOG() \
288  AS2( movd esp, mm6 ) \
289  AS2( movd esi, mm5 ) \
290  AS2( movd ebx, mm4 ) \
291  AS2( movd edi, mm3 ) \
292  AS1( emms ) \
293  asm(".att_syntax");
294  #else
295  #define AS1(x) __asm x
296  #define AS2(x, y) __asm x, y
297 
298  #define PROLOG() \
299  AS1( push ebp ) \
300  AS2( mov ebp, esp ) \
301  AS2( movd mm3, edi ) \
302  AS2( movd mm4, ebx ) \
303  AS2( movd mm5, esi ) \
304  AS2( movd mm6, ebp ) \
305  AS2( mov edi, ecx ) \
306  AS2( mov esi, DWORD PTR [ebp + 8] )
307 
308  /* ebp already set */
309  #define EPILOG() \
310  AS2( movd esi, mm5 ) \
311  AS2( movd ebx, mm4 ) \
312  AS2( movd edi, mm3 ) \
313  AS2( mov esp, ebp ) \
314  AS1( pop ebp ) \
315  AS1( emms ) \
316  AS1( ret 8 )
317 
318  #endif
319 
320 
321 
322 
323  // x = esi, y = [esp], s_ = ebp
324  // edi always open for G1 and G2
325  // G1 also uses edx after save and restore
326  // G2 also uses eax after save and restore
327  // and ecx for tmp [esp] which Rounds also use
328  // and restore from mm7
329 
330  // x = G1(a) bytes(0,1,2,3)
331 #define ASMG1(z, zl, zh) \
332  AS2( movd mm2, edx ) \
333  AS2( movzx edi, zl ) \
334  AS2( mov esi, DWORD PTR [ebp + edi*4] ) \
335  AS2( movzx edx, zh ) \
336  AS2( xor esi, DWORD PTR 1024[ebp + edx*4] ) \
337  \
338  AS2( mov edx, z ) \
339  AS2( shr edx, 16 ) \
340  AS2( movzx edi, dl ) \
341  AS2( xor esi, DWORD PTR 2048[ebp + edi*4] ) \
342  AS2( movzx edx, dh ) \
343  AS2( xor esi, DWORD PTR 3072[ebp + edx*4] ) \
344  AS2( movd edx, mm2 )
345 
346 
347  // y = G2(b) bytes(3,0,1,2) [ put y into ecx for Rounds ]
348 #define ASMG2(z, zl, zh) \
349  AS2( movd mm7, ecx ) \
350  AS2( movd mm2, eax ) \
351  AS2( mov edi, z ) \
352  AS2( shr edi, 24 ) \
353  AS2( mov ecx, DWORD PTR [ebp + edi*4] ) \
354  AS2( movzx eax, zl ) \
355  AS2( xor ecx, DWORD PTR 1024[ebp + eax*4] ) \
356  \
357  AS2( mov eax, z ) \
358  AS2( shr eax, 16 ) \
359  AS2( movzx edi, zh ) \
360  AS2( xor ecx, DWORD PTR 2048[ebp + edi*4] ) \
361  AS2( movzx eax, al ) \
362  AS2( xor ecx, DWORD PTR 3072[ebp + eax*4] ) \
363  AS2( movd eax, mm2 )
364 
365 
366  // encrypt Round (n),
367  // x = esi, k = ebp, edi open
368  // y is in ecx from G2, restore when done from mm7
369  // before C (which be same register!)
370 #define ASMENCROUND(N, A, A2, A3, B, B2, B3, C, D) \
371  /* setup s_ */ \
372  AS2( movd ebp, mm1 ) \
373  ASMG1(A, A2, A3) \
374  ASMG2(B, B2, B3) \
375  /* setup k */ \
376  AS2( movd ebp, mm0 ) \
377  /* x += y */ \
378  AS2( add esi, ecx ) \
379  AS2( add ebp, 32 ) \
380  /* y += x + k[2 * (n) + 1] */ \
381  AS2( add ecx, esi ) \
382  AS2( rol D, 1 ) \
383  AS2( add ecx, DWORD PTR [ebp + 8 * N + 4] ) \
384  /* (d) = rotlFixed(d, 1) ^ y */ \
385  AS2( xor D, ecx ) \
386  AS2( movd ecx, mm7 ) \
387  /* (c) ^= x + k[2 * (n)] */ \
388  AS2( mov edi, esi ) \
389  AS2( add edi, DWORD PTR [ebp + 8 * N] ) \
390  AS2( xor C, edi ) \
391  /* (c) = rotrFixed(c, 1) */ \
392  AS2( ror C, 1 )
393 
394 
395  // decrypt Round (n),
396  // x = esi, k = ebp, edi open
397  // y is in ecx from G2, restore ecx from mm7 when done
398 #define ASMDECROUND(N, A, A2, A3, B, B2, B3, C, D) \
399  /* setup s_ */ \
400  AS2( movd ebp, mm1 ) \
401  ASMG1(A, A2, A3) \
402  ASMG2(B, B2, B3) \
403  /* setup k */ \
404  AS2( movd ebp, mm0 ) \
405  /* x += y */ \
406  AS2( add esi, ecx ) \
407  AS2( add ebp, 32 ) \
408  /* y += x */ \
409  AS2( add ecx, esi ) \
410  /* (d) ^= y + k[2 * (n) + 1] */ \
411  AS2( mov edi, DWORD PTR [ebp + 8 * N + 4] ) \
412  AS2( add edi, ecx ) \
413  AS2( movd ecx, mm7 ) \
414  AS2( xor D, edi ) \
415  /* (d) = rotrFixed(d, 1) */ \
416  AS2( ror D, 1 ) \
417  /* (c) = rotlFixed(c, 1) */ \
418  AS2( rol C, 1 ) \
419  /* (c) ^= (x + k[2 * (n)]) */ \
420  AS2( mov edi, esi ) \
421  AS2( add edi, DWORD PTR [ebp + 8 * N] ) \
422  AS2( xor C, edi )
423 
424 
425 #ifdef _MSC_VER
426  __declspec(naked)
427 #endif
428 void Twofish::AsmEncrypt(const byte* inBlock, byte* outBlock) const
429 {
430  PROLOG()
431 
432  #ifdef OLD_GCC_OFFSET
433  AS2( add edi, 60 ) // k_
434  #else
435  AS2( add edi, 56 ) // k_
436  #endif
437 
438  AS2( mov ebp, edi )
439 
440  AS2( mov eax, DWORD PTR [esi] ) // a
441  AS2( movd mm0, edi ) // store k_
442  AS2( mov ebx, DWORD PTR [esi + 4] ) // b
443  AS2( add ebp, 160 ) // s_[0]
444  AS2( mov ecx, DWORD PTR [esi + 8] ) // c
445  AS2( movd mm1, ebp ) // store s_
446  AS2( mov edx, DWORD PTR [esi + 12] ) // d
447 
448  AS2( xor eax, DWORD PTR [edi] ) // k_[0]
449  AS2( xor ebx, DWORD PTR [edi + 4] ) // [1]
450  AS2( xor ecx, DWORD PTR [edi + 8] ) // [2]
451  AS2( xor edx, DWORD PTR [edi + 12] ) // [3]
452 
453 
454  ASMENCROUND( 0, eax, al, ah, ebx, bl, bh, ecx, edx)
455  ASMENCROUND( 1, ecx, cl, ch, edx, dl, dh, eax, ebx)
456  ASMENCROUND( 2, eax, al, ah, ebx, bl, bh, ecx, edx)
457  ASMENCROUND( 3, ecx, cl, ch, edx, dl, dh, eax, ebx)
458  ASMENCROUND( 4, eax, al, ah, ebx, bl, bh, ecx, edx)
459  ASMENCROUND( 5, ecx, cl, ch, edx, dl, dh, eax, ebx)
460  ASMENCROUND( 6, eax, al, ah, ebx, bl, bh, ecx, edx)
461  ASMENCROUND( 7, ecx, cl, ch, edx, dl, dh, eax, ebx)
462  ASMENCROUND( 8, eax, al, ah, ebx, bl, bh, ecx, edx)
463  ASMENCROUND( 9, ecx, cl, ch, edx, dl, dh, eax, ebx)
464  ASMENCROUND(10, eax, al, ah, ebx, bl, bh, ecx, edx)
465  ASMENCROUND(11, ecx, cl, ch, edx, dl, dh, eax, ebx)
466  ASMENCROUND(12, eax, al, ah, ebx, bl, bh, ecx, edx)
467  ASMENCROUND(13, ecx, cl, ch, edx, dl, dh, eax, ebx)
468  ASMENCROUND(14, eax, al, ah, ebx, bl, bh, ecx, edx)
469  ASMENCROUND(15, ecx, cl, ch, edx, dl, dh, eax, ebx)
470 
471 
472  AS2( movd ebp, mm6 )
473  AS2( movd esi, mm0 ) // k_
474  #ifdef __GNUC__
475  AS2( mov edi, [ebp + 16] ) // outBlock
476  #else
477  AS2( mov edi, [ebp + 12] ) // outBlock
478  #endif
479 
480  AS2( xor ecx, DWORD PTR [esi + 16] ) // k_[4]
481  AS2( xor edx, DWORD PTR [esi + 20] ) // k_[5]
482  AS2( xor eax, DWORD PTR [esi + 24] ) // k_[6]
483  AS2( xor ebx, DWORD PTR [esi + 28] ) // k_[7]
484 
485  AS2( mov [edi], ecx ) // write out
486  AS2( mov [edi + 4], edx ) // write out
487  AS2( mov [edi + 8], eax ) // write out
488  AS2( mov [edi + 12], ebx ) // write out
489 
490 
491  EPILOG()
492 }
493 
494 
495 #ifdef _MSC_VER
496  __declspec(naked)
497 #endif
498 void Twofish::AsmDecrypt(const byte* inBlock, byte* outBlock) const
499 {
500  PROLOG()
501 
502  #ifdef OLD_GCC_OFFSET
503  AS2( add edi, 60 ) // k_
504  #else
505  AS2( add edi, 56 ) // k_
506  #endif
507 
508  AS2( mov ebp, edi )
509 
510  AS2( mov ecx, DWORD PTR [esi] ) // c
511  AS2( movd mm0, edi ) // store k_
512  AS2( mov edx, DWORD PTR [esi + 4] ) // d
513  AS2( add ebp, 160 ) // s_[0]
514  AS2( mov eax, DWORD PTR [esi + 8] ) // a
515  AS2( movd mm1, ebp ) // store s_
516  AS2( mov ebx, DWORD PTR [esi + 12] ) // b
517 
518  AS2( xor ecx, DWORD PTR [edi + 16] ) // k_[4]
519  AS2( xor edx, DWORD PTR [edi + 20] ) // [5]
520  AS2( xor eax, DWORD PTR [edi + 24] ) // [6]
521  AS2( xor ebx, DWORD PTR [edi + 28] ) // [7]
522 
523 
524  ASMDECROUND(15, ecx, cl, ch, edx, dl, dh, eax, ebx)
525  ASMDECROUND(14, eax, al, ah, ebx, bl, bh, ecx, edx)
526  ASMDECROUND(13, ecx, cl, ch, edx, dl, dh, eax, ebx)
527  ASMDECROUND(12, eax, al, ah, ebx, bl, bh, ecx, edx)
528  ASMDECROUND(11, ecx, cl, ch, edx, dl, dh, eax, ebx)
529  ASMDECROUND(10, eax, al, ah, ebx, bl, bh, ecx, edx)
530  ASMDECROUND( 9, ecx, cl, ch, edx, dl, dh, eax, ebx)
531  ASMDECROUND( 8, eax, al, ah, ebx, bl, bh, ecx, edx)
532  ASMDECROUND( 7, ecx, cl, ch, edx, dl, dh, eax, ebx)
533  ASMDECROUND( 6, eax, al, ah, ebx, bl, bh, ecx, edx)
534  ASMDECROUND( 5, ecx, cl, ch, edx, dl, dh, eax, ebx)
535  ASMDECROUND( 4, eax, al, ah, ebx, bl, bh, ecx, edx)
536  ASMDECROUND( 3, ecx, cl, ch, edx, dl, dh, eax, ebx)
537  ASMDECROUND( 2, eax, al, ah, ebx, bl, bh, ecx, edx)
538  ASMDECROUND( 1, ecx, cl, ch, edx, dl, dh, eax, ebx)
539  ASMDECROUND( 0, eax, al, ah, ebx, bl, bh, ecx, edx)
540 
541 
542  AS2( movd ebp, mm6 )
543  AS2( movd esi, mm0 ) // k_
544  #ifdef __GNUC__
545  AS2( mov edi, [ebp + 16] ) // outBlock
546  #else
547  AS2( mov edi, [ebp + 12] ) // outBlock
548  #endif
549 
550  AS2( xor eax, DWORD PTR [esi ] ) // k_[0]
551  AS2( xor ebx, DWORD PTR [esi + 4] ) // k_[1]
552  AS2( xor ecx, DWORD PTR [esi + 8] ) // k_[2]
553  AS2( xor edx, DWORD PTR [esi + 12] ) // k_[3]
554 
555  AS2( mov [edi], eax ) // write out
556  AS2( mov [edi + 4], ebx ) // write out
557  AS2( mov [edi + 8], ecx ) // write out
558  AS2( mov [edi + 12], edx ) // write out
559 
560 
561  EPILOG()
562 }
563 
564 
565 
566 #endif // defined(DO_TWOFISH_ASM)
567 
568 
569 
570 
571 
572 } // namespace
573 
574