首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[原创]第十一题 图穷匕见 一道不用逆向的纯算法
发表于: 2021-12-14 23:27 18902

[原创]第十一题 图穷匕见 一道不用逆向的纯算法

xym 活跃值
4
2021-12-14 23:27
18902

题目非常小巧，IDA打开后所有算法也清晰可见。相比第十题各种逆向方法百花齐放，这题简单到可以把F5后的结果直接复制出来使用。
题目逻辑也很清晰：将输入经过一轮s盒转换后当成密钥，分别对两组明文进行加密，如果与指定的两组密文相同，则将输入经过hash比较无误后输出"Correct!"。整体就是已知两对明密文和加密算法，求密钥的操作。
加密函数sub_140002970也不复杂，梳理一下就是一个Feistal结构的加密，据此容易构造出解密方法。加密轮数只有5轮，定义域在GF(2^64)上。

其中只有一个sub_1400028C0子函数比较特殊。而这个函数粗一看可能比较奇怪，仔细研究后发现就是一个基于0x247F43CB7的乘法。

把异或看成是加法的话，sub_1400028C0函数完全满足乘法三大定律。即

因此可以进一步把加密过程的每一轮都化简为如下形式

如果把加密过程的每一轮都表示成如上形式后，可以发现密文在理论上可以表示为明文的表达式，而且里面只有KEY0和KEY1两个未知变元，因此利用两组明密文列出的两个方程在理论上可以求解得到秘钥。
使用sagemath实现题目的过程，如下：

直接构造方程的思路比较简单，但是方程次数指数级增长导致难以求解。考虑到尽量降低方程次数，编写相应的解密函数，采用中间相遇攻击方法，利用在不同轮数中的相遇情况，可以列出6个方程，然后使用Groebner基方法即可求解出方程组的解。
具体过程如下：

由于上述方程只有唯一解0xf39a46cc6199261d, 0xbdeded27481af0e0，所以该解经过s盒的逆变换后变化得到的字符串de23f9d82798377ea01743d43d5353cd直接通过了后面部分的HASH校验。

