逆向分析加解密之TwoFish算法

逆向分析加解密之TwoFish算法
2019-07-31 10:15:00 Author: xz.aliyun.com(查看原文) 阅读量:119 收藏

前几天某师傅给我发来一个逆向题，拿来分析发现竟是AES决赛算法之一的TwoFish算法，之前网上对此算法的逆向分析竟然一个都没有，对算法的介绍也只有寥寥数语，于是想准备在这里与大家分享对该算法的逆向分析以及CTF中此算法的变体。

算法流程

官方有一个68页的pdf，有兴趣可以看一下
http://www.schneier.com/twofish-analysis-shiho.pdf

流程图

TwoFish的意思应该就是这样交叉运算的形状吧

算法分析

TwoFish加密需要明文(plain)和密钥(key)
总的来说进行一次加解密可分为三个环节

Input whitening
16次循环
Output whitening

Input whitening

拓展密钥

在Twofish 算法中，规定密钥的长度 N = 128, N = 192, N = 256三种。也就是说密钥的长度可以在128-bit ~ 256-bit之间变化。

我们需要产生40个与密钥相关的K(i)，这里的K(i)是根据密钥算出来的32-bit数据
除此以外，我们还需要4个与密钥相关的S-box，也就是s(i)()。

为计算K和S，定义MDS矩阵

且对于MDS 矩阵，有限域GF的定义如下：
GF(2^8) ≡ GF(2)(x)/v(x)，其中v(x) = x^8 + x^6 + x^5 + x^3 + 1

此外还需要h函数

y(k,j) = x(j)                     j = 0, ... ,3

     如果：k == 4

         y(3,0) = q1[y(4,0)] xor l(3,0)
         y(3,1) = q0[y(4,1)] xor l(3,1)
         y(3,2) = q0[y(4,2)] xor l(3,2)
         y(3,3) = q1[y(4,3)] xor l(3,3)

     如果：k >= 3

         y(2,0) = q1[y(3,0)] xor l(2,0)
         y(2,1) = q1[y(3,1)] xor l(2,1)
         y(2,2) = q0[y(3,2)] xor l(2,2)
         y(2,3) = q0[y(3,3)] xor l(3,3)

     对于所有情况：

         y0 = q1[q0[q0[y(2,0)] xor l(1,0)] xor l(0,0)]
         y1 = q0[q0[q1[y(2,1)] xor l(1,1)] xor l(0,1)]
         y2 = q1[q1[q0[y(2,2)] xor l(1,2)] xor l(0,2)]
         y3 = q0[q1[q1[y(2,3)] xor l(1,3)] xor l(0,3)]

实现代码稍后来说

输入白化

因为加密前的plain text是128 bits，也就是16 bytes。假设这16 bytes分别是p0, ... ,p15。将p0, ... ,p15分为4组：
P(i) = ∑p(4i+j)2^(8j)，其中i,j = 0, ... ,3

然后进行运算R(0,i) = P(i) xor K(i)，其中i = 0, ... ,3

16次运算

将以下公式循环16次

(F(r,0), F(r,1)) = F(R(r,0), R(r,1), r)
   R(r+1,0) = ROR(R(r,2) xor F(r,0), 1)
   R(r+1,1) = ROL(R(r,3), 1) xor F(r,1)
   R(r+1,2) = R(r,0)
   R(r+1,3) = R(r,1)

其中，F函数为以下操作

t0 = g(r0)
t1 = rol(r1, 8)
t1 = g(t1)
o = 2*r
F0 = (T0 +  T1 + K(2r+8)) mod 2^32
F1 = (T0 + 2T1 + K(2r+9)) mod 2^32

其中g函数为核心函数

x(i) = [X/2^(8i)] mod 2^8  其中i = 0, ... ,3
     y(i) = s(i)(x(i))       其中i = 0, ... ,3

Z = ∑z(i)2^(8i)，其中i = 0, ... ,3

输出白化

C(i) = R(16,(i+2) mod 4) xor K(i+4)，其中i = 0, ... ,3

最后计算组成密文

c(i) = [C(i/4) / 2^(8(i mod 4))] mod 2^8，其中i = 0, ... ,15

下面来逆向分析看一下实际实现吧

逆向分析

拿到题后PEID分析

分析到了TwoFish算法

IDA分析一下，进入主函数看到流程

发现有五个选项，选项名字在sub_402FDA中

int sub_402FDA()
{
  puts("welcome to jiami jiemi game go.go.go.");
  puts("1._jiemi_(admin only)");
  puts("2._jiami_");
  puts("3._jiemi__flag(admin only)");
  puts("4.exit");
  return puts("5._yanzheng__");
}

只有选项2和5可用，即加密和验证flag

进入验证函数sub_40302B查看

这里我已经注释出密文和key，因此我们只需要解密即可，但只用标准解密算法就可以吗？我们来验证一下

很明显加密函数为sub_402E5D(&key, plain, &v3); 参数v3传出密钥

