逆向分析加解密之TwoFish算法

Author Avatar
kabeor 7月 25, 2019

逆向分析加解密之TwoFish算法

本文由本人首发于先知社区 https://xz.aliyun.com/t/5807

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

算法流程

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

流程图

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

算法分析

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

  1. Input whitening
  2. 16次循环
  3. Output whitening

Input whitening

  1. 拓展密钥

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

实现代码稍后来说

  1. 输入白化

因为加密前的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算法共有三处可发生变化以提高出题难度

  1. rsm函数,0x14d可替换为其他数字
  2. Twofish_generate_ext_s_keys函数中gf的参数0x166可替换
  3. Twofish_mds_mul函数中gf的参数0x166可替换

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

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

From https://kabeor.github.io/逆向分析加解密之TwoFish算法/ bye

This blog is under a CC BY-NC-SA 4.0 Unported License
本文链接:https://kabeor.github.io/逆向分析加解密之TwoFish算法/