七色雑記

Reverse-Engineering Hardware 1

回路図は面倒くさいので書いていませんが，Verilogのコードをここで公開しています．

https://gist.github.com/idzuna/72a107412fe0e0ff5d8c

問題ページから入手できるもの

• gpio.pyというソースコード
• ボードの写っている写真
• ボードのLEDが点滅している動画

これらからまずわかったこと

• gpio.pyでは，DAとDBから信号を出力し，X1-X6から信号を入力して，なにかやっている
• 写っているプリント基板はRaspberry Pi 2（Linuxが動く小型のコンピュータ）
• ブレッドボードに刺さっているICは74HC74（2回路入りDフリップフロップ）

ピン配置と配線の把握

とりあえず，Raspberry Pi 2のピン配置をググって印刷し，gpio.py上での変数名と，ブレッドボードのどの位置に繋がっているかを目で追いかけて，ピン配置の紙にメモしていった．この時点で，X1-X6に対応するピンが，LEDの近くに配線されていることがわかったので，動画のLEDの点滅から答えがわかるんじゃないかと期待して，LEDとX1-X6の各ポートの対応関係を，写真から目で見て確認した．詳細はverilogのコード参照．

プログラムとLEDの把握

回路のほうはなんとなくわかったので，次にgpio.pyをしっかり読んでみた．

• ピンX1-X6からの入力を，X1を最上位，X6を最下位とし，それに32を足したものを文字として出力している
• ピンDAとDBの出力は，ループの回数と，前のループで出力した文字に依存して変わる

やっぱり動画からだけでは答えを得るのは難しいかなあと思いつつ，動画をコマ送りして，LEDの点滅の様子をメモしたが，情報量が少なく無理だったので，ブレッドボード上でごちゃごちゃしている回路をきちんと追ってみることにした．

ブレッドボード上の回路の把握

ブレッドボードを見てみると，各LEDのそばに，3本足の黒い部品が1つと，ダイオードが2つ，抵抗が3つ並んでいる．3本足の部品の正体は見ただけではわからなかったが，これがNPNのバイポーラトランジスタだとすると，ダイオード2つとセットでDiode-transistor logicになってるのかなと想像しながら回路を追ってみると，どうやらそれっぽい．7つとも全部同じで，それぞれがNORゲートになっている（最初，ダイオードの極性を間違えてNANDゲートだと思っていたが，Verilog化して動かしたときに間違いに気づいた）．

そうとわかれば，あとはジャンパワイヤーを追ってゲート間の配線を把握するだけ．

Verilog化

回路はわかったが，これを頭の中でシミュレーションするのは難しそうなので，Verilogに書き起こして回路シミュレーターで動かすことにした．回路のVerilog化自体は大して時間は掛からなかったが，Pythonとかいう未知の言語で書かれた逐次処理プログラムをVerilogに移植するのにやたら手間取ってしまった．さて動かすぞ，と思ったところで手元のマシンにシミュレーターが入ってなかったことに気づき慌ててModelSimをダウンロードしようとするが，ファイルがでかすぎてなかなかダウンロードが終わらない．しかたなく，Icarus Verilogとかいうフリーソフトをダウンロードしてインストールし，ネットで使い方をググりつつ動かした．

まずは動画のLEDの点滅が再現できるかどうか試すと，うまく動いた．続いて問題のコードを動かすと出力が得られた．緊張しながらSECCONのページから送信すると，正解だった．そのころちょうどModelSimのダウンロードが終わった．

Find the prime numbers

まず，Find the prime numbersというタイトルと，pailler.quals.seccon.jp というURLから，これは昔授業で習ったPaillier暗号かなと思った．ソースコードを読むと，その通りだということがわかった．

まず最初にnが求まらないと始まらないので，h = (c * o) % (n * n)となるnを総当たりで求めた．もう少しスマートなやり方もあると思うが，動かしてみたら数秒で求まったので，これでいいやということにした．ページに表示されるc, o, hの値は一定時間ごとに変わるが，どれについても同じnが求まったので，たぶん合ってるだろうという確証が得られた．

次に，nを素因数分解してa,bを求めた．「素因数分解」でググったらこんなサイトが出てきたので使った．

素因数分解 - 高精度計算サイト

あとは，Paillier暗号の復号の仕方を調べながら平文を計算し，ページのURLの最後に，"?(その数字)"とつけると答えが現れた．

