平方求幂&damCTF tracing-into-the-night wp

平方求幂算法

平方求幂算法是一种快速计算一个数的幂次的方法
$$
x^n=\begin{cases}
x^{\frac{n}{2}}\ if\ x\ is\ odd\
x\times x^{\frac{n-1}{2}}\ if \ x\ is\ even
\end{cases}
$$
利用这个规律可以递归求一个数的整数幂次。普通求幂复杂度为$O(n)$，该算法复杂度为$O(log_2n)$

tracing-into-the-night wp

使用ida静态分析，可以看到一些函数无法识别，但是看到了长长的十进制字符串，猜测是gnump库。进入gdb调试，有函数名，标注进IDA，得到如下反编译代码。

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
int __cdecl main(int argc, const char **argv, const char **envp)
{
  __int64 v3; // rbp
  __int64 *v4; // rsi
  __int64 v5; // rdx
  int v6; // ST0C_4
  unsigned __int64 v7; // rdi
  int result; // eax
  unsigned __int64 v9; // rsi
  unsigned __int64 v10; // rt1
  int i; // [rsp-658h] [rbp-658h]
  signed int j; // [rsp-654h] [rbp-654h]
  int k; // [rsp-650h] [rbp-650h]
  __int64 *input_num; // [rsp-648h] [rbp-648h]
  __int64 *v15; // [rsp-640h] [rbp-640h]
  __int64 mpz_n; // [rsp-638h] [rbp-638h]
  __int64 mpz_t1; // [rsp-628h] [rbp-628h]
  mpz_t mpz_t_input; // [rsp-618h] [rbp-618h]
  __int64 mpz_res; // [rsp-608h] [rbp-608h]
  __int64 *v20; // [rsp-600h] [rbp-600h]
  __int64 input; // [rsp-5F8h] [rbp-5F8h]
  unsigned __int64 v22; // [rsp-10h] [rbp-10h]
  __int64 v23; // [rsp-8h] [rbp-8h]

  __asm { endbr64 }
  v23 = v3;
  v22 = __readfsqword(0x28u);
  puts(">>> ", argv, envp);
  scanf("%1499s", &input);
  gmpz_inits(&mpz_n, &mpz_t1, &mpz_t_input, 0LL);
  gmpz_set_str(
    &mpz_n,
    "44718451071997505459737203382097036763157674563410285094015196661873160587515660365739479080754310646285927975698840"
    "75919491076155228633904614970948895838322855053680110252775015931685739923032704890382246914424506867596898917291406"
    "11332152177145996284158921291450051409647476573907180263447394788228251424280628988395605571911678859197411847278057"
    "91400587658248775006672823048997257062183136366283575435863850765350233224739628379263972613356404602105716389643245"
    "17304756914352778058093193795607623318712943463163160677253581696533782339191585362014857109889012022353032581293578"
    "60206058478283916330455251797686976821594656048049233954144004025483722105654884172390572538592913614550964028742160"
    "90293906545836344587821140092248468913058755753661122747418378547696731251743370151912439465855419692768832807886171"
    "61119953930555532581063235725600001511098008638586065561150355649771521595492214987293575278242808126982207431794687"
    "22094175413271548368111459152019209395355285403167321317054983346720908955526763883023592954877344827198138450778799"
    "84586727200403718241500034435659943656658321479270769282796202188603446386026445427003762433292713575110502402853472"
    "3013339718674741591919194067341852869368415679054292752733683732089731387",
    10LL);
  gmpz_set_str(
    &mpz_t1,
    "20619486314897341844318499801192377793444872681514265976447810269422099657211923575185395447621708419343082909350420"
    "44722984884526242093626873391758965963625822281049298074982301079998961895199836931743163026038825656545514475458669"
    "01593208120708529551321959949630329565423658895459815612132400107388877020500657132548424936286415877973588244076409"
    "66168118534946988780352124447250486391602877115374749255917590522107130383257354161066774381783854733236051601578721"
    "00921293042212211836183729677392992987773635562510585202428914012812566497860201863986256052255479138196297630309271"
    "16797845975035799543683839219783896048175102837544478413783104917473648240255777477126155618892207667435904754185970"
    "34124241987364543256876480363180951673554712287184795885954238526134182476977957020075710207967797122138761794542028"
    "38904288156820819377922807485116093665788839281617306977143707941755642552793152090536335517622717864224098377424237"
    "71079598091135349027890359740015253411564713414564272128678631947183569729406893947313967249940381200018159756340255"
    "86570301765537327984403658958087369263542596635695098080079490219110960567217248626806197822943112103408691817283370"
    "6720523324225354562780368660709612457907279718303360035550622133576978589",
    10LL);
  gmpz_set_str(&mpz_t_input, &input, 10LL);
  v4 = (__int64 *)1;
  gmpz_init_set_ui(&mpz_res, 1LL);
  input_num = mpz_t_input.data;
  for ( i = HIDWORD(mpz_t_input.len) - 1; i >= 0; --i )
  {
    for ( j = 0; j <= 63; ++j )
    {
      gmpz_mul(&mpz_res, &mpz_res, &mpz_res);   // r=r**2
      v4 = &mpz_res;
      gmpz_mod(&mpz_res, &mpz_res, &mpz_n);     // r=r mod n
      if ( (input_num[i] & 0x8000000000000000LL) == 0x8000000000000000LL )// 取最高位
      {
        gmpz_mul(&mpz_res, &mpz_res, &mpz_t1);
        v4 = &mpz_res;
        gmpz_mod(&mpz_res, &mpz_res, &mpz_n);
      }
      v5 = 2 * input_num[i];                    // 左移1位
      input_num[i] = v5;
    }
  }
  v15 = v20;
  v6 = 8 * HIDWORD(mpz_res);
  v7 = (unsigned __int64)"<<< ";
  puts("<<< ", v4, v5);
  for ( k = v6 - 1; k >= 0; --k )
  {
    v7 = (unsigned int)*((char *)v15 + k);
    put_char(v7);
  }
  result = 0;
  v10 = __readfsqword(0x28u);
  v9 = v10 ^ v22;
  if ( v10 != v22 )
    result = sub_4010E0(v7, v9);
  return result;
}

