nkhrlab~

280字超の記事

HarekazeCTF 2019 想定解法 (nkhrlab 作問分)

CTF HarekazeCTF Crypto

本記事では，HarekazeCTF 2019で出題された問題のうち，私が作問した2問について解法の解説を行う． ctf.harekaze.com

本記事には次の2問の解説を含む．

  • [Crypto 100] Twenty-five (Solved: 56 Teams)
  • [Crypto 200] One Quadrillion (Solved: 7 Teams)

[Crypto 100] Twenty-five

ppencode (あらゆるPerlスクリプトを予約語と空白のみを用いて記述する難読化の一種) によるPerlスクリプトを平文とする古典的な単一換字式暗号に対し頻度分析で換字表を割り出す問題．この問題は56チームが正解した．

問題文

With “ppencode”, you can write Perl code using only Perl reserved words. github.com

想定解法

twenty-five.zip を展開すると， twenty-five.pl, crypto.txt, reserved.txtを得る．twenty-five.pl の内容を次に示す．

use open qw/:utf8/;

open(my $F, "<:utf8", 'crypto.txt') or die;
my $text;
while (my $l = <$F>)
{
  $l =~ s/[\r\n]+/ /g;
  $text .= $l;
}
close($F);

$text =~ y/abcdefghijklmnopqrstuvwxy/*************************/;
eval($text);

また，crypto.txt の内容を一部抜粋して示す．

m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo
o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji
m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo
o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji
m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo o sji m oo
...
...
sji ytyw wlnfa ytyw whgrf whidl fdfy gliyl vgdj wlnfa rsf lysi idy tgl o myrgf sji
m m m whl pyjxah o o kyw ytda yksp blysq gfyj ygu idy blysq spslr o myrgf sji m
m m pyjxah o ol fdfy lywk yswh xyaw uwjap dja o myrgf sji m m m whl pyjxah o o kyw
ytda yksp blysq gfyj ygu idy blysq spslr o myrgf sji m m m pyjxah o ol lyu fgf clday
uglq ejady ytf cslj o myrgf sji m m m whl pyjxah o o kyw ytda yksp blysq gfyj ygu
...
...
sji adry o myrgf sji m m m whl pyjxah o o kyw ytda yksp blysq gfyj ygu idy blysq
spslr o myrgf sji m m m pyjxah o ol lyu fgf clday uglq ejady ytf cslj gwa xgag lsji
ejiyu gli gwa fldja lyu ejady kyw wrf sji adry whgrf o myrgf sji m m m whl pyjxah
o o kyw ytda yksp blysq gfyj ygu idy blysq spslr o myrgf sji m m m pyjxah o o kyw
ejadp ejady whidl xlyf ierf whgcj fldja yswh sji ytyw o myrgf sji yksp yksp

reserved.txt にはPerlの予約語 (関数名および演算子) が数多く列挙されている．

twenty-five.pl の処理の内容を大まかにいうと，crypto.txtを読み込み，単一換字を施して eval するという処理を行う．問題は，換字表が伏せられていることである．そこで，reserved.txt にPerlの予約語 (関数名および演算子) が列挙されている点， crypto.txtの内容に換字を施すとPerlスクリプトとして解釈できる点，crypto.txtが英小文字，空白，改行文字のみからなる点に着目すると，平文はppencodeではないかと推測できる．Perlには200種類余り (バージョンによって異なり， reserved.txt には236種類を掲載している) の予約語が存在し，これをコーパスとして用いることで頻度分析による暗号文単独攻撃を行うことができる．英語などの自然言語に比べて出現する単語が限られているので頻度分析は易しい．換字表を完成させ，twenty-five.plを実行すると， crypto.txt の内容に換字を施したものがフラグを表示するPerlスクリプトとして解釈され，フラグ HarekazeCTF{en.wikipedia.org/wiki/Frequency_analysis} が得られる．1

[Crypto 200] One Quadrillion

独自実装によるハッシュとソルトの不適切な運用を咎める問題．この問題は7チームが正解した．

問題文

(問題文には問題サーバへのリンクが書かれていたが問題サーバはすでに停止しているので，代わりにDockerを使って問題サーバを建てられるファイル群へのリンクを掲載する．) github.com

index.php(censored):

<?php
error_reporting(0);

function h($str)
{
  echo htmlspecialchars($str, ENT_QUOTES, 'UTF-8');
}

function baby_hash($msg)
{
  $t = array(5676567,  858051, 5476703,  265259,
             4058727, 5112531,  964143, 1099579,
             8277687, 8717411, 2022783, 7207499,
             1997447, 5864691,  828623, 3917019
            );

  $v = array(7602007, 2906371, 4037663, 3996139);

  $n = intdiv(6 + strlen($msg), 7);
  $msg = str_pad($msg, 7 * $n, "0", STR_PAD_RIGHT);

  for($i = 0; $i < $n; $i++)
  {
    $s = intval(substr($msg, 7 * ($n - $i - 1), 7), 10);
    $k = $t[$i % 16];
    $a = $v[1 + $i % 3];
    $b = $v[1 + (1 + $i) % 3];
    $c = $v[1 + (2 + $i) % 3];
    $d = ($a * $b + $b * $c + $c * $s ^ $k) % 10000000;
    $v = array(($d + $v[1]) % 10000000, ($d | $v[2]) % 10000000, $d * $v[3] % 10000000, $d);
  }
  
  $r = "";
  for($i = 0; $i < 4; $i++)
  {
    $r = $r . str_pad($v[$i], 7, "0", STR_PAD_LEFT);
  }

  return $r;
}