_BYTE *__cdecl sub_402E5D(int a1, int a2, int a3)
{
  _DWORD *v3; // ST1C_4

  v3 = sub_401570(a1, 128u);                    // a1 = key   密钥生成k和s
  sub_401626(v3, a2, a3);                          //输入白化，循环，输出白化
  return sub_401626(v3, (a2 + 16), a3 + 16);
}

下面来结合标准实现分析

int __cdecl sub_401570(int a1, unsigned int a2)
{
  _DWORD *v2; // ST1C_4
  _BYTE *v3; // ST18_4
  void *v4; // eax
  int v5; // eax
  int v6; // ST14_4

  v2 = sub_402D53(a1, a2 >> 3);                 // key_t* tf_key = expand_key(s, len/8);  拓展密钥
  v3 = sub_4025C6(v2);                          // subkey_t *tf_subkey = Twofish_generate_subkey(tf_key);  生成密钥
  v4 = malloc(4260u);
  v5 = sub_401B7A(v4, v3, 0x1010101, *v2 >> 3); // tf_twofish = Twofish_generate_ext_k_keys(tf_twofish,tf_subkey,0x01010101,(tf_key->len/8));  生成k
  v6 = sub_401CF8(v5, v3, *v2 >> 3);            // tf_twofish = Twofish_generate_ext_s_keys(tf_twofish,tf_subkey,(tf_key->len/8));  生成s
  free(v2[1]);
  free(v2);
  free(v3);
  return v6;
}

拓展密钥

可以看到题中对位数分析的判定进行了修改

生成密钥

c实现

rsm函数定义为

#define rsm(i,a,b,c,d,e,f,g,h)  \
        gf(nxt(tf_key->k,r*8),a,0x14d)^gf(nxt(tf_key->k,r*8+1),b,0x14d)^\
        gf(nxt(tf_key->k,r*8+2),c,0x14d)^gf(nxt(tf_key->k,r*8+3),d,0x14d)^\
        gf(nxt(tf_key->k,r*8+4),e,0x14d)^gf(nxt(tf_key->k,r*8+5),f,0x14d)^\
        gf(nxt(tf_key->k,r*8+6),g,0x14d)^gf(nxt(tf_key->k,r*8+7),h,0x14d)

k生成

h函数内部，可以看出，IDA将二维数组直接一维化

q0,q1都是256大小的数组

标准