可以看到是一个平方求幂算法，这里算的是
$$
res=t1^{input}mod\ n
$$
是一个rsa算法，所以找到对应的解密密钥即可。

查看trace.asm文件，这里记录了程序执行过的指令。汇编中这两句值得注意。

1
2
3
4
5
6
7
8
9
4013a6:       48 8b 00                mov    (%rax),%rax
4013a9:       48 ba 00 00 00 00 00    movabs $0x8000000000000000,%rdx
4013b3:       48 21 c2                and    %rax,%rdx
4013b6:       48 b8 00 00 00 00 00    movabs $0x8000000000000000,%rax
4013c0:       48 39 c2                cmp    %rax,%rdx
4013c3:       75 40                   jne    401405 <main+0x1cf>
401405:       8b 85 b0 f9 ff ff       mov    -0x650(%rbp),%eax
40140b:       48 98                   cltq
40140d:       48 8d 14 c5 00 00 00    lea    0x0(,%rax,8),%rdx

即判断是否为相等，不相等就跳转，对应程序中的if语句。使用这个特征，根据jnz语句后面的语句地址，可以判断密钥的当前位是1还是0，使用python脚本解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import base64
import hashlib
flag = ''
with open('trace.asm','r') as f:
    line = f.readline()
    nline = ''
    while line:
        if line[:7]=='4013c3:':
            nline = f.readline()
            if not nline:
                break
            if nline[:7]=='401405:':
                flag+='0'
            else:
                flag+='1'
        line = f.readline()
