| Tweet |  |
2017年3月1日に公開された、毎年恒例（というか採用試験なので当たり前なのですが）のエクストリームCTF。（ココをクリックするとそのページに飛びます・・・と言いたいところですが、もうなくなっていますね。）mondai1は流石に簡単（これが分からないとさすがにダメでしょ）なので省略しますが、それを解いて入手した問題データ。この問題データの中身（ヒント）が以下のような内容でした。
漏洩したマイナンバーの文字列をつなげてsha1でハッシュせよ
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: ğǬǧľĵúŕȱÿȫȱũ
これ、社長のTwitterや他の回答者や有識者によると、これは近年話題になった「セキュリティフォント」というものだそうです。あの樋渡啓祐といえば思い出す人が居るでしょう。そうです、武雄市の図書館問題（ツタヤ図書館）を初めとした数々の事件を引き起こした市長です（現在は元市長。）この樋渡（あえて呼び捨て）が生み出したとされる、マイナンバーを（コピペから）守る技術、らしいです。しかし、いわゆる換字式暗号と専用のフォントデータを組み合わせたもののようで、単にグリフを入れ替えただけの模様。このため、フォントが入手されると一発でばれる（このため定期的に更新が必要）という大きな欠点を持ち合わせており、またそもそも換字式暗号であるため、速攻で解析できると、有識者やセキュリティ関係者が大きく話題にしておりました。（さらに言うなら、この技術は海外企業のパクリらしいのです・・・）
このあたり、このページで詳細にまとめられております。ご興味のある方は是非ご覧下さい。
https://piyo-ko.github.io/misc/security_font_ww.html
閑話休題。（長いよ！）
さて、このmondai2を解いていきます。（一応、採用試験に影響がない10月以降であれば公開しても良さそうなやりとりが見られたので、この時期に公開です。まあ結局公開終了まで待っていたので今になってしまいましたが）
まずデータを見ますと、どうも10種類以上の文字が使われています。それもそのはず、セキュリティフォントは一対一対応の換字式暗号ではなく、一対多対応の換字式暗号なのです。（例えば、0→A or F or T、1→C or K or Xのように変換する。）
ゆえに、一対一対応の解法では解けません。まあ一対一だったらマイナンバーは数字10文字しか無いので精々計算量10!*α程度で済んでしまうので、今のPCなら一瞬で解けます。
まずは、このテキストデータを扱いやすい形に変えるため、まずはアルファベットに置換します。しかし、Windowsのメモ帳だと、「ũ」「Ũ」の2文字を同一として扱っているようで、置換すると同一の文字に変化しました。これではまずいので、Excelで読み込ませました。読み込み後一文字ずつ分解した結果がこちらになります。
| number: | ǧǍǡȱǬǡǡŕðǡŕĵ | ǧ | Ǎ | ǡ | ȱ | Ǭ | ǡ | ǡ | ŕ | ð | ǡ | ŕ | ĵ |
| number: | ưśǡľľŕȫǬśȫȶȱ | ư | ś | ǡ | ľ | ľ | ŕ | ȫ | Ǭ | ś | ȫ | ȶ | ȱ |
| number: | ƿǧĵǡƿȫŕŕŨğũƿ | ƿ | ǧ | ĵ | ǡ | ƿ | ȫ | ŕ | ŕ | Ũ | ğ | ũ | ƿ |
| number: | ũľľŨũĵȫŨśưÿś | ũ | ľ | ľ | Ũ | ũ | ĵ | ȫ | Ũ | ś | ư | ÿ | ś |
| number: | ğƿÿŕǬśǬȫǍȶÿǬ | ğ | ƿ | ÿ | ŕ | Ǭ | ś | Ǭ | ȫ | Ǎ | ȶ | ÿ | Ǭ |
| number: | ğǬȫǬǬǬƿƿśũȶś | ğ | Ǭ | ȫ | Ǭ | Ǭ | Ǭ | ƿ | ƿ | ś | ũ | ȶ | ś |
| number: | ǧśǍȱǍľĵğưǡśƿ | ǧ | ś | Ǎ | ȱ | Ǎ | ľ | ĵ | ğ | ư | ǡ | ś | ƿ |
| number: | ȱŨğŨȱúȱŕȫǡǡƿ | ȱ | Ũ | ğ | Ũ | ȱ | ú | ȱ | ŕ | ȫ | ǡ | ǡ | ƿ |
| number: | ŨŕũȶȱưľȱũǧŨȫ | Ũ | ŕ | ũ | ȶ | ȱ | ư | ľ | ȱ | ũ | ǧ | Ũ | ȫ |
| number: | ưŨĵśǧǬȫȶũľŨƿ | ư | Ũ | ĵ | ś | ǧ | Ǭ | ȫ | ȶ | ũ | ľ | Ũ | ƿ |
| number: | úľǬľȫðȱľŨðǡğ | ú | ľ | Ǭ | ľ | ȫ | ð | ȱ | ľ | Ũ | ð | ǡ | ğ |
| number: | ğȫśÿŨśśũưğśğ | ğ | ȫ | ś | ÿ | Ũ | ś | ś | ũ | ư | ğ | ś | ğ |
| number: | ƿȶȶŨǍğÿǧǬľľũ | ƿ | ȶ | ȶ | Ũ | Ǎ | ğ | ÿ | ǧ | Ǭ | ľ | ľ | ũ |
| number: | ğǡŕğŨŕũðȶǍǬğ | ğ | ǡ | ŕ | ğ | Ũ | ŕ | ũ | ð | ȶ | Ǎ | Ǭ | ğ |
| number: | Ǭȱśÿũŕǧÿŕƿúǡ | Ǭ | ȱ | ś | ÿ | ũ | ŕ | ǧ | ÿ | ŕ | ƿ | ú | ǡ |
| number: | ǧĵĵśȱȶȶÿŕũȱǧ | ǧ | ĵ | ĵ | ś | ȱ | ȶ | ȶ | ÿ | ŕ | ũ | ȱ | ǧ |
| number: | ľðǬǍúưðğȶưȶȶ | ľ | ð | Ǭ | Ǎ | ú | ư | ð | ğ | ȶ | ư | ȶ | ȶ |
| number: | ưúǧðȱŨǡȫŨǬĵŨ | ư | ú | ǧ | ð | ȱ | Ũ | ǡ | ȫ | Ũ | Ǭ | ĵ | Ũ |
| number: | ǬǬśȫśĵǍǧðƿȫȫ | Ǭ | Ǭ | ś | ȫ | ś | ĵ | Ǎ | ǧ | ð | ƿ | ȫ | ȫ |
| number: | ğǬǧľĵúŕȱÿȫȱũ | ğ | Ǭ | ǧ | ľ | ĵ | ú | ŕ | ȱ | ÿ | ȫ | ȱ | ũ |
これらの文字コードを取得して重複除去を行い、ユニーク値と適当なアルファベットとを一対一に対応させて変換しました。なお、文字コード取得関数は「code()」ではなく「unicode()」を使用します。Code関数だと、0x3Fまたは0xFFの値になるため使えません。
そしてアルファベットに置換したのがこちらです。A-Sまでの19文字が使われています。
| 1 | A | K | P | F | I | P | P | M | R | P | M | Q |
| 2 | B | L | P | J | J | M | N | I | L | N | O | F |
| 3 | C | A | Q | P | C | N | M | M | G | E | D | C |
| 4 | D | J | J | G | D | Q | N | G | L | B | S | L |
| 5 | E | C | S | M | I | L | I | N | K | O | S | I |
| 6 | E | I | N | I | I | I | C | C | L | D | O | L |
| 7 | A | L | K | F | K | J | Q | E | B | P | L | C |
| 8 | F | G | E | G | F | H | F | M | N | P | P | C |
| 9 | G | M | D | O | F | B | J | F | D | A | G | N |
| 10 | B | G | Q | L | A | I | N | O | D | J | G | C |
| 11 | H | J | I | J | N | R | F | J | G | R | P | E |
| 12 | E | N | L | S | G | L | L | D | B | E | L | E |
| 13 | C | O | O | G | K | E | S | A | I | J | J | D |
| 14 | E | P | M | E | G | M | D | R | O | K | I | E |
| 15 | I | F | L | S | D | M | A | S | M | C | H | P |
| 16 | A | Q | Q | L | F | O | O | S | M | D | F | A |
| 17 | J | R | I | K | H | B | R | E | O | B | O | O |
| 18 | B | H | A | R | F | G | P | N | G | I | Q | G |
| 19 | I | I | L | N | L | Q | K | A | R | C | N | N |
| 20 | E | I | A | J | Q | H | M | F | S | N | F | D |
さて、これをどう解くか。セキュリティフォントデータの入手は不可能に近い（セキュリティフォントの入手先が軒並み遁走または雲隠れまたは隠蔽している）ため、総当たり(Brute force)で解く方法を用います。とはいっても、計算量は1019*α、これを総当たりでzipのパスワード解析に使用していては終わりが見えません。
ここで、マイナンバーの性質を確認します。マイナンバーの仕様は「行政手続における特定の個人を識別するための番号の利用等に関する法律施行令」の第八条、「行政手続における特定の個人を識別するための番号の利用等に関する法律の規定による通知カード及び個人番号カード並びに情報提供ネットワークシステムによる特定個人情報の提供等に関する省令」の第五条に定められています。これらの情報から、以下の条件を仮定します。
・ マイナンバーは他のマイナンバーと重複しない（＝20個全て違うマイナンバーである）
・ 12桁目はチェックデジット（検査用数字）である。
この条件でC言語にてプログラムを組みました(Visual studio 2015使用、最適化は最大(/Ox))。 グローバル変数や冗長な部分やマジックナンバーが入っているのでアレですが。あとマルチスレッド化していないので、CPUコア1個だけ使用率100%になります。
さて、このプログラム、見た目問題は無さそうなのですが、実際に走らせるといつまで経っても終わりません。（2時間で止めた。）それもそのはず、愚直に19文字*（0～9）のループなので、計算量が莫大です。
なので、まずは20種のマイナンバーのうち、文字数が合計9種～10種類程度になる特定の2種類のみ抜き出して解答候補を計算させることにしました。これならば計算量は大きく減らせますが、解答候補を書き出すためのディスクスペースが必要になります。今回のプログラムだと、最大で26*10^11byte=2.6TB必要です・・・が、実際には最大でも26GB程度で収まりました。（このほかにワークスペースとして同量必要。）
まず、マイナンバー計算候補の洗い出しに使用した表がこちら。
myn_search_sheet.zip
マイナンバー計算候補それぞれで重複文字削除を行い、その結果を見ながら候補を選択しました。
最初の算出に使用したVS2015用のソースコードとヘッダファイルがこちらです。コメントは可能な限り入れました。
myn_search.zip
2種類用の解答候補を絞り出したら、それ以外のマイナンバーに対して同じように計算させます。このとき追加で選択するのは一回につき1～2種程度、また未検索の文字数が0～3程度の増加にとどまるようになるように選択しました。（この候補選択もExcelで色づけしながらにらめっこ（さすがに条件付き書式使いましたが）。ここの自動化もできそうですが・・・時間がもったいなかった。）
そして、ファイル読み込みと書き込みを含めた、2回目以降に使用したプログラムがこちらです。
myn_search_tuiji.zip
基本部分は1回目と同じですが、ファイル読み込み処理に関連した部分が追加されています。具体的には、読み込んだ候補データで一部の文字の値を固定化しています。なお本プログラムの読み出しファイル名、書き込みファイル名が決め打ちになっています。
このプログラムで、順次解答候補の絞り出しをしていきました。（ヘッダーファイルに記載したマイナンバーのコメントを順次解除しています。並び順はその名残。）残りのマイナンバーが5種になったところで候補数がかなり限られてきたので一気に実行しました。
最終的には、解答候補データのファイルサイズが26byte。つまり候補が1個になったことを示しました。この候補をExcelに書き戻し、マイナンバー20種の解答を割出してそれをzipパスワードとして指定したところ、mondai3を解凍することが出来ました。
ちなみに、mondai3は私が解けていませんorz。だれかmondai3以降を解答出来ることを期待します。
さて、mondai2が難しいと叫ばれていた数が多かったのか、社長がTwitterでヒントを出していました。（19種の文字のうち11種の答え）これを使用して同じプログラムで計算させたところ、約1分で解答の算出に至りました。
以下参考ツイート
814895727129 => ğǬǧľĵúŕȱÿȫȱũ
-- lumin 求人活動中(python,仮想通貨,swift) (@lumin) 2017年3月2日
これで計算力が1/100 以下になるはず。
なお、全ての問題を解析・解答した方がいらっしゃいましたので、敬意を表し、下記にリンクを記載しておきます。
某CTF(2018年3月卒向け)のWriteUp 前半 https://qiita.com/todaemon/items/7dae7fcbd9832fcf259b #Qiita（todaemon氏）
- Newer: Windows PowerShellのスクリプトだけで画像のサムネイル生成をした話
- Older: まさかの三週連続初期不良：Try UQ mobile SIMカード（nanoSIM）【1週間ぶり32度目】
Comments:0
Trackbacks:0
- TrackBack URL for this entry
- https://pc-diary.com/movt_direc_post/mt-tb.cgi/1669
- Listed below are links to weblogs that reference
- NetAgent エクストリームCTF2018 mondai2を（ヒント無しで）解いたその方法。 from PC破壊日記的ブログ