uint8_t q[2][256] =
{
    /* q0 */
    {   0xa9,0x67,0xb3,0xe8,0x4,0xfd,0xa3,0x76,0x9a,0x92,0x80,0x78,0xe4,0xdd,0xd1,0x38,
0xd,0xc6,0x35,0x98,0x18,0xf7,0xec,0x6c,0x43,0x75,0x37,0x26,0xfa,0x13,0x94,0x48,
0xf2,0xd0,0x8b,0x30,0x84,0x54,0xdf,0x23,0x19,0x5b,0x3d,0x59,0xf3,0xae,0xa2,0x82,
0x63,0x1,0x83,0x2e,0xd9,0x51,0x9b,0x7c,0xa6,0xeb,0xa5,0xbe,0x16,0xc,0xe3,0x61,
0xc0,0x8c,0x3a,0xf5,0x73,0x2c,0x25,0xb,0xbb,0x4e,0x89,0x6b,0x53,0x6a,0xb4,0xf1,
0xe1,0xe6,0xbd,0x45,0xe2,0xf4,0xb6,0x66,0xcc,0x95,0x3,0x56,0xd4,0x1c,0x1e,0xd7,
0xfb,0xc3,0x8e,0xb5,0xe9,0xcf,0xbf,0xba,0xea,0x77,0x39,0xaf,0x33,0xc9,0x62,0x71,
0x81,0x79,0x9,0xad,0x24,0xcd,0xf9,0xd8,0xe5,0xc5,0xb9,0x4d,0x44,0x8,0x86,0xe7,
0xa1,0x1d,0xaa,0xed,0x6,0x70,0xb2,0xd2,0x41,0x7b,0xa0,0x11,0x31,0xc2,0x27,0x90,
0x20,0xf6,0x60,0xff,0x96,0x5c,0xb1,0xab,0x9e,0x9c,0x52,0x1b,0x5f,0x93,0xa,0xef,
0x91,0x85,0x49,0xee,0x2d,0x4f,0x8f,0x3b,0x47,0x87,0x6d,0x46,0xd6,0x3e,0x69,0x64,
0x2a,0xce,0xcb,0x2f,0xfc,0x97,0x5,0x7a,0xac,0x7f,0xd5,0x1a,0x4b,0xe,0xa7,0x5a,
0x28,0x14,0x3f,0x29,0x88,0x3c,0x4c,0x2,0xb8,0xda,0xb0,0x17,0x55,0x1f,0x8a,0x7d,
0x57,0xc7,0x8d,0x74,0xb7,0xc4,0x9f,0x72,0x7e,0x15,0x22,0x12,0x58,0x7,0x99,0x34,
0x6e,0x50,0xde,0x68,0x65,0xbc,0xdb,0xf8,0xc8,0xa8,0x2b,0x40,0xdc,0xfe,0x32,0xa4,
0xca,0x10,0x21,0xf0,0xd3,0x5d,0xf,0x0,0x6f,0x9d,0x36,0x42,0x4a,0x5e,0xc1,0xe0
    },
    /* q1 */
    {
0x75,0xf3,0xc6,0xf4,0xdb,0x7b,0xfb,0xc8,0x4a,0xd3,0xe6,0x6b,0x45,0x7d,0xe8,0x4b,
0xd6,0x32,0xd8,0xfd,0x37,0x71,0xf1,0xe1,0x30,0xf,0xf8,0x1b,0x87,0xfa,0x6,0x3f,
0x5e,0xba,0xae,0x5b,0x8a,0x0,0xbc,0x9d,0x6d,0xc1,0xb1,0xe,0x80,0x5d,0xd2,0xd5,
0xa0,0x84,0x7,0x14,0xb5,0x90,0x2c,0xa3,0xb2,0x73,0x4c,0x54,0x92,0x74,0x36,0x51,
0x38,0xb0,0xbd,0x5a,0xfc,0x60,0x62,0x96,0x6c,0x42,0xf7,0x10,0x7c,0x28,0x27,0x8c,
0x13,0x95,0x9c,0xc7,0x24,0x46,0x3b,0x70,0xca,0xe3,0x85,0xcb,0x11,0xd0,0x93,0xb8,
0xa6,0x83,0x20,0xff,0x9f,0x77,0xc3,0xcc,0x3,0x6f,0x8,0xbf,0x40,0xe7,0x2b,0xe2,
0x79,0xc,0xaa,0x82,0x41,0x3a,0xea,0xb9,0xe4,0x9a,0xa4,0x97,0x7e,0xda,0x7a,0x17,
0x66,0x94,0xa1,0x1d,0x3d,0xf0,0xde,0xb3,0xb,0x72,0xa7,0x1c,0xef,0xd1,0x53,0x3e,
0x8f,0x33,0x26,0x5f,0xec,0x76,0x2a,0x49,0x81,0x88,0xee,0x21,0xc4,0x1a,0xeb,0xd9,
0xc5,0x39,0x99,0xcd,0xad,0x31,0x8b,0x1,0x18,0x23,0xdd,0x1f,0x4e,0x2d,0xf9,0x48,
0x4f,0xf2,0x65,0x8e,0x78,0x5c,0x58,0x19,0x8d,0xe5,0x98,0x57,0x67,0x7f,0x5,0x64,
0xaf,0x63,0xb6,0xfe,0xf5,0xb7,0x3c,0xa5,0xce,0xe9,0x68,0x44,0xe0,0x4d,0x43,0x69,
0x29,0x2e,0xac,0x15,0x59,0xa8,0xa,0x9e,0x6e,0x47,0xdf,0x34,0x35,0x6a,0xcf,0xdc,
0x22,0xc9,0xc0,0x9b,0x89,0xd4,0xed,0xab,0x12,0xa2,0xd,0x52,0xbb,0x2,0x2f,0xa9,
0xd7,0x61,0x1e,0xb4,0x50,0x4,0xf6,0xc2,0x16,0x25,0x86,0x56,0x55,0x9,0xbe,0x91
    }
};

MDS矩阵运算

S-box生成

输入白化，循环，输出白化 sub_401626

c实现

f函数

算法解密

解密函数如下

void Twofish_decryt(twofish_t* tf_twofish, uint8_t *cypher, uint8_t *data)
{
    uint32_t r0, r1, r2, r3, f0, f1, c2,c3;
    /* Input Whitenening */
    r0 = tf_twofish->k[4]^pack(cypher);
    r1 = tf_twofish->k[5]^pack(cypher+4);
    r2 = tf_twofish->k[6]^pack(cypher+8);
    r3 = tf_twofish->k[7]^pack(cypher+12);

    /* The black box */
    for (int i=15; i >= 0;--i)
    {
        Twofish_f(tf_twofish, i, r0, r1, &f0, &f1);
        c2 = (rol(r2,1)^f0);
        c3 = ror((f1^r3),1);
        /* swap */
        r2 = r0;
        r3 = r1;
        r0 = c2;
        r1 = c3;
    }

    /* Output Whitening */
    c2 = r0;
    c3 = r1;
    r0 = tf_twofish->k[0]^r2;
    r1 = tf_twofish->k[1]^r3;
    r2 = tf_twofish->k[2]^c2;
    r3 = tf_twofish->k[3]^c3;

    for (int i=0;i<4;++i)
    {
        data[i]   = unpack(r0,i);
        data[i+4] = unpack(r1,i);
        data[i+8] = unpack(r2,i);
        data[i+12]= unpack(r3,i);
    }
}

