某CTF(2018年3月卒向け)のWriteUp 前半

セキュリティで有名な某会社が新卒向けに(エクストリーム)CTFをやっていて、社会人ならこれくら解けなきゃいけないのかな、と思って毎年チャレンジしています。

毎年、モヤモヤが残るのですが(2016年の岬名とか)、今年は結構すっきりしたのでまとめて見ました。前半・後半の2部構成で書きます。まずは前半です。

ただ、2018年1月現在でも、まだ問題公開中なので、各問題の回答については微妙にぼかしておきます。

mondai1

URLにアクセスするとエクストリームCTFのところに下記の文字列が提示されております。
R28gaHR0cDovL3BiaC5qcC8yMDE4Lw==
使われてる文字の種類とイコール記号でパディングされているのでbase64文字列ですね。

echo "R28gaHR0cDovL3BiaC5qcC8yMDE4Lw==" | base64 -d

でURLを含んだ文字列が得られます。

mondai2

mondai1のURLに行くとzipファイルをDLできます。ここからが本番です。

sec_font.txt

my number: ǧǍǡȱǬǡǡŕðǡŕĵ
my number: ưśǡľľŕȫǬśȫȶȱ
my number: ƿǧĵǡƿȫŕŕŨğũƿ
my number: ũľľŨũĵȫŨśưÿś
my number: ğƿÿŕǬśǬȫǍȶÿǬ
my number: ğǬȫǬǬǬƿƿśũȶś
my number: ǧśǍȱǍľĵğưǡśƿ
my number: ȱŨğŨȱúȱŕȫǡǡƿ
my number: ŨŕũȶȱưľȱũǧŨȫ
my number: ưŨĵśǧǬȫȶũľŨƿ
my number: úľǬľȫðȱľŨðǡğ
my number: ğȫśÿŨśśũưğśğ
my number: ƿȶȶŨǍğÿǧǬľľũ
my number: ğǡŕğŨŕũðȶǍǬğ
my number: Ǭȱśÿũŕǧÿŕƿúǡ
my number: ǧĵĵśȱȶȶÿŕũȱǧ
my number: ľðǬǍúưðğȶưȶȶ
my number: ưúǧðȱŨǡȫŨǬĵŨ
my number: ǬǬśȫśĵǍǧðƿȫȫ
my number: ğǬǧľĵúŕȱÿȫȱũ

漏洩したマイナンバーの文字列をつなげてsha1でハッシュせよ

とのことです。

なぞの文字列の部分がセキュリティフォントで、計20個のマイナンバーが暗号化されているようです。
この文字列は1行あたり24byteで構成されています。
マイナンバーは12桁の数字のため1つの数字が2byteのコードポイントに換字されているということですね。
20個の暗号化されたマイナンバーを2byte単位で区切ると、19種類のコードポイントがあることがわかります。

19種類のものを10種類の数字にマッピングして、マイナンバーのチェックサム仕様に合致する組み合わせを求める必要があります。

出現頻度の高いコードポイントから深さ優先探索で数字を総当りして、マイナンバーの12桁の数字が揃ったら、チェックサムが一致しているかどうかをチェックするというプログラムを用意しましたが、残念ながら私のプログラムでは19種類のものを総当りするには計算リソースが全く足りませんでした。

出題者から下記のヒントが出ており、11種類のコードポイントが判明します。

814895727129 => ğǬǧľĵúŕȱÿȫȱũ
これで計算力が1/100 以下になるはず。

— lumin (@lumin) 2017年3月2日

11個も判明すると、1/10^11 も計算量が減る気がするのですが、深追いしないことにします。
これを用いると2秒くらいでサクッとマイナンバーが探索完了します。

得られた20個のマイナンバーを改行なしで連結して、sha1sum コマンドに食わせた下記の文字列がパスワードになります。

3c3e087734f15d0dc0c427fc833de465bc??????

mondai3

 暗号化された法人番号の元の法人番号を順につなげた26桁の数字
 1d575a9b004dfded8e29a361356677a92dae7fb9
 e825c2c041cb00624205a4a23722170ea5be42d4

次は法人ナンバーです。
暗号化された文字列ですが、40文字のhexな文字種類なのでSHA1ですね。
法人ナンバーも何かしらの法則がありそうなのですが、国税庁のサイトで法人番号の全データをDLできますので、それに対して総当りしてみます。
サイトから48個のzipファイルをダウンロードしてきて、csvに含まれる法人番号のsha1を作成します。
mondai2と違って、法人番号に改行(\n)を付けた文字列にしなければならないというゆらぎがありましたが、求めるものが見つかります。

