How to use keyboard/mouse for PS4 part4 -challenge response-

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

How to use keyboard/mouse for PS4 part3 -Btstack is GOD- - aki33524’s blog

DS4は非正規製品の流通を防ぐため、認証の機構を備えている。このパートではそれがどのような仕組みなのかを解説する。完全に理解したと思っているのに認証が通ってくれない。USB snifferが欲しい……

General

DS4の認証はChallenge-Responseベースである。1分に1回程度の割合でランダムなデータが送られて来て、それに対する適切なデータを送り返さなければPS4はそのコントローラーからの入力を無視するようになっている。

しかし解析Wikiでは「どうやらChallenge-Responseらしい」程度の情報しか載っておらず、実際に何が行われているのかはわからなかった。何故仕組みが分かっていないのに現在(デバイスを用いるとはいえ)コンバータが存在するかと言えば、「どうやらこのChallenge-ResponseはRelayしてパスすることが出来る」ということが分かっているからだった。

http://www.psdevwiki.com/ps4/DS4-BT#0xF0

http://www.psdevwiki.com/ps4/DS4-BT#0xF1

What are these data?

確かに、ファームウェアも読めないような認証の仕組みを明らかにするのは不可能に思える。しかし、暗号についての幾つかの知見があれば自然な類推で仕組みを明らかにすることが出来る。ここでは僕がどのようにして仕組みを知ったかを順に書いていく。冗長かも知れないが僕の実験の楽しさ(と苦しさ)の片鱗を味わってもらいたい。

さて、最初の取っ掛かりはWikiにあるPacket 0x0d is padded with zeros, except bytes 58 and 60 (both are 0x01).だった。こういう風に書かれると何のことだか分からないが、58-60byteが0x010001になっていると言われると暗号徒であれば察するところがあると思う。そう、0x010001とはRSAのeとして広く用いられている数である。

Challenge-ResponseでRSAが関係すると言われればまず間違い無く署名である。Challengeデータをコントローラーの内部にある秘密鍵で署名してResponseとして返す。これなら筋が通る。

eがResponseの中に入っているからにはもう1つの秘密鍵であるnも入っているはずである。実際にデータを見ると幾つかの連続したデータ列と0-paddingがある。具体的には16byteのデータ列1つ、256byteのデータ列3つ、そしてeがResponseに含まれるデータだった。

長さから考えて256byteのデータのどれかがnである。今度はこれを特定しよう。

まず、何回かのChallenge-Responseを眺めると2つの256byteの列は固定だった。ランダムなデータは間違い無くResponseデータであるし、公開鍵は変化することが無いのでこの内の1つがnである。残る列が何かと言えばこれはnを署名した列だと推測できる(そうでなければ公開鍵ごと偽造すれば簡単に破ることが出来る)。

どちらがnだろうか。これを確かめるのは簡単で、素因数分解をしてみれば良い。nは非常に大きな素数p, qの積からなるため小さい素因数を持たない。実際、片方の列は10000までの素因数を持たないにも関わらず、Miller-Rabin素数判定によって合成数であることが分かった。極めてn的な数である。

n, e, Challengeを手に入れたが、ここからどうやってChallengeを署名しているか特定する必要があった。これは幸いにも一般に署名に使われるPKCS1 PSSだった。Challengeをsha256でハッシュ化した後適切なパディングを施してd乗 mod nをする。

実際に得られたn, e, Challenge, Responseを使ってPKCS1 PSSでverifyすると通った。めでたい。

ところでn, e, nの署名(と思われるデータ)はペアリングをやり直しても不変だった。これはnの署名がLink KeyなどのPS4-DS4間で共有されるデータに依存しないことを意味する。

この考察から、Replayしても認証は上手く動くのである(と思っていた)。

Challenge-Response over USB

しかしここからが大変だった。

普通、先述の認証はBluetooth通信で行われる。そこでBluetooth通信をMITMすることで認証をReplayしようと思っていた。 しかし実際に書くと分かるがBtstackを使って複数のコネクションを管理するのは極めて大変な作業である。加えて1つのBluetoothドングルではPS4とChallenge-Response Oracle用DS4と同時に繋ぐとパケットロスが生じる。ドングルを2つ用意するのも手だが、他の方法を考えた。

実は新しい基板のDS4はUSBでの通信に対応している。そしてその設定をするページには「USBケーブルを使って通信する場合マイクが使えなくなります」とと言った文言がある。これは実はとても示唆に富んでいる。何故なら、DS4において「音声信号は必ずBluetooth上でやり取りされる」からだ。これは@ka1l氏に基板の写真を見てもらった時に指摘されていて、つまりは物理的に不可能なようだ。

僕はこの時までずっとUSBで操作の入力だけやり取りして他の音声や認証情報はBluetoothを使うと信じていた。しかし、音声情報が使えないということは一切Bluetoothを使わない可能性が高いと考えられる。つまり、Challenge-ResponseをUSBで行うことが出来る可能性が高いと考えた。

