SECCON-CTF-2014-Decrypt-It-easy

题目

给了三个文件ecrypt1.bin,readme.txt,rnd

其中readme.txt:

$ ./rnd crypt1.png ecrypt1.bin

Solve

看到前面有一个$,猜测可能和linux系统有关，这一条信息有点像使用./目录下的rnd对crypt1.png进行某种操作，输出为ecrypt1.bin.

file一下

file /home/mangofeng/桌面/rnd
/home/mangofeng/桌面/rnd: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=6a1443272dd530117d3c63884e195120a845c499, stripped

是一个32位的ELF文件,通过32ida反编译找主函数可以得到伪代码:

int __cdecl main(int a1, char **a2)
{unsigned int v3; // eaxFILE *v4; // [esp+10h] [ebp-10h]FILE *v5; // [esp+14h] [ebp-Ch]char ptr; // [esp+1Fh] [ebp-1h] BYREFif ( a1 <= 2 )return 1;v3 = time(0);srand(v3);v4 = fopen(a2[1], "rb");v5 = fopen(a2[2], "wb");while ( fread(&ptr, 1u, 1u, v4) == 1 ){ptr ^= rand() % 256;fwrite(&ptr, 1u, 1u, v5);}fclose(v4);fclose(v5);return 0;
}

  unsigned int v3; // eaxFILE *v4; // [esp+10h] [ebp-10h]FILE *v5; // [esp+14h] [ebp-Ch]char ptr; // [esp+1Fh] [ebp-1h] BYREF/*上面这些都是定义了各种变量*/

  if ( a1 <= 2 )return 1;//判断了一个a1是否小于等于2,若是的话,则返回1,下面语句都不会执行,则我们的a1应大于2

v3 = time(0);
//time()参数一般为0或者Null相当于 取系统时间()
如:
#include <iostream>
#include <ctime>
using namespace std;int main()
{int a;a=time(0);//time(0)返回的是系统的时间（从1970.1.1午夜算起），单位：秒cout<<a<<endl;
}
//1648089941
即时间戳:
时间戳是指格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总秒数。
在CPP中,时间戳默认就是10位，其精度是秒

  srand(v3);

先提一提rand()

rand()函数常用来生成伪随机数
rand()函数是使用线性同余法做的，它并不是真的随机数，因为其周期特别长，所以在一定范围内可以看成随机的。
rand()函数不需要参数，它将会返回0到RAND_MAX之间的任意的整数。

如:

#include<time.h>
#include<stdlib.h>
#include<iostream>
using namespace std;int main()
{for(int i = 0; i < 10; i++)
{cout << rand()<<endl;
}
}/*
41
18467
6334
26500
19169
15724
11478
29358
26962
24464*/

srand()

srand()为初始化随机数发生器，用于设置rand()产生随机数时的种子。传入的参数seed为unsigned int类型，通常我们会使用time(0)或time(NULL)的返回值作为seed。

srand(time(0));
for(int i = 0; i < 10; i++)
{cout << rand() << endl;
}
/*22954
16198
7083
19454
25323
32035
19825
3031
24100
11374*/

而且:

此方法默认参数为srand(1),当种子确定以后,输出也是确定的.例:

srand(1);
for(int i = 0; i < 10; i++)
{cout << rand() << endl;
}
cout<<time(0);
/*
41
18467
6334
26500
19169
15724
11478
29358
26962
24464
1648090722
*/
/*
41
18467
6334
26500
19169
15724
11478
29358
26962
24464
1648090746
*/

我运行了两次上述代码,可通过时间戳看出,发现rand()结果是一样的.

让我们再回到反编译的代码:

  v3 = time(0);srand(v3);

通过上述分析我们得知,此处设置了一个种子,种子为运行时的时间戳.

  v4 = fopen(a2[1], "rb");v5 = fopen(a2[2], "wb");