因此TwoFish加解密代码如下

twofish.h

#ifndef __TWOFISH__H
#define __TWOFISH__H
#include "stdint.h"

#define TWOFISH
#ifdef  TWOFISH
typedef struct twofish_t 
{
    uint8_t len;
    uint32_t k[40];
    uint32_t s[4][256];
}twofish_t;
#endif
/*
 * Twofish MDS Multiply Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   data
 * @param   cypher
 * @usage
 * {@code}
 */
void Twofish_encryt(twofish_t* tf_twofish, uint8_t *data, uint8_t *cypher);
/*
 * Twofish Decryption Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   cypher
 * @param   data
 * @usage
 * {@code}
 */
void Twofish_decryt(twofish_t* tf_twofish, uint8_t *cypher, uint8_t *data);
/*
 * Twofish Setup Function
 * 
 * Description:
 *
 * @param   s
 * @param   len
 * @usage
 * {@code}
 */
twofish_t*  Twofish_setup(uint8_t *s, uint32_t len);

#endif

tables.h

#ifndef __TABLES__H
 #define __TABLES__H

 /* The MDS Matrix */
 uint8_t mds[4][4]=
 {
    {0x01, 0xef, 0x5b, 0x5b},
    {0x5b, 0xef, 0xef, 0x01},
    {0xef, 0x5b, 0x01, 0xef},
    {0xef, 0x01, 0xef, 0x5b}
 };

uint8_t q[2][256] =
{
    /* q0 */
    {

        0xa9,0x67,0xb3,0xe8,0x4,0xfd,0xa3,0x76,0x9a,0x92,0x80,0x78,0xe4,0xdd,0xd1,0x38,
        0xd,0xc6,0x35,0x98,0x18,0xf7,0xec,0x6c,0x43,0x75,0x37,0x26,0xfa,0x13,0x94,0x48,
        0xf2,0xd0,0x8b,0x30,0x84,0x54,0xdf,0x23,0x19,0x5b,0x3d,0x59,0xf3,0xae,0xa2,0x82,
        0x63,0x1,0x83,0x2e,0xd9,0x51,0x9b,0x7c,0xa6,0xeb,0xa5,0xbe,0x16,0xc,0xe3,0x61,
        0xc0,0x8c,0x3a,0xf5,0x73,0x2c,0x25,0xb,0xbb,0x4e,0x89,0x6b,0x53,0x6a,0xb4,0xf1,
        0xe1,0xe6,0xbd,0x45,0xe2,0xf4,0xb6,0x66,0xcc,0x95,0x3,0x56,0xd4,0x1c,0x1e,0xd7,
        0xfb,0xc3,0x8e,0xb5,0xe9,0xcf,0xbf,0xba,0xea,0x77,0x39,0xaf,0x33,0xc9,0x62,0x71,
        0x81,0x79,0x9,0xad,0x24,0xcd,0xf9,0xd8,0xe5,0xc5,0xb9,0x4d,0x44,0x8,0x86,0xe7,
        0xa1,0x1d,0xaa,0xed,0x6,0x70,0xb2,0xd2,0x41,0x7b,0xa0,0x11,0x31,0xc2,0x27,0x90,
        0x20,0xf6,0x60,0xff,0x96,0x5c,0xb1,0xab,0x9e,0x9c,0x52,0x1b,0x5f,0x93,0xa,0xef,
        0x91,0x85,0x49,0xee,0x2d,0x4f,0x8f,0x3b,0x47,0x87,0x6d,0x46,0xd6,0x3e,0x69,0x64,
        0x2a,0xce,0xcb,0x2f,0xfc,0x97,0x5,0x7a,0xac,0x7f,0xd5,0x1a,0x4b,0xe,0xa7,0x5a,
        0x28,0x14,0x3f,0x29,0x88,0x3c,0x4c,0x2,0xb8,0xda,0xb0,0x17,0x55,0x1f,0x8a,0x7d,
        0x57,0xc7,0x8d,0x74,0xb7,0xc4,0x9f,0x72,0x7e,0x15,0x22,0x12,0x58,0x7,0x99,0x34,
        0x6e,0x50,0xde,0x68,0x65,0xbc,0xdb,0xf8,0xc8,0xa8,0x2b,0x40,0xdc,0xfe,0x32,0xa4,
        0xca,0x10,0x21,0xf0,0xd3,0x5d,0xf,0x0,0x6f,0x9d,0x36,0x42,0x4a,0x5e,0xc1,0xe0
    },
    /* q1 */
    {

        0x75,0xf3,0xc6,0xf4,0xdb,0x7b,0xfb,0xc8,0x4a,0xd3,0xe6,0x6b,0x45,0x7d,0xe8,0x4b,
        0xd6,0x32,0xd8,0xfd,0x37,0x71,0xf1,0xe1,0x30,0xf,0xf8,0x1b,0x87,0xfa,0x6,0x3f,
        0x5e,0xba,0xae,0x5b,0x8a,0x0,0xbc,0x9d,0x6d,0xc1,0xb1,0xe,0x80,0x5d,0xd2,0xd5,
        0xa0,0x84,0x7,0x14,0xb5,0x90,0x2c,0xa3,0xb2,0x73,0x4c,0x54,0x92,0x74,0x36,0x51,
        0x38,0xb0,0xbd,0x5a,0xfc,0x60,0x62,0x96,0x6c,0x42,0xf7,0x10,0x7c,0x28,0x27,0x8c,
        0x13,0x95,0x9c,0xc7,0x24,0x46,0x3b,0x70,0xca,0xe3,0x85,0xcb,0x11,0xd0,0x93,0xb8,
        0xa6,0x83,0x20,0xff,0x9f,0x77,0xc3,0xcc,0x3,0x6f,0x8,0xbf,0x40,0xe7,0x2b,0xe2,
        0x79,0xc,0xaa,0x82,0x41,0x3a,0xea,0xb9,0xe4,0x9a,0xa4,0x97,0x7e,0xda,0x7a,0x17,
        0x66,0x94,0xa1,0x1d,0x3d,0xf0,0xde,0xb3,0xb,0x72,0xa7,0x1c,0xef,0xd1,0x53,0x3e,
        0x8f,0x33,0x26,0x5f,0xec,0x76,0x2a,0x49,0x81,0x88,0xee,0x21,0xc4,0x1a,0xeb,0xd9,
        0xc5,0x39,0x99,0xcd,0xad,0x31,0x8b,0x1,0x18,0x23,0xdd,0x1f,0x4e,0x2d,0xf9,0x48,
        0x4f,0xf2,0x65,0x8e,0x78,0x5c,0x58,0x19,0x8d,0xe5,0x98,0x57,0x67,0x7f,0x5,0x64,
        0xaf,0x63,0xb6,0xfe,0xf5,0xb7,0x3c,0xa5,0xce,0xe9,0x68,0x44,0xe0,0x4d,0x43,0x69,
        0x29,0x2e,0xac,0x15,0x59,0xa8,0xa,0x9e,0x6e,0x47,0xdf,0x34,0x35,0x6a,0xcf,0xdc,
        0x22,0xc9,0xc0,0x9b,0x89,0xd4,0xed,0xab,0x12,0xa2,0xd,0x52,0xbb,0x2,0x2f,0xa9,
        0xd7,0x61,0x1e,0xb4,0x50,0x4,0xf6,0xc2,0x16,0x25,0x86,0x56,0x55,0x9,0xbe,0x91
    }
};