print(flag)
print(int(flag,base=2))
1
2
0011101111111000000101111111110110000010010100000100011010110100001010010101010100011010111011111111010010110001000011100110111101100000010010011101000110101011001000110110001010111010101101110010101100101100101111110000110100011100110110100000101111001011101001111001100011110000100001101101100110000010001100100001110110101010000110001100000110100100011101011000001110000011100111110111000100100110001011110011010000001101011111111010011011110101010101100011110001110100101000110111000000111011010010011110111010101011100000110101111011000111101100000011111000111010011010110101100111110000011010110110101101010001010001000000001010010001011000001100100111011100101101100001010100011101011111001011001100110001001001000001001011001111011101101011110011100110110010011001000010111010010001110100101100000100100101010111010010111100101000100101011001100011010111101001000011111110010110110000011100110001011000100011100101010001011001010110010110100011010000011000000100000111000000001111100111100111011000111111001101101101101101001110001011010101001111011001110100001001110001110100001000001100110101011110100011110111100011110101011110010000001110010001010111000001001100000101100010101101000110000001111001011011001001100100100010100000110100010101100110000100100110101110011000111001101001011010011011110001001100111100011100001011111010011010010101101110101011001000001000111110000100110011101010011000100110110001010100011101010101001001001011000111101011101110001010011000101110010001111101000110000101110100001101001011110001111010101110011101111100101011011001111000010011000010001010101000100011111111110110000111000001000011100011111010001000110100111111010011110111011011111100111001111011000100101001000110101100001101100010100110110111111101100011011101111000101101100010100010001100111010001000101101110111110100010010111000000111110110010010010110000101111001110111110111100000000110111100000000000011001110110100000101100111010010101111101111111111001101011100001011111001110011000100010000101111011100110001100111010011000110011110010111011111111001001111110101101100001111010101011110111110010011001011101001000101011110100100110000111101101100111111011001000011010000111111101101010011111001001100110010001111100100110100110000111101100111011001111000000001010101010100010101010010001001110001001000010100011110111110001100011101001110011010100001000000000110101000100100101010100010100001000101010111101111000010111001100110101001010010000111010100011000101110111111000110111001010100001001101011110001101101010011110010110011111010100011101001000100111101010101011010000101011101110100001111000010011101011101100011011100100000001011100011001010111101010010111101101010100000100000001100000001010101110110011001101001101010110111011011010011111000000010101001100100010101111101000011000110011000011111000001100100010011001000110001010000010111111110100001010011101111110010110101111101100000111011101001011000001001100110011000110111000010000110001101011101100001001001100110001000000010010110010100111100011000011111111011111101100011010111010010100111000000010110001000101001100011010011000101011010000000101100001000010101111101000110011111010100010010100000000101001100001101010110100111010000000101011100000111001000000010010101100101011100110100111010110101110010100001100010110001011001011001100101101001000011101000111001100100000000100001000111010110001011110101001101100001110111101001000100110100110011100100000000001010000101011001110010110100110110001000111001110000110001010101000111100100101110101000111011001010100000001100001001000010110111101010100001000101011110000101110101111000000101010101000111011111110001100101011110000001110110101111111000001011101010101111010000100010000011101111001101000110110111010101111110100100011101011101010001101100000010101010000111110010001011101100001101010010001101110010101100001101111101011001110000001010111101010110101000011001100111110011011100011111101001011100001001110001101011100011011111101001001111100111010101111010010101001111111110110101111010101110111011101101110100001000010010011000011101101011001001
244652648608644057289603953074612700175933964244789320848667909167563692702652547784242339814218808951063055612658793570186844889979282952606878226608877859935559988556621623278752812292605612612163883997532869509885618332866441068962865470136130272926263303521750180711550883814600026677234330838029265221441047841355637850083056067511836089295432603059046109298537904428654107114553910703320935211803599935665225999452564664140186232164739291375407556107412707105250411308366447742913058979723684840765449422267902293487537073300912104264330520400754843332881465525532116517816288168335852096828051764240859454454009518120111671812902113201938369763608841769720763131720010223805776325980208111929662026610968279056747490265115993253416851071451892127738460444147514901971784385322720069737101076139227245987315223123169336706863690888801293487213146614146679028050257150777887496982927824949105219206894794372697828812226397922441686397417061966543488748591869285400239357533529688996471390996874988047597260063994210684092801510867133594884893681119353051040329814500624965262408435785310992711659906711739870502390260550767314380870394028475183756688989994399612240550769839124489086507436798682013488698499282429664122768579273