//这句话就有点像python里面的,v4就是我要读取数据的文件,打开方式为read binary;v5就是我要写入数据的文件,打开方式为write binary;

  while ( fread(&ptr, 1u, 1u, v4) == 1 ){ptr ^= rand() % 256;fwrite(&ptr, 1u, 1u, v5);}

fread函数用于从文件流中读取数据，其函数原型为：
size_t fread(void* buffer, size_t size, size_t count, FILE*stream);【参数设置】
1) 
buffer为接收数据的地址，对于fread来书是要读出数据的地址，即数据保存的地址
2)  size是要读出内容的单字节数。
3)  count是要进行读出size字节的数据项的个数。
4)  stream为目标文件指针
fwrite()
size_t fwrite(const void* buffer, size_t size, size_t count, FILE* stream);-- buffer:指向数据块的指针-- size:每个数据的大小，单位为Byte(例如：sizeof(int)就是4)-- count:数据个数-- stream:文件指针

然后大概就是原来文件的数据与生成的rand()异或得到新的文件数据.

然后我们之前分析了srand()函数,只要其传入参数一致,生成的rand()即一致

然后我们去分析一下生成文件ecrypt1bin的相关更改时间

可以通过stat命令查看文件的状态

stat /home/mangofeng/桌面/ecrypt1.bin文件：/home/mangofeng/桌面/ecrypt1.bin大小：45989           块：96         IO 块：4096   普通文件
设备：801h/2049d        Inode：21607       硬链接：1
权限：(0766/-rwxrw-rw-)  Uid：( 1000/mangofeng)   Gid：( 1000/mangofeng)
最近访问：2022-03-24 11:12:41.937672000 +0800
最近更改：2014-11-22 22:46:30.000000000 +0800    #this
最近改动：2022-03-24 11:12:42.026137518 +0800
创建时间：2022-03-24 11:12:41.938137515 +0800

将该更改时间转换为时间戳

a = "2014-11-22 22:46:30"
#将其转换为时间数组
import time
timeArray = time.strptime(a, "%Y-%m-%d %H:%M:%S" )
#转换为时间戳:
timeStamp = int (time.mktime(timeArray))
print(timeStamp)
#1416667590

或者

stat --printf=%Y /home/mangofeng/桌面/ecrypt1.bin                                                                                                       
1416667590

然后用一下解密脚本:

#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[]) {FILE *cipher = fopen(argv[1], "rb");FILE *plain = fopen(argv[2], "wb");unsigned int seed = atoi(argv[3]);int c;srand(seed);c = (fgetc(cipher) & 0xff) ^ (rand() & 0xff);while (!feof(cipher)) {fputc(c, plain);c = (fgetc(cipher) & 0xff) ^ (rand() & 0xff);}fclose(plain);fclose(cipher);
}

然后用一下gcc编译

gcc /home/mangofeng/桌面/decode.c -o /home/mangofeng/decode┌──(mangofeng㉿kali)-[~]
└─$ gcc /home/mangofeng/桌面/decode.c -o /home/mangofeng/桌面/decode                                                                                               ┌──(mangofeng㉿kali)-[~]
└─$ /home/mangofeng/桌面/decode /home/mangofeng/桌面/ecrypt1.bin /home/mangofeng/桌面/output.png 1416667590

其中N都不是太大的值，可以分解成pq

先一步一步干吧,用yafu分解一下

N1=0xB8AE199365
print(int(N1))
p1 = 913799
q1 = 868019
N2=0xB86E78C811
print(int(N2))
p2 = 904727
q2 = 875543
N3=0x7BD4071E55
print(int(N3))
p3 = 890459
q3 = 597263
assert (q1*p1==N1)
assert (q2*p2==N2)
assert (q3*p3==N3)

因为N都不是太大，就会导致加密的m不能太大，再看有三块，推测flag应该是三块短的字符串拼凑在一起

解法一:

已知flag格式为:SECCON{}

则试一试一块flag大概有多长

