nkhrlab~

140字超の記事

ウェブアプリケーション脆弱性関連情報の届出をした

セキュリティ 脆弱性関連情報 XSS

概要

あるウェブアプリケーションにXSS脆弱性を発見したので，情報セキュリティ早期警戒パートナーシップガイドラインに則りウェブアプリケーション脆弱性関連情報として情報処理推進機構 (IPA) に届け出たところ，届出が受理された．

将来の脆弱性関連情報の届け出に際して本記事が少しでも参考になると期待して，届出の内容と受理までの経過を以下にまとめる．

なお，当該脆弱性の悪用を防ぐため，届出の内容の一部を改変して掲載する．

届出の内容

以下の内容を 2019/03/09 に届け出た．

届出の内容は主に脆弱性の発見の経緯とそれにより想定される被害の2点に要約される．今回発見した脆弱性は典型的なXSS脆弱性であったため，想定される被害としてXSS脆弱性一般に通用する内容を記入して届け出た．

続きを読む

LaTeXでマークシート式試験

作問 数学 LaTeX TeX センター試験

マークシート式試験の組版

大学入試センター試験に代表されるマークシート式試験の組版では，同じ大問中で連続した解答欄 (例えば，マークが10箇所であれば解答欄「ア」～「コ」) を使うことが多い．これをLaTeXで実現する場合，1つの大問を通して利用するカウンタと解答欄の記号を対応付けるテーブルを用いる方法が考えられる．

また，数学の問題では，2桁以上の解答に複数の解答欄を使用するので，桁数を指定して自動的に解答欄を割り当てたい．さらに，前の解答欄を参照する場合に相互参照ができると問題の入れ替え時などに解答欄がずれなくなり利便性が向上する．

LaTeXテンプレート

以上の要件を盛り込んだマークシート式試験向けテンプレート「marksheet.sty」を作成した．このテンプレートを使用すると，下の画像のような組版が容易に実現できる．
f:id:nkhrlab:20190217123759j:plain

続きを読む

分数が出てこない行列の対角化問題の作問の手法

数学 作問

本記事の目的

次のような形の問題は，「行列の対角化問題」と呼ばれる問題である．本記事では，これを単に「対角化問題」と呼ぶ．

行列 Aに対し，次のような条件を満たす対角行列 Dと行列 Pの組を1つ求めよ．

D = P^{-1}AP.

対角化問題は，行列やベクトルに関する他の問題 (行列の累乗A^nを nの式として表す問題など) の解法の一部として重要な問題である．

また，問題設定によっては行列 Pの逆行列 P^{-1}を計算する必要もあり，机上で解く場合には分数の取り扱いが面倒な問題としても知られている．行列 Aの成分に計算量を減らす特別な配慮がなければ，計算は大変厄介なものとなるだろう．また，あまりにも煩雑な計算を含む対角化問題は解答者の対角化の技能を確かめるのには不適切な場合もある．

そこで，本記事では対角化問題における行列 A, D, P, P^{-1}のすべての成分が整数となるように設定する作問の手法について記述する．

続きを読む

nkhrlab challenge 2019 想定解法

CTF Writeup

はじめに

この記事は，2019/1/1 0:00より主催したCTF「nkhrlab challenge 2019」の解説記事である．

次のリンクから問題用のファイルをダウンロードできる．問題用のファイルとサーバは少なくとも2019/1/10 23:59まで有効である．
www.dropbox.com

以下，問題の解法を解説する．

続きを読む

勝敗グラフと有向閉路の存在性

グラフ アルゴリズム

勝敗グラフ

本記事における勝敗グラフを次のように定義する．勝敗グラフは有向グラフの一種である．

頂点集合 V，辺集合 Aを持つ有向グラフ G = (V, A)を考える．
i, j \in Vに対し a_{i, j}を次のように定義する．
a_{i, j} = \begin{cases} 1 & \left((i, j) \in A\right) \\ 0 & \left((i, j) \notin A\right) \end{cases}.

Gが次に示す条件を満たすとき，かつその場合に限り， Gは勝敗グラフである．
\forall i, j \in V, a_{i, j} + a_{j, i} = \begin{cases} 0 & \left(i = j\right) \\ 1 & \left(i \neq j\right) \end{cases}.

本記事の主張

次の命題は勝敗グラフGが有向閉路を持つことの必要十分条件である．
\exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

続きを読む

AtCoder に登録したら解くべき精選過去問 10 問を PostgreSQL で解いてみた

競技プログラミング AtCoder AtCoder Beginners Selection SQL PostgreSQL アルゴリズム

はじめに

この記事は，次のQiita記事に「過去問精選 10 問！」として示されている10問の問題をPostgreSQLを用いて解いたものである．
qiita.com

また，AtCoderではこれらの問題をまとめた初心者向け問題集として「AtCoder Beginners Selection」を用意している．

問題

これらの問題では，PostgreSQLで標準入出力を取り扱うことが困難であるため，入力は共通表式(WITH句)を用いていくつかのテーブルとして与え，出力もまたテーブルとするよう，問題を変形している．

また，各問題の解答方針についての解説はすでに公式に公開されているため，本記事では解答方針についての解説を詳しく行うことはせず，主にSQL特有の事情についての解説を中心とする．

0. PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

問題文の冒頭に「高橋君はデータの加工が行いたいです。」とあるが，SQL(DML)はすでに構造化されたテーブルデータの操作を行うために作られた言語であり，未だ構造化されていない段階のデータを取り扱うのは容易ではないため，この冒頭のみで「はじめてのあっとこーだー」というには難易度の高い問題であることが予感される．果たしてその予感は的中するのだ．

テーブルtblに，標準入力の文字列と「何行目に入力された文字列か」という情報を与える．テーブルは順序を保持しないため何行目であるかの情報が必要である．解答には，テーブルtbl内の情報から必要な部分の文字列を正規表現を用いて切り出し，数値に変換する操作と，文字列の結合操作が必要である．

WITH tbl(num, str) AS
(
  VALUES
  (1, '72'),
  (2, '128 256'),
  (3, 'myonmyon')
)
SELECT
  (
    TO_NUMBER((SELECT str FROM tbl WHERE num = 1), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '^.*\ '), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '\ .*$'), '9999')
  )::TEXT ||
  ' ' ||
  (SELECT str FROM tbl WHERE num = 3) AS result
続きを読む

HarekazeCTF2018: [Misc 127]Unnormalized-form Data 想定解法

CTF HarekazeCTF PostgreSQL Writeup SQL

この記事について

本記事は，HarekazeCTF2018に私が出題した問題 [Misc 127]Unnormalized-form Data の想定解法について解説を行うものである．HarekazeCTF2018の期間中に43チームが本問題のフラグを獲得した． harekaze.com

問題文

Unnormalized-form data is troublesome.

解法

配布された unf.zip を展開して，2つのファイルを得る．

  • operation.txt
  • unf.sql

operation.txt の観察

operation.txt は次のような内容である．

$ sudo nano postgresql.conf
$ sudo /etc/init.d/postgresql reload
[ ok ] Reloading postgresql configuration (via systemctl): postgresql.service.
$ psql -U postgres -c "CREATE DATABASE unf"
CREATE DATABASE
$ psql -U postgres -d unf < unf.sql >> /dev/null
$ psql -U postgres -d unf -c "SELECT FLAG()"
             flag
-------------------------------
 HarekazeCTF{****************}
(1 row)

$

この記述はフラグの取得までの手順を示している．

続きを読む