输入得到flag

1
2
3
kali@kali:~/Downloads$ ./tracing-into-the-night 
>>> 244652648608644057289603953074612700175933964244789320848667909167563692702652547784242339814218808951063055612658793570186844889979282952606878226608877859935559988556621623278752812292605612612163883997532869509885618332866441068962865470136130272926263303521750180711550883814600026677234330838029265221441047841355637850083056067511836089295432603059046109298537904428654107114553910703320935211803599935665225999452564664140186232164739291375407556107412707105250411308366447742913058979723684840765449422267902293487537073300912104264330520400754843332881465525532116517816288168335852096828051764240859454454009518120111671812902113201938369763608841769720763131720010223805776325980208111929662026610968279056747490265115993253416851071451892127738460444147514901971784385322720069737101076139227245987315223123169336706863690888801293487213146614146679028050257150777887496982927824949105219206894794372697828812226397922441686397417061966543488748591869285400239357533529688996471390996874988047597260063994210684092801510867133594884893681119353051040329814500624965262408435785310992711659906711739870502390260550767314380870394028475183756688989994399612240550769839124489086507436798682013488698499282429664122768579273
<<< dam{and_1nto_d4ta_depend3ncy}

参考资料

[1] 平方求幂–wikipedia

[2] DamCTF rev/tracing-into-the-night wp by macz–ctftime

附录