N, B, FLAG = 0xB8AE199365, 0xFFEEE, b'SECCON{'
for i in range(1, len(FLAG)+1):M = bytes_to_long(FLAG[0:i])print(FLAG[0:i],'\t',str(hex(M * (M + B) % N)),end="\n")
b'S'     0x52fc213
b'SE'    0x54f0cb0bf
b'SEC'   0x8c0ad9b877
b'SECC'          0x704d68c1fb
b'SECCO'         0x8d5051562b
b'SECCON'        0x2339eed575
b'SECCON{'       0x1bce931b16

发现到五位长度以后，明文就经过了取模操作，即我们猜测flag每一块被分成不超过五位的明文块

验证一下

B=[0xFFEEE,0xFFFEE,0xFEFEF]
C=[0x8D5051562B,0x5FFA0AC1A2,0x6008DDF867]
p=[913799,904727,890459]
q=[868019,875543,597263]
N=[p1*q1,p2*q2,p3*q3]
test=b'SECCO'
M=bytes_to_long(test)
print(bool(hex(M*(M+B[0])%N[0])=='0x8d5051562b'))
#True

则我们就可以去用ascii爆破剩下的两个明文块，每个长度最多为5;

N, B =N[1],B[1]
for i in range(32, 127):for j in range(32, 127):for k in range(32, 127):M = ('N{' + chr(i) + chr(j) +chr(k))M =bytes_to_long(bytes(M, encoding='UTF-8'))if ((M * (M + B) % N) == int(0x5FFA0AC1A2)):print('N{' + chr(i) + chr(j) + chr(k))
#N{Ra_

for i in tqdm.tqdm(range(32, 127)):for j in range(32, 127):for k in range(32, 127):for l in range(32,127):MM = chr(i) + chr(j) +chr(k)+chr(l)+'}'MM =bytes_to_long(bytes(MM, encoding='UTF-8'))if (((MM * (MM + B[2]))% N[2]) == int(0x6008DDF867)):print(chr(i) + chr(j) + chr(k)+chr(l)+'}')break
#b1_N}

SECCON{Ra_b1_N}

解法二:

N大概在2^40左右,要想从modN下找到一个值满足条件是不现实的

但我们已经把N分解成了p,q，根据中国剩余定理可以把条件拆成两个
$\begin{cases}C_p\equiv m_p\cdot(m_p+B)\pmod{p}\\C_q\equiv m_q\cdot(m_q+B)\pmod{q}\end{cases}$
p,q都比较小,可以爆破,寻找到满足上述两式的 $m_p和m_q$
$\begin{cases}m\equiv m_p\pmod{p}\\m\equiv m_q\pmod{q}\end{cases}$
然后就可以根据CRT求解出m啦。

def CRT(moudle,a):M = reduce((lambda x,y : x * y),moudle)result = 0for mi in moudle:Mi = M // miinv_Mi = gmpy2.invert(Mi,mi)result = (result + a[moudle.index(mi)] * Mi * inv_Mi) % Mreturn (result % M)
for i in range(0,3):for a1 in [m_p for m_p in range(p[i]) if (C[i] % p[i]) == (m_p * (m_p + B[i])) % p[i]]:# 遍历所有小于p[i]的值for a2 in [m_q for m_q in range(q[i]) if (C[i] % q[i]) == (m_q * (m_q + B[i])) % q[i]]:# 遍历所有小于q[i]的值x = CRT([p[i],q[i]],[a1,a2])print(long_to_bytes(x))
b'eh\xc6Q('
b'W_V"\xa7'
b'aN\xb3q\xd0'
b'SECCO'
b'\x86V\t\xc5\xee'
b'i\xf3\x16f\xc4'
b'N{Ra_'
b'2\x18_\x025'
b'\x19\xa2\x97\xdf\xe9'
b'%\xf5"\x992'
b'U\xde\xd4\x954'
b'b1_N}'
SECCON{Ra_b1_N}