看雪.WiFi万能钥匙 CTF 2017第十三题 点评及解题思路

发布者：Editor
发布于：2017-06-28 17:45


看雪CTF 2017 比赛进行至第十三题

截止至今天中午12点，第十三题破解人数为 2 人！

防守方 hsadkhk 依然位居首位~


此题过后，风间仁依然处于第一位~，kkHAIKE升至第二位。


比赛进入尾声，仅剩 2 题。

对于比赛前几名的争夺战，将在前十名之间展开。

期待ing......

接下来我们来回顾一下第十三题

看看 看雪评委和出题者是怎么说的ヾ(๑╹◡╹)ﾉ"。


看雪评委 netwind 点评


此题考查攻方选手对算法的分析能力。该题算法模型是：考虑一条有限域椭圆曲线上的已知点 G1, G2, 以及给定的系数 h1,h2,h3,求点S(x,y) 满足方程：h1( S + h3*G1) = h2(S + h3*G2)  mod n，判断正确的key等价于判断方程两边运算的点的x坐标： 两个大数相等。如果对算法模型不熟悉，做起来可能会有一定难度。


作者简介


论坛ID为readyu，毕业于中国科学技术大学自动控制专业，从事软件开发多年。在软件保护技术、加密算法方面有一些体会。曾在北京多看科技从事电子阅读加密技术的研究，现在MIUI做系统与安全相关的工作。


看雪 CTF 2017 第十二题设计思路


根据规则，crackme 内部name固定。 SN唯一。
本题sn为：
7A7102F36F3B344D666132A6FF7EF4BA05B99640BB815C9E712A72C64B6ABC582C2

正确提示：
"Oh Yes! You got it.",


设计思路：

（1）考虑一条有限域椭圆曲线上的已知点 G1, G2, 以及给定的系数 h1,h2,h3,求点S(x,y) 满足方程, 以下大写字母表示有限域椭圆曲线上的点， 小写字母表示数值：

h1( S + h3*G1) = h2(S + h3*G2)   mod n

那么， 判断正确的key， 等价于判断方程两边运算的点的x坐标： 两个大数相等。

因此， 比较key，不会出现明文比较。这里S是可以计算的，并没有用到ECDLP（椭圆曲线离散对数）。

那么，如何求出S(x,y)：

=> (h1 - h2) S = h2*h3*G2 - h1*h3*G1

S(x,y) = (h2*h3/(h1 - h2)) * G2-  (h1*h3/(h1 - h2)) * G1  mod n

sn = S(x,y) ， x,y is the point on the cuver ECC2K-130

椭圆曲线选取公开的ECC2K-130：

（参数取自如下pdf文档）

http://www.ecc-challenge.info/anon.pdf

========
ECC2K-130   GF(2^m)
========
E:     y^2  + xy =   x^3 + a*x^2 + b  

m = 131
f = x^131 + x^13 + x^2 + x + 1

a = 0
b = 1

E 即：  y^2 + xy = x^3 + 1  , over  GF(2^131)

point P (G1)：
X= 51C99BFA6F18DE467C80C23B98C7994AA
Y= 42EA2D112ECEC71FCF7E000D7EFC978BD

Point Q (G2)：
X= 6C997F3E7F2C66A4A5D2FDA13756A37B1
Y= 4A38D11829D32D347BD0C0F584D546E9A

np (number of points) = 80000000000000001353F755C0E8FC9A4

n  (prime order) = 200000000000000004D4FDD5703A3F269

（2） 补充细节的考虑 之一 关于hash。

为了使得h1, h2, h3 线性无关，并且与name, 和相关字符 关联起来， 这里取md5 hash作为系数。
h1 = hash1(0x1 name - pediy);
h2 = hash2(0x2 0x2 name - 2017);
h3 = hash3(0x3 0x3 0x3 name - crackme);
hash 采用md5

例如： name = readyu

readyu-pediy
hexstring= 017265616479752D7065646979
hash1=
51c75f1f444baa97ed18dd6c340835d7

readyu-2017
hexstring= 02027265616479752D32303137
hash2=
0e5cf7f068d6efa16f42f935ec424a75