実際、USBで通信する設定を有効にしたコントローラーのBluetooth通信のログを見ると一切パケットが流れていなかった。

幸いにもGET_REPORT/SET_REPORTはUSBのHIDにもある概念で(と言うよりBluetoothがUSBから輸入した?)、ReportIDなども一致した。少し逸れるがLinuxカーネルには何故かDS4用のドライバが入っており、これを無効にしなければcontrolでの通信が出来なかった(結局必要なかったがデバドラの仕組みを調べたりした)。

果たしてGET_REPORT/SET_REPORTの0xf0, 0xf1, 0xf2のデータを適切にUSBでやり取りすると、きちんと署名されたデータが返ってきた。勝利を確信した瞬間である。

What's wrong?

しかしここからも大変なのだ。

0xf0, 0xf1, 0xf2のデータ以外にもGET_REPORT/SET_REPORTには0x03, 0x04のデータがやり取りされている。PS4からDS4に32byteのデータを送信してDS4が40byte返す。これはランダムなデータで内容も分かっていない。全く重要で内容に見える。

http://www.psdevwiki.com/ps4/DS4-BT#0x03

http://www.psdevwiki.com/ps4/DS4-BT#0x04

ところがこのデータを返さなければChallenge-Response用の通信もロックされてタイムアウトしてしまう。しばらく考えたが結局何のデータなのか分からず、urandomで生成したデータを流したが(少なくともそれを流した瞬間には)問題無いように見えた。

何故このデータもreplayしないのかと思うだろう。それはDS4のUSB通信ではReportID 0x03が存在しないからだ。これに相当するデータがあるのかないのか、あるならどのIDでやり取りしているのか覗いてみたいがUSB Snifferは存外大変らしい(金で殴れば解決する)。

雑な0x03, 0x04のデータを流して今度こそ解決したかと思われた。認証はタイムアウトせず全てのデータが流れきった。しかし最後のデータが渡った瞬間に入力が無視された。明らかに認証でハネられている。

どうやら考え残しているところがあるようだ。

一番怪しいのは0x03, 0x04だが、他にも可能性はある。

コントローラーのBDADDRに偽装してみたがこれもダメだった。

認証時にLink Keyを用い無いと考えていたが、PKCS1 PSSはパディングに乱数値を入れるため、この箇所にLink Keyに依存した情報が入っているのかもしれない。そう考えて同じLink Keyを使っている2つのResponseに入っている乱数値を取り出してみたが異なる値だった。

どれか他のReport IDが0x03, 0x04の代わりをしているかと探ったがこれもダメだった。

かなり煮詰まっているので記事に書いた(記事に書くと何故か進捗が生まれるジンクス、内容を自分で整理出来るからだろうか)。

Demo

Responseを返し切るまでは入力が受理されるところ。

www.youtube.com

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

www.youtube.com

ThinkpadBluetoothでDS4として登録する。その後数秒おきに◯ボタンを押している。最後に注目して欲しいのだが接続が解除されている。これはThinkpadから解除したのではなくPS4側から解除されている。

実はPS4はライセンスされたコントローラーしか使えない仕組みが導入されている。次パートではそれについて解説する。もし新しいコントローラーで仕様変わってたら死ねる……

と思ってたけど今冷静に動画見たらこれはただ単に自分で接続切ってるだけだった……

www.youtube.com

◯を一回だけ押して後は上下を交互に押し続けるようにした。どうやら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向けはこれを書いた後に不安定になった気もするのであまり手を出したくないという理由もある。

追記

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のBluetoothPS4に登録されていない場合、PS4が自身のBluetoothMACBluetoothでは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を無視して送信する必要があった(と言っても下の箇所をコメントアウトするだけ)。

github.com

hcidumpやwiresharkで見ると送れているはずのhci packetが遅れていないのか謎の挙動をするしもう何もわからん。

一応不安定なりにたまにペアリングが出来る時があり、上手く行った時の動画を載せておく。

www.youtube.com

多分ここまで200時間位かかっていて、うち150時間くらいはBluetoothとBluezと闘っていた。本当にクソ。

一応上手く行っていないコードを載せておく。誰か問題点を指摘してくれ頼む。setup処理はBluetoothの諸々の設定をしているだけでさほど重要ではないと思う。hcidumpではl2capのconnection requestが送られて来ているにも関わらず383行目のacceptが返ってこない。もう意味がわからん。

Bluezを捨ててBtstack(組み込み向けのプロトコルスタック)を使ったほうが良い気がしているのだけど、ここしばらくずっとBluetoothの学習(という名の無駄)に時間が割かれていて疲れた。

gist.github.com

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オーバーウォッチをやった。PS4FPSは初めてだったのだが、アナログパッドで全くエイムが合わない。規約上問題ない様なのでキーボードとマウスを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で通信しているところを直接抜き取れば良い。

