-
-
[原创]CTF2017 第十三题 readyuCrackMe 解题报告
-
2017-6-29 12:55
-
CTF2017 第十三题 readyuCrackMe
前言
回忆之前对 ECC 的理解，就是初始化的时候选个标准曲线，然后生成公私钥么。等做到这道题的时候，才知道要去真正的理解什么是有限域，什么是椭圆曲线，学习资料1 学习资料2
反汇编
程序使用的算法库是 MIRACL，但我在 IDA 全部人肉标记完了之后，才搜索到这个方法，之前，我是通过一个函数(其实是 reduce2)内部的判断有限域参数的时候(就是看到 571、1223)才知道是 ECC 库的，然后去 github 上搜索相关的库，只找到这个库支持 1223，之前还找到了个 relic 库，不过不支持 103，然后对比源码标记函数名
程序是很简单的 win32 对话框工程，在对话框初始化消息中，设定了 user 输入框的内容为 readyu，并隐藏。然后在 Check 事件处理中，判断输入必须开头不为 0(过滤掉多解)，必须大写和数字，然后进入重要的 check(code, user) 函数
int check(char *code, const char *user)
{
get_mip();
y_hex[0] = 0;
memset(&y_hex[1], 0, 32u);
*(_WORD *)&y_hex[33] = 0;
y_hex[35] = 0;
m_hex = [0x10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x79];
mirinit(); // 初始化 MIRACL
m_ = m;
A_ = A;
g_ = g;
Xy_ = Xy;
Xx_ = Xx;
B_ = B;
y_ = y;
bytes_to_big(34, m_hex, m); // 将上面的 34字节数组 转成大数 m
cinstr(g_, code); // 将输入 code 转成大数 g
if ( mr_compare(g_, m_) <= 0 ) // g <= m
{
power(g_, 5, m_, y_); // y = g ** 5 % m
memset(y_hex, 0, sizeof(y_hex));
if ( big_to_bytes(34, y_, y_hex, 1) == 34 ) // 将 y 转成 34字节数组
{
bytes_to_big(17, y_hex, Xx_); // 取前17字节转成大数 Xx
bytes_to_big(17, &y_hex[17], Xy_); // 取后17字节转成大数 Xy
convert(0, A_); // A = 0
convert(1, B_); // B = 1
ret = 1;
if ( ecurve2_init(131, 13, 2, 1, A_, B_, 0, 0) )// 初始化 m131 a13 b2 c1的五项式基二元扩张有限域，和 A0 B1 的椭圆曲线方程
{
qmemcpy(Px_hex, a51c99bfa6f18de, 34u);
qmemcpy(Py_hex, a42ea2d112ecec7, 34u);
qmemcpy(Qx_hex, a6c997f3e7f2c66, 34u);
qmemcpy(Qy_hex, a4a38d11829d32d, 34u);
qmemcpy(n_hex, a20000000000000, 34u);
strcpy(const_strs, "pediy");
memset(&const_strs[6], 0, 24u);
*(_WORD *)&const_strs[30] = 0;
*(_DWORD *)&const_strs[32] = *(_DWORD *)a2017;// 2017
const_strs[36] = a2017[4];
memset(&const_strs[37], 0, 24u);
*(_WORD *)&const_strs[61] = 0;
const_strs[63] = 0;
*(_DWORD *)&const_strs[68] = *(_DWORD *)&aCrackme[4];
*(_DWORD *)&const_strs[64] = *(_DWORD *)aCrackme;// crackme
memset(&const_strs[72], 0, 24u);
LOBYTE(src[0]) = 0;
memset((char *)src + 1, 0, 764u);
*(_WORD *)((char *)&src[191] + 1) = 0;
BYTE3(src[191]) = 0;
cnt = 0;
tmp = (char *)src;
md5hashp = md5hashs;
const_str = const_strs;
do
{
strcpy(tmp, user);
strcat(tmp, asc_4180E0); // - 号
strcat(tmp, const_str);
MD5_hash(tmp, strlen(tmp), md5hashp, cnt + 1);
tmp += 256;
++cnt;
const_str += 32;
md5hashp += 16;
}
while ( cnt < 3 );
h0 = mirvar(0);
h1 = mirvar(0);
h2 = mirvar(0);
Px = mirvar(0);
Py = mirvar(0);
Qx = mirvar(0);
Qy = mirvar(0);
n = mirvar(0);
P = epoint_init();
Q = epoint_init();
P_ = epoint_init();
Q_ = epoint_init();
X = epoint_init();
if ( epoint2_set(Xx_, Xy_, 0, X) ) // 将前面分离的 Xx Xy 组成点 X
{
cinstr(Px, Px_hex);
cinstr(Py, Py_hex);
epoint2_set(Px, Py, 0, P); // 组成点 P
cinstr(Qx, Qx_hex);
cinstr(Qy, Qy_hex);
epoint2_set(Qx, Qy, 0, Q); // 组成点 Q
bytes_to_big(16, md5hashs, h0); // 将三组 hash 转成大数 h0 h1 h2
bytes_to_big(16, &md5hashs[16], h1);
bytes_to_big(16, &md5hashs[32], h2);
ecurve2_mult(h2, P, P_); // P_ = h2 * P
ecurve2_mult(h2, Q, Q_); // Q_ = h2 * Q
ecurve2_add(X, P_); // P_ += X
ecurve2_add(X, Q_); // Q_ += X
ecurve2_mult(h0, P_, P_); // P_ *= h0
ecurve2_mult(h1, Q_, Q_); // Q_ *= h1
epoint2_get(P_, Px, Py); // 取出 x y
epoint2_get(Q_, Qx, Qy);
cinstr(n, n_hex);
divide(Px, n, n); // Px = Px % n
divide(Qx, n, n); // Qx = Qx % n
ret = 3; // 再加把劲
if ( !mr_compare(Px, Qx) )
ret = 0; // 一样才正确
}
else
{
ret = 2; // 错误SN
}
mirkill(h0);
mirkill(h1);
mirkill(h2);
mirkill(Px);
mirkill(Qx);
mirkill(Py);
mirkill(Qy);
mirkill(n);
epoint_free(P);
epoint_free(Q);
epoint_free(P_);
epoint_free(Q_);
epoint_free(X);
}
mirexit();
result = ret;
}
else
{
mirexit();
result = 1;
}
}
else
{
mirexit();
result = 1;
}
return result;
}解题过程
起初搜索到这个 有限域的时候，搜索到一个ECC2K-130挑战，发现题目中给出的常量都是取自这个挑战，我还以为这题是要求 ECDLP 问题，但是这个分布式挑战还在跑还没有解啊，后面仔细看了看题发现不是，因短时间理解有限，不正确的地方请指出
求解代码
先用 python 求解 h0、h1、h2 以及 t①
import hashlib
import gmpy2
def md5_hash(s, n):
md5 = hashlib.md5()
for _ in xrange(n):
md5.update(chr(n))
md5.update(s)
return md5.hexdigest()
h0 = md5_hash("readyu-pediy", 1)
h1 = md5_hash("readyu-2017", 2)
h2 = md5_hash("readyu-crackme", 3)
print "h0:", h0
print "h1:", h1
print "h2:", h2
n = long("200000000000000004D4FDD5703A3F269", 16)
t = gmpy2.invert(long(h1, 16) - long(h0, 16), n) * long(h2, 16) % n
print "t:", hex(t)[2:].rstrip("L")用 MIRACL 库求解 X
extern "C" {
#include <miracl.h>
}
void printbig(const char* prefix, big x)
{
char buf[256];
int len = big_to_bytes(0, x, buf, FALSE);
printf("%s: ", prefix);
for (int i=0; i<len; ++i) {
printf("%02x",(BYTE)buf[i]);
}
printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
// 仿造题目初始化环境
mirsys(576, 2);
miracl *h = get_mip();
h->IOBASE = 16;
set_io_buffer_size(1024);
irand(GetTickCount());
// 仿造题目初始化椭圆曲线
void* mem = memalloc(8);
big A = mirvar_mem((char*)mem, 0);
zero(A);
big B = mirvar_mem((char*)mem, 1);
zero(B);
convert(0, A);
convert(1, B);
ecurve2_init(131, 13, 2, 1, A, B, FALSE, 0);
flash Px = mirvar(0);
flash Py = mirvar(0);
flash Qx = mirvar(0);
flash Qy = mirvar(0);
flash n = mirvar(0);
flash h0 = mirvar(0);
flash h1 = mirvar(0);
flash h2 = mirvar(0);
cinstr(Px, "51C99BFA6F18DE467C80C23B98C7994AA");
cinstr(Py, "42EA2D112ECEC71FCF7E000D7EFC978BD");
cinstr(Qx, "6C997F3E7F2C66A4A5D2FDA13756A37B1");
cinstr(Qy, "4A38D11829D32D347BD0C0F584D546E9A");
cinstr(n, "200000000000000004D4FDD5703A3F269");
cinstr(h0, "51c75f1f444baa97ed18dd6c340835d7");
cinstr(h1, "0e5cf7f068d6efa16f42f935ec424a75");
cinstr(h2, "a4cd1d64486abde1be441944460cd41d");
epoint* P = epoint_init();
epoint* Q = epoint_init();
epoint* P_ = epoint_init();
epoint* Q_ = epoint_init();
epoint2_set(Px, Py, 0, P);
epoint2_set(Qx, Qy, 0, Q);
// 上面准备好所有常量，下面开始计算
ecurve2_mult(h0, P, P_); // P_ = h0 * P
ecurve2_mult(h1, Q, Q_); // Q_ = h1 * Q
ecurve2_sub(Q_, P_); // P_ -= Q 起初就是这个地方参数位置搞错浪费我时间
flash t = mirvar(0);
cinstr(t, "1a5d091f2adea1d4d5a992f55bcfd2a45");
epoint* X = epoint_init();
ecurve2_mult(t, P_, X); // X = t * P_
flash Xx = mirvar(0);
flash Xy = mirvar(0);
epoint2_get(X, Xx, Xy); // 取出 X 点
printbig("Xx", Xx);
printbig("Xy", Xy);
return 0;
}最后用 python 解出最终解
m = long("10"+"0"*64+"79", 16)
print hex(gmpy2.powmod(long(Xx + Xy, 16), gmpy2.invert(5, m - 1), m))[2:].rstrip("L").upper()[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