readyu-crackme
hexstring= 0303037265616479752D637261636B6D65
hash3=
a4cd1d64486abde1be441944460cd41d

（3） 

补充细节的考虑 之二 关于sn 编码。

采用一个素数P269， 把S（x,y） 用d加密编码。 结果就是sn。用到了费马小定理。
sn = S^d mod P

P269(prime)= 10000000000000000000000000000000000000000000000000000000000000000079

e=0x5

d= CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCD2D

这里有：
m^(P-1) = 1 (mod P)    (m为自然数， P为素数，  1 <= m < P) 费马小定理
e*d = 1   （ mod  (P-1) ）   , 素数P的欧拉函数是P-1

=〉
(m^d)^e  = m  ( mod P)


（4） 答案：

计算hash：
readyu-pediy
017265616479752D7065646979
hash1 = 51c75f1f444baa97ed18dd6c340835d7

readyu-2017
02027265616479752D32303137
hash2 = 0e5cf7f068d6efa16f42f935ec424a75

readyu-crackme
0303037265616479752D637261636B6D65
hash3 = a4cd1d64486abde1be441944460cd41d

计算S(x,y)：
h1=51C75F1F444BAA97ED18DD6C340835D7
h2=0E5CF7F068D6EFA16F42F935EC424A75
h3=A4CD1D64486ABDE1BE441944460CD41D
G1(x,y)=(51C99BFA6F18DE467C80C23B98C7994AA , 42EA2D112ECEC71FCF7E000D7EFC978BD)
G2(x,y)=(6C997F3E7F2C66A4A5D2FDA13756A37B1 , 4A38D11829D32D347BD0C0F584D546E9A)

S(x,y) = (h2*h3/(h1 - h2)) * G2 - (h1*h3/(h1 - h2)) * G1  mod Order

Order = 200000000000000004D4FDD5703A3F269

h1 - h2 = 436A672EDB74BAF67DD5E43


下面选取攻击者 风间仁 的破解分析


1. 处理逻辑

name是内置的: readyu

