Square
渡されたプログラムはフラグを部分文字列に分解し、各文字列をstr2hexしたものを16進数と見做し2乗した総和を出力するプログラムである。 (プログラム上は部分文字列は区間を重複することも出来るはずだが、重複はないとして考えた。)
フラグは'ASIS_md5(hoge)'の形式なので、37文字で'A','S','I','_','0'-'9','a-f'の文字のみ含まれている。
問題で与えられた整数の平方根は
0x5260fac0e4ee9973db5b68d9a4
となり16進数で26文字であることから、部分文字列の最大超は13であることが分かる。(12文字だと文字列がたくさん必要となり37文字を越える)
次に最大長の部分文字列の個数を考える。
- 13文字の部分文字列が3個加算されたものだとする。
sqrt('0'**2 * 3) > 0x52よりありえない
- 13文字の部分文字列が2個加算されたものだとする。
'a' > 0x52より'a'-'f'はどちらの先頭にも出現しない。
sqrt('9'**2 * 2) < 0x50 より、どちらの先頭も'0'-'9'ということはありえない。
sqrt('S'**2 + '0' ** 2) > 0x53より、片方の先頭が'S'ということはありえない。
sqrt('I'**2 + '0' ** 2) > 0x53より、片方の先頭が'I'ということはありえない。
sqrt('_'**2 + '0' ** 2) > 0x53より、片方の先頭が'_'ということはありえない。
sqrt('A'**2 + '0' ** 2) < 0x53, sqrt('A'**2 + '9' ** 2) > 0x53より片方の先頭が'A'にはなりうる
- 13文字の部分文字列が1個加算されたものだとする。
- 12文字の部分文字列による影響を考えても、一番左の文字列は'R','Q','P'のどれかとなるはずで、このような文字は含まれないのでありえない。
以上より、13文字の部分文字列は2つ加算されており、片方は'A'で始まる文字列である。
'A'で始まる文字列というのはフラグの先頭部分"ASIS_..."しかありえない。 そこで、それぞれ"ASIS_00000000"及び"ASIS_ffffffff"を2乗したものを引いて平方根を求めると、
ASIS_00000000 => 0x323038399890c92765bac161a8 ASIS_ffffffff => 0x32303839984a3939e7f3467c9d
それぞれの共通部分を見てみると"32303839"となっている。これはASCII文字列に直すと、" 2089"となっていて、これは2つ目の13文字の部分文字列の先頭4文字であると分かる。 ここで、13文字ではない部分文字列の最大の長さが10だったとすると、5文字目の情報まで失なうことはないため、13文字でない部分文字列の最大の長さは11となる。13+13+11=37より部分文字列は3つしか存在しない。
ここで、問題の数値をN, "ASIS_"から始まる部分文字列をA、もう一つの13文字の部分文字列をB、11文字の部分文字列をCとする。 以下のプログラムを用いてA,Bについて、先頭5文字を探索し、ありえるパターンを列挙した。
1 require 'gmp'
2 N = 42598113503607816275290739917038018215431555012399274191982894
3 def squ(str)
4 str.unpack("H*")[0].to_i(16)**2
5 end
6 def sqr(f)
7 GMP::Z(f).sqrt.to_i
8 end
9 T = ARGV[0].to_i
10 C = '0123456789abcdef'
11 CS = C.chars.map{|a|a.unpack("H*")[0]}
12 def maxs(s)
13 s + 'f' * (13-s.size)
14 end
15 def mins(s)
16 s + '0' * (13-s.size)
17 end
18 def search(a,b,k)
19 c1 = sqr(N - squ(maxs(a)) - squ(maxs(b)))
20 c2 = sqr(N - squ(mins(a)) - squ(mins(b)))
21 c1 = c1.to_s(16)
22 c2 = c2.to_s(16)
23 c = ''
24 11.times do |i|
25 if c1[i*2,2] == c2[i*2,2]
26 return unless CS.include?(c1[i*2,2])
27 c += c2[i*2,2]
28 else
29 ok = false
30 ((c1[i*2,2].to_i(16))..(c2[i*2,2].to_i(16))).each do |a|
31 if CS.include?(a.to_s(16))
32 ok = true
33 end
34 end
35 return unless ok
36 break
37 end
38 end
39 c += "?" * (22 - c.size)
40 if k == T
41 p [a,b,c,c1,c2]
42 return
43 end
44 C.each_char do |p|
45 C.each_char do |q|
46 na,nb = a,b
47 if a.size <= k
48 na += p
49 end
50 nb += q
51 search(na,nb,k+1)
52 end
53 break unless a.size <= k
54 end
55 end
56
57 search('ASIS_', '2089', 4)
$ ruby search.rb ["ASIS_", "20890", "66????????????????????", "661e43919a7868b989823e", "665b83e6d702233e1451ac"] ["ASIS_", "20892", "65????????????????????", "6521682750d179b510739c", "655f41452e7391bbac68c4"] ["ASIS_", "20894", "64????????????????????", "64220e407533845d65dece", "646084b4ff1a6ace4e2e66"] ["ASIS_", "20896", "63????????????????????", "63202296bd2332187225ec", "635f3b2b1b974255ae086f"] ["ASIS_", "20898", "62????????????????????", "621b90e67ee1308c7c7dff", "625b50a33f97773353c4c1"]
探索結果よりBの5文字目は'0', '2', '4', '6', '8'であると分かる。
A,Bの下8文字について探索することを考える。 A,B,Cの下の桁から2乗した値が一致するかを確認しながら探索すると、 16 ** 24(探索しなきゃいけないパターン数) / 16 ** 16(枝刈りされるはずのパターン数)より2 ** 32程度の計算で全て探索することが出来る。A,Bの下8文字が求まったら、上5桁の5パターンについて、C = sqrt(N - A ** 2 - B ** 2)を考え、Cが'0'-'9','a'-'f'で表される文字列になるようなものを探せば、A,B,Cを特定することが出来る。
以下のプログラムで実際に探索した所、1時間程度で解が得られた。
1 #include <stdio.h>
2 #include <unistd.h>
3 #include <gmp.h>
4 #include <sys/wait.h>
5 #include <stdlib.h>
6 #define BASE 10
7
8 mpz_t A,B,C,N,D;
9 mpz_t AA,BB,CC,NN,DD;
10 mpz_t KK;
11 mpz_t ADD;
12 mpz_t ADD1;
13 mpz_t ADD2;
14 mpz_t ADD3;
15 mpz_t ADD4;
16 mpz_t ADD5;
17 #define ulong unsigned long long
18
19
20 ulong n = 17577079109955850542ULL;
21 ulong numbers[] = {48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102};
22 char strs[64];
23 void check2() {
24 mpz_sub(DD, N, A);
25 mpz_sub(NN, DD, B);
26 if(mpz_cmp_si(NN, 0) < 0) return;
27 mpz_sqrt(CC, NN);
28 mpz_mul(KK, CC, CC);
29 if(mpz_cmp(NN, KK) == 0) {
30 mpz_out_str(stdout, 16, AA);puts("");
31 mpz_out_str(stdout, 16, BB);puts("");
32 mpz_out_str(stdout, 16, CC);puts("");
33 fflush(stdout);
34 }
35 }
36 void check(ulong a, ulong b) {
37 sprintf(strs, "%llu", a);
38 mpz_set_str(A, strs, 10);
39 sprintf(strs, "%llu", b);
40 mpz_set_str(C, strs, 10);
41 mpz_add(AA, A, ADD);
42 mpz_mul(A, AA, AA);
43 mpz_add(BB, C, ADD1); mpz_mul(B, BB, BB);
44 check2();
45 mpz_add(BB, C, ADD2); mpz_mul(B, BB, BB);
46 check2();
47 mpz_add(BB, C, ADD3); mpz_mul(B, BB, BB);
48 check2();
49 mpz_add(BB, C, ADD4); mpz_mul(B, BB, BB);
50 check2();
51 mpz_add(BB, C, ADD5); mpz_mul(B, BB, BB);
52 check2();
53 }
54 void search(ulong a, ulong b, ulong c, ulong k) {
55 if(k == 8) {
56 check(a,b);
57 check(b,a);
58 check(a,c);
59 check(c,a);
60 check(b,c);
61 check(c,b);
62 }else{
63 ulong mask = (1ULL << ((k + 1) << 3)) - 1;
64 if(k == 7) mask = -1;
65 int shift = k << 3;
66 for(int i = 0; i < 16; i++) {
67 ulong na = a | (numbers[i] << shift);
68 for(int j = 0; j < 16; j++) {
69 ulong nb = b | (numbers[j] << shift);
70 for(int l = 0; l < 16; l++) {
71 ulong nc = c | (numbers[l] << shift);
72 if((na*na+nb*nb+nc*nc-n)&mask){
73
74 }else{
75 search(na,nb,nc,k+1);
76 }
77 }
78 }
79 }
80 }
81 }
82
83 int main() {
84 int a,b,c;
85 if(fork() == 0) {
86 a = 101;
87 b = 102;
88 c = 57;
89 }else if(fork() == 0) {
90 a = 101;
91 b = 55;
92 c = 98;
93 }else if(fork() == 0) {
94 a = 102;
95 b = 49;
96 c = 51;
97 }else if(fork() == 0) {
98 a = 49;
99 b = 98;
100 c = 99;
101 }else if(fork() == 0) {
102 a = 53;
103 b = 54;
104 c = 55;
105 }else if(fork() == 0) {
106 a = 53;
107 b = 57;
108 c = 98;
109 }else{
110 int t;
111 wait(&t);
112 wait(&t);
113 wait(&t);
114 wait(&t);
115 wait(&t);
116 wait(&t);
117 }
118 mpz_init2(A, 256);
119 mpz_init2(B, 256);
120 mpz_init2(C, 256);
121 mpz_init2(N, 256);
122 mpz_init2(D, 256);
123 mpz_init2(AA, 256);
124 mpz_init2(BB, 256);
125 mpz_init2(CC, 256);
126 mpz_init2(NN, 256);
127 mpz_init2(DD, 256);
128 mpz_init2(KK, 256);
129
130 mpz_init2(ADD, 256);
131 mpz_init2(ADD1, 256);
132 mpz_init2(ADD2, 256);
133 mpz_init2(ADD3, 256);
134 mpz_init2(ADD4, 256);
135 mpz_init2(ADD5, 256);
136 mpz_set_str(ADD, "5175606464536044217397227290624", 10);
137 mpz_set_str(ADD1, "32303839300000000000000000", 16);
138 mpz_set_str(ADD2, "32303839320000000000000000", 16);
139 mpz_set_str(ADD3, "32303839340000000000000000", 16);
140 mpz_set_str(ADD4, "32303839360000000000000000", 16);
141 mpz_set_str(ADD5, "32303839380000000000000000", 16);
142 mpz_set_str(N, "42598113503607816275290739917038018215431555012399274191982894", 10);
143 search(a,b,c,1);
144 }
$ g++ search.cpp -O3 -march=native -lgmp -osearch $ ./search 415349535f6531326635373339 32303839303330346266353365 6638316230386334373066
後は、B,Cの並び方について両方試せばフラグを得ることが出来る。