void sub_140002970(UINT64 *Plaintext, UINT64 *key, int len, UINT64 *const0, UINT64 *Ciphertext)
{
    UINT64 v8; // rax
    UINT64 v9; // rax
    UINT64 v10; // rax
    UINT64 v14; // [rsp+40h] [rbp-38h]
    UINT64 v17; // [rsp+58h] [rbp-20h]
    UINT64 v18; // [rsp+60h] [rbp-18h]
 
    v17 = Plaintext[0];
    v18 = Plaintext[1];
    for (int i = 0; i < len; ++i)
    {
        v8 = v18 ^ key[i % 2] ^ const0[i];
        v9 = sub_1400028C0(v8, v8);
        v10 = sub_1400028C0(v9, v8);
        v14 = v17 ^ v10;
        v17 = v18;
        v18 = v14;
    }
    Ciphertext[0] = v17;
    Ciphertext[1] = v18;
}
void sub_140002970(UINT64 *Plaintext, UINT64 *key, int len, UINT64 *const0, UINT64 *Ciphertext)
{
    UINT64 v8; // rax
    UINT64 v9; // rax
    UINT64 v10; // rax
    UINT64 v14; // [rsp+40h] [rbp-38h]
    UINT64 v17; // [rsp+58h] [rbp-20h]
    UINT64 v18; // [rsp+60h] [rbp-18h]
 
    v17 = Plaintext[0];
    v18 = Plaintext[1];
    for (int i = 0; i < len; ++i)
    {
        v8 = v18 ^ key[i % 2] ^ const0[i];
        v9 = sub_1400028C0(v8, v8);
        v10 = sub_1400028C0(v9, v8);
        v14 = v17 ^ v10;
        v17 = v18;
        v18 = v14;
    }
    Ciphertext[0] = v17;
    Ciphertext[1] = v18;
}
UINT64 sub_1400028C0(UINT64 a1, UINT64 a2)
{
    UINT64 v3;
    v3 = 0;
    while (a2)
    {
        if ((a2 & 1) != 0)
            v3 = v3 ^ a1;
        a2 >>= 1;
        if (a1 & 0x8000000000000000)
            a1 = (2 * a1) ^ 0x247F43CB7;
        else
            a1 *= 2;
    }
    return v3;
}
UINT64 sub_1400028C0(UINT64 a1, UINT64 a2)
{
    UINT64 v3;
    v3 = 0;
    while (a2)
    {
        if ((a2 & 1) != 0)
            v3 = v3 ^ a1;
        a2 >>= 1;
        if (a1 & 0x8000000000000000)
            a1 = (2 * a1) ^ 0x247F43CB7;
        else
            a1 *= 2;
    }
    return v3;
}
sub_1400028C0(a, b) == sub_1400028C0(b, a)
sub_1400028C0(sub_1400028C0(a, b), c) == sub_1400028C0(a, sub_1400028C0(b, c))
sub_1400028C0(a xor b, c) == sub_1400028C0(a, c) xor sub_1400028C0(b, c))
sub_1400028C0(a, b) == sub_1400028C0(b, a)
sub_1400028C0(sub_1400028C0(a, b), c) == sub_1400028C0(a, sub_1400028C0(b, c))
sub_1400028C0(a xor b, c) == sub_1400028C0(a, c) xor sub_1400028C0(b, c))
v14 = (P1 + KEY0 + const0) ^ 3 + P0;
P0 = P1;
P1 = v14;
...
v14 = (P1 + KEY0 + const0) ^ 3 + P0;
P0 = P1;
P1 = v14;
...
def enc(pt, key):
  pt0, pt1 = pt
  key0, key1 = key
  var('x')
  var('a')
  K.<a> = GF(2^64, name='a',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
  c0=0x20F4641148FA59A5
  c1=0x96950F0D368EB90D
  c2=0x7467551A8419E0B5
  c3=0x01A61218FE968D86
  c4=0x192DB7EB78969270
  cntList=[]
  cntList.append(K.fetch_int(c0))
  cntList.append(K.fetch_int(c1))
  cntList.append(K.fetch_int(c2))
  cntList.append(K.fetch_int(c3))
  cntList.append(K.fetch_int(c4))
  Left = K.fetch_int(pt0)
  Right = K.fetch_int(pt1)
  keyList=[]
  keyList.append(K.fetch_int(key0))
  keyList.append(K.fetch_int(key1))
  for i in range(5):
    tmp = Right+keyList[i%2]+cntList[i]
    tmp = tmp^3
    tmp = tmp + Left
    Left = Right
    Right = tmp
  return [hex(Left.integer_representation()),hex(Right.integer_representation())]
pt=[0x73C51960EF361B30, 0xFBD5C824382C435D]
key = [0xb118c960bcb118c9, 0xb118c960bcb118c9]
enc(pt,key)
def enc(pt, key):
  pt0, pt1 = pt
  key0, key1 = key
  var('x')
  var('a')
  K.<a> = GF(2^64, name='a',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
  c0=0x20F4641148FA59A5
  c1=0x96950F0D368EB90D
  c2=0x7467551A8419E0B5
  c3=0x01A61218FE968D86
  c4=0x192DB7EB78969270
  cntList=[]
  cntList.append(K.fetch_int(c0))
  cntList.append(K.fetch_int(c1))
  cntList.append(K.fetch_int(c2))
  cntList.append(K.fetch_int(c3))
  cntList.append(K.fetch_int(c4))
  Left = K.fetch_int(pt0)
  Right = K.fetch_int(pt1)
  keyList=[]
  keyList.append(K.fetch_int(key0))
  keyList.append(K.fetch_int(key1))
  for i in range(5):
    tmp = Right+keyList[i%2]+cntList[i]
    tmp = tmp^3
    tmp = tmp + Left
    Left = Right
    Right = tmp
  return [hex(Left.integer_representation()),hex(Right.integer_representation())]
pt=[0x73C51960EF361B30, 0xFBD5C824382C435D]
key = [0xb118c960bcb118c9, 0xb118c960bcb118c9]
enc(pt,key)
#下面代码可以直接在sage中运行
 
#1. 构造数域
K.<x> = GF(2^64, name='x',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
#2. 方程的构造
#首先形式化计算出表示方法
P0=var('P0')
P1=var('P1')
M0=var('M0')
M1=var('M1')
y = var('y')
z = var('z')
c0 = var('c0')
c1 = var('c1')
c2 = var('c2')
c3 = var('c3')
c4 = var('c4')
R.<P0,P1,y,z,c0,c1,c2,c3,c4,M0,M1>=GF(2)[]
#正向加密过程形式化计算
v17 = P0
v18 = P1
 
v8 = v18 + y + c0
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_1 = v18
 
v8 = v18 + z + c1
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_2 = v18
 
v8 = v18 + y + c2
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_forward_3 = v18
#逆向解密过程形式化计算
v17 = M1
v18 = M0
 
v8 = v18 + y + c4
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_1 = v18
 
v8 = v18 + z + c3
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_2 = v18
 
v8 = v18 + y + c2
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18
v18 = v14
 
eq_backward_3 = v18
 
#其次带入实际数据
 
ct0 = 0x55250D8CEEDFFB35
ct1 = 0xDBAFC899D2AAD5EC
ct2 = 0xD30CE81D5CFD183E
ct3 = 0x3C205341A484C650
pt0 = 0x73C51960EF361B30
pt1 = 0xFBD5C824382C435D
pt2 = 0x79EEBA9CCF47A451
pt3 = 0x55B4D0E1061D12D0
cnt0 = 0x20F4641148FA59A5
cnt1 = 0x96950F0D368EB90D
cnt2 = 0x7467551A8419E0B5
cnt3 = 0x01A61218FE968D86
cnt4 = 0x192DB7EB78969270
 
y,z=K['y,z'].gens()
 
#利用第1组明密文对列3个方程
eq1 = \
eq_forward_1(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_3(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq2 = \
eq_forward_2(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_2(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq3 = \
eq_forward_3(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_1(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
#利用第2组明密文对列3个方程
eq4 = \
eq_forward_1(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_3(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq5 = \
eq_forward_2(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_2(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
eq6 = \
eq_forward_3(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\
-eq_backward_1(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\
c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))
 
#至此列出6个方程。
 
#3.利用sagemath自带的Groebner基解方程
I=ideal(eq1,eq2,eq3,eq4,eq5,eq6)
B=I.groebner_basis()
key0 = hex(B[0].coefficients()[1].integer_representation())
key1 = hex(B[1].coefficients()[1].integer_representation())
print(key0,key1)
#下面代码可以直接在sage中运行
 
#1. 构造数域
K.<x> = GF(2^64, name='x',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)
#2. 方程的构造
#首先形式化计算出表示方法
P0=var('P0')
P1=var('P1')
M0=var('M0')
M1=var('M1')
y = var('y')
z = var('z')
c0 = var('c0')
c1 = var('c1')
c2 = var('c2')
c3 = var('c3')
c4 = var('c4')
R.<P0,P1,y,z,c0,c1,c2,c3,c4,M0,M1>=GF(2)[]
#正向加密过程形式化计算
v17 = P0
v18 = P1
 
v8 = v18 + y + c0
v10 = v8 * v8 * v8
v14 = v17 + v10
v17 = v18

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2021-12-14 23:27 被xym编辑 ，原因：
收藏
免费 ・7
支持
分享
最新回复 (1)
zx_348891
雪    币： 73
活跃值： (923)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
完全看不懂，话说请教下楼主，做这样的题，大概需要哪些知识呢？是要对各种密码学中的加密算法都很熟悉吗？
2021-12-21 09:48
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//