code是输入的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int __cdecl sub_40AEF0(HWND hDlg)
{
    ...
  GetDlgItemTextA(hDlg, 1000, name, 64);
  v1 = GetDlgItemTextA(hDlg, 1001, code, 256);
  v2 = v1;
  if ( v1 >= 0x21 )
  {
    if ( code[0] != 0x30 )
    {
      v3 = 0;
      if ( v1 <= 0 )
      {
LABEL_9:
        memset(byte_41BC84, 0, sizeof(byte_41BC84));
        v5 = off_418078[check(code, name)];
        MessageBoxA(hDlg, v5, v5, 0);
        return 0;
      }
      while ( 1 )
      {
        v4 = code[v3];
        if ( !isxdigit(v4) || islower(v4) )
          break;
        if ( ++v3 >= v2 )
          goto LABEL_9;
      }
    }
    ...
}


z = 10000000000000000000000000000000000000000000000000000000000000000079

r = code ^ 5 mod z

r有34字节,  前17字节作为x,  后17字节作为y

epInput = (x,y)


根据name计算3个md5值:

md0=md5("\x01readyu-pediy")=51C75F1F444BAA97ED18DD6C340835D7

md1=md5("\x02\x02readyu-2017")=0E5CF7F068D6EFA16F42F935EC424A75

md2=md5("\x03\x03\x03readyu-crackme")=A4CD1D64486ABDE1BE441944460CD41D


椭圆曲线: m=131, a=13, b=2, c=1, a2=0, a6=1

前面的epInput是这个曲线上的点

ep1 = ( 51C99BFA6F18DE467C80C23B98C7994AA, 42EA2D112ECEC71FCF7E000D7EFC978BD )

ep2 = ( 6C997F3E7F2C66A4A5D2FDA13756A37B1, 4A38D11829D32D347BD0C0F584D546E9A )

n = 200000000000000004D4FDD5703A3F269

校验 (md2 * ep1 + epInput) * md0 mod n == (md2 *ep2 + epInput) * md1 mod n


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
signed int __cdecl check(char *code, const char *a2)
{
    ...
  get_mip();
  v29[0] = 0;
  memset(&v29[1], 0, 0x20u);
  *(_WORD *)&v29[33] = 0;
  v29[35] = 0;
  ptr[0] = 0x10;
  ptr[1] = 0;
  ptr[2] = 0;
  ptr[3] = 0;
  ptr[4] = 0;
  ptr[5] = 0;
  ptr[6] = 0;
  ptr[7] = 0;
  ptr[8] = 0;
  ptr[9] = 0;
  ptr[10] = 0;
  ptr[11] = 0;
  ptr[12] = 0;
  ptr[13] = 0;
  ptr[14] = 0;
  ptr[15] = 0;
  ptr[16] = 0;
  ptr[17] = 0;
  ptr[18] = 0;
  ptr[19] = 0;
  ptr[20] = 0;
  ptr[21] = 0;
  ptr[22] = 0;
  ptr[23] = 0;
  ptr[24] = 0;
  ptr[25] = 0;
  ptr[26] = 0;
  ptr[27] = 0;
  ptr[28] = 0;
  ptr[29] = 0;
  ptr[30] = 0;
  ptr[31] = 0;
  ptr[32] = 0;
  ptr[33] = 0x79;
  mirsys_init();
  v2 = z;
  a2_1 = ::a2;
  v4 = ::x;
  y = dword_41BC68;
  x = dword_41BC64;
  a6 = dword_41BC70;
  w = dword_41BC74;
  bytes_to_big(34, ptr, z);
  cinstr(v4, code);
  if ( mr_compare(v4, v2) <= 0 )
  {
    power(v4, 5, v2, w);
    memset(v29, 0, sizeof(v29));
    if ( big_to_bytes(34, w, v29, 1) == 34 )
    {
      bytes_to_big(17, v29, x);
      bytes_to_big(17, &v29[17], y);
      convert(0, a2_1);
      convert(1, a6);
      v17 = 1;
      if ( ecurve2_init(131, 13, 2, 1, a2_1, a6, 0, 0) )
      {
        qmemcpy(v46, "51C99BFA6F18DE467C80C23B98C7994AA", sizeof(v46));
        qmemcpy(v47, "42EA2D112ECEC71FCF7E000D7EFC978BD", sizeof(v47));
        qmemcpy(v44, "6C997F3E7F2C66A4A5D2FDA13756A37B1", sizeof(v44));
        qmemcpy(v43, "4A38D11829D32D347BD0C0F584D546E9A", sizeof(v43));
        qmemcpy(v45, "200000000000000004D4FDD5703A3F269", sizeof(v45));
        v30 = dword_418118;
        v31 = word_41811C;
        memset(v32, 0, sizeof(v32));
        v33 = 0;
        v34 = dword_4180E4;
        v35 = byte_4180E8;
        memset(v36, 0, sizeof(v36));
        v37 = 0;
        v38 = 0;
        v40 = dword_4180F0;
        v39 = dword_4180EC;
        memset(v41, 0, sizeof(v41));
        a1 = 0;
        memset(v49, 0, sizeof(v49));
        v50 = 0;
        v51 = 0;
        i = 0;
        v6 = &a1;
        a3 = (char *)mds;
        lpMem = (flash)&v30;
        do
        {
          strcpy(v6, a2);
          strcat(v6, "-");
          strcat(v6, (const char *)lpMem);
          xmd5(v6, strlen(v6), a3, i + 1);
          v6 += 256;
          ++i;
          lpMem += 4;
          a3 += 16;
        }
        while ( i < 3 );
        md0 = mirvar(0);
        md1 = mirvar(0);
        md2 = mirvar(0);
        x1 = mirvar(0);
        a3a = mirvar(0);
        x2 = mirvar(0);
        lpMema = mirvar(0);
        v9 = mirvar(0);
        ep1 = epoint_init();
        ep2 = epoint_init();
        p1 = epoint_init();
        p2 = epoint_init();
        epInput = epoint_init();
        if ( epoint2_set(x, y, 0, epInput) )
        {
          cinstr(x1, v46);
          cinstr(a3a, v47);
          epoint2_set(x1, a3a, 0, ep1);
          cinstr(x2, v44);
          cinstr(lpMema, v43);
          epoint2_set(x2, lpMema, 0, ep2);
          bytes_to_big(16, (_BYTE *)mds, md0);
          bytes_to_big(16, mds[1], md1);
          bytes_to_big(16, mds[2], md2);
          ecurve2_mult(md2, ep1, p1);
          ecurve2_mult(md2, ep2, p2);
          ecurve2_add(epInput, p1);
          ecurve2_add(epInput, p2);
          ecurve2_mult(md0, p1, p1);
          ecurve2_mult(md1, p2, p2);
          epoint2_get(p1, x1, a3a);
          epoint2_get(p2, x2, lpMema);
          cinstr(v9, v45);
          divide(x1, v9, v9);
          divide(x2, v9, v9);
          v17 = 3;
          if ( !mr_compare(x1, x2) )
            v17 = 0;
        }
        else
        {
          v17 = 2;
        }
        mirkill(md0);
        mirkill(md1);
        mirkill(md2);
        mirkill(x1);
        mirkill(x2);
        mirkill(a3a);
        mirkill(lpMema);
        mirkill(v9);
        epoint_free(ep1);
        epoint_free(ep2);
        epoint_free(p1);
        epoint_free(p2);
        epoint_free(epInput);
      }
      mirexit();
      result = v17;
    }
    else
    {
      mirexit();
      result = 1;
    }
  }
  else
  {
    mirexit();
    result = 1;
  }
  return result;
}


2. 计算


(md2 * ep1 + epInput) * md0 mod n == (md2 *ep2 + epInput) * md1 mod n

=>

epInput = (md2 * md1 * ep2 - md2 * md0 * ep1) * (((md0 - md1) ^-1) mod n)

得到 ( 02D23461BA71B50AF182DC76E5A7C726F5, 07BE013AF19BD185BCD20BB341EA31298B )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void test2()
{
    big a2 = mirvar(0);
    big a6 = mirvar(1);
    if (ecurve2_init(131, 13, 2, 1, a2, a6, 0, 0))
    {
        epoint *epInput = epoint_init();
        big x = mirvar(0);
        big y = mirvar(0);
         
        big md0 = mirvar(0);
        big md1 = mirvar(0);
        big md2 = mirvar(0);
        cinstr(md0, "51C75F1F444BAA97ED18DD6C340835D7");
        cinstr(md1, "0E5CF7F068D6EFA16F42F935EC424A75");
        cinstr(md2, "A4CD1D64486ABDE1BE441944460CD41D");
         
        epoint *p1 = epoint_init();
        big x1 = mirvar(0);
        big y1 = mirvar(0);
        cinstr(x1, "51C99BFA6F18DE467C80C23B98C7994AA");
        cinstr(y1, "42EA2D112ECEC71FCF7E000D7EFC978BD");
        epoint2_set(x1, y1, 0, p1);
         
        epoint *p2 = epoint_init();
        big x2 = mirvar(0);
        big y2 = mirvar(0);
        cinstr(x2, "6C997F3E7F2C66A4A5D2FDA13756A37B1");
        cinstr(y2, "4A38D11829D32D347BD0C0F584D546E9A");
        epoint2_set(x2, y2, 0, p2);
         
        big n = mirvar(0);
        cinstr(n, "200000000000000004D4FDD5703A3F269");
         
        ecurve2_mult(md2, p2, p2);
        ecurve2_mult(md1, p2, p2);
        ecurve2_mult(md2, p1, p1);
        ecurve2_mult(md0, p1, p1);
        ecurve2_sub(p1, p2);
         
        big r = mirvar(0);
        big rd = mirvar(0);
        big nd = mirvar(0);
        big z = mirvar(0);
        subtract(md0, md1, r);
        xgcd(r, n, rd, nd, z);
         
        ecurve2_mult(rd, p2, epInput);
     
        epoint2_get(epInput, x, y);
        char sx[256];
        char sy[256];
        cotstr(x, sx);
        cotstr(y, sy);
        printf("%s\n", sx);
        printf("%s\n", sy);
    }
}


用RDLP计算得到code

>>> 7A7102F36F3B344D666132A6FF7EF4BA05B99640BB815C9E712A72C64B6ABC582C2


声明：该文观点仅代表作者本人，转载请注明来自看雪