ログイン
編集不可のページディスカッション情報添付ファイル
CTF/Writeup/ASIS CTF Finals 2014/Square

MMA

Square

渡されたプログラムはフラグを部分文字列に分解し、各文字列をstr2hexしたものを16進数と見做し2乗した総和を出力するプログラムである。 (プログラム上は部分文字列は区間を重複することも出来るはずだが、重複はないとして考えた。)

フラグは'ASIS_md5(hoge)'の形式なので、37文字で'A','S','I','_','0'-'9','a-f'の文字のみ含まれている。

問題で与えられた整数の平方根は

0x5260fac0e4ee9973db5b68d9a4

となり16進数で26文字であることから、部分文字列の最大超は13であることが分かる。(12文字だと文字列がたくさん必要となり37文字を越える)

次に最大長の部分文字列の個数を考える。

  1. 13文字の部分文字列が3個加算されたものだとする。
    • sqrt('0'**2 * 3) > 0x52よりありえない

  2. 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'にはなりうる

  3. 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の並び方について両方試せばフラグを得ることが出来る。

CTF/Writeup/ASIS CTF Finals 2014/Square (最終更新日時 2014-10-15 12:22:18 更新者 nomeaning)