首页 > itarticle > 逆向分析加解密之twofish算法

逆向分析加解密之twofish算法

admin 1月 28, 2021 0

https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/https://kabeor.cn/

本文由本人首发于先知社区 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中