復号の過程で，mod nにおけるlの逆元を求める必要があるが，その計算もやはり「mod 逆元」ググって出てきたこのサイトを使った．

合同式の逆元 - 高精度計算サイト

（お客様の声に書いてある，暗号解読のために使った60歳以上の研究員の男性が何者なのかすごく気になる）

解き方は以上だが，あとになって見返してみると，これはスマートではなかった．まず，最初のwhileループではdという値を求めているが，実はこれがlの逆元である．わざわざ逆元の求め方を調べなくてもよかった．ちなみにこのアルゴリズムは拡張ユークリッドの互除法と呼ばれている．

そして2つの目のwhileループでは，乱数xに対して，yという値が1であることを確かめている．なぜこんなことをしているかというと，Paillier暗号の性質として，xがたまたまaまたはbの整数倍になってしまうと，暗号文から平文を復号できなくなってしまうからである．

そして，このyを求める処理が，まさにPaillier暗号の復号方法である．1を暗号化するとoが得られて，oを復号するとy=1が得られる．同様に，cに対してm = (((pow(c, l, n * n) - 1) // n) * d) % nを計算すると，平文mが求まる．つまり，Paillier暗号の復号の仕方を知らなくても，まず素因数分解でa,bを求めて，このコードをちょっと修正して実行すれば，平文が得られる．

Reverse-Engineering Hardware 2

Reverse-Engineering Hardware 1と違い，問題文に74HC161と書いてある上に，写真も鮮明で親切だった．74HC161は4bitの二進カウンターICで，クロックを叩くごとにQ3-Q0の値が1ずつ上がっていく．カウンターが15までくると，桁上げ出力のRCOが1になるので，74HC161をもう1つ用意して，RCO出力をもう一つのほうのClock Enableに入力すると，合わせて8bitカウンターとして使える．

まずは回路を目で追って，配線とソースコード上での変数名の対応を調べた．

• RasPiのp0-p7出力は，2つの74HC161のP0-P3入力へ繋がっている
• RasPiのq0-q7入力は，2つの74HC161のQ0-Q3出力へ繋がっている
• RasPiのload, clock, resetはそれぞれ74HC161の~LOAD, CLK, ~CLRへ繋がっている
• ただし，2つ目の74HC161のCLK入力は，RasPiではなく1つ目の74HC161のRCO出力に繋がっている

次に，Pythonのソースコードを読んだ．

• p0-p7, load出力はまったく使っていない
• リセットして，何回かクロックを叩いて，q0-q7入力を読んでいるだけ
• バイナリファイルを1バイトずつ読み込み，q0-q7入力をxorして1バイトずつ別のファイルに書き込んでいる
• xorしているだけなので，エンコードされたデータを元に戻すにはもう一度同じようにxorすればよい

先ほど書いたように，74HC161を2つ繋ぐと8bitカウンターになるが，このボードでは，下位4bitからの桁上げ出力RCOが上位4bitのCLKに入っているので，桁上がりが1クロック分早くなってしまっている．つまり，カウンターの値は，... , 0C, 0D, 0E, 1F, 10, 11, 12, ... というふうになる．

結局，これはクロックを叩く回数ごとにq0-q7の値が増えていくだけなので，回路の動作を再現するVerilogのコードさえ書く必要がなかった．次のURLに，問題を再現するC++のプログラムを載せた．

https://gist.github.com/idzuna/ca1977d07cfdbffdaf1c

これを実行すると，1F 8B 08 08 ...で始まるバイナリファイルができあがったが，はじめはなんのことだかさっぱりわからなかった．しばらく悩んでみて，ためしに7-zipに突っ込んでみたら，開くことができた．中のflagというファイルに回答が書いてあった．

後で調べてわかったが，1F 8B 08 08 はgzipのファイルヘッダで，このへんはCTFでは常識らしい．

感想

今回初めてSECCONに参加しました．いままで，CTFにはなんとなく興味がありましたが，サーバーをクラッキングしたりするのは私には難しいと思っていて，参加したことはありませんでした．しかし，参加してみると，時間掛ければ自分でも解けそうな問題もあり，また問題を解けないにしろ，解こうと試みる過程で，普段使わないような技術や知識が身につきました．なによりチームで問題を解くのは楽しかったです．おそらく，誘われなければ一生参加することはなかったと思います．誘ってくださり，いっしょに参加された友利奈緒の皆様，ありがとうございました．