STEM CTF: Cyber Challenge 2019 writeup

ctf web crypto

はじめに

以前延期になったCTFが開催されていたのでやってみた。

In Plain Text Binary RE - 50 points

以下問題文。

Starring: Mary McCormack, Fred Weller, Nichole Hiltz, Todd Williams, Lesley Ann Warren, Paul Ben-Victor, Cristián de la Fuente, Rachel Boston

stringsコマンド実行したらFLAGがあった。

$ strings challenge
MCA{y3ah_sur3_here_y0u_g0}

Turing Test Web - 50 points

以下、問題のページ。秘密の質問をパスすれば良いっぽい。

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

Alan Turingについてググって内容を埋めるだけで良いらしい。難しく考えすぎていて悲しい... f:id:kent056-n:20190224152859p:plain

TODO Web - 100 points

アクセスしてみると以下のようなページがあった。 f:id:kent056-n:20190224150927p:plain

URLhttp://138.247.13.110/todolist/1000/の1000の箇所を書き換えると過去のTODOが見れるようだ。
あとは、1000のTODOの中からFLAGが書かれているページを探して終了。以下、solverです。

import requests
import re

baseurl = 'http://138.247.13.110/todolist/'
for i in range(1000):
    payload = {'page': str(i)}
    url = baseurl + str(i) + '/'
    r = requests.get(url)
    print('[*]Requests: ' + url)
    if re.search(r'MCA', r.text):
        print(r.text)
        break;

http://138.247.13.110/todolist/678/にFLAGがあったようです。FLAGはMCA{al3x4_5et_a_r3minder}。

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

Warm UP Crypto - 50 points

競技時間以内に解けなかった。以下のwriteupを見たらちょっとした気づきがあったのでメモを残す。 github.com

以下問題文。

Description
Everyone says that PGP is hard to use. Show ‘em how it’s done.

渡されたファイルは以下の4つ。

flag.html.enc
key.enc
mitre-ctf-2019-private.asc
passphrase.txt

とりあえずパスフレーズを確認する。

$ cat passphrase.txt
just use ctfd

適当に秘密鍵をインポートしてみる。

$ gpg --allow-secret-key-import --import mitre-ctf-2019-private.asc
gpg: key CB374E23: secret key imported
gpg: /home/vagrant/.gnupg/trustdb.gpg: trustdb created
gpg: key CB374E23: public key "CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>" imported
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)
gpg:       secret keys read: 1
gpg:   secret keys imported: 1

秘密鍵のインポートができたら、key.encを復号する。パスフレーズは先ほど確認したものを入力すれば良い。

$ gpg key.enc

You need a passphrase to unlock the secret key for
user: "CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>"
2048-bit RSA key, ID 87BA2B5E, created 2018-12-03 (main key ID CB374E23)

gpg: gpg-agent is not available in this session
gpg: encrypted with 2048-bit RSA key, ID 87BA2B5E, created 2018-12-03
      "CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>"
gpg: key.enc: unknown suffix
Enter new filename [key]: decrypted_key
gpg: Signature made Mon Dec  3 22:48:09 2018 UTC using RSA key ID F2FFFCB4
gpg: Can't check signature: public key not found

これでkey.encの復号は完了。あとは、key.encを復号した結果の鍵を利用してflag.html.encを復号すれば良さそう。
しかし、flag.html.encが何のアルゴリズムで暗号化されているかどうかわからずに競技が終了してしまった。
どうやら鍵長とbinwalkの結果でアルゴリズムを特定することができたらしい。以下、binwalkの実行結果。

$ binwalk flag.html.enc

DECIMAL       HEXADECIMAL     DESCRIPTION
--------------------------------------------------------------------------------
0             0x0             OpenSSL encryption, salted, salt: 0xF61A179-5D7CAE48

最初はファイルサイズからRSAあたりのアルゴリズムかと思っていたが、パスフレーズとソルトを鍵としたAESによって暗号化されているようだ。 ここまでできたら以下のコマンドを実行し、flag.html.encを復号する。

openssl aes-256-cbc -kfile decrypted_key -d -in flag.html.enc -out flag

最後に中身を確認して終了。

<!DOCTYPE html>
<html>
<head>
  <title>MITRE CTF 2019 Homepage.</title>
</head>
<body>
<h1>This is an HTML Page</h1>
<br>
<p>Test Flag please ignore:</p>
<p>MCA{0p3n55l_c0mm4nd_l1ne_ch4ll3ng3_fl4g}</p>
<p style="display:none;">MCA{66b2f50cd2d6b9622c6be902ee2b0976badb4684}</p>
</body>
</html>

おわりに

最近のcrypto難しくないですか...

参考

https://wiki.openssl.org/index.php/Enc
https://github.com/swag-wafu/mitre-2019/blob/master/PGP.md
https://jemsec.blog.so-net.ne.jp/2013-02-10
https://gist.github.com/reggi/4459803#file-openssl-list-cipher-commands

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

webauthn

はじめに

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 displayName、username、attestationという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

ctf crypto

はじめに

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.

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

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となった時点で抜けるので，nとm^{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

はじめに

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

crypto

web

rev

いろいろ

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

crypto

はじめに

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

動作環境用意

環境

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

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の２種類のアカウントが存在する。
ここでは，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

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が更新され次第モジュールの中身はが変わる思いますので、詳細は公式のリポジトリやドキュメントを参照いただければ幸いです。

クラス

PyWebAuthnでFIDO2なサーバーを実装する際、主に以下の5つのクラスを利用します。

  • WebAuthnMakeCredentialOptions
  • WebAuthnRegistrationResponse
  • WebAuthnUser
  • WebAuthnAssertionOptions
  • WebAuthnAssertionResponse

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}}

WebAuthnAssertionOptions

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

webauthn_assertion_options = webauthn.WebAuthnAssertionOptions(
    webauthn_user,
    challenge)

IN

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

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）

ctf crypto

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

Hanukkah

以下問題文。

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

hannukah.zip

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

  • 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.encとpubkey.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を生成し、素数p、qを乗算した結果nを公開鍵として出力している。こちらも一見RSAにあるような処理だが、素数p、qの生成の仕方が特徴的である。

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を復元し、p、qを求められるか試す。pとqはそれぞれ以下のような二次方程式である。
　　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
]

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

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の候補が４つになる。
(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

これより、NABJがFLAGに対応することがわかるので、その近辺のみを復号して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について、もう少しどういう処理をしているのか調べてみたい。
最初のアルファベットを謎の記号に割り振る部分をなんとかして自動化したい。

参考