#endif

twofish.c

#include <stdio.h>
#include <malloc.h>
#include "twofish.h"
#include "tables.h"

#define xor(g,r)    (g^r)                   /* Xor operation */
#define ror(g,n)    ((g>>n)|(g<<(32-n)))    /* Rotate right  */
#define rol(g,n)    ((g<<n)|(g>>(32-n)))    /* Rotate left   */
#define nxt(g,r)    (*(g+r))                /* Get next byte */
#define LITTILE_ENDIAN
#ifdef  LITTILE_ENDIAN
#define unpack(g,r) ((g>>(r*8))&0xff)                               /* Extracts a byte from a word.  */
#define pack(g)     ((*(g))|(*(g+1)<<8)|(*(g+2)<<16)|(*(g+3)<<24))  /* Converts four byte to a word. */
#endif
#define rsm(i,a,b,c,d,e,f,g,h)  \
        gf(nxt(tf_key->k,r*8),a,0x14d)^gf(nxt(tf_key->k,r*8+1),b,0x14d)^\
        gf(nxt(tf_key->k,r*8+2),c,0x14d)^gf(nxt(tf_key->k,r*8+3),d,0x14d)^\
        gf(nxt(tf_key->k,r*8+4),e,0x14d)^gf(nxt(tf_key->k,r*8+5),f,0x14d)^\
        gf(nxt(tf_key->k,r*8+6),g,0x14d)^gf(nxt(tf_key->k,r*8+7),h,0x14d)
#define u(x,a)\
        x[0] = unpack(a,0); \
        x[1] = unpack(a,1); \
        x[2] = unpack(a,2); \
        x[3] = unpack(a,3);
#define release(a,b,c)  { free(a); free(b);free(c); }
#ifdef  TWOFISH
typedef struct key_t 
{
    uint8_t len;
    uint8_t *k;
}key_t;
typedef struct subkey_t 
{
    uint8_t len;
    uint8_t s[4][4];
    uint8_t me[4][4];
    uint8_t mo[4][4];
}subkey_t;
#endif
/*
 * Twofish Expand Key Function
 * 
 * Description:
 *
 * @param   s
 * @param   len
 * @usage
 * {@code}
 */