function verify($progress, $answer, $salt)
{
  if(preg_match("/^[0-9]{43}$/", $progress) &&
     preg_match("/^[0-9]{1,5}$/", $answer) &&
     intval(substr($progress, 5, 4), 10) + intval(substr($progress, 19, 4), 10) === intval($answer, 10) &&
     baby_hash(intval(substr($progress, 28, 15), 10) . $salt) === substr($progress, 0, 28)
    )
  {
    return TRUE;
  }
  return FALSE;
}

$salt = CENSORED;

usleep(200000);

if ($_SERVER['REQUEST_METHOD'] === 'POST')
{
  $progress = $_POST['progress'];
  $answer = $_POST['answer'];
  if(verify($progress, $answer, $salt))
  {
    $cleared = intval(substr($progress, 28, 22), 10) + 1;
    $new_progress = baby_hash($cleared . $salt) . str_pad(strval($cleared), 15, "0", STR_PAD_LEFT);
    $left = intval(substr($new_progress, 5, 4), 10);
    $right = intval(substr($new_progress, 19, 4), 10);
  }
  else
  {
    $cleared = 0;
    $new_progress = baby_hash("0" . $salt) . "000000000000000";
    $left = intval(substr($new_progress, 5, 4), 10);
    $right = intval(substr($new_progress, 19, 4), 10);
  }
}
else
{
    $cleared = 0;
    $new_progress = baby_hash("0" . $salt) . "000000000000000";
    $left = intval(substr($new_progress, 5, 4), 10);
    $right = intval(substr($new_progress, 19, 4), 10);
}
?>
<!doctype html>
<html lang="en">
<head>
    <meta charset="utf-8">
</head>
<body>

<?php
if($cleared >= 1000000000000000)
{
?>
<p> CENSORED </p>
<?php
}
else
{
?>

<p> Question <?php h($cleared + 1); ?> / 1000000000000000</p>
<form action="#" method="post">
<p>
<?php h($left) ?> + <?php h($right) ?> = <input type="text" name="answer">.
<input type="hidden" name="progress" value="<?php h($new_progress) ?>">
</p>
</form>

<?php
}
?>

</body>
</html>

想定解法

サーバにアクセスすると1000兆問の足し算が出題される． f:id:nkhrlab:20190519225112p:plain

たとえサーバとの対話を自動化しても，1000兆回の通信を開催期間内に終えることなどできないことは明らかである．どうにかして1000兆問の足し算を回避してサーバにそれを行ったと誤認させたい．

HTMLのソースを見るとPOST時に隠しパラメータ progress が送信されるようになっていることがわかる．また，添付ソース (PHP) を見ると足し算の問題に使われている数字も progress の一部から選ばれていることがわかる． progress には独自実装のハッシュ関数 baby_hash により生成されたハッシュ値と現在何問目かを表す情報が含まれている．

baby_hash の処理の概要は次のようである． - 長さ16の配列 $t と長さ4の配列 $v を用意し，定数で初期化する． - 引数 $msg の末尾にパディングを施し，長さを7の倍数にする． - $msg を7桁ずつに分け (分けられた7桁のかたまり一つ一つをブロックと呼ぶことにする．)，末尾のブロックから順に $v の各要素および $t の1つの要素と演算をおこない，その結果によって $v を更新する． - $msg をすべて処理し終わったときの $v の値をならべたものを十進28桁のハッシュ値とする．

いま， baby_hash("0" . $salt) の値がわかっているとしよう (これは最初に問題サーバにアクセスしたときの progress の値からわかる．)． baby_hash の処理をよく見ると，長さが7の倍数であるような文字列 $prefix に対して， baby_hash($prefix . "0" . $salt) の値は $prefix と baby_hash("0" . $salt) から計算できてしまうことがわかる (Length Extension Attackの一種) ．ただし， $salt の長さは未知なので， $salt の長さについて何通りかの仮定をおいてハッシュを計算してみる必要がある． 2 以上の内容について $prefix = "99999999999999" (長さ14) とすると baby_hash("999999999999990" . $salt) の値がわかるので，1000兆問のうち(1000兆 - 10)問を飛ばして残り10問の状態から足し算を始めることができる．残った10問を自力で足し算して答えを送信するとフラグ HarekazeCTF{The_prefix_representing_one_quadrillion_times_of_a_unit_is_peta.} が表示される．3

  1. ちなみに，問題名の「Twenty-five」はppencodeで生成したperlスクリプトが「z」以外の25種類のアルファベットからなっていたことからついている．「z」が出現していないことに気づく前の問題名の原案は「Twenty-six」だった．↩

  2. すでに処理したブロックの個数 $i の値によって，$k, $a, $b, $c に代入する $t, $v の要素の添字は周期48で遷移するので，高々48通りを計算すれば十分である．↩

  3. ちなみに， index.php(censored) で隠されているソルトの値は $salt = "20988936657440586486151264256610222593863921"; となっている．たぶんテンキーをガチャガチャして出てきた値をそのまま使っている．↩

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

セキュリティ 脆弱性関連情報 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
続きを読む