How to use keyboard/mouse for PS4 part3 -Btstack is GOD-
How to use keyboard/mouse for PS4 part1 -Sniffing HCI-UART- - aki33524’s blog
How to use keyboard/mouse for PS4 part2 -How does Bluetooth work?- - aki33524’s blog
Part2で少し話に出したが、Btstackを使ってみると一気に進捗が出た。Bluezなんて一生使わねえぞ。
Bluez vs Btstack
Bluezは現在Linuxで採用されているBluetoothプロトコルスタックである。標準であるからには優れたものだと思っていたが実際にはそびえ立つクソだった。料理を作ろうとしたらチェーンソーを渡されてしかもたまに突然歯が逆回転したりするような感じ。
Btstackはとてもシンプルな組み込み向けのシンプルなプロトコルスタックである。組み込み向けとは言うものの、libusbをインストールすることでUNIX-basedの環境にも対応するし、daemonもあるようだ。料理を作ろうとしたら小さなナイフを幾つか渡された感じ。決して高機能ではないし、ナイフの選択には少しばかり注意が必要だが思い通りの動作が出来る。
Btstackは組み込み向けであるからして、kernelの機能を使わない。その分デバッグや細かい制御がとても簡単に行える。ドキュメントも存在しているし、例示も充実している。Keyboardエミュレータまで存在するのは驚いた。Bluezが何故クソかと言えば、これらが全て満たされないからだ。kernelに依存するのは良いが、それが謎の挙動をするのだからクソでしか無い。ドキュメントは本当に一切無いし、最も良い例示はbluetoothdのコードである。加えて難解なkernelのコードを読む必要もある。
もちろんBluezだって良いところはある。どうやらBluezは様々なデバイスをホスト側で扱うことに注力しているようだ。加えて、ユーザーがGUIで簡単に設定できるようにしており（むしろCUIはなおざりらしい）、一般ユーザーが使う分には便利。今回は用途が違った。
Btstack
BtstackはBluetoothの仕様に従い階層化したイベント駆動で動く。各階層のやり取りは独自の（仮想化した）HCI packetを使って行うようだ。パケットログが若干汚くなるがそこまで気にならないから良しとしよう。多分ログに保存しない方法もあるはず。
正しい作法なのかわからないが、実装されているコードは極めて簡素であるから自分でカスタマイズした。DS4はHuman Interface Device（HID）プロトコルでやり取りする。Btstackのhid_device.cはL2CAPのDatapacketに関して一切イベントを送出しない。しかし、DS4で接続した直後に飛んでくるGET_REPORTに答えなければ入力待ち状態にならないため、新しいイベントを送出するように書き換えた。
SDP
SDPは適切に設定すれば勝手に分割されて送信される。これはPart1で作ったsnifferで取り出したSDPデータを分割した（HIDとDIDの2つのserviceが入っており、1つずつ設定する必要があるため）。これはWikiに載っている内容と少し食い違っているからで、ProductIDから違う。新しいバージョンのコントローラーはUSBによるキー入力に対応しており、別のデバイスとして認識されるようだ。
GET_REPORT
先述したように、PS4に接続した直後に飛んでくるGET_REPORTに答えなければならない。Wikiに載っている情報はおそらく以前のバージョンのコントローラー（Aug 3 2013）で、実際にsniffするとこの箇所が2016になっていた。ちょうど発売時期と一致する。
http://www.psdevwiki.com/ps4/DS4-BT#0x06
0x06と0xa3に応答するのはいかにも大切そうだが、あまり解析されていない0x02のreportを返すのも大切だった。これを返して初めてコントローラーは応答待ちになる。これもWikiのデータとは食い違っていた。これがコントローラーそれぞれによって違うのか基板レベルなのかは謎。
http://www.psdevwiki.com/ps4/DS4-BT#0x02
Demo
ThinkpadをBluetoothでDS4として登録する。その後数秒おきに◯ボタンを押している。最後に注目して欲しいのだが接続が解除されている。これはThinkpadから解除したのではなくPS4側から解除されている。
実はPS4はライセンスされたコントローラーしか使えない仕組みが導入されている。次パートではそれについて解説する。もし新しいコントローラーで仕様変わってたら死ねる……
と思ってたけど今冷静に動画見たらこれはただ単に自分で接続切ってるだけだった……
◯を一回だけ押して後は上下を交互に押し続けるようにした。どうやらchallengeに応答しないと入力が無視されるだけで接続が切られるわけでは無いようだ。
そもそも何故動的に入力を作ってないかというと、CRCをCでパッと書くのが面倒だから（Pythonで10000メッセージくらい作って流してる）。
Bluetooth Class
Bluetoothは幾つかの消費電力の区分でクラス分けされている。どうやらX220に内蔵されているBluetoothはClass-3なのかとても弱くて接続が安定しなかった。今日Class-1（なんと理論上100mまで通信可能）を買ってきたら安定した。
DS4で使われているAR3002はSupports both Class-2 (up to +4 dBm) and Class-1 (up to +10 dBm) operationとあり比較的強い電波強度である。しかしClass-1を名乗るには100mW以上必要だと理解していたけど10mWまでに見える、どういうことだ。100mWは上限であって、Class-2以上であれば良いようだ。
DS4をペアリングする時にえらく認識されるのが速いのはClassだけが理由ではない。DS4は起動時にいろいろな初期化を行っており、その際にスキャンされやすい（その代わりに消費電力も上がる）設定をする。Bluez向けのコードではこれを実装していたがBtstack向けではまだやっていない。とは言え書かなくても問題無いらしい。Bluez向けはこれを書いた後に不安定になった気もするのであまり手を出したくないという理由もある。
追記
X220のbluetoothモジュールは表面に張ってある紙の文字を見る限りBCM92046が使われてるっぽいがこのICのデータシートはそう簡単には出てこず、探して見つけたBCM92046入りモジュールの仕様には1.09dBmとある。弱すぎ
— nasusu (@TA7368PG) 2018年2月17日
How to use keyboard/mouse for PS4 part2 -How does Bluetooth work?-
How to use keyboard/mouse for PS4 part1 -Sniffing HCI-UART- - aki33524’s blog
今回は前回に引き続き、Bluetoothの簡単な説明を行う。
Bluetoothについて調べると他の分野に比べて資料が少なくて驚くと思う。
仕様書はまだ平易な英語で書かれているし、検索もやりやすいが膨大（3000Pくらい）で筋だった理解を得るのは難しい。適当な二次資料を読みながら仕様書で確認するのが良い。
とは言え僕自身Bluetoothのことは殆ど分かっていないし、結局上手く行っていない。あまりに上手く行かないのでとりあえず記事を書くことにした。
上記から分かるように、この記事の内容は間違っているものとして扱って欲しい。加えてBluetoothを一般に書くと広範すぎるため、DS4に特化した説明になると思う（これは僕がある機能がDS4固有なのかそうでないのかすら判断がついていないからでもある）。
General
Bluetoothの初期接続は大きく分けて3つのフェイズに分かれる。Inquiry/Page, SDP, Pairing/Bondingである。
Inquiry/Page
InquiryはWifiにおけるBeaconのような機能である。PS4がスキャンをしてDS4が応答を返す。これには自身がコントローラーであることなどの情報がも含まれる。
Pageは機器同士のコネクションを張る機能。
SDP
Service Discovery Protocol（SDP）とはあるBluetoothデバイスがどのような機能をサポートしているかを通知するためのプロトコルである。pageが終わった後にPS4がrequestを送ってくるので、適切なSDPを返す必要がある。ただ、SDPの長さは本来L2CAP MTUの制限である672byte以内になるはずなのだが、DS4は700byte以上送る必要がある。これは最初LinuxのKernel moduleを直接書き換えてre-compileすることで対応していた。実際にDS4が送っているSDPをsniffしてみるとパケットを分割して送信していた（L2CAPがMTUをオーバーした時の分割をサポートする）。
http://www.psdevwiki.com/ps4/DS4-BT#DS4
Pairing/Bonding
よく「ペアリング」は「機器の登録」として捉えられるが、実際には鍵交換や認証のフェイズを意味するらしい。それらを保存することをBondingと呼ぶようだ。
よく目にするペアリングではPINコードという4桁もしくは6桁のパスワードを入力するが、DS4ではSecure Simple Pairing（SSP）という仕組みで動的にLink Keyを生成して鍵交換を行う。僕が見た仕組みでは互いに生成した乱数値をECDHで交換し、それをhash化することでLink Keyを生成するらしい。この手法では「互いの機器が自分だけで鍵を設定する事ができない」ようになっており、鍵固定化攻撃を妨げている（後述するがDS4ではここに穴がある）。
DS4-USB
ここまで読んで不思議に思った人も居るかと思う。普通にPS4で遊ぶ時にコントローラーでSSPによるペアリング処理を行うことは無いからだ。
実はDS4では二通りのペアリング手法を用意しており、SSPによるペアリングは裏技的機能である。やり方もPSボタンとShareボタンを同時に長押といういかにも裏技らしい方法となっている。
普通、初めて使うDS4は有線でPS4に接続する。この時にペアリング的な処理が行われている（Bluetoothの仕様に則っては居ないと思うが本質的にはまさしくペアリング）。
DS4を接続した際、DS4のBluetoothがPS4に登録されていない場合、PS4が自身のBluetoothのMAC（BluetoothではBD_ADDRなどと呼ぶ。Ethernetと同じで6byteであり、ベンダーコードも一致するようではあるが。）とLink Keyを送信する。
これにより鍵交換と機器の登録が行われ、次の接続からはコントローラーの電源を入れればInquiryやSDP, Pairing処理を端折って通信を行う事ができる。
http://www.psdevwiki.com/ps4/DS4-USB#Class_Requests
ここで注目すべきはPS4が鍵をそのまま送りつけて来るということである。この仕様だと簡単にman-in-the-middleで鍵をrelayすることが出来る。GIMXはこの手法を用いている。
しかし、実はUSBのman-in-the-middleには（決して高級なわけではないが）少々特殊なデバイスが必要となる。普通PCについているUSBポートはホスト側であり、デバイス側に偽装することが出来ないからだ。例えばRaspberryPiZeroなどはデバイスモードに対応している。
ところで今回の目的は特殊なデバイスを用いずにDS4をエミュレーションすることであった。GMIXの手法を使うことは出来ない。 BluetoothではUSBのように物理的なホスト/デバイスの区別がない。理論的には可能なはずだ。
Bluez
Bluezは現在Linuxで使われているそびえ立つクソBluetoothプロトコルスタックである。ややこしいBluetoothをsocket通信で扱える便利モジュールであるはずだった。
残念ながらBluezを使ってデバイスのエミュレーションをするのはとんでもなく面倒な作業である。どうやらBluezはGUIからホスト側でBluetoothデバイスを扱うことに注力しているようで、実際にsocketでガリガリいじろうとすると謎の挙動のオンパレードだった。
これは僕が悪いのかPS4が悪いのかBluezが悪いのかBluetoothデバイスが悪いのかわからない。ただ、Bluezには一切のドキュメントが存在しないし（bluetoothdのコードとkernelのコードと仕様書を読み続けるハメになる）、hcidumpで読めているl2capのconnection requestをガン無視して一生socketをacceptしてくれないしマジでクソ。
というか多分Bluezはガリガリ弄ることを想定していないらしい（だからドキュメントもないのだろう）。
例えばさっき述べたように700byteのSDPを送信しようとすると（本当は何かやり方があるはずだけど）、bluetooth.koのコードを弄ってMTUを無視して送信する必要があった（と言っても下の箇所をコメントアウトするだけ）。
hcidumpやwiresharkで見ると送れているはずのhci packetが遅れていないのか謎の挙動をするしもう何もわからん。
一応不安定なりにたまにペアリングが出来る時があり、上手く行った時の動画を載せておく。
多分ここまで200時間位かかっていて、うち150時間くらいはBluetoothとBluezと闘っていた。本当にクソ。
一応上手く行っていないコードを載せておく。誰か問題点を指摘してくれ頼む。setup処理はBluetoothの諸々の設定をしているだけでさほど重要ではないと思う。hcidumpではl2capのconnection requestが送られて来ているにも関わらず383行目のacceptが返ってこない。もう意味がわからん。
Bluezを捨ててBtstack（組み込み向けのプロトコルスタック）を使ったほうが良い気がしているのだけど、ここしばらくずっとBluetoothの学習（という名の無駄）に時間が割かれていて疲れた。
How to use keyboard/mouse for PS4 part1 -Sniffing HCI-UART-
If there is someone who wants to read this article in English, please contact me. I'm not good at English, so I don't want to write in English for anybody.
Motivation
最近研究室でPS4版オーバーウォッチをやった。PS4でFPSは初めてだったのだが、アナログパッドで全くエイムが合わない。規約上問題ない様なのでキーボードとマウスをPS4で使う術を考えた。
PS4で外部デバイスを使う試みはGIMXにより行われているが、デバイスを自作する必要がある。今回はそういったデバイスの自作無しで実現することを目的とする。
現状大凡の目処は立っているものの、細かい問題が解消されず未だ出来ていない。出来た時に記事にしようと思っていたが膨大になりそうなので幾つかのパートに分ける。おそらく4,5パート程度になると思われる。
Sniffing HCI-UART
PS4コントローラー（以下DS4）とPS4本体はBluetooth2.1+EDRで通信をしている。Wifiとは異なり、Bluetoothのプロミスキャスキャプチャはとても困難なようだ。これはどうやらBluetoothのスペクトラム拡散方式である周波数ホッピングによるものらしい。
加えて、PS4ではSecure Simple Pairingというプロトコルにより動的に鍵（以下Link Key）を生成しており、これを外部から盗聴することは出来ない。
DS4とPS4の内部に格納されたLink Keyを取り出すことは困難らしい（読み出しされにくい領域に置く）。実はPS4-DS4間のLink Keyを読み出す方法はあるのだが、これに外部デバイスを必要とする（どこかのパートで書く）。
果たしてBluetoothの盗聴は不可能に思われるが、実は物理的なHackでなんとかなる。BluetoothのチップにUARTで通信しているところを直接抜き取れば良い。
この記事に沿って行った。
まず、ボタンの壊れたDS4を購入（2000円程度で買えた）して分解する。
先の記事の写真と見比べると分かるが基板が違う。DS4は新旧2種があり、どうやらそれによって基板も変わったらしい。@TA7368PG氏によれば3種以上基板があるようだ。
真面目にデータシートと基板を読む。DS4に搭載されているBluetoothチップはAtheros AR3002でこれは10, 11番ピンにTx, Rxが配置されている。
基板を眺めるとおそらくデバッグ用のパッドに伸びている。ここに線をはんだ付けする。
Rx, Tx, GNDを取ってきてブレッドボードに配置する。シリアル通信モジュールは記事に倣いFT232を搭載したものを用いる。ボーレートが3Mbps以上であればなんでも良い。
その後、これをコンパイルして終わり。
ただ、このプログラムはTx, Rx用に2つモジュールがなければ動かない。そこでPORT2をコメントアウトしてfd2に-1をセットすると上手く動く。
小話
ハードウェアに関して全く詳しく無いので@TA7368PG氏と@ka1l氏にTwitterで聞きまくった。ありがとうございました。と言うか最近人々にTwitterで質問しまくってる。
どう考えてもこれを最初にやるべきなのだけど、しばらくsniffer無しで頑張っていた。しかしどうも煮詰まったので止むを得なくPS4ごと買った（これまでPS4を持っていなくて研究室においてあるもので実験していた。流石に人のコントローラーを分解するわけにはいかない）。
基板が違った時はマジで詰んだと思った。
メルカリで落としたコントローラーを分解したら犬の毛が入ってて笑った。
本当は音声端子を剥がしてそこからケーブルを出したかったのだが、はんだ剥がしがつらすぎて諦めた。
Tx, Rx用にモジュールが2つ必要で秋月で注文した。その後5年前に買ったきり一切触っていない回路箱を覗いたら何故かFT232が載ったモジュールがあったのでとりあえず実験した。
画像に情報を埋め込む -SteganographyとWatermarking-
大学でSteganography and Watermarkingについての講義があった。
SteganographyといえばCTFでたまに出題されるが、Gussingクソ問が多くあまり良いイメージを持っていなかった。実際には色々と考えられているようで面白い分野だった。試しに両方の簡単な実装を行った。
SteganographyとWatermarking
この2つは目的が異なっている。Steganographyは「データを隠す」ことが目的であり、Watermarkingは「データに埋め込んだ情報が指定の変換に対して頑健であったり、除去することが難しい」ことを目的としている（多分）。
Watermarking
Watermarkingの目的としては著作者人格権保護などが挙げられる。たまにTwitterで他人が描いた絵を自分が描いたと言い張る人間がいるが、そういう時にどうすれば描いた本人の保証できるかを考えていた。
これはkeyに依存して画像サイズの乱数列Wrを生成し、目的のbitが0であればWr, 1であれば-Wrを画像に足し込むという手法が有名らしい。足しこんだ後の画像とWrの内積を取ることで1bitの情報を得ることが出来る。
実際には内積を取るのではなく平均値を引いた後に内積を取ってベクトルの長さで正規化することで、元の画像の性質に依らずに棄却領域を割り出す事ができる（この理論で射影空間とかがちょっと出てきて面白い）。
これを拡張して1枚の画像にn-bitの情報を埋め込めるようにする。これは画像をn個に分割してそれぞれに1bit情報を埋め込むことにした。ここでどのように分割したかが分からないようにkeyに依存して生成した乱数列によってシャッフルする。
ユーザーはkeyがわからない時に画像の情報を大きく損なわずにWrを除去するのが難しいと思われる（フィルタ掛けたりされると厳しい。白色ガウスノイズの乗せたり輝度変化したりには強いことが知られている。）
しかし、これではユーザーがWatermarkingの検証を行うことが出来ない。除去の困難性を保証するのはWrがどこに埋め込まれているかを知らないからである。
何とかして万人が検証可能で除去が困難なWatermarkingを作れないか考えたがTrusted Third Partyが存在しない限りは無理そうだった。これなら簡単で、画像とkeyとメッセージをTTPに渡して埋め込んでもらうと良い。ここでどこに埋め込まれているかは画像の作成者すら知らない。乱数はkeyとTTPのみが知る情報によって生成される。keyとTTP保有のデータで新しいkeyを作るイメージ。その後に画像とkeyを公開すれば万人がTTPに対してリクエストすることで検証を行う事ができ、またどこに埋め込まれているか分からないので除去も困難である。
Steganography
Steganographyの目的としては情報を持っている事自体の秘匿が挙げられる。つまり、画像中にデータが存在していることすらバレてはいけない。
こちらはいろんな操作に対して頑健である必要はないので一般にはWatermarkingより画像に埋め込むことができるデータ量が増える。僕の実装では800x500程度の画像中にWatermarkingでは数十byteしか埋め込めなかった一方、Steganographyでは数十Kbyte埋め込むことが出来た。なんと1000倍！（Steganographyならある画像のpngにその画像のjpegを埋め込むことくらいなら出来る）。
こちらもWatermarkingと同様にkeyに依存した乱数列を作ってやり、あとはテキトーにランダムに選んだ画素の下位1bitに埋め込むだけで良い。強いて言えば埋め込むメッセージにProbabilistic Encryptionを施すとIND-CCA安全やらが保たれて良さそう。
あまりに大量のデータを埋め込むと下位bitが一様乱数に近くなるので、DCTでスペクトルを出した時に高周波成分が多く出てそれによって埋め込んでいることがバレるかもしれない。真っ白な画像に埋め込むと即バレる。自然風景画像やらに埋め込むと強そう。
Codefestival 2017 Finals Eに対する雑な考察
この問題の線形代数による考察を記しておきます。線形代数が何もわからない。
まずbjxzjaを26を法とするベクトルとして考えます。
これをあるベクトル群の一次結合によって表現出来るかを考えます。
ここで、回文の基底を考えると以下のようになります。
各操作も同様にベクトルで表すと次のようになります。
回文の基底と操作ベクトルを合わせたベクトル群の一次結合によりが表現することが出来たなら答えはYESになります。
式で書くと次のようになります。
さて、は密なので拡大行列を簡約化するコストは大きいように見えます。しかし、先に差分行列（累積行列も差分行列も正則なのは簡単に確かめられます）を掛けてやることでこれらは疎になります。
疎行列に対する簡約化のコストは小さいので十分間に合います。は体でないので諸所が面倒に見えますが解けます（ほんまか）（多分、列ベクトルに注目すると1, -1をちょうど同じ数だけ含むので逆元を持たないことが問題にならないと思う）（ユニモジュラ行列っぽい何かに思うからなんか性質良くなれ良くなれ）。
想定解のUnionFindを使う方法は、連結した頂点数 = rank(それを結んだ辺（ベクトル）で構成される行列)となるということに注目するのだと思います（この辺がよくわからない）。これはつまり連結している頂点のコストの合計が変わらないなら自由に再分配出来ることを意味します。
SMT Solver無しでXorshift128+を解く
先週のCBCTFではXorshift128+の32個の出力列が与えられた場合にその先を予測させる問題が出題された（Random RSA）。
想定解はSMT Solverを使うのだが、宗教上の理由で使えない人が居るかもしれないため別の解法を考えた。
なお、先に言っておくとこの解法は多大なリソースを必要とし、具体的にはメモリを200GBほど使用する。研究室の500万円の計算機で64Thread立てて計算しても30分ほど掛かった。要するにz3を使え、その辺のパソコンで10秒で解ける。
Xorshift128+とは
while True: s1 = s[0] s0 = s[1] s[0] = s0 s1 ^= (s1 << 23) & ((1<<64) - 1) s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5) yield (s[1] + s0) & ((1<<64) - 1)
Xorshiftとは主にxor, bitshiftで構成された軽量な乱数生成器である。Xorshift系の乱数生成器には様々なバリエーションが有り、その中の1つであるXorshift128+はadditionを加えることで線形性を除いている（後述）。なお、128とは状態数が128bitなことに起因すると思われる（もしかしたら周期かも？）。
Xorshift128+の難しさ
もしこの出題が普通のXorshift128であったなら簡単に解くことが出来る。
何故なら、Xorshift128に使われる処理はxorと固定長bitshiftだけであり、これらは共に状態bitをGF(2)上のベクトルと見なせば線形性を持つ。つまり、全ての演算が行列で書き表せる為に逆行列を作ることで簡単に初期状態を復元できる。
しかし、Xorshift128+の出力列は最後に加算される。この処理は線形性を持たない。この簡単な処理を付け加えるだけで問題は飛躍的に難しくなる。
Xorshift128+の線形性
しかし、Xorshift128+であっても線形性を持つ箇所がある。LSB（最下位bit）である。
LSBは下の桁が無いため、繰り上がりを気にしなくても良い。その為32個の出力列から32個の線形方程式を得ることが出来る。もう少し考察すると、注目するbitより下位が全て1である場合も繰り上がりを気にしなくてもよく、N個の出力列からおよそN/2個の方程式を得ることが出来る。
Random RSAでは新たに28個の線形方程式を得て、60個の方程式が集った。
行列に対するMITM
60個の方程式を集めたということは、128bit中60bitがleakしたと考えることが出来る。しかしまだ68bitの総当りが残る。
これを何とかしてMITMで計算量を落とせないか考えた。ここからの説明はかなり雑なので分かる人しか分からないと思う（真面目に行列の式書くのがめんどい……）。
ここから内部状態を64bitずつのx, yと表すことにする。
今60個しか式が集まっていないが、適当に4bit固定することにより64個の線形独立な式を得る。この行列を変形し、[E | M]のように左半分を単位行列とする行列を得る。これにより、xとyの関係を線形方程式で記述出来る（x + My = 64次ベクトル）。
ここで1つ目の出力列により、yを定めればxが定まる。また、先述の線形方程式からもyを定めればxが定まり、これらが一致すれば解となる。
ここでyを上位32bitと下位32bitに分割する（y1, y2）。そうすると先の線形方程式はx + M1y1 + M2y2 = 64次ベクトル という様な式に変形できる（y1, y2を定めるとxはそれぞれ繰り上がりの有無を無視すれば一意に定まることに注意）。以上から、M1'y1 + M2'y2 = 64次ベクトル という式を得る。
これは、M1'y1 - 64次ベクトル とM2'y2をそれぞれ独立に計算し、一致する場合を探せば良い。
これを実装すると64個の解が出てきた。これは最初に足りない4bitを定めた分と無視した繰り上がりの2bitで6bitの自由度を持った為だと考えられる。あとは全て試すと正しい解を得た。
enumulating all y1 merging vectors miv1: 8589934592 enumulating all y2 merging vectors miv2: 4294967296 serching 2476520362 61509141 2157264084 3353016742 656009753 1860619162 2574392452 2567461328 3446121306 463614785 3288533184 2667169677 3065249141 186478286 769889559 1500841788 540840065 3086893980 1799405833 2135579198 954749789 548963819 3960811688 2581296186 3103250995 4048812002 2904438575 287535986 1008273453 742342059 1609709208 525912563 102537622 2128507249 2446164013 1093192679 2075536625 1789293171 1195834711 2725839867 295618493 3554538105 2373988069 3548126869 1347207931 483994859 1071373495 101210017 193547184 2191692163 1021151311 519290032 1916084563 544594116 2047105320 318595631 66506444 2834209036 1251206337 3094191279 4186820173 2782881948 2114031298 3190589275 508037032 453555974 745063296 2750048806 2923802844 1177402636 2832440853 273566763 1518323354 358834199 1122617837 2403936068 1091218555 4018685749 4136247442 294350163 2928405395 1799492342 2197082799 759383716 4077570164 1016706399 3093126019 3118276782 2943083703 1649561999 3404147677 124557829 716115770 275919643 2901710221 4203208796 657711912 331906217 2690332004 2083220237 433830677 896965898 1296534180 1664930400 1977485902 3742108858 3115534102 689202550 1477097847 3976949959 378126705 2382484743 2943110840 288054401 3860062577 4057827336 1338808793 100592408 133487806 3607172407 2616266322 477564116 3764152924 916057340 1307750470 153169944 1629761026 657825298 829409657 396404147 3151417975 3300223157 2494409012 3774521208 3045576677 1401251776 1775617714 3515828845
y1, y2 = 508037032, 453555974が答え。
実装
64Threadで実行して30分くらいだった。
GF(2)上であれば行列積がandとbitcountになることを使って高速化したりしたがまだまだ重い。ソート列のマージをシングルスレッドで行っているのがボトルネックで、頑張れば10分を切るくらいにはなると思う。メモリも工夫すれば60GB程度には減らせそう。最初はy2の列だけ生成して各y1で二分探索していたのだけど期待よりかなり重くなった。研究室マシンが1.5TBのメモリを持っていたので雑に両方持ってやったほうが速いようだ。
あと普段競プロで並列化やメモリキャッシュやらに気を配ることが殆ど無いのでこのあたりのノウハウが皆無なことに気がついた。悲しい。
CBCTF Writeups
miyaji-labで参加した。これは暗号系研究室に所属している以上Cryptoを全完するという強い決意を表している（大嘘）。
結果としてはRandom RSAを時間中に解くことが出来なかった。悲しい。
Common Modulus 1
Common Modulus Attackをする。
Common Modulus 2
Common Modulus Attack 1と異なりeが3を最大公約数として持つので、m3 mod nが求まる。
mが十分に小さいのでm3 % n = m3となり、二分探索により3乗根を解けば良い。
Common Modulus 3
平文mの後ろに0をpaddingするということが左にbitshiftする(_m * = m * 2x)ということに気がつけば簡単。
これまでと同様にm17 mod nを得るが、m17 = (m * 2x)17 = m17 * 217*xとなる。
xはこれまでのフラグから適当に定めて217*xの逆元を掛けてやるとm17 mod nを得る。
Common Modulus Attack 2と同様の考察から17乗根を求めると良い。
Pailler Oracle
Pailler暗号に対する選択暗号文攻撃をする。得られる情報は復号した結果のLSBである。
Pailler暗号は加法準同型を満たす珍しい暗号である。
また、Pailler暗号は加法準同型だけで無く、mに対する暗号文cが得られている時、任意のrを選択しm*rの暗号文c'rを作成することが出来る。
これら2つの性質は今回の問題において平文に対する加減乗除が行えることを示唆する。
よってm-1とm/2の演算を行うことにより、mを右shiftした平文に対する暗号文を作成することが出来る。
つまり、LSBが0のときはm/2をし、1のときは(m-1)/2をする。これを繰り返すことで全てのbitをleakすることが出来る。
余談
準同型性でLSBの情報がleakすると言えばRSAのBleichenbacher Attackの亜種が有名である。実はこの知識があったせいで変に勘ぐりすぎて時間が掛かった。
詳細は割愛するが、nが常に奇数なことによりLSBからmの範囲を限定する（上位1bitをleakする）。これを繰り返して二分探索のようにすることでmの全体を得る。
同じような攻撃が成り立つのだろうとしばらく複雑に考えてしまったが、Pailler暗号は加法準同型を満たすことを冷静に考えたら解けた。
ちなみに僕はまだPailler暗号が何故成立するのかを理解しておらず、式を眺めれば解けた。この理解の放棄は上手く行ったと思う。
あと、netcatで上手く整数を取得する方法が分からなくてかなり汚いコードになった。良いやり方を知ってる人は教えてください。
Smoke on the water
eが大きいと言えばWiener's attackというのが相場である。これはeが大きいことが本質ではなく、その時にdが小さくなり得るのが問題である（実際にはほとんどのdが小さくならないので余り気にしなくて良いのではないかと考えている。この点について詳しい人が居れば教えてください）。
実際、式中でd_が小さいことが保証されているのでWiener's attackを使うのがほぼ確定する。
まずコード中の式を変形するとd = (p-1) * (q-1) - dよりe * d = e * ((p-1) * (q-1) - d) = -e * d_ = 1 mod phi(n)である。
普通のWiener's attackはe * d = 1 mod phi(n)においてdが十分小さい時にn, eよりdが求まるというものである。
よって既存の手法のe * d - 1とある箇所をe * d + 1（ここにおけるdはd_なことに注意）と書き直せば良い。
これによって求まる d_を用いてcd_ = m-1 mod nを求め逆元を取ると良い。
余談
Wiener's attackは名前と成立条件だけ知っていて、詳細を知らなかった。そこで既存のコードを変形することを軸に考えたのが上手く行った。問題を開いてから10分も掛からなかったと思う。
Random RSA
この問題は2つのフェイズに分かれる。乱数列を予測するフェイズとそれを元にmを復元するフェイズである。
乱数列予測で沼にハマったが、これはxorshift+と呼ばれるものでz3というSMT solverを用いれば簡単に解けるようだ。
http://inaz2.hatenablog.com/entry/2016/03/07/194034
そこからmを予測するフェイズであるが、これは実は2つの平文があれば解くことが出来る。
ある2つの暗号文c1 = (m + b1)e, c2 = (m + b2)eとb1, b2と公開鍵が得られている時、mを求めることが出来る（Franklin-Reiter related-message attack）。
これは(x + b1)e - c1 = (x + b2)e - c2 = 0において、2つの多項式が共通の多項式(x - m)を持つことを利用して多項式におけるgcdを解く。
ということを普段多変数多項式の研究をしている研究室の友人に言ってみたところMangaで解いてくれた。
余談
実はSMT solverを使わなくても32個の出力列を使えば解けるのではないかと思う。ただかなり実装が面倒な上、もしかしたらSMT solverの再開発かも知れない（SMT solverの中身を知らない）。
Franklin-Reiter related-message attackのことを何も理解していないので理解したい。
所感
久々のCTFの割に解けたほうだと思うが、勉強不足を痛感した。それに加えて下手に知識を得ていたせいで調べることを放棄して無駄に考えてしまう時間が長かった。この辺りはCTF慣れだろうか。