key_t* expand_key(uint8_t *s, uint32_t len);
/*
 * Twofish Galois Field Multiplication Function
 * 
 * Description:
 *
 * @param   x
 * @param   y
 * @param   m
 * @usage
 * {@code}
 */
uint8_t gf(uint8_t x, uint8_t y, uint16_t m);
/*
 * Twofish Generate Subkeys Function
 * 
 * Description:
 *
 * @param   tf_key
 * @usage
 * {@code}
 */
subkey_t* Twofish_generate_subkey(key_t* tf_key);
/*
 * Twofish h Function
 * 
 * Description:
 *
 * @param   x[]
 * @param   y[]
 * @param   s
 * @param   stage
 * @usage
 * {@code}
 */
void Twofish_h(uint8_t x[],  uint8_t y[], uint8_t s[][4], int stage);
/*
 * Twofish MDS Multiply Function
 * 
 * Description:
 *
 * @param   y[]
 * @param   out[]
 * @usage
 * {@code}
 */
void Twofish_mds_mul(uint8_t y[],  uint8_t out[]);
/*
 * Twofish Genrate Extended K Keys Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   tf_subkey
 * @param   p
 * @param   k
 * @usage
 * {@code}
 */
twofish_t* Twofish_generate_ext_k_keys(twofish_t* tf_twofish, subkey_t *tf_subkey,uint32_t p, uint8_t k);
/*
 * Twofish Genrate Extended S Keys Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   tf_subkey
 * @param   k
 * @usage
 * {@code}
 */
twofish_t* Twofish_generate_ext_s_keys(twofish_t* tf_twofish, subkey_t *tf_subkey, uint8_t k);
/*
 * Twofish f Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   r
 * @param   r0, r1
 * @param   f0, f1
 * @usage
 * {@code}
 */
void Twofish_f(twofish_t* tf_twofish, uint8_t r,uint32_t r0, uint32_t r1, uint32_t* f0, uint32_t* f1);
/*
 * Twofish g Function
 * 
 * Description:
 *
 * @param   tf_twofish
 * @param   x
 * @usage
 * {@code}
 */
uint32_t Twofish_g(twofish_t* tf_twofish, uint32_t x);

twofish_t* Twofish_setup(uint8_t *s, uint32_t len)
{
    /* Expand the key if necessary. */
    key_t* tf_key = expand_key(s, len/8);

    /* Generate subkeys: s and k */
    subkey_t *tf_subkey = Twofish_generate_subkey(tf_key);

    /* Generate 40 K keys */
    twofish_t* tf_twofish = (twofish_t*)malloc(sizeof(twofish_t));
    tf_twofish = Twofish_generate_ext_k_keys(tf_twofish,tf_subkey,0x01010101,(tf_key->len/8));
    /* Generate 4x256 S keys */
    tf_twofish = Twofish_generate_ext_s_keys(tf_twofish,tf_subkey,(tf_key->len/8));

    /* Free memory */
    release(tf_key->k, tf_key, tf_subkey);

    return tf_twofish;
}

void Twofish_encryt(twofish_t* tf_twofish, uint8_t *data, uint8_t *cypher)
{
    uint32_t r0, r1, r2, r3, f0, f1, c2,c3;
    /* Input Whitenening */
    r0 = tf_twofish->k[0]^pack(data);
    r1 = tf_twofish->k[1]^pack(data+4);
    r2 = tf_twofish->k[2]^pack(data+8);
    r3 = tf_twofish->k[3]^pack(data+12);

    /* The black box */
    for (int i=0; i<16;++i)
    {
        Twofish_f(tf_twofish, i, r0, r1, &f0, &f1);
        c2 = ror((f0^r2), 1);
        c3 = (f1^rol(r3,1));
        /* swap */
        r2 = r0;
        r3 = r1;
        r0 = c2;
        r1 = c3;
    }

    /* Output Whitening */
    c2 = r0;
    c3 = r1;
    r0 = tf_twofish->k[4]^r2;
    r1 = tf_twofish->k[5]^r3;
    r2 = tf_twofish->k[6]^c2;
    r3 = tf_twofish->k[7]^c3;

    for (int i=0;i<4;++i)
    {
        cypher[i]   = unpack(r0,i);
        cypher[i+4] = unpack(r1,i);
        cypher[i+8] = unpack(r2,i);
        cypher[i+12]= unpack(r3,i);
    }
}