平方求幂算法汇编代码

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
.text:0000000000401236 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:0000000000401236                 public main
.text:0000000000401236 main            proc near               ; DATA XREF: _start+21↑o
.text:0000000000401236 ; __unwind {
.text:0000000000401236                 endbr64
.text:000000000040123A                 push    rbp
.text:000000000040123B                 mov     rbp, rsp
.text:000000000040123E                 sub     rsp, 650h
.text:0000000000401245                 mov     rax, fs:28h
.text:000000000040124E                 mov     [rbp-8], rax
.text:0000000000401252                 xor     eax, eax
.text:0000000000401254                 lea     rdi, asc_4029E0 ; ">>> "
.text:000000000040125B                 mov     eax, 0
.text:0000000000401260                 call    puts
.text:0000000000401265                 lea     rax, [rbp-5F0h]
.text:000000000040126C                 mov     rsi, rax
.text:000000000040126F                 lea     rdi, a1499s     ; "%1499s"
.text:0000000000401276                 mov     eax, 0
.text:000000000040127B                 call    scanf
.text:0000000000401280                 lea     rdx, [rbp-610h]
.text:0000000000401287                 lea     rsi, [rbp-620h]
.text:000000000040128E                 lea     rax, [rbp-630h]
.text:0000000000401295                 mov     ecx, 0
.text:000000000040129A                 mov     rdi, rax
.text:000000000040129D                 mov     eax, 0
.text:00000000004012A2                 call    gmpz_inits
.text:00000000004012A7                 lea     rax, [rbp-630h]
.text:00000000004012AE                 mov     edx, 0Ah
.text:00000000004012B3                 lea     rsi, N          ; "447184510719975054597372033820970367631"...
.text:00000000004012BA                 mov     rdi, rax
.text:00000000004012BD                 call    gmpz_set_str
.text:00000000004012C2                 lea     rax, [rbp-620h]
.text:00000000004012C9                 mov     edx, 0Ah
.text:00000000004012CE                 lea     rsi, C          ; "206194863148973418443184998011923777934"...
.text:00000000004012D5                 mov     rdi, rax
.text:00000000004012D8                 call    gmpz_set_str
.text:00000000004012DD                 lea     rcx, [rbp-5F0h]
.text:00000000004012E4                 lea     rax, [rbp-610h]
.text:00000000004012EB                 mov     edx, 0Ah
.text:00000000004012F0                 mov     rsi, rcx
.text:00000000004012F3                 mov     rdi, rax
.text:00000000004012F6                 call    gmpz_set_str
.text:00000000004012FB                 lea     rax, [rbp-600h]
.text:0000000000401302                 mov     esi, 1
.text:0000000000401307                 mov     rdi, rax
.text:000000000040130A                 call    gmpz_init_set_ui
.text:000000000040130F                 mov     rax, [rbp-608h]
.text:0000000000401316                 mov     [rbp-640h], rax
.text:000000000040131D                 mov     eax, [rbp-60Ch]
.text:0000000000401323                 mov     [rbp-644h], eax
.text:0000000000401329                 mov     eax, [rbp-644h]
.text:000000000040132F                 sub     eax, 1
.text:0000000000401332                 mov     [rbp-650h], eax
.text:0000000000401338                 jmp     loc_40145D
.text:000000000040133D ; ---------------------------------------------------------------------------
.text:000000000040133D
.text:000000000040133D loc_40133D:                             ; CODE XREF: main+22E↓j
.text:000000000040133D                 mov     dword ptr [rbp-64Ch], 0
.text:0000000000401347                 jmp     loc_401449
.text:000000000040134C ; ---------------------------------------------------------------------------
.text:000000000040134C
.text:000000000040134C loc_40134C:                             ; CODE XREF: main+21A↓j
.text:000000000040134C                 lea     rdx, [rbp-600h]
.text:0000000000401353                 lea     rcx, [rbp-600h]
.text:000000000040135A                 lea     rax, [rbp-600h]
.text:0000000000401361                 mov     rsi, rcx
.text:0000000000401364                 mov     rdi, rax
.text:0000000000401367                 call    gmpz_mul
.text:000000000040136C                 lea     rdx, [rbp-630h]
.text:0000000000401373                 lea     rcx, [rbp-600h]
.text:000000000040137A                 lea     rax, [rbp-600h]
.text:0000000000401381                 mov     rsi, rcx
.text:0000000000401384                 mov     rdi, rax
.text:0000000000401387                 call    gmpz_mod
.text:000000000040138C                 mov     eax, [rbp-650h]
.text:0000000000401392                 cdqe
.text:0000000000401394                 lea     rdx, ds:0[rax*8]
.text:000000000040139C                 mov     rax, [rbp-640h]
.text:00000000004013A3                 add     rax, rdx
.text:00000000004013A6                 mov     rax, [rax]
.text:00000000004013A9                 mov     rdx, 8000000000000000h
.text:00000000004013B3                 and     rdx, rax
.text:00000000004013B6                 mov     rax, 8000000000000000h
.text:00000000004013C0                 cmp     rdx, rax
.text:00000000004013C3                 jnz     short loc_401405
.text:00000000004013C5                 lea     rdx, [rbp-620h]
.text:00000000004013CC                 lea     rcx, [rbp-600h]
.text:00000000004013D3                 lea     rax, [rbp-600h]
.text:00000000004013DA                 mov     rsi, rcx
.text:00000000004013DD                 mov     rdi, rax
.text:00000000004013E0                 call    gmpz_mul
.text:00000000004013E5                 lea     rdx, [rbp-630h]
.text:00000000004013EC                 lea     rcx, [rbp-600h]
.text:00000000004013F3                 lea     rax, [rbp-600h]
.text:00000000004013FA                 mov     rsi, rcx
.text:00000000004013FD                 mov     rdi, rax
.text:0000000000401400                 call    gmpz_mod
.text:0000000000401405
.text:0000000000401405 loc_401405:                             ; CODE XREF: main+18D↑j
.text:0000000000401405                 mov     eax, [rbp-650h]
.text:000000000040140B                 cdqe
.text:000000000040140D                 lea     rdx, ds:0[rax*8]
.text:0000000000401415                 mov     rax, [rbp-640h]
.text:000000000040141C                 add     rax, rdx
.text:000000000040141F                 mov     rdx, [rax]
.text:0000000000401422                 mov     eax, [rbp-650h]
.text:0000000000401428                 cdqe
.text:000000000040142A                 lea     rcx, ds:0[rax*8]
.text:0000000000401432                 mov     rax, [rbp-640h]
.text:0000000000401439                 add     rax, rcx
.text:000000000040143C                 add     rdx, rdx
.text:000000000040143F                 mov     [rax], rdx
.text:0000000000401442                 add     dword ptr [rbp-64Ch], 1
.text:0000000000401449
.text:0000000000401449 loc_401449:                             ; CODE XREF: main+111↑j
.text:0000000000401449                 cmp     dword ptr [rbp-64Ch], 3Fh
.text:0000000000401450                 jle     loc_40134C
.text:0000000000401456                 sub     dword ptr [rbp-650h], 1
.text:000000000040145D
.text:000000000040145D loc_40145D:                             ; CODE XREF: main+102↑j
.text:000000000040145D                 cmp     dword ptr [rbp-650h], 0
.text:0000000000401464                 jns     loc_40133D
.text:000000000040146A                 mov     rax, [rbp-5F8h]
.text:0000000000401471                 mov     [rbp-638h], rax
.text:0000000000401478                 mov     eax, [rbp-5FCh]
.text:000000000040147E                 shl     eax, 3
.text:0000000000401481                 mov     [rbp-644h], eax
.text:0000000000401487                 lea     rdi, asc_4029EC ; "<<< "
.text:000000000040148E                 mov     eax, 0
.text:0000000000401493                 call    puts
.text:0000000000401498                 mov     eax, [rbp-644h]
.text:000000000040149E                 sub     eax, 1
.text:00000000004014A1                 mov     [rbp-648h], eax
.text:00000000004014A7                 jmp     short loc_4014D0
.text:00000000004014A9 ; ---------------------------------------------------------------------------
.text:00000000004014A9
.text:00000000004014A9 loc_4014A9:                             ; CODE XREF: main+2A1↓j
.text:00000000004014A9                 mov     eax, [rbp-648h]
.text:00000000004014AF                 movsxd  rdx, eax
.text:00000000004014B2                 mov     rax, [rbp-638h]
.text:00000000004014B9                 add     rax, rdx
.text:00000000004014BC                 movzx   eax, byte ptr [rax]
.text:00000000004014BF                 movsx   eax, al
.text:00000000004014C2                 mov     edi, eax
.text:00000000004014C4                 call    put_char
.text:00000000004014C9                 sub     dword ptr [rbp-648h], 1
.text:00000000004014D0
.text:00000000004014D0 loc_4014D0:                             ; CODE XREF: main+271↑j
.text:00000000004014D0                 cmp     dword ptr [rbp-648h], 0
.text:00000000004014D7                 jns     short loc_4014A9
.text:00000000004014D9                 mov     eax, 0
.text:00000000004014DE                 mov     rsi, [rbp-8]
.text:00000000004014E2                 xor     rsi, fs:28h
.text:00000000004014EB                 jz      short locret_4014F2
.text:00000000004014ED                 call    sub_4010E0
.text:00000000004014F2
.text:00000000004014F2 locret_4014F2:                          ; CODE XREF: main+2B5↑j
.text:00000000004014F2                 leave
.text:00000000004014F3                 retn
.text:00000000004014F3 ; } // starts at 401236
.text:00000000004014F3 main            endp