HCI UART sniffer – GIMX

この記事に沿って行った。

まず、ボタンの壊れたDS4を購入(2000円程度で買えた)して分解する。

f:id:aki33524:20180212121706j:plain

先の記事の写真と見比べると分かるが基板が違う。DS4は新旧2種があり、どうやらそれによって基板も変わったらしい。@TA7368PG氏によれば3種以上基板があるようだ。

真面目にデータシートと基板を読む。DS4に搭載されているBluetoothチップはAtheros AR3002でこれは10, 11番ピンにTx, Rxが配置されている。

f:id:aki33524:20180213024254p:plain
AR3002 Single Chip Bluetooth v4.0 UART HCI Data Sheetより

基板を眺めるとおそらくデバッグ用のパッドに伸びている。ここに線をはんだ付けする。 f:id:aki33524:20180212132500j:plain f:id:aki33524:20180212154055j:plain

Rx, Tx, GNDを取ってきてブレッドボードに配置する。シリアル通信モジュールは記事に倣いFT232を搭載したものを用いる。ボーレートが3Mbps以上であればなんでも良い。

f:id:aki33524:20180212235152j:plain

その後、これをコンパイルして終わり。

github.com

ただ、このプログラムはTx, Rx用に2つモジュールがなければ動かない。そこでPORT2をコメントアウトしてfd2に-1をセットすると上手く動く。

f:id:aki33524:20180213030800p:plain

小話

ハードウェアに関して全く詳しく無いので@TA7368PG氏と@ka1l氏にTwitterで聞きまくった。ありがとうございました。と言うか最近人々にTwitterで質問しまくってる。

どう考えてもこれを最初にやるべきなのだけど、しばらくsniffer無しで頑張っていた。しかしどうも煮詰まったので止むを得なくPS4ごと買った(これまでPS4を持っていなくて研究室においてあるもので実験していた。流石に人のコントローラーを分解するわけにはいかない)。

基板が違った時はマジで詰んだと思った。

メルカリで落としたコントローラーを分解したら犬の毛が入ってて笑った。

本当は音声端子を剥がしてそこからケーブルを出したかったのだが、はんだ剥がしがつらすぎて諦めた。

Tx, Rx用にモジュールが2つ必要で秋月で注文した。その後5年前に買ったきり一切触っていない回路箱を覗いたら何故かFT232が載ったモジュールがあったのでとりあえず実験した。

snifferの375行目のfd1はどう考えてもfd2のtypo

画像に情報を埋め込む -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でスペクトルを出した時に高周波成分が多く出てそれによって埋め込んでいることがバレるかもしれない。真っ白な画像に埋め込むと即バレる。自然風景画像やらに埋め込むと強そう。

GitHub - aki33524/watermark

GitHub - aki33524/steganography

Codefestival 2017 Finals Eに対する雑な考察

この問題の線形代数による考察を記しておきます。線形代数が何もわからない。

まずbjxzjaを26を法とするベクトルとして考えます。


S =
	\left(\begin{array}{c}
		1 \\
		8 \\
		23 \\
		25 \\
		9 \\
		0
    \end{array}
    \right)

これをあるベクトル群の一次結合によって表現出来るかを考えます。

ここで、回文の基底を考えると以下のようになります。


palindrome =

	a_1
	\left(\begin{array}{c}
		1 \\
		0 \\
		\vdots \\
		0 \\
		1 \\
    \end{array}
    \right)

    +

    a_2
    \left(\begin{array}{c}
		0 \\
		1 \\
		\vdots \\
		1 \\
		0 \\
    \end{array}
    \right)

    + \dots

各操作も同様にベクトルで表すと次のようになります。


v_i =
	\left(\begin{array}{c}
		0 \\
		\vdots \\
		0 \\
		1 \\
		\vdots \\
		1 \\
		0 \\
		\vdots \\
		0
    \end{array}
    \right)


回文の基底と操作ベクトルを合わせたベクトル群の一次結合により S が表現することが出来たなら答えはYESになります。

式で書くと次のようになります。


S = palindrome

	+ 

	\sum b_i v_i

さて、 v_iは密なので拡大行列を簡約化するコストは大きいように見えます。しかし、先に差分行列(累積行列も差分行列も正則なのは簡単に確かめられます)を掛けてやることでこれらは疎になります。

疎行列に対する簡約化のコストは小さいので十分間に合います。 Z/26Zは体でないので諸所が面倒に見えますが解けます(ほんまか)(多分、列ベクトルに注目すると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のメモリを持っていたので雑に両方持ってやったほうが速いようだ。

あと普段競プロで並列化やメモリキャッシュやらに気を配ることが殆ど無いのでこのあたりのノウハウが皆無なことに気がついた。悲しい。

GitHub - aki33524/xorshiftplus