TwoFish算法逆向分析与CTF应用

1. TwoFish算法概述

TwoFish是一种对称密钥分组加密算法，由Bruce Schneier等人设计，是AES竞赛的五个决赛算法之一。它是一种Feistel网络结构的分组密码，具有以下特点：

• 分组长度：128位
• 密钥长度：支持128位、192位和256位
• 轮数：16轮
• 采用预白化-轮函数-后白化的结构

2. 算法流程

TwoFish加密过程分为三个主要阶段：

1. 输入白化(Input Whitening)
2. 16轮循环运算
3. 输出白化(Output Whitening)

2.1 输入白化

将128位明文分为4个32位字：

P(i) = ∑p(4i+j)2^(8j), i,j = 0,...,3

然后与扩展密钥的前4个字进行异或：

R(0,i) = P(i) xor K(i), i = 0,...,3

2.2 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函数是TwoFish的核心函数。

2.3 输出白化

将最终结果与扩展密钥的后4个字进行异或：

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

3. 关键组件分析

3.1 密钥扩展

TwoFish的密钥扩展过程生成：

1. 40个32位的子密钥K(i)
2. 4个与密钥相关的S盒s(i)()

密钥扩展步骤：

1. 将密钥分为k=2,3或4个64位块（对应128,192,256位密钥）
2. 生成Me和Mo矩阵
3. 使用RS矩阵生成S盒
4. 生成扩展密钥K

3.1.1 RS矩阵运算

RS矩阵运算定义如下：

#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)

其中0x14d是有限域GF(2^8)的生成多项式。

3.1.2 h函数

h函数是密钥扩展中的核心函数，使用q0和q1两个固定的置换表：

uint8_t q[2][256] = {
    /* q0 */ {...},
    /* q1 */ {...}
};

h函数的多级结构：

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])];

3.2 F函数

F函数是TwoFish轮函数的核心：

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]);
}

3.3 G函数

G函数是F函数的基础，使用S盒进行非线性变换：

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)]);
}

3.4 MDS矩阵

TwoFish使用固定的MDS矩阵进行扩散：

uint8_t mds[4][4] = {
    {0x01, 0xef, 0x5b, 0x5b},
    {0x5b, 0xef, 0xef, 0x01},
    {0xef, 0x5b, 0x01, 0xef},
    {0xef, 0x01, 0xef, 0x5b}
};

MDS矩阵乘法实现：

void Twofish_mds_mul(uint8_t y[], uint8_t out[]) {
    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));
}

4. 逆向分析要点

在逆向分析TwoFish算法时，需要关注以下特征：

1. 密钥扩展过程：

   • 40个子密钥K的生成
   • 4个S盒的生成
   • h函数的多级结构
   • RS矩阵运算

2. 加密流程：

   • 输入白化（明文与K[0..3]异或）
   • 16轮Feistel结构
   • 输出白化（密文与K[4..7]异或）

3. 关键函数：

   • F函数（包含G函数调用）
   • G函数（使用S盒的非线性变换）
   • 轮函数中的ROL/ROR操作

4. 固定结构：

   • q0和q1置换表
   • MDS矩阵
   • GF(2^8)上的乘法

5. CTF中的变体与对抗

在CTF题目中，TwoFish算法可能被修改以下部分以增加难度：

1. RS矩阵参数：

   • 0x14d可能被替换为其他多项式

2. MDS矩阵参数：

   • Twofish_generate_ext_s_keys函数中gf的参数0x169可能被修改
   • Twofish_mds_mul函数中gf的参数0x169可能被修改

3. S盒生成：

   • 修改q0和q1置换表
   • 改变h函数的级联结构

4. 轮函数：

   • 修改F函数中的加法/乘法操作
   • 改变G函数的S盒使用方式

6. 解密实现

TwoFish解密流程与加密类似，但轮次顺序相反：

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);
    }
}

7. 实际逆向案例分析

在提供的逆向题目中，TwoFish实现有以下特点：

1. 密钥长度为128位

2. 提供了加密和验证功能

3. 密钥扩展过程被修改：

   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); // 生成K
   v6 = sub_401CF8(v5, v3, *v2 >> 3); // 生成S
   

4. 关键识别点：

   • 40个子密钥K
   • 4个S盒
   • 16轮Feistel结构
   • 输入/输出白化

8. 总结

TwoFish算法逆向分析的关键在于：

1. 识别密钥扩展过程，特别是h函数和RS矩阵
2. 分析轮函数结构，特别是F函数和G函数
3. 确认S盒生成方式和MDS矩阵参数
4. 注意CTF中可能的变体，特别是有限域参数和S盒生成方式的修改

通过理解标准TwoFish实现的结构和组件，可以有效地分析和逆向工程其变体实现。