void Twofish_decryt(twofish_t* tf_twofish, uint8_t *cypher, uint8_t *data)
{
    uint32_t r0, r1, r2, r3, f0, f1, c2,c3;
    /* Input Whitenening */
    r0 = tf_twofish->k[4]^pack(cypher);
    r1 = tf_twofish->k[5]^pack(cypher+4);
    r2 = tf_twofish->k[6]^pack(cypher+8);
    r3 = tf_twofish->k[7]^pack(cypher+12);

    /* The black box */
    for (int i=15; i >= 0;--i)
    {
        Twofish_f(tf_twofish, i, r0, r1, &f0, &f1);
        c2 = (rol(r2,1)^f0);
        c3 = ror((f1^r3),1);
        /* swap */
        r2 = r0;
        r3 = r1;
        r0 = c2;
        r1 = c3;
    }

    /* Output Whitening */
    c2 = r0;
    c3 = r1;
    r0 = tf_twofish->k[0]^r2;
    r1 = tf_twofish->k[1]^r3;
    r2 = tf_twofish->k[2]^c2;
    r3 = tf_twofish->k[3]^c3;

    for (int i=0;i<4;++i)
    {
        data[i]   = unpack(r0,i);
        data[i+4] = unpack(r1,i);
        data[i+8] = unpack(r2,i);
        data[i+12]= unpack(r3,i);
    }
}

void Twofish_f(twofish_t* tf_twofish, uint8_t r,uint32_t r0, uint32_t r1, uint32_t* f0, uint32_t* f1)
{
    uint32_t t0, t1, o;
    t0 = Twofish_g(tf_twofish, r0);
    t1 = rol(r1, 8);
    t1 = Twofish_g(tf_twofish, t1);
    o = 2*r;
    *f0= (t0 + t1 + tf_twofish->k[o+8]);
    *f1= (t0 + (2*t1) + tf_twofish->k[o+9]);
}

twofish_t* Twofish_generate_ext_k_keys(twofish_t* tf_twofish, subkey_t *tf_subkey,uint32_t p, uint8_t k)
{
    uint32_t a, b;
    uint8_t x[4], y[4], z[4];
    for(int i=0;i<40;i+=2)                  /* i = 40/2 */
    {
        a = (i*p);                          /* 2*i*p */
        b = (a+p);                          /* ((2*i +1)*p */
        u(x,a);
        Twofish_h(x, y, tf_subkey->me, k);
        Twofish_mds_mul(y,z);
        a = pack(z);                        /* Convert four bytes z[4] to a word (a). */
        u(x,b);                             /* Convert a word (b) to four bytes x[4]. */
        Twofish_h(x, y, tf_subkey->mo, k);
        Twofish_mds_mul(y,z);        
        b = pack(z);
        b = rol(b,8);
        tf_twofish->k[i] = ((a + b));
        tf_twofish->k[i+1] = rol(((a + (2*b))),9);
    }
    return tf_twofish;
}

twofish_t* Twofish_generate_ext_s_keys(twofish_t* tf_twofish, subkey_t *tf_subkey, uint8_t k)
{
    uint8_t x[4], y[4];
    for(int i=0;i<256;++i)
    {
        x[0] = x[1] = x[2] = x[3] = i;
        Twofish_h(x, y, tf_subkey->s, k);
        /* Special MDS multiplication */
        tf_twofish->s[0][i] = (gf(y[0], mds[0][0],0x169) |(gf(y[1],mds[0][1],0x169)<< 8)|(gf(y[2], mds[0][2],0x169)<<16) |(gf(y[3], mds[0][3], 0x169) <<24));
        tf_twofish->s[1][i] = (gf(y[0], mds[1][0],0x169) |(gf(y[1],mds[1][1],0x169)<< 8)|(gf(y[2], mds[1][2],0x169)<<16) |(gf(y[3], mds[1][3], 0x169) <<24));
        tf_twofish->s[2][i] = (gf(y[0], mds[2][0],0x169) |(gf(y[1],mds[2][1],0x169)<< 8)|(gf(y[2], mds[2][2],0x169)<<16) |(gf(y[3], mds[2][3], 0x169) <<24));
        tf_twofish->s[3][i] = (gf(y[0], mds[3][0],0x169) |(gf(y[1],mds[3][1],0x169)<< 8)|(gf(y[2], mds[3][2],0x169)<<16) |(gf(y[3], mds[3][3], 0x169) <<24));
    }
    return tf_twofish;
}

void Twofish_mds_mul(uint8_t y[],  uint8_t out[])
{
    /* MDS multiplication */
    out[0] = (gf(y[0], mds[0][0], 0x169)^gf(y[1], mds[0][1], 0x169)^gf(y[2], mds[0][2], 0x169)^gf(y[3], mds[0][3], 0x169));
    out[1] = (gf(y[0], mds[1][0], 0x169)^gf(y[1], mds[1][1], 0x169)^gf(y[2], mds[1][2], 0x169)^gf(y[3], mds[1][3], 0x169));
    out[2] = (gf(y[0], mds[2][0], 0x169)^gf(y[1], mds[2][1], 0x169)^gf(y[2], mds[2][2], 0x169)^gf(y[3], mds[2][3], 0x169));
    out[3] = (gf(y[0], mds[3][0], 0x169)^gf(y[1], mds[3][1], 0x169)^gf(y[2], mds[3][2], 0x169)^gf(y[3], mds[3][3], 0x169));
}