5010001076???   1d575a9b004dfded8e29a361356677a92dae7fb9
5010001168???   e825c2c041cb00624205a4a23722170ea5be42d4
  => 5010001076???5010001168???

パスワードは法人番号を順につなげた26桁の数字なので、それを用いて解凍すると次の問題に進めます。

ちなみに対象の法人番号は住所はともに東京で同じビルでした。それがどんな意味なのかは深追いしてません。

mondai4

zipファイルを解凍すると下記のc++コードが得られます。

binaryhacks.cpp

#include <stdio.h>

int main(int argc, char **argv) {

        unsigned char func1[] = {
                0x4D, 0x00, 0x00, 0xE3,
                0x00, 0x08, 0xA0, 0xE1,
                0x41, 0x12, 0x05, 0xE3,
                0x01, 0x00, 0x80, 0xE1,
                0x1E, 0xFF, 0x2F, 0xE1,
        };

        unsigned char func2[] = {
                0x10, 0x07, 0x02, 0xE3,
                0x98, 0x13, 0x05, 0xE3,
                0x01, 0x00, 0x80, 0xE0,
                0x3F, 0x00, 0x40, 0xE2,
                0x1E, 0xFF, 0x2F, 0xE1,
        };

        unsigned char func3[] = {
                0x54, 0x00, 0x00, 0xE3,
                0x00, 0x08, 0xA0, 0xE1,
                0x4C, 0x11, 0x04, 0xE3,
                0x01, 0x00, 0x80, 0xE1,
                0x1E, 0xFF, 0x2F, 0xE1,
        };

        unsigned long ret1 = ((unsigned long(*)())func1)();
        unsigned long ret3 = ((unsigned long(*)())func3)();
        printf("flag : %s%d%s\n", (char *)(&ret1), ((unsigned long(*)())func2)(), (char *)(&ret3));

        return 0;

}

マシンコードが埋め込まれたコードです。
コードをググってみるとARM系のコードらしいのですが、スキルが無いので人力でアセンブラになんかできません。

手持ちのARMマシンでRaspberryPiがありましたので、そちらで逆アセンブルしてみます。

$ echo -ne "\x4D\x00\x00\xE3\x00\x08\xA0\xE1\x41\x12\x05\xE3\x01\x00\x80\xE1\x1E\xFF\x2F\xE1" > hoge
$ objdump -D -b binary -marm hoge

セクション .data の逆アセンブル:

00000000 <.data>:
   0:   e300004d        movw    r0, #77 ; 0x4d
   4:   e1a00800        lsl     r0, r0, #16
   8:   e3051241        movw    r1, #21057      ; 0x5241
   c:   e1800001        orr     r0, r0, r1
  10:   e12fff1e        bx      lr

このようにして得られたアセンブラをfunc2とfunc3についても同様にして、binaryhacks.cppをC言語的に書き直すと下記のようになります

#include <stdio.h>

unsigned long func1()
{
  int r0,r1;
  r0 = 77;
  r0 <<= 16;
  r1 = 21057;
  r0 |= r1;
  return r0; /* 5067329 */
}

unsigned long func2()
{
  int r0,r1;
  r0 = 10000;
  r1 = 21400;
  r0 += r1;
  r0 -= 63;
  return r0; /* 31337 */
}

unsigned long func3()
{
  int r0,r1;
  r0 = 84;
  r0 <<= 16;
  r1 = 16716;
  r0 |= r1;
  return r0; /* 5521740 */
}

int main()
{
  unsigned long ret1 = func1();
  unsigned long ret3 = func3();

  printf("flag : %s%d%s\n", (char *)(&ret1), ((unsigned long(*)())func2)(), (char *)(&ret3));
  return 0;
}

これをコンパイルして実行すると、出力された文字列でzipファイルを解凍することができます。

mondai5

mondai5.zipを解凍すると下記のようなテキストが得られます

mondai5.txt

575685483番目の素数と100376328168番目の素数をかけた数を求めよ

※この問題、訂正が入っており後者の方は、100026248000番目を求める必要があります。

なかなかハードなお題です。こういうのは自力で頑張ってはいけません。
oeis.orgのリストを見ても、数えられるほどしか掲載されていないのですが、LINKSのところにThe Nth Prime Page というイケてるページが見つかります。

ここの情報を頼ると、下記の素数が得られて、それを掛け合わせることでパスワードが得られます。

The 575,685,483rd prime is 12,793,176,???.
The 100,026,248,000th prime is 2,761,479,317,???. 
=> 12793176??? * 2761479317??? = 353280920043598??????

後半に続きます