uint32_t Twofish_g(twofish_t* tf_twofish, uint32_t x)
{
    return (tf_twofish->s[0][unpack(x,0)]^tf_twofish->s[1][unpack(x, 1)]^tf_twofish->s[2][unpack(x,2)]^tf_twofish->s[3][unpack(x,3)]);
}

void Twofish_h(uint8_t x[],  uint8_t out[], uint8_t s[][4], int stage)
{
    uint8_t y[4];
    for (int j=0; j<4;++j)
    {
        y[j] = x[j];
    }

    if (stage == 4)
    {
        y[0] = q[1][y[0]] ^ (s[3][0]);
        y[1] = q[0][y[1]] ^ (s[3][1]);
        y[2] = q[0][y[2]] ^ (s[3][2]);
        y[3] = q[1][y[3]] ^ (s[3][3]);
    }
    if (stage > 2)
    {
        y[0] = q[1][y[0]] ^ (s[2][0]);
        y[1] = q[1][y[1]] ^ (s[2][1]);
        y[2] = q[0][y[2]] ^ (s[2][2]);
        y[3] = q[0][y[3]] ^ (s[2][3]);
    }

    out[0] = q[1][q[0][ q[0][y[0]] ^ (s[1][0])] ^ (s[0][0])];
    out[1] = q[0][q[0][ q[1][y[1]] ^ (s[1][1])] ^ (s[0][1])];
    out[2] = q[1][q[1][ q[0][y[2]] ^ (s[1][2])] ^ (s[0][2])];
    out[3] = q[0][q[1][ q[1][y[3]] ^ (s[1][3])] ^ (s[0][3])];
}

subkey_t* Twofish_generate_subkey(key_t* tf_key)
{
    int k, r, g;
    subkey_t *tf_subkey = (subkey_t*)malloc(sizeof(subkey_t));
    k = tf_key->len/8;                                  /* k=N/64 */
    for(r=0; r<k;++r)
    {
        /* Generate subkeys Me and Mo */
        tf_subkey->me[r][0] = nxt(tf_key->k, r*8    );
        tf_subkey->me[r][1] = nxt(tf_key->k, r*8 + 1);
        tf_subkey->me[r][2] = nxt(tf_key->k, r*8 + 2);
        tf_subkey->me[r][3] = nxt(tf_key->k, r*8 + 3);
        tf_subkey->mo[r][0] = nxt(tf_key->k, r*8 + 4);
        tf_subkey->mo[r][1] = nxt(tf_key->k, r*8 + 5);
        tf_subkey->mo[r][2] = nxt(tf_key->k, r*8 + 6);
        tf_subkey->mo[r][3] = nxt(tf_key->k, r*8 + 7);

        g=k-r-1;                                        /* Reverse order */
        /* Generate subkeys S using RS matrix */
        tf_subkey->s[g][0] = rsm(r, 0x01, 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e);
        tf_subkey->s[g][1] = rsm(r, 0xa4, 0x56, 0x82, 0xf3, 0x1e, 0xc6, 0x68, 0xe5);
        tf_subkey->s[g][2] = rsm(r, 0x02, 0xa1, 0xfc, 0xc1, 0x47, 0xae, 0x3d, 0x19);
        tf_subkey->s[g][3] = rsm(r, 0xa4, 0x55, 0x87, 0x5a, 0x58, 0xdb, 0x9e, 0x03);
    }
    return tf_subkey;
}

key_t* expand_key(uint8_t *s, uint32_t len)
{
    int n;
    /* Pad factor */
    if (len<16)       n = 16;
    else if (len<24)  n = 24;
    else if (len<32)  n = 32;
    key_t* tf_key = (key_t*)malloc(sizeof(key_t));
    uint8_t* ss = (uint8_t*)malloc(n);
    /* Do actual padding. */
    for (int g=0; g<n; ++g)
    {
        if (g < len)
        {
            *(ss+g) = *(s+g);
            continue;
        }
        *(ss+g) = 0x00;
    }
    tf_key->k = ss;
    tf_key->len=n;
    return tf_key;
}

uint8_t gf(uint8_t x, uint8_t y, uint16_t m)
{
    uint8_t c, p = 0;
    for (int i=0; i<8; ++i)
    {
        if (y & 0x1)
            p ^= x;
        c = x & 0x80;
        x <<= 1;
        if (c)
            x ^= m;
        y >>= 1;
    }
    return p;
}

写一个main函数直接调用即可。

CTF出题变化分析

TwoFish算法共有三处可发生变化以提高出题难度

rsm函数，0x14d可替换为其他数字
Twofish_generate_ext_s_keys函数中gf的参数0x166可替换
Twofish_mds_mul函数中gf的参数0x166可替换

对于这类分组加密算法，即使插件没有识别，只要看出相关函数结构，就可以很快确定具体算法，找到可能变化的参数，相应修改解密函数即可

附件中附上了题目和idb文件供自行分析

文章来源: http://xz.aliyun.com/t/5807
如有侵权请联系:admin